> For AI agents: the documentation index is at https://docs.umbraprivacy.com/llms.txt, and every page is available as Markdown at its URL with .md appended. # The note tree (/docs/state/note-tree) The note tree is where every note's leaf goes, spent or not, dummy or real. It is an append-only Merkle tree of up to 2³² leaves, stored on chain as a 19,249-byte account that holds the tree's frontier and its last 512 roots, never the leaves themselves. ## Shape The tree has eleven levels. The bottom ten give each node eight children and the top level gives the root four, so it holds 8¹⁰ × 4 = 2³² leaves exactly. A membership path is eleven hashes, each over eight or four children, which fits the Solana Poseidon syscall's limit of twelve inputs. The [Merkle trees](https://docs.umbraprivacy.com/docs/cryptography/merkle-trees) page explains why eight children beat two. Because the tree only grows, the program does not keep the leaves. It keeps the frontier: for each level, the eight slots of the node still being filled. Appending a leaf updates the frontier and gives a new root. The whole account is 19,249 bytes: a 5-byte header, the next free index, a root counter, four record counters the program uses to number its log entries, the frontier (11 levels × 8 slots × 32 bytes) and a ring of 512 roots. That is more than one instruction can create, so the account is created at 10,240 bytes, grown by the staging buffers' resize instruction and then finalized into an empty tree. Anyone who wants the leaves rebuilds them from the program's logs, which is what the indexer does to serve Merkle paths. An empty position holds a fixed non-zero constant, derived from a Keccak-512 hash and reduced into the field, rather than zero. The indexed trees use zero for their empty slots, so the two kinds of tree never share an empty root. ## Leaves, slots and positions A value transaction appends exactly three leaves, one per output slot, whether the output is a real note or a dummy. The program computes each leaf itself, as `H_on(36, commitment, insertion slot, insertion position)`; see [note commitments](https://docs.umbraprivacy.com/docs/state/commitments). - The **insertion slot** is the Solana slot of the transaction that appended the leaf. - The **insertion position** is global: the pool index times 2³² plus the leaf's index within its tree. Every leaf in every pool index has a different position, and the largest possible one is 2⁴⁸ − 1. The position is also an input to the note's nullifier, so a note's nullifier is tied to the one leaf it occupies. See [nullifiers](https://docs.umbraprivacy.com/docs/state/nullifiers). ## Roots and the recent-root window Every append of one to eight leaves produces one new root. The program numbers roots by a sequence: the empty tree's root is 0, and each append's root takes the next number. A transaction names the root its proof used by that number, and the program looks it up in a ring of the 512 most recent roots. A number that has not been published, or that has fallen out of the ring, is refused with error 23, and the client proves again against a current root. Each value transaction appends to its note tree once, so a busy tree turns its 512-root window over in 512 transactions. The identity tree advances only when someone registers, so its window lasts much longer in practice. A stale identity-tree root is refused with error 24, the identity tree's counterpart of error 23; both are in the reference section below. ## Pool indexes A pool index is a 16-bit number naming one instance of the pool's trees. Each pool index has its own note tree, identity tree, fee commitment tree and three staging buffers, each at an address derived from the pool index. All pool indexes share the same program, the same pool token accounts and the same verifying keys, which are compiled into the program. Anyone can create the trees for a new pool index: the initialisation instructions need only a fee payer to fund the accounts' rent, and each tree can be created once. A value transaction names two pool indexes, and they need not be the same. The chart below shows a transaction that spends from pool index 0 and appends its new notes to pool index 1. ```mermaid flowchart LR tx(["Value transaction"]) subgraph P0["Pool index 0"] ct0["Note tree"] it0["Identity tree"] ns0["Nullifier staging buffer"] end subgraph P1["Pool index 1"] ct1["Note tree"] ft1["Fee commitment tree"] end tx -- "proves inputs" --> ct0 tx -- "proves sender, recipients" --> it0 tx -- "stages nullifiers" --> ns0 tx -- "appends 3 leaves" --> ct1 tx -- "stages 3 fee notes" --> ft1 ``` *What one value transaction reads and writes when its spend and append pool indexes differ.* The spend pool index supplies the note-tree root its inputs are proved against, the identity tree its sender and recipients are proved against and the staging buffer its nullifiers go into. The append pool index names the note tree its three outputs are appended to and the fee tree its fee notes are staged in, which also numbers the transaction's record. The two may differ only for a transaction that spends at least one real note: the transaction proof folds whether they differ and refuses it when all three inputs are dummies, so a deposit, or any transaction that spends nothing, appends to the pool index it spends from. The SDK's deposit and spend builders set them equal. A note in one pool index is spent against that pool index's trees only, including its identity tree. An owner who is registered in one pool index's identity tree and holds a note in another cannot spend it until they are registered there as well. ## When a tree fills A tree refuses an append that would take it past 2³² leaves, and the program refuses the whole transaction with error 19 before anything moves; it checks the append tree's room for three outputs and the append pool index's fee tree's room for three more fee notes after every staged one. The root counter is a 32-bit number, and running out of root numbers is refused with the same error. ### Keeping room for every note to leave A pool index also stops taking value transactions that spend from it before its nullifier tree runs short. Every note in it must stay able to leave by the [escape hatch](https://docs.umbraprivacy.com/docs/operations/escape-hatch), which spends one note for one nullifier and needs no new note. So the program refuses a value transaction with error 88 when the pool index's nullifiers and its notes, counted together after the transaction, would pass the room in its nullifier tree less a margin of 2²⁰ leaves. A real nullifier always spends a note, so that count covers every dummy nullifier and every note still unspent. A transaction's outputs count against the pool index it spends from only when it appends them there too. Escapes are never refused this way. Each one stages one nullifier for one note that was already counted, so a pool index at the limit keeps room for every note it holds. The staging buffer itself refuses any nullifier past the last batch of 12 its tree has room for, with `TreeFull`; see [preventing double spends](https://docs.umbraprivacy.com/docs/state/double-spend). No valid traffic reaches the limit. A pool index's note tree holds at most 2³² notes, wherever they came from. A transaction that spends from a pool index either appends its three outputs there or spends at least one of its real notes, because a transaction whose inputs are all dummies must append to its own pool index. So a pool index stages at most four nullifiers per note its tree can hold, and its nullifiers and notes together stay under 5 × 2³², well inside a nullifier tree of 2³⁶ leaves. The limit is checked only for the pool index a transaction spends from; notes appended from other pool indexes need no check, because the same bound covers them. The limit is a backstop. ### Moving on to a new pool index The code offers one way on: a transaction that spends a real note can name a different pool index as its append tree, which only needs that pool index's trees to exist. Its fee notes go with its outputs, so a full fee tree in the pool index it leaves does not stop it. Nothing beyond that is built. No instruction retires a full tree, migrates its notes or moves registrations between pool indexes, and the SDK's deposit and spend builders append to the pool index they spend from. ## Reference **Errors** | Code | Error | Meaning | | ---- | ----------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | `19` | `CommitmentTreeFull` | Returned when an append would take a tree past its leaf capacity, or past the last root its counter can number. Shared by the commitment, identity and fee commitment trees. | | `23` | `CommitmentTreeRootNotRecent` | The folded \`commitmentTreeRoot\` is not in the commitment tree's recent-roots ring. Either the proof was built against a root that has since aged out of the recent-roots window, or the root was never one this program published. The two are indistinguishable by design — both mean the note membership proof binds nothing — but this is the EXPECTED failure of the three, because the commitment tree advances on every transaction: a client seeing it should simply re-prove. Distinct from the turnstile's own \`StaleRoot\`, which is Gate A on the NULLIFIER root. | | `24` | `IdentityTreeRootNotRecent` | The folded \`identityTreeRoot\` is not in the identity tree's recent-roots ring. Rarer than \[\`Self::CommitmentTreeRootNotRecent\`]: this tree only advances when an identity registers. | | `88` | `PoolCapacityReserved` | This pool's nullifier set is nearly full, and the room left is held so that every unspent note can still leave by the escape hatch. The pool takes no more transactions that spend from it; escape the note instead. | Read at build time from `libs/typescript/errors/error-manifest.json`. ## Related - [Every tree](https://docs.umbraprivacy.com/docs/state/trees): All of Umbra's trees in one table. - [Note commitments](https://docs.umbraprivacy.com/docs/state/commitments): What a leaf wraps. - [Merkle trees](https://docs.umbraprivacy.com/docs/cryptography/merkle-trees): Membership proofs and frontier storage in general. - [Preventing double spends](https://docs.umbraprivacy.com/docs/state/double-spend): The staging buffer each pool index has. Last updated 6 October 2026