Skip to main content

The Merkle Forest

Every commitment the pool inserts becomes a leaf of a Merkle tree, and the trees together form a forest. A spend proves its note is a leaf by naming a tree's root, never the leaf itself.

Trees and leaves​

PropertyValue
Depth20 levels
Leaves per tree2^20 = 1,048,576
Node hashPoseidon2(left, right); an empty subtree is the zero hash of its height
Leaf indexGlobal and u32; a leaf's tree is leaf_index >> 20
InsertionAppend-only: each commitment takes the next leaf and is never removed

Each insert updates the active tree's root and emits MerkleRootUpdated { old_root, new_root, tree_size }; the operation's own event reports the leaf index. The active tree keeps every internal node on-chain (MerkleLeaves, MerkleNodes, PoseidonRoot), and CommitmentToLeafIndex maps each commitment to its leaf.

Sealing​

When an insert fills the 1,048,576th leaf, the runtime seals that tree in the same insert, and so in the same block:

  1. The tree's final root is stored permanently in SealedTreeRoots (by tree id) and SealedRootIndex (by root).
  2. TreeSealed { tree_id, final_root, first_leaf_index, leaf_count } is emitted.
  3. The active tree resets to empty, and the next commitment becomes leaf 0 of the next tree.

A sealed root never expires. A note in a sealed tree stays spendable forever, and a proof built against a sealed root never goes stale.

Roots a spend may use​

A spend names the root each input is proven against. The runtime accepts a root that is:

RootKept for
The active tree's current rootUntil the next insert
Any earlier root of the active treeRootRetentionBlocks, 300 blocks (about 30 minutes), counted from the insert that replaced it
A sealed tree's final rootForever

The window starts when a root is replaced, not when it was created. The current root never expires, so a wallet may prove against one that has been current for longer than the window; when the next insert replaces it, that proof still has the full 300 blocks to land.

Recent roots live in HistoricPoseidonRoots; MaxHistoricRoots (16,384) caps that queue as a safety limit, not as the window. Any other root is refused with UnknownMerkleRoot. The window outlasts the 64 blocks an unsigned spend stays valid in the transaction pool, so an admitted spend's root cannot expire before inclusion. See Spend Validity.

Pruning sealed trees​

The active tree stores all of its internal nodes. Once a tree is sealed, nothing changes in it, so the runtime reclaims most of that storage:

  • Every block, a sweep removes 512 internal nodes of sealed trees, resuming where the previous block stopped.
  • Levels 1–5 are removed; levels 6–19 are kept, 32,766 nodes per tree. Leaves (level 0) and the sealed root are never removed.
  • A path for a note in a sealed tree rebuilds the removed siblings from the leaves of the note's 64-leaf block, and reads the kept levels as stored.

Pruning never affects which notes can be spent.

Subtree roots​

Each tree splits into 16,384 blocks of 64 leaves. The root of a block is a subtree root, a node at level 6.

privacy_getSubtreeRoots(tree_id, start, count) returns up to 4,096 consecutive subtree roots of one tree, with the root the tree anchors to at the same state: the live root of the active tree, or a sealed tree's final root. Blocks past the last leaf are omitted. The response is the same for every wallet.

Building a path locally​

Asking a node for a note's Merkle path tells that node which note is about to be spent. The wallet builds the path itself:

  1. The lower 6 levels come from the 64 leaves of the note's block. The wallet keeps that block from the scan. When it has not kept it, or the block has grown, it reads the aligned 1,024-leaf window holding the note from the indexer, a window every wallet reads alike.
  2. The upper 14 levels come from the tree's subtree roots.
  3. The check. The note's leaf must sit at its offset in the block, the block must hash to its subtree root, and the whole tree must fold to the anchoring root. Any mismatch stops the spend.

buildLocalPath in @orbinum/protocol performs these steps and returns the 20 siblings the circuit expects. The indexer follows finalized blocks; the wallet checks that the root it anchors to is one the chain still accepts.

When the path cannot be built locally, the spend is refused. Falling back to the node's proof (privacy_getMerkleProof) is opt-in and off by default, because it names the note being spent; the app never enables it.

Where a wallet's note gets its leaf​

A path needs the note's leaf index. The wallet never searches the tree for a note.

NoteWhere its leaf comes from
A note the wallet creates (a shield, a transfer's change or self-transfer output, an unshield's change)The insert events of the block it landed in, read whole from the node the wallet submitted to
A note it receivesThe scan feed, which carries each commitment's leaf index
An imported backup or payment slipThe node, asked when the note is imported

When the landing block's events could not be read, the note keeps that block's hash, and its leaf is read from the same events later, by the block sync or by a spend that comes first. While the vault is unlocked, the app runs that block sync every 2 minutes: it places such notes and completes the 64-leaf blocks of its notes from the indexer's leaf windows. Every unlocked wallet reads the tip's windows on the same schedule, whether or not it holds a note there.

A note with no known leaf is refused at spend time, with a message pointing to Recover Notes.

Proof RPCs and their queue​

privacy_getSubtreeRoots, privacy_getMerkleProof (by leaf index) and privacy_getMerkleProofByCommitment run on blocking threads, at most half the node's cores at once, because a sealed tree's path is rebuilt from leaves. Further requests wait in a queue of 128 for up to 2 seconds; past that they are refused with -32009 (server is busy). The full method list is in Public RPC Node.

Spending notes from two trees​

A private transfer spends up to two notes and names one root per input (merkle_roots[2]), so the two notes may come from different trees.

  • Each root must be one the chain accepts (see Roots a spend may use).
  • When only one input is real, the dummy input's root must repeat the real one. The circuit does not constrain a dummy's root, so the pallet requires it; any other value is rejected.
  • The two roots differ only when both inputs are real notes from different trees.

A cross-tree transfer reveals which two trees its notes came from and links them in one transaction. The wallet picks a single note that covers the amount first, then the smallest pair from one tree, and a pair from two trees only when no same-tree pair covers it. An unshield spends one note and names one root.