The note tree
The append-only Poseidon2 Merkle tree that holds every note commitment - depth, pair insertion, root history, rollover and how wallets rebuild it.
Every note commitment ever created is a leaf of one append-only Merkle tree in PrivateVault
(its PoseidonMerkleTree base contract). A spend proves membership against a root of this tree, without saying which leaf.
Parameters
| Constant | Value | Meaning |
|---|---|---|
TREE_DEPTH | 24 | 2^24 = 16,777,216 leaves per tree |
ROOT_HISTORY_SIZE | 64 | Recent roots accepted by isKnownRoot |
| Empty leaf | 0 | zeros[0] = 0, zeros[i+1] = H(zeros[i], zeros[i]) |
| Node | H(left, right) | Poseidon2 over BN254, the same as the circuit's node |
function root() external view returns (uint256);
function isKnownRoot(uint256 root) external view returns (bool);
function nextLeafIndex() external view returns (uint32);
function treeNumber() external view returns (uint32);
function isFinalRoot(uint256 root) external view returns (bool);
event TreeCompleted(uint256 indexed treeNumber, uint256 finalRoot);Pair insertion
Leaves are always inserted two at a time, at an even index (_insertPair(left, right)):
current = H(left, right) level 1
for level 1 .. 23:
if the node is a left child: remember it in filledSubtrees, current = H(current, zeros[level])
else: current = H(filledSubtrees[level], current)
nextLeafIndex += 2That is 1 + (TREE_DEPTH - 1) = 24 Poseidon2 calls per pair, instead of 48 for two single insertions.
| Operation | Leaves inserted |
|---|---|
transact | (cm0, cm1), at first and first + 1, both emitted as NoteAdded |
shield (also through PrivateRouter.buy) | (cm, 0): the note and an empty leaf |
A single note is padded with an empty leaf, which leaves the root exactly as if the note had been inserted alone.
The padding leaf emits no event and is never a note. Every insertion therefore starts at an even index, and the
index in Shielded and the first NoteAdded of a transact is always even.
On top of the tree hashes, shield computes one more Poseidon2 hash (the commitment). Measured on testnet, one call to the Yul hasher costs about 20,600 gas after the first.
Root history
Each insertion writes a new root into a ring buffer of 64. isKnownRoot(root) is true if the root is:
- a final root of a full tree (see below), or
- one of the last 64 roots.
Zero is never a known root. A proof names one root, so it stays valid while that root is one of the last 64. Every
shield and transact is one insertion. If 64 or more insertions happen between building a
proof and its inclusion, the transaction reverts with UnknownRoot and must be rebuilt and proved again. No funds
are at risk: nothing is written when it reverts.
Rollover when a tree is full
When a pair is inserted and nextLeafIndex has reached 2^24:
The current root becomes a final root: isFinalRoot[root] = true, valid forever.
The contract emits TreeCompleted(treeNumber, finalRoot) and increments treeNumber.
The pair is inserted at index 0 of a new tree. The stored left siblings need no reset, because each one is written before it is read.
Notes in a full tree stay spendable forever against its final root, so filling the tree cannot lock anyone out. Leaf indexes restart at 0 in each tree, and the circuit's nullifier uses the index inside its tree (see Notes).
A proof has one root, so both inputs of one transaction must come from the same tree. The app's coin selection picks the two largest notes of the tree where they add up to the most.
What the client rebuilds
The wallet keeps a full copy of the tree, rebuilt from events:
Read NoteAdded, Shielded, NullifierSpent and TreeCompleted from the vault's deployment block,
from the indexer, the chain, or both.
Replay leaves in chain order (block, then log index). At each TreeCompleted, start a new tree at index 0.
Restore the padding: when a leaf arrives at an index one past the tree's size, insert an empty leaf first.
For each leaf, try to own it: decrypt its NoteAdded ciphertext with the viewing key, and for a shielded note take
the shares from the Shielded event with the same transaction and leaf index. Accept it only if the recomputed
commitment matches.
Compute each owned note's nullifier and drop it if a NullifierSpent event has it.
Check the rebuilt current root with isKnownRoot. If it is unknown and the data came from the indexer, reread
everything from the chain; if it came from the chain, stop with an error.
The indexer serves the same block ranges to everyone and never learns which notes a wallet owns. A lying indexer that drops or alters a leaf produces a root the contract does not know, and the wallet falls back to the chain.
NOIR on Pons
What NOIR is, the Pons V2 terms it trades under, who receives its fees and how to check them on-chain, and how the noircash contracts are deployed around it.
Deployments
Network details, contract addresses, the Pons contracts NOIR trades on, and the public bundler of noircash on Robinhood Chain.