Every tree

The protocol keeps eight Merkle trees. Three are append-only trees that prove something exists (a note, an identity, a fee note), three are indexed trees that prove something is new (a nullifier, a registration, a collected fee note), and two small trees hold configuration (zone signing keys and per-token fee rates).

The diagram below groups the eight trees by what they prove. The first six exist once per pool index; the two configuration trees exist once for the whole protocol.

All eight use Poseidon nodes of up to eight children, which the Solana syscall can hash. The Merkle trees page covers membership and non-membership proofs in general, and hash functions lists the leaf domains.

How they compareCopy Anchor Link

The table compares the trees on how many leaves each can hold, how long a superseded root stays usable in a proof, and what writes to it. The sections after it explain each tree.

The three append-only treesCopy Anchor Link

An append-only tree proves that a value exists. Values go in one after another at the next free position and are never removed or changed. Each of these trees has ten levels of eight children under a top level of four, which is 2³² leaves. All three are stored the same way: a 19,249-byte tree body holding the frontier (the last filled node at each level), the next free index and a ring of the last 512 roots. The fee commitment tree's account also holds its fee store after the body. A transaction names the root it proved against by its sequence number, and the program accepts it while it is still in the ring.

Note treeCopy Anchor Link

The note tree holds every note ever created in its pool index, dummies included. Each leaf is a Poseidon hash, under domain 36, of the note's commitment together with the slot and position at which the chain appended it, so a leaf cannot be moved or replayed elsewhere. Every value transaction appends its three output notes, and every spend proves its inputs are leaves of it. The note tree page has the detail.

Identity treeCopy Anchor Link

The identity tree holds every registered identity commitment (sometimes called the user commitment). It is the pool's registry of who can hold notes: every spend proves its sender's identity commitment is in it, and every identity-owned output's owner must be in it too. Its leaves are the raw commitments, without a slot or position. register appends one leaf per registration. It lives in the shielded pool program, not in the user registry program, which stores nothing. See your identity commitment.

Fee commitment treeCopy Anchor Link

The fee commitment tree holds the protocol's fee notes: three per value transaction, one per token slot, each owned by the treasury identity the fee enclave record names. A transaction's fee notes go to the fee commitment tree of the pool index it appends its output notes to, so each pool index's fee tree grows with its note tree. Its leaves are a Poseidon hash under domain 38 of the fee commitment, the slot, the position and, as a fifth input, the treasury owner commitment. The fee collection circuits prove fee notes are in it. See fee collection.

The fee storeCopy Anchor Link

A value transaction does not append its fee commitments to the fee commitment tree. It stages them, as one entry, in the fee store kept in the same account: a ring of 1,024 entries, each holding the transaction's three fee commitments, the slot it executed in and the treasury owner commitment the fee enclave record held then. Appending three leaves would cost each transaction three leaf hashes and a fold up to the root; staging costs one write.

The insert instruction moves entries from the store into the tree, oldest first, as many as are staged up to 16, and anyone may send it at any time. The sender does not choose how many: an insert that could take more never takes fewer, so a backlog cannot be split into many small inserts that each publish a root and push recent roots out of the ring a fee collection names its root in. It builds each entry's three leaves from what the entry stored and folds them in one batch, so the tree publishes one root per insert. Entries leave in the order they arrived and each becomes three leaves, so the entry staged nth always becomes the leaves at positions 3n to 3n + 2: the positions an immediate append would have given them. The program refuses an insert whose store and tree disagree on how many entries have been inserted.

When the store is full, the transaction inserts the oldest entry itself before staging its own, so a full store never refuses a transaction; it only costs that transaction an insert. A fee note can be collected only once its entry has been inserted.

The account holds the tree and the store, 158,529 bytes, more than one instruction can create. The note and identity trees are created the same way, without a store, because their 19,249 bytes are also more than one instruction can create. It is created at 10,240 bytes, grown by the staging buffers' resize instruction and then finalized into an empty tree with an empty store.

