Merkle Trees

Commitment Merkle Tree

Hinkal accumulates every note commitment into an on-chain Poseidon Merkle tree. The current root is a succinct digest of the entire commitment set; spending a note requires proving, in zero knowledge, that its commitment is a leaf under a recent root (see MainEVMCircuit). The tree is therefore append-driven and append-heavy: leaves are added as deposits and transactions occur, and the structure must support cheap incremental updates and cheap membership proofs at large scale.

Node hashing and indexing

Internal nodes are combined with the binary Poseidon hash H(a, b) = Poseidon([a, b]) (poseidon2). The empty/default node value is the literal field element 0 — there is no table of precomputed zero-subtree constants; an absent child simply hashes as H(x, 0).

Nodes live in a flat mapping(uint256 => uint256) under binary-heap indexing: a node at index i has parent i / 2 and children 2i and 2i + 1, with the root occupying index 1. The leaf layer begins at MINIMUM_INDEX = 2^(LEVELS-1), and the insertion pointer m_index starts there and increments per leaf, so the number of inserted leaves is count = m_index - MINIMUM_INDEX. LEVELS is fixed at deployment and an insert reverts once m_index reaches 2^LEVELS ("Tree is full.").

Dynamic-depth root

The defining trick of Hinkal's tree is that the root height is not fixed — it tracks the fill level. On each insert the contract computes

twoPower = ceil(log2(count))      // logarithm2() rounds up

and updates exactly twoPower levels, taking the root from level twoPower rather than from a fixed top of a fully padded tree. Concretely, the root is the apex of the minimal perfect subtree that covers all current leaves: 9 leaves → root at level 4, 1024 leaves → root at level 10, and so on. Empty right-hand siblings along the climb are filled with 0. This keeps both storage and update cost proportional to log2(count), the actual number of leaves, instead of the maximum capacity LEVELS.

Append-only property

For the production insert path, the tree never stores all nodes — only the right frontier. Here tree[i] is indexed by level i (not heap position) and holds the single rightmost node currently known at that level. insertOne bubbles a new leaf upward over twoPower levels:

• if the current node is a left child (even index), store it as the level's frontier (tree[i] = prevHash) and carry prevHash = H(prevHash, 0) upward, treating the not-yet-existing right sibling as 0;

• if it is a right child (odd index), combine it with the stored left frontier: prevHash = H(tree[i], prevHash).

The new root is tree[twoPower]. insertMany batches this: leaves are grouped into left/right pairs (sortInPairs, accounting for whether the first new leaf lands on an odd slot) so that each completed pair is hashed once via insertTwo. Total persistent storage is O(LEVELS) regardless of how many leaves have been inserted.

Root history

MerkleBase keeps a ring buffer roots[] of the last MAX_ROOT_NUMBER = 200 roots, with rootIndex as the write cursor (rootIndex = (rootIndex + 1) % 200). getRootHash() returns the latest entry; rootHashExists(root) scans the ring. Retaining a window of recent roots lets a proof built against a slightly stale root remain valid for a bounded number of subsequent insertions, which is what makes concurrent proving practical — without it, any insert between proof generation and submission would invalidate an honest user's proof, an easy griefing vector. (As noted above, removals deliberately collapse this window.)

Off-chain mirror and proof generation

Clients maintain a generic mirror of the tree to build membership proofs. It uses the same heap indexing (getStartIndex() = 2^(levels-1)) and the same dynamic-depth rule (logarithm2 rounds up, ancestors recomputed via the configured hashFunction, missing children → defaultNodeValue). Leaves are inserted at the absolute node index recovered from on-chain events, so local positions match the contract exactly; remove(index) is just forceInsert(defaultNodeValue, index).

Two invariants matter for correctness:

• Completeness. Before producing a root or proof, completenessCheck() asserts count == index - getStartIndex() — i.e. there are no gaps between the first leaf and the highest inserted index. A sparse/incomplete local tree throws MerkleTreeIncompleteError, because a proof built from it would hash against a wrong root. (This is why flows that deposit then immediately spend must first wait for the deposited commitments to appear in the local tree.)

• Dynamic root retrieval. getRootHash() scans levels 1, 2, 4, … and returns the first populated node — the same floating apex the contract computes.

For each spent commitment the client emits the witness the circuit consumes:

• getSiblingHashesForVerification(item) walks from the leaf's index upward (index /= 2), collecting the sibling at each level (getSiblingIndex), defaulting to 0, and truncates to CIRCOM_MERKLE_LENGTH = 25 levels;

• getSiblingSides(item) emits the corresponding side bit per level (0 = left, 1 = right).

In-circuit verification

Inside the proof, MerkleRootCalculator(treeDepth) folds the leaf commitment with these 25 siblings/side bits back up to a candidate root, and ForceEqualIfEnabled asserts it equals the public rootHashHinkal — enabled only for non-zero (real) inputs. On-chain, the contract additionally requires that rootHashHinkal is one of the roots still present in the 200-entry ring (rootHashExists). Together these bind every spend to a commitment that genuinely sits under a recent, still-valid tree state.

---