The commitment tree

Every note commitment is a leaf in a single, append-only Merkle tree. Proving that a note exists means proving its commitment is a leaf under the current tree root — without revealing which leaf. The tree is the membership backbone of the whole pool.

Parameters (frozen)

These constants (TREE_DEPTH, ZERO_VALUE, ROOT_HISTORY_SIZE) are shared by the contract, the circuit, and @hestia/common. The JS tree must reproduce the on-chain root exactly: same zero subtrees, same Poseidon(2), same left/right ordering by index bit.

Incremental insertion

The tree is incremental: leaves are appended in order, and only the path affected by a new leaf is recomputed. Empty subtrees are represented by precomputed "zeros" so the structure is always a full depth-32 tree.

import { IncrementalMerkleTree } from "@hestia/common";

const tree = await IncrementalMerkleTree.create(); // depth 32 by default
const index = tree.insert(commitment);             // append, returns leaf index
const root = tree.root;                            // current root

A leaf's index is assigned by insertion order and matters elsewhere: a shield deposit's label is derived from its leaf index, and the index is bound into the note's nullifier.

Inclusion proofs

To spend a note, the SDK produces a Merkle proof for its leaf and feeds it to the circuit:

interface MerkleProof {
  leaf: bigint;            // the commitment being proven
  pathElements: bigint[];  // sibling at each level, leaf → root
  pathIndices: number[];   // 0 = node is the left child, 1 = right
  root: bigint;            // root this path resolves to
}

const proof = tree.proof(index);
IncrementalMerkleTree.verify(hasher, proof); // true

The circuit walks pathElements / pathIndices from the leaf upward, hashing pairwise, and checks that the result equals a root the contract recognizes. The spender proves a leaf is included; the proof never says which index, so the spent note stays unlinkable.

The rolling root window

New deposits change the root constantly. If the contract only accepted the very latest root, every proof would be invalidated by the next block's deposit. Instead, the MerkleTreeWithHistory contract keeps the last 64 roots and accepts a proof against any of them. That gives a transaction a comfortable window to be built, proven, and mined without racing other depositors — while still bounding how stale a proof may be.

Why a tree at all

A Merkle tree turns "is this note one of the millions in the pool?" into a single root comparison plus a 32-step hash check inside the proof. It is what lets a spend assert membership in the entire anonymity set cheaply, and what the association set reuses to assert membership in the approved subset.