> For the complete documentation index, see [llms.txt](https://hinkal-team.gitbook.io/hinkal/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hinkal-team.gitbook.io/hinkal/technical-description/setup/merkle-trees.md). # 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. ***