# Merkle trees

The pool needs to answer "is this commitment in the deposit set?" without iterating through every deposit on every check. That's what the Merkle tree is for.

## The basic idea

A Merkle tree is a binary tree where:

* **Leaves** are the data you care about: in TONado Cash's case, the commitments.
* **Internal nodes** are hashes of their two children.
* **The root** is a 256-bit hash that uniquely fingerprints the entire set of leaves.

```
                    root
                   /    \
                 h12     h34
                /  \    /  \
              h1   h2  h3   h4
              │    │   │    │
              c1   c2  c3   c4
```

Any change to any leaf changes the root. Two trees with the same root must have the same leaves.

## Why the pool uses it

The Merkle tree gives us two things:

1. **A single 256-bit root that summarizes all current deposits.** The pool stores this, not the leaves themselves.
2. **Membership proofs in `log₂(N)` hashes.** To prove that commitment `c_i` is at position `i`, you provide a *Merkle path*: the sibling hashes at each level up to the root. The verifier recomputes the root from `c_i` and the path, and checks it matches.

For a tree of height 20 (1,048,576 leaves), a Merkle proof is just 20 hashes, about 640 bytes. Verification is 20 Poseidon hashes.

## TONado Cash's tree shape

| Parameter                       | Value                                  | Why                                                                                                    |
| ------------------------------- | -------------------------------------- | ------------------------------------------------------------------------------------------------------ |
| Height                          | **20**                                 | 2^20 ≈ 1 million capacity per pool. Conservative for v1; can be raised in a v2 pool.                   |
| Hash                            | **Poseidon over BLS12-381**            | Fast inside a SNARK, sound over our field. See [Poseidon vs. MiMC](/how-it-works/poseidon-vs-mimc.md). |
| Empty-slot value (`ZERO_VALUE`) | `keccak256("tornado") mod r_BLS12_381` | Same convention as Tornado-EVM, reduced into our field.                                                |

## Pre-computed "zeros"

The pool needs to support partially-filled trees. When only the first 5 leaves are filled, the right half of the tree is still empty. Rather than recompute the Merkle hash of an empty subtree on every deposit, the contract uses a **pre-computed zeros table**: `zeros[i]` is the Poseidon hash of an empty subtree of height `i`.

These constants are computed off-chain by [`scripts/precompute-zeros.ts`](https://github.com/tonadocash/monorepo/blob/main/apps/contracts/scripts/precompute-zeros.ts) and patched directly into [`merkle_tree.tolk`](https://github.com/tonadocash/monorepo/blob/main/apps/contracts/contracts/merkle_tree.tolk) before compilation.

Why off-chain? Computing Poseidon recursively up to height 20 from scratch would cost \~2^20 Poseidon evaluations on the first deposit, far beyond TON's gas budget. (This was the original `merkle_tree.zeros` bug; see [security review C-4](/security/security-review.md).)

## Root history

The pool stores not just the current root, but the **30 most recent roots** in a ring buffer. Why?

Imagine you build a withdrawal proof against root `R`. Before you submit, three more deposits land. The current root is now `R + 3`, but your proof references `R`. Without a history, your proof would be invalid.

The pool accepts a withdrawal whose proof references *any* root in the last-30 ring. This gives you a generous submission window. (Why 30? It's the same value Tornado-EVM used. In practice, even 5–10 would suffice for normal submission latencies.)

If 30+ new deposits land between proof generation and submission, your proof becomes stale and you have to regenerate it against a current root.

## How the root is updated

This is where TONado Cash *significantly* differs from Tornado-EVM.

### Tornado-EVM: pool computes the new root

The Solidity contract takes the deposit's commitment, runs MiMC (a relatively cheap hash on BN254), and computes the new root on-chain. Each deposit costs a few hundred thousand gas.

### TONado Cash: depositor proves the new root

Poseidon over BLS12-381 is **much** more expensive to evaluate inside the TVM than MiMC is to evaluate inside the EVM:

| Component                   | Cost per Poseidon hash on TVM |
| --------------------------- | ----------------------------- |
| \~675 field multiplications | \~33–60K gas                  |
| Constant-table loads        | \~12K gas                     |
| Control flow                | \~5K gas                      |
| **Total**                   | **\~200K gas / hash**         |

At height 20, a deposit needs 20 hashes ≈ 4M gas. TON's workchain-0 block limit is 1M gas per transaction. **Computing the root on-chain is impossible.**

The fix: **the depositor's wallet computes the new root off-chain, and submits a Groth16 SNARK proving the root is the correct insertion of the new commitment into the previous root.**

This adds a second circuit, `merkleUpdate.circom`, with its own zkey, deployed in a second auto-generated verifier ([`verifier_merkle_update.tolk`](https://github.com/tonadocash/monorepo/blob/main/apps/contracts/contracts/verifier_merkle_update.tolk)). Every deposit message carries both the commitment and a small Groth16 proof.

On-chain the pool does:

1. Look up the previous root.
2. Verify the deposit's root-update SNARK against `(prevRoot, newRoot, commitment, leafIndex)`.
3. If valid: insert the commitment into the commitments dict, advance the root-history ring with `newRoot`, advance `nextIndex`.

The total deposit-side gas cost is now \~150K gas for one pairing check, well within TON's block limit. **Two Groth16 proofs per deposit-withdraw cycle**, but everything is achievable on-chain.

For the post-mortem of an earlier, broken design that tried to skip this proof, see [the off-chain root post-mortem](/protocol-reference/off-chain-root.md).

## Building a Merkle proof for withdrawal

When you withdraw, your client needs to provide a Merkle path showing your commitment is in the tree. The path looks like:

```
pathElements[0..20]   // sibling hash at each level
pathIndices[0..20]    // 0 if your leaf is the left child at this level, 1 if right
```

The client builds this by:

1. Downloading the full ordered list of commitments from the relayer (`GET /tree/commitments`), or by scanning the chain directly.
2. Rebuilding the Merkle tree locally.
3. Computing the path for the leaf at *your* position.

Crucially, **downloading the full list** is what protects your privacy. If the client asked the relayer "give me the path for commitment X," the relayer would learn which deposit you're about to withdraw. By downloading everything and computing locally, the relayer learns nothing.

(The relayer does also expose a `GET /tree/path?commitment=X` endpoint for convenience in cases where the client doesn't care about that privacy axis; see [Relayer HTTP API](/operations/relayer-api.md).)


---

# 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://docs.tonadocash.com/how-it-works/merkle-trees.md?ask=<question>
```

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.