The three indexed treesCopy Anchor Link

An indexed tree can prove that a value is absent. Its leaves form a sorted linked list: each leaf is a Poseidon hash under domain 37 of a value, the index of the next larger value and that next value. To show a value is absent, a proof opens the leaf whose value is just below it and whose next value is just above it.

Each indexed tree lives inside a staging-buffer account, which the code calls a turnstile. The account holds the tree's current root, a ring of recent roots and its next free index, alongside two buffers of values waiting to be inserted. The leaves themselves are kept off chain by the forester and the indexer. Values enter the tree only through the forester, twelve at a time, each batch with a proof. Each tree has eleven levels of eight under a top level of eight, for 8¹² = 2³⁶ leaves, sixteen times the append-only trees. All three share that shape because every batch is proved under the one batch-append key, and the circuits that prove absence from them (freshness, registration, escape hatch and fee collection) are built for it too.

Nullifier treeCopy Anchor Link

The nullifier tree records every spent note's nullifier. A value transaction proves its three nullifiers are absent from it with a separate freshness proof, and an escape hatch proves the same inside its own circuit. Its staging buffer keeps up to 512 recent roots. See preventing double spends. A pool index stops taking value transactions that spend from it while this tree still has a leaf for every note that might need to escape; the note tree explains the limit.

Registration treeCopy Anchor Link

The registration tree records every identity commitment that has registered. The registration proof shows the new commitment is absent from it, which stops the same identity registering twice. Its staging buffer keeps up to 120 recent roots.

Fee-nullifier treeCopy Anchor Link

The fee-nullifier tree records every fee note already collected, and each fee collection proof shows its notes' nullifiers are absent from it. Its staging buffer keeps up to 512 recent roots, like the nullifier tree's.

The watermarkCopy Anchor Link

A recent root in the ring is not enough on its own. Each staging buffer also keeps a watermark, the oldest root sequence still accepted. When a buffer's values have all been inserted and the buffer is cleared, the watermark moves up to the root that includes them. Once cleared, those values exist only in the tree, so a proof against a root from before their insertion would miss them; the watermark refuses that root. The double-spend page explains it.

The two configuration treesCopy Anchor Link

Zone signer setCopy Anchor Link

The zone signer set belongs to the zone registry program, and the shielded pool reads it. Each leaf is a Poseidon hash under domain 39 of a zone's BabyJubJub signing key and its zone number. A transaction that spends notes of a zone, or creates notes in a zone, proves inside the circuit that the zone's key in this tree signed it, so only the root is public and the zone is not revealed.

Anyone may rebuild the root, and someone must after a zone is approved, rotated, frozen, unfrozen, recovered or revoked. Freezing and revoking set the zone's leaf back to the empty value. The registry keeps only its live root. Every leaf change makes the pool refuse that root until a rebuild has folded the change, and a root the rebuild replaces is never accepted again, so a transaction proved just before a change is proved again. A key rotation or an unfreeze waits a governance-set cooldown since the zone's leaf last changed, which bounds how often that happens. The registry's account can hold up to six levels, and the transaction circuit is built for two levels of eight, 64 positions. The registry admits at most 61 zones under any shape, so one Solana transaction always rebuilds the whole root. See zones.

Fee-rate treeCopy Anchor Link

The fee-rate tree lets governance give a token rates below the four default rates. Each leaf is a Poseidon hash under domain 40 of a token's mint identifier and its packed rates, and the tree has two levels of eight, for 64 tokens. Only its root is on chain, in the pool's process policy, next to the default rates; the leaves are published off chain.

For each of its tokens, a transaction either proves the token's leaf is in the tree and applies that leaf's rates, or applies the default rates. The circuit refuses a leaf rate above the default, so applying the defaults never costs less than the tree's rate would. Because the policy keeps only the current root, a change to the rates invalidates proofs made against the old root. See the fee model.

RelatedCopy Anchor Link