> For the complete documentation index, see [llms.txt](https://valargroup.gitbook.io/shielded-vote-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://valargroup.gitbook.io/shielded-vote-docs/circuit-components/merkle-tree-membership.md).

# Merkle Tree Membership

**Used in:** ZKP #1 (condition 10), ZKP #2 (condition 1), ZKP #3 (condition 1)

## What it does

Proves that a leaf value is a member of a Merkle tree at a given root, via a Merkle authentication path. The prover supplies a leaf, a position, and an authentication path (sibling hashes at each level). The circuit hashes up the path and checks that the result equals the expected root.

Critically, the Merkle path is a **private witness** — the verifier learns that *some* leaf exists in the tree, but not *which* one.

## The three trees

Shielded Vote uses three distinct Merkle trees. Each has a different purpose, hash function, and depth.

### 1. Note Commitment Tree (ZCash mainchain)

| Property      | Value                                                                                     |
| ------------- | ----------------------------------------------------------------------------------------- |
| Purpose       | Stores Orchard note commitments on the ZCash mainchain                                    |
| Hash function | **Sinsemilla** (matching the Orchard specification)                                       |
| Depth         | **32** (up to \~4 billion leaves)                                                         |
| Structure     | Append-only                                                                               |
| Used in       | ZKP #1 (condition 10) — proves a real Orchard note exists on-chain at the snapshot height |

This is the standard note commitment tree from ZCash. We do not modify it; we prove membership in it as-is. See [Orchard spec §5.4.7.3](https://zips.z.cash/protocol/protocol.pdf).

### 2. Indexed Merkle Tree (nullifier set)

| Property      | Value                                                                     |
| ------------- | ------------------------------------------------------------------------- |
| Purpose       | Stores all on-chain nullifiers, enabling non-membership proofs            |
| Hash function | **Poseidon** (fast in-circuit proving)                                    |
| Depth         | **29** (up to \~512 million nullifiers)                                   |
| Structure     | Sorted interval tree (supports both membership and non-membership proofs) |
| Used in       | ZKP #1 (condition 13) — proves a note's nullifier has NOT been spent      |

The Indexed Merkle Tree (IMT) is described in detail in [IMT Non-Membership](https://github.com/z-cale/shielded-vote-book/blob/main/circuits/shielded_vote_book/circuits/imt-non-membership.md). ZCash mainnet currently has \~51 million nullifiers, so depth 29 provides roughly 10x headroom with no constant updates needed.

### 3. Vote Commitment Tree (vote chain)

| Property      | Value                                                                                 |
| ------------- | ------------------------------------------------------------------------------------- |
| Purpose       | Stores VAN commitments and Vote Commitments on the vote chain                         |
| Hash function | **Poseidon** (fast in-circuit proving)                                                |
| Depth         | **24** (up to \~16.7 million entries)                                                 |
| Structure     | Append-only (same structure as the note commitment tree, but with Poseidon)           |
| Leaf types    | VAN commitments (`DOMAIN_VAN = 0`) and Vote Commitments (`DOMAIN_VC = 1`)             |
| Used in       | ZKP #2 (condition 1) — proves a VAN exists; ZKP #3 (condition 1) — proves a VC exists |

The Vote Commitment Tree is **global** — it persists across voting rounds and is never reset. Cross-round safety comes from `voting_round_id` being hashed into VAN commitments, VAN nullifiers, vote commitments, and share nullifiers. Domain tags in the first Poseidon input distinguish VAN leaves from VC leaves (see [Domain Tag Separation](https://github.com/z-cale/shielded-vote-book/blob/main/circuits/shielded_vote_book/circuits/domain-tag-separation.md)).

**Capacity analysis:** Each voter produces up to 16 votes (one per proposal) plus some delegation transactions. Assuming each voter generates \~20 tree entries on average, depth 24 supports over **800,000 unique voters** per voting round — far exceeding realistic participation in a 2-week poll.

## Circuit

Given:

* `leaf` — the commitment value
* `path[0..depth-1]` — sibling hashes at each level
* `position` — a `depth`-bit index encoding left/right at each level
* `root` — the expected Merkle root (public input)

The circuit iterates from leaf to root:

```
current = leaf
for i in 0..depth:
    if position_bit(i) == 0:
        current = H(current, path[i])
    else:
        current = H(path[i], current)
assert current == root
```

Where `H` is **Sinsemilla** for the note commitment tree and **Poseidon** for the IMT and Vote Commitment Tree.

## Implementation

The circuit is implemented using a **conditional swap gate** (`q_merkle_swap`) paired with a Poseidon hash chip. Halo2 splits circuit logic into two distinct phases.

### Phase 1: Configure (key generation time)

`configure` runs once when the proving and verification keys are generated. It registers a polynomial identity into the constraint system — no witness data exists yet.

The gate declares five advice columns and constrains them with three polynomial expressions that must all equal zero on any row where `q_merkle_swap = 1`:

| Constraint     | Expression                                         | Role                                                                 |
| -------------- | -------------------------------------------------- | -------------------------------------------------------------------- |
| `swap left`    | `left - current - pos_bit*(sibling - current) = 0` | Mux: pins `left` to either `current` or `sibling` based on `pos_bit` |
| `swap right`   | `left + right - current - sibling = 0`             | Conservation: `right` gets whichever value `left` did not            |
| `bool pos_bit` | `pos_bit*(1 - pos_bit) = 0`                        | Forces `pos_bit` to be 0 or 1, preventing fractional cheating        |

The `swap left` constraint is a linear interpolation: `left = current + pos_bit*(sibling - current)`. When `pos_bit = 0` this collapses to `left = current`; when `pos_bit = 1` it collapses to `left = sibling`. The `swap right` constraint then uniquely determines `right = current + sibling - left`.

The gate selector handle is stored in the `Config` struct and used in Phase 2 to activate the gate.

### Phase 2: Synthesize (proof time)

`synthesize` runs once per proof. The prover iterates over all 24 tree levels, and for each level allocates an independent single-row region:

1. **Extract `pos_bit_i`** — bit `i` of the leaf position: `(position >> i) & 1`
2. **Witness `sibling_i`** — the sibling hash at this level from the authentication path
3. **Enable the gate** — writes `1` into the selector column at offset 0, activating the constraints
4. **Copy `pos_bit` and `current`** into `advices[0]` and `advices[1]` via equality constraints, binding them to previously assigned cells
5. **Assign `left`** — prover directly writes the correct value: `sibling` if `pos_bit = 1`, else `current`
6. **Assign `right`** — derived as `current + sibling - left` (no branching needed)
7. **Hash** — feed `(left, right)` into the Poseidon chip to produce the parent node, which becomes `current` for the next level

There is no swap *operation* — the prover directly places already-correct values into the `left` and `right` cells. The gate's polynomial constraints make any incorrect placement unprovable: a dishonest assignment would produce a non-zero polynomial evaluation, causing the inner product argument to fail.

After 24 levels, the final `current` value is equality-constrained to the `VOTE_COMM_TREE_ROOT` public input.

### Column layout (per level, two regions)

**Region A — swap row** (`q_merkle_swap = 1`, `advices[0..4]`):

| Col      | `[0]`     | `[1]`     | `[2]`     | `[3]`  | `[4]`   |
| -------- | --------- | --------- | --------- | ------ | ------- |
| offset 0 | `pos_bit` | `current` | `sibling` | `left` | `right` |

**Region B — Poseidon rows** (internal to `PoseidonChip`, `advices[5..8]`):

| Col         | `[5]`         | `[6]`     | `[7]`     | `[8]`     |
| ----------- | ------------- | --------- | --------- | --------- |
| offset 0..N | partial S-box | `state_0` | `state_1` | `state_2` |

## Variations

### ZKP #1 — Note commitment tree membership (condition 10)

Proves a real Orchard note exists in the mainchain note commitment tree at the snapshot height.

For **dummy notes** (v = 0), this check is **skipped** via Orchard's standard dummy note mechanism: `v * (root - nc_root) = 0`. The circuit remains uniform — the path is still provided as witness, but the root-check gate is gated off when v = 0.

### ZKP #2 — Vote commitment tree membership (condition 1)

Proves a Vote Authority Note exists in the vote commitment tree. Uses Poseidon. The anchor `vote_comm_tree_root` is a public input, verified by the vote chain to match a real tree state.

### ZKP #3 — Vote commitment tree membership (condition 1)

Proves a Vote Commitment exists in the vote commitment tree. Same tree and hash function as ZKP #2.

## Reference

Orchard spec §5.4.7.3 — Merkle Path Validity (adapted for value-gated skip and Poseidon)