# 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.
***
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://hinkal-team.gitbook.io/hinkal/technical-description/setup/merkle-trees.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.