> 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.

# Merkle trees (/docs/cryptography/merkle-trees)

A Merkle tree folds any number of leaves into one 32-byte root, and anyone holding a leaf can prove it is in the tree with a short path of hashes. Umbra keeps two kinds: append-only trees, which prove that a note or identity exists, and indexed trees, which prove that a nullifier or registration does not.

## Membership proofs

Each node of a Merkle tree is the hash of its children, up to a single root. To show that a leaf is in the tree, you give the leaf and, at every level, the other children of each node on the way up. Hashing upward from the leaf must reproduce the root. The chart below shows one such path in an Umbra tree, where every node has eight children.

```mermaid
flowchart BT
leaf["Your leaf"] --> n1["Level 1 node"]
s1["7 sibling leaves"] --> n1
n1 --> n2["Level 2 node"]
s2["7 sibling nodes"] --> n2
n2 --> more["9 more levels"]
more --> root["Root"]
```

*A membership path: the leaf is hashed with its seven siblings, the result with its seven siblings, and so on up to the root.*

The path is the leaf plus the siblings at every level. Anyone who holds the root can check it, and it reveals nothing about the other leaves beyond their hashes.

Inside a zero-knowledge proof, the leaf and the path are private and only the root is public. The proof then says that some leaf in the tree has the properties the circuit checks, without saying which leaf. That is how a spend shows it consumes notes that exist without revealing which notes they are: every note in the tree is a candidate.

## Append-only frontier trees

The note trees, the identity tree and the fee commitment tree only ever grow. A leaf is never changed or removed, and new leaves go in the next free positions. For a tree like that the chain does not need to store the leaves, only the frontier: at each level, the children of the one node still being filled. Appending a leaf updates the frontier and produces a new root.

Each of these trees holds up to 2³² leaves, and its whole account is 19,249 bytes: the frontier, the next free position, a root counter and the last 512 roots. The leaves themselves are rebuilt off chain from the program's records by anyone who wants them, which is what the indexer does to serve paths. The note and identity trees append up to eight leaves in one call, and a fee insert up to 48; an empty position holds a fixed constant rather than zero.

## Why eight children

1. Leaf
2. 10 levels of 8 children: one Poseidon call each
3. 1 level of 4 children
4. Root: 8¹⁰ × 4 = 2³² leaves

*The shape of the note, identity and fee trees. The indexed trees are twelve levels of eight, for 2³⁶ leaves.*

A binary tree of 2³² leaves has 32 levels, so a path costs 32 hashes. The `sol_poseidon` syscall takes up to 12 inputs, and eight is the largest power of two within that limit, so Umbra's trees give each node eight children. Ten levels of 8 and a top level of 4 hold exactly 2³² leaves, and a path is 11 hashes. Fewer levels means fewer hash calls, on chain for every append and in the circuit for every membership path, at the cost of carrying seven siblings per level instead of one.

The smaller trees use the same arity: the zone signer-set tree and the fee-rate tree are both two levels of 8, or 64 leaves, as the transaction circuit is built today.

## Indexed trees for non-membership

A membership path cannot show that something is absent. The nullifier tree, the registration tree and the fee-nullifier tree use an indexed Merkle tree instead, which can.

Each leaf of an indexed tree holds a value, and also the next larger value in the tree and the position of the leaf that holds it. Leaves are appended in arrival order, but their next pointers link them into a list sorted by value. The first leaf holds the value zero, and the leaf with the largest value points to nothing.

The chart below shows four leaves linked in value order, and where a query for 50 lands.

```mermaid
flowchart LR
a["value 0, next 17"] --> b["value 17, next 42"]
b --> c["value 42, next 90"]
c --> d["value 90, next none"]
q(["query 50"]) -. "falls between 42 and 90" .-> c
```

*An indexed tree's leaves linked in value order. The value 50 falls in the gap between 42 and 90, so it is not in the tree.*

To prove that a value is absent, the prover shows a leaf in the tree whose value is below it and whose next value is above it, or whose next pointer is empty. If the value were in the tree, the list would have a leaf for it between those two, and no such leaf could skip over it. Each leaf is hashed with its own domain, `H_on(37, value, next index, next value)`, and the comparisons are done on the full field values.

Inserting a value means appending its leaf and updating the leaf just below it to point at the new one. On chain, values are first staged, then inserted in batches of 12 by a proof that shows each step was done correctly. See [preventing double spends](https://docs.umbraprivacy.com/docs/state/double-spend) and [the forester](https://docs.umbraprivacy.com/docs/state/forester).

## Recent-root windows

A proof is made against a root, and by the time the transaction lands, other transactions may have appended leaves and produced newer roots. The program therefore accepts any root from a recent window. A transaction names the root it used by its sequence number rather than by value, so the program can look it up in its own history instead of searching for it. A proof made against a root that has left its window is refused, and the client has to make it again against a current root. The trees differ in how long that window is.

**Append-only trees.** The note trees, the identity tree and the fee commitment tree each keep their last 512 roots, and accept any of them. These trees only grow, so an older root is still a correct statement about the leaves it covers.

**Indexed trees.** The nullifier and fee-nullifier trees keep up to 512 recent roots each, and the registration tree up to 120. An older root is not always safe here, because a non-membership proof against an old root says nothing about values inserted since. Newly spent nullifiers wait in the staging buffer (which the code calls the turnstile), and a spend is checked against the buffer as well as the tree, so a proof against a recent root is still sound. Once a staged batch has been inserted into the tree and a grace window of further roots has passed, 512 for the nullifier and fee-nullifier trees and 64 for the registration tree, the program empties that batch from the buffer and raises a watermark to the root at which the insertion finished. Roots below the watermark are refused from then on, because they predate nullifiers the buffer no longer holds. [Preventing double spends](https://docs.umbraprivacy.com/docs/state/double-spend) walks through it.

**Zone signer-set tree.** It keeps one root, and the pool accepts only that one. Every change to a leaf raises a counter in the signer set, and the pool refuses the root until a rebuild that folded every leaf records the counter it saw. A root that a rebuild replaces is never accepted again, so a rotated-out, frozen or revoked zone key stops verifying in the instruction that removes it. The cost is that a transaction proved against the replaced root has to be proved again. Zone changes are rare, and a key rotation or an unfreeze waits a governance-set cooldown since the zone's leaf last changed, so one zone cannot change the root often.

## Related

- [Every tree](https://docs.umbraprivacy.com/docs/state/trees): All of Umbra's trees, what they hold and who writes them.
- [The note tree](https://docs.umbraprivacy.com/docs/state/note-tree): Leaves, positions and pool indexes.
- [Preventing double spends](https://docs.umbraprivacy.com/docs/state/double-spend): The nullifier tree and its staging buffer.
- [Hash functions](https://docs.umbraprivacy.com/docs/cryptography/hashing): The Poseidon forms every node and leaf uses.


Last updated 12 October 2026