Merkle Tree

The Poseidon-based anonymity set

Overview#

The Merkle tree is the core data structure underlying the anonymity pool. All deposit commitments are stored as leaves in a binary Poseidon Merkle tree of depth 20. The tree root is stored on-chain in the MixerState account and updated periodically via multisig transactions.

Tree Parameters#

| Parameter | Value | |---|---| | Depth | 20 levels | | Leaf count | 2²⁰ = 1,048,576 maximum | | Hash function | Poseidon (2 inputs) | | Default empty leaf | 0n | | Leaf content | Poseidon(nullifier, secret) | | Implementation | In-memory array in relayer |

Leaf Computation#

leaf = Poseidon(nullifier, secret)

Where:

• nullifier = Poseidon(spendingKey, DOMAIN_SEPARATOR, counter) — 32 bytes
• secret — random 254-bit field element

The leaf is also called the commitment and is emitted in the DepositEvent during the shield operation.

Incremental Insertion#

The relayer maintains the tree as an in-memory array:

class PoseidonMerkleTree {
  leaves: bigint[] = [];

  insert(leaf: bigint): number {
    this.leaves.push(leaf);
    return this.leaves.length - 1;  // leaf index
  }

  root(): bigint {
    // Recompute all levels from leaves
    let level = [...this.leaves];
    while (level.length > 1) {
      const next: bigint[] = [];
      for (let i = 0; i < level.length; i += 2) {
        const left = level[i];
        const right = level[i + 1] ?? 0n;  // zero-pad
        next.push(hashPair(left, right));
      }
      level = next;
    }
    return level[0];
  }

  path(index: number): { pathElements: bigint[]; pathIndices: number[] } {
    // Return sibling path from leaf to root
    // pathElements: [sibling_0, sibling_1, ..., sibling_19]
    // pathIndices: [0|1, 0|1, ..., 0|1] — left/right at each level
  }
}

Root Update Mechanism#

Unlike Tornado Cash (which updates the root per-deposit), Mini Veil batches updates:

1. Deposits accumulate in the relayer's in-memory tree
2. When pendingLeaves >= threshold (default: 1 for MVP), a root update is triggered
3. The relayer builds a update_root instruction with the new root
4. Two of three oracle keypairs sign the transaction (2-of-3 multisig)
5. On-chain: update_root counts oracle signers and requires approvals >= threshold(2)
6. Sets mixer_state.merkle_root = new_root

Merkle Proof Structure#

A proof consists of 20 sibling hashes and 20 binary path indices:

pathElements[0] = sibling at level 0 (leaf level)
pathElements[1] = sibling at level 1
...
pathElements[19] = sibling at level 19

pathIndices[i] = 0 (left) or 1 (right) at each level

The circuit verifies:

computedRoot = root
for i in 0..20:
  if pathIndices[i] == 0:
    computedRoot = Poseidon(leaf, pathElements[i])
  else:
    computedRoot = Poseidon(pathElements[i], leaf)
assert(computedRoot == merkle_root)

On-chain Storage#

Only the root is stored on-chain:

pub struct MixerState {
    pub merkle_root: [u8; 32],
    pub vault_bump: u8,
    pub total_shielded: u64,
    pub bump: u8,
}

Space: 8 (discriminator) + 32 + 1 + 8 + 1 = 50 bytes

Denomination Separation#

Each denomination has its own Merkle tree:

• 0.1 SOL tree at PDA ["mixer", 0x00e1f505] (100,000,000 LE)
• 1 SOL tree at PDA ["mixer", 0x00ca9a3b] (1,000,000,000 LE)
• 10 SOL tree at PDA ["mixer", 0x00e40b5402] (10,000,000,000 LE)