Merkle Trees

The Specter protocol uses Merkle trees to efficiently prove that a commitment exists in a set without revealing which commitment is being referenced. The tree is an off-chain incremental binary Merkle tree with on-chain root tracking. The full tree is maintained by off-chain indexers; the blockchain stores only the current root hash and a history of recent roots.

Tree Parameters

Parameter	Value
Tree depth	20 levels
Max commitments	2^20 = 1,048,576
Hash function	PoseidonT3 (2-input Poseidon over BN254)
Root history size	100 roots (ring buffer)
Tree type	Append-only (no deletion, no modification)
Storage model	Full tree off-chain, root + history on-chain

Tree Structure

A Merkle tree of depth 20 has 2^20 leaves at the bottom level. Each leaf holds either a commitment hash or a zero hash (indicating an empty slot). Internal nodes are computed by hashing their two children:

node = PoseidonT3(leftChild, rightChild)

The diagram shows a simplified view. The actual tree has 20 levels and over 1 million leaf positions. In practice, only a small fraction of leaves contain commitments — the rest are empty (zero hashes).

Zero Hashes

Empty leaves and their ancestor nodes use precomputed zero hashes. The zero hash at each level is deterministic:

zeroHash[0]  = 0                                          // Empty leaf
zeroHash[1]  = PoseidonT3(zeroHash[0], zeroHash[0])       // Two empty leaves
zeroHash[2]  = PoseidonT3(zeroHash[1], zeroHash[1])       // Two empty subtrees
...
zeroHash[20] = PoseidonT3(zeroHash[19], zeroHash[19])     // Root of empty tree

These values are computed once at initialization and stored as constants. When building or verifying a Merkle proof, any path through empty subtrees uses the appropriate precomputed zero hash rather than recomputing it.

Append-Only Insertion

The tree is append-only: new commitments are inserted at the next available leaf position, and no leaf can ever be modified or deleted. This property is critical for security:

• No rewriting history. Once a commitment is in the tree, it stays there permanently. A proof of membership against a past root remains valid.
• No censorship via deletion. A root operator cannot remove a commitment from the tree to prevent its reveal.
• Deterministic ordering. Each commitment gets a unique leafIndex that monotonically increases.

When a commitment is inserted:

1. The commitment hash is placed at leafIndex = nextLeafIndex
2. All ancestor nodes along the path from the new leaf to the root are recomputed
3. The new root hash is submitted on-chain
4. nextLeafIndex is incremented

Root Management

On-Chain Root Storage

The CommitmentTree contract stores:

• currentRoot — the most recently published root hash
• rootHistory[100] — a ring buffer of the 100 most recent roots
• nextLeafIndex — the index where the next commitment will be inserted

When a new root is published via updateRoot(), it is written to both currentRoot and the next position in the ring buffer.

Root History (100-Root Buffer)

The 100-root history serves a critical usability purpose. Between the time a user commits data and the time they generate a ZK proof, new commitments may be added to the tree, changing the root. If only the current root were valid, any proof generated against a slightly older root would be rejected.

The ring buffer allows proofs against any of the 100 most recent roots:

During reveal, the contract checks: isKnownRoot(proof.root) — this returns true if the root is in the ring buffer. If the root has been rotated out (more than 100 root updates have occurred since the proof was generated), the proof is rejected and must be regenerated against a newer root.

Root Operator

The root operator is a trusted off-chain service that:

1. Monitors the blockchain for CommitmentAdded events
2. Maintains a complete local copy of the Merkle tree
3. Recomputes the root after each new commitment
4. Submits the new root on-chain via updateRoot()

The root operator role is controlled by access control on the CommitmentTree contract. Only the designated operator address can call updateRoot().

Separate Trees

The protocol maintains separate Merkle trees for different commitment types:

Tree	Contract	Used By	Purpose
CommitmentTree	CommitmentTree	CommitRevealVault / BatchCommitRevealVault	Token commitments (7-input Poseidon)
OpenCommitmentTree	OpenCommitmentTree	OpenGhostVault, PersistentKeyVault	Data commitments (4-input Poseidon)

Separate trees provide clean isolation between token and data privacy operations. They use separate root operators, separate root histories, and separate leaf index counters. A token commitment in CommitmentTree cannot be confused with a data commitment in OpenCommitmentTree.

The PersistentKeyVault shares the OpenCommitmentTree with OpenGhostVault. This means a commitment inserted via OpenGhostVault can later be used for persistent access via PersistentKeyVault (and vice versa). They also share the OpenNullifierRegistry, so revoking a persistent key spends the same nullifier that a one-time reveal would have used.

Merkle Proofs

To prove a commitment exists in the tree, the prover provides a Merkle proof: the 20 sibling hashes along the path from the commitment's leaf to the root.

The proof consists of:

• pathElements[20] — the 20 sibling hashes (one per level)
• pathIndices[20] — the 20 direction bits (0 = leaf is left child, 1 = leaf is right child)

Verification starts at the leaf and hashes upward:

currentHash = commitment
for i = 0 to 19:
    if pathIndices[i] == 0:
        currentHash = PoseidonT3(currentHash, pathElements[i])
    else:
        currentHash = PoseidonT3(pathElements[i], currentHash)

assert(currentHash == root)

This computation is performed inside the ZK circuit as private computation. The circuit takes the path elements and path indices as private inputs, computes the root, and checks it against the public root input. The on-chain verifier only sees the root (public) — not the path, not the leaf position, and not the commitment itself.

Liveness Dependency

The Merkle tree design introduces a liveness dependency on the root operator. If the root operator goes offline:

• New commitments can still be submitted to the smart contract (they are queued with assigned leaf indices)
• Reveals and access proofs stall because the on-chain root does not advance to include recent commitments
• Existing reveals against already-published roots continue to work (within the 100-root history window)

This is a deliberate trade-off. Computing Merkle tree updates on-chain (with 20 levels of Poseidon hashing per insertion) would cost approximately 600,000 gas per commitment — prohibitively expensive. The off-chain root operator reduces this to a single updateRoot() transaction per batch of commitments.

Mitigations for root operator downtime:

• Decentralized root operators — multiple independent operators can compute and submit roots
• Anyone can run an operator — the operator role only requires read access to on-chain events and a funded wallet for submitting root updates
• 100-root history — proofs remain valid against recent roots even during temporary operator outages
• Root operator is not trusted with privacy — the operator sees only commitment hashes (opaque), never the underlying data

Gas Costs

Operation	Gas Cost	Frequency
Insert commitment (on-chain)	~50,000	Per commit
Update root (on-chain)	~30,000	Per batch of commits
PoseidonT3 hash (on-chain)	~30,000	Per Merkle node during root updates
Merkle proof verification	0 (off-chain, inside ZK circuit)	Per reveal/access

The on-chain cost per commitment is dominated by the storage write for the commitment hash and event emission. The expensive Merkle path computation happens off-chain (in the indexer, the root operator, and the ZK prover), keeping on-chain gas costs manageable.