The Merkle tree
The append-only Poseidon tree of note commitments, its zero values, the per-slot root history, and the layout of the tree account.
Every note commitment is a leaf of one append-only Merkle tree of depth 26, kept in a single program account. A proof shows that its input notes are leaves under a root the program recorded. The app keeps the same tree client-side.
Shape
| Property | Value |
|---|---|
Depth (LEVELS) | 26 |
| Capacity | 2^26 = 67,108,864 leaves |
| Node hash | Poseidon(left, right), circomlib's parameters over BN254, through the sol_poseidon syscall (big-endian) |
| Empty leaf | 0 |
| Inserts | Two leaves per transact, the two output commitments, at the next even index |
Root history (ROOT_HISTORY) | 192 entries, one per slot that had an insert |
When the next pair would not fit, transact fails with TreeFull.
Zero values
An empty subtree at each level has a fixed hash:
zero[0] = 0
zero[i + 1] = Poseidon(zero[i], zero[i]) for i = 0 .. 25
empty root = zero[26]initialize computes them once with the syscall and writes them into the account. The app computes the same values
with poseidon-lite.
Inserting a pair
Inserting the pair (a, b) hashes it once, then climbs one hash per level, keeping the left node of every
incomplete subtree:
h = Poseidon(a, b) the node at level 1
i = next / 2
for level = 1 .. 25:
if i is even: filled[level] = h; h = Poseidon(h, zero[level])
else: h = Poseidon(filled[level], h)
i = i / 2
new root = h
next = next + 2That is 26 Poseidon hashes per transaction. The program emits the first leaf's index in
Inserted { index, commitments }.
Root history
A proof is built against the root the client saw. By the time the transaction lands, other inserts may have moved the tree on, so the program keeps recent roots.
- The history is a ring of 192 entries, each a root (32 bytes) and the slot it was recorded in (8 bytes).
- Within one slot, every insert replaces that slot's entry with the latest root. A new slot takes the next entry.
- So the ring holds the final root of each of the last 192 slots that had an insert: about 77 seconds of continuous activity at 400 ms a slot, and longer when the pool is quieter.
Keying the history by slot means a burst of inserts in one slot uses one entry, so it cannot push out the roots that pending proofs rely on.
A transact names its root by root_index, a position in the ring (one byte). The program reads the root from its own
account and never takes a root from the caller. It refuses an index of 192 or more, or an entry that was never written
(BadRoot). If the entry has been overwritten since the proof was built, the root no longer matches and the proof
fails (BadProof), and the transaction has to be proven again against a recorded root. The relayer's simulation
catches this before anything is sent.
The tree account
The tree is a raw account at the PDA ["tree"], owned by the program. initialize funds it, then allocates and
assigns it (rather than create_account), so it can be created even if someone sent lamports to the address first.
| Offset | Size | Field |
|---|---|---|
| 0 | 8 | Magic: the ASCII bytes voidtree |
| 8 | 8 | next: the next leaf index (u64, little-endian) |
| 16 | 8 | root_index: the current position in the root history (u64, little-endian) |
| 24 | 832 | filled: 26 × 32 bytes, the left nodes of incomplete subtrees (level 0 is unused, since leaves come in pairs) |
| 856 | 864 | zeros: 27 × 32 bytes, zero[0] to zero[26] |
| 1,720 | 7,680 | Root history: 192 × (root 32 bytes ‖ slot 8 bytes, little-endian) |
| 9,400 | Total (TREE_SIZE) |
Every read and write checks the magic (BadTree). The account stays within the 10 KiB that an account created
through a CPI may have.
Clients
A client reads the account by the layout above: next, root_index and the 192 (root, slot) entries. The
root_index it passes to transact is the position of the entry that holds its root.
The app downloads every leaf from the indexer, rebuilds the tree, and looks for its root in the account:
- found: the indexer's view is complete and correct, and the app proves against that index;
- not found while the account has more leaves than the app: the indexer is behind, so the app waits;
- not found otherwise: the leaves do not match the chain, and the app proves nothing against them.
The indexer runs the same check on its own tree, and stops serving leaves when it fails.
Notes, commitments and nullifiers
What a note contains, how its commitment and nullifier are computed, how notes are encrypted and found, and why every transaction has two inputs and two outputs.
The transact circuit
The one zero-knowledge circuit behind every shield, private transfer and unshield - its inputs, constraints, public inputs, the ext-data binding and the proof system.