Merkle Tree Implementation

BN254 Poseidon-based sparse Merkle tree for commitment tracking

Overview

BTCVault’s privacy contracts use a sparse Merkle tree to track deposit commitments with:

• BN254 Poseidon(2) hash function (Garaga-compatible)
• Depth 10 (capacity: 1,024 leaves)
• Root history ring buffer (30 recent roots)
• Zero-value optimization for sparse subtrees

Architecture

Leaf 0: commitment_0 ──┐
                       Hash(L0, L1) ──┐
Leaf 1: commitment_1 ──┘              │
                                   Hash(H01, H23) ──┐
Leaf 2: commitment_2 ──┐              │             │
                       Hash(L2, L3) ──┘             │
Leaf 3: commitment_3 ──┘                            │
                                                  Root

Parameters

Parameter	Value	Description
TREE_DEPTH	10	Max depth (2^10 = 1,024 leaves)
ROOT_HISTORY_SIZE	30	Recent roots kept in ring buffer
Hash Function	BN254 Poseidon(2)	circomlib-compatible

Why Depth 10? Balances capacity (1,024 deposits) with proof size (10 sibling hashes). Shielded pools are expected to rotate denominations frequently, keeping leaf count manageable.

Storage

Core State

next_index: u32                      // Next available leaf index (0-1023)
filled_subtrees: Map<u32, u256>      // Last hash at each level (sparse optimization)
roots: Map<u32, u256>                // Ring buffer of recent roots
current_root_index: u32              // Current position in ring buffer
commitments: Map<u256, bool>         // Commitment uniqueness check

Sparse Optimization

Instead of storing the entire tree, only filled_subtrees (10 values) are stored:

• filled_subtrees[0] = rightmost hash at level 0 (leaves)
• filled_subtrees[1] = rightmost hash at level 1
• …
• filled_subtrees[9] = rightmost hash at level 9 (root parent)

Zero values at each level are precomputed:

zero[0] = 0
zero[i] = Poseidon(zero[i-1], zero[i-1])

Hash Function

BN254 Poseidon(2)

The tree uses Garaga’s BN254 Poseidon implementation, matching circomlib’s specification:

use garaga::hashes::poseidon_bn254::poseidon_hash_2;

fn bn254_hash_pair(left: u256, right: u256) -> u256 {
    poseidon_hash_2(left, right)
}

Poseidon is a ZK-friendly hash function optimized for SNARK circuits. Much cheaper to prove than SHA-256 or Keccak.

Operations

Insert Commitment

fn _insert(ref self: ContractState, leaf: u256) -> u32 {
    let current_index = self.next_index.read();
    assert(current_index < 1024, 'Pool: tree full');

    let mut current_hash = leaf;
    let mut current_level_index = current_index;
    let mut i: u32 = 0;

    while i < TREE_DEPTH {
        if current_level_index % 2 == 0 {
            // Left child: store current hash, pair with zero
            self.filled_subtrees.write(i, current_hash);
            let zero_hash = self._get_zero_value(i);
            current_hash = bn254_hash_pair(current_hash, zero_hash);
        } else {
            // Right child: pair with stored left sibling
            let left = self.filled_subtrees.read(i);
            current_hash = bn254_hash_pair(left, current_hash);
        }
        current_level_index = current_level_index / 2;
        i += 1;
    };

    // Store new root in ring buffer
    let new_root_index = (self.current_root_index.read() + 1) % ROOT_HISTORY_SIZE;
    self.roots.write(new_root_index, current_hash);
    self.current_root_index.write(new_root_index);

    let leaf_index = current_index;
    self.next_index.write(current_index + 1);
    leaf_index
}

1. Read current leaf index (next_index)
2. Starting from level 0, compute parent hashes:
   • If index is even: store hash, pair with zero on right
   • If index is odd: pair stored left sibling with current hash
3. Repeat for all 10 levels
4. Store final root in ring buffer
5. Increment next_index

Verify Root

fn _is_known_root(self: @ContractState, root: u256) -> bool {
    if root == 0 { return false; }
    let current = self.current_root_index.read();
    let mut i: u32 = 0;
    let mut found = false;
    while i < ROOT_HISTORY_SIZE {
        let idx = if current >= i {
            current - i
        } else {
            ROOT_HISTORY_SIZE - (i - current)
        };
        if self.roots.read(idx) == root {
            found = true;
            break;
        }
        i += 1;
    };
    found
}

Root History Window: 30 roots ≈ 30 deposits of latency tolerance. If a user generates a proof using root R, they have ~30 deposits to submit it before R expires.

Compute Zero Values

fn _get_zero_value(self: @ContractState, level: u32) -> u256 {
    let mut current: u256 = 0;
    let mut i: u32 = 0;
    while i < level {
        current = bn254_hash_pair(current, current);
        i += 1;
    };
    current
}

Zero value precomputation:

level 0: 0
level 1: Poseidon(0, 0)
level 2: Poseidon(Poseidon(0,0), Poseidon(0,0))
...

Merkle Proof Generation

Proof generation happens off-chain in the client. To prove a leaf is at index i:

1. Query current root: pool.get_last_root()
2. Compute Merkle path (10 sibling hashes):
   • For each level, sibling is either:
     • filled_subtrees[level] if i % 2 == 1
     • zero_value[level] if i % 2 == 0
3. Generate Groth16 proof proving:
   • commitment = Poseidon(secret, nullifier)
   • Path from commitment to root is valid
   • nullifierHash = Poseidon(nullifier)

Off-Chain Proof (TypeScript)

import { poseidon } from 'circomlibjs';
import { groth16 } from 'snarkjs';

// Compute commitment
const commitment = poseidon([secret, nullifier]);

// Fetch Merkle path
const pathElements = [];
for (let level = 0; level < 10; level++) {
  const sibling = leafIndex % 2 === 1
    ? await pool.filled_subtrees(level)
    : zeroValues[level];
  pathElements.push(sibling);
  leafIndex = Math.floor(leafIndex / 2);
}

// Generate Groth16 proof
const { proof, publicSignals } = await groth16.fullProve(
  {
    secret,
    nullifier,
    recipient,
    relayer,
    fee,
    batchStart,
    batchSize,
    pathElements,
    pathIndices,
  },
  'circuit.wasm',
  'proving_key.zkey'
);

Circuit Constraints

The Groth16 circuit enforces:

template WithdrawCircuit(levels) {
    // Private inputs
    signal input secret;
    signal input nullifier;
    signal input pathElements[levels];
    signal input pathIndices[levels];

    // Public inputs
    signal input root;
    signal input nullifierHash;
    signal input recipient;
    signal input relayer;
    signal input fee;
    signal input batchStart;
    signal input batchSize;

    // Constraint 1: commitment = Poseidon(secret, nullifier)
    component commitmentHasher = Poseidon(2);
    commitmentHasher.inputs[0] <== secret;
    commitmentHasher.inputs[1] <== nullifier;
    signal commitment <== commitmentHasher.out;

    // Constraint 2: Merkle path from commitment to root
    component merkleProof = MerkleTreeChecker(levels);
    merkleProof.leaf <== commitment;
    for (var i = 0; i < levels; i++) {
        merkleProof.pathElements[i] <== pathElements[i];
        merkleProof.pathIndices[i] <== pathIndices[i];
    }
    merkleProof.root === root;

    // Constraint 3: nullifierHash = Poseidon(nullifier)
    component nullifierHasher = Poseidon(1);
    nullifierHasher.inputs[0] <== nullifier;
    nullifierHasher.out === nullifierHash;
}

Performance

Operation	Gas Cost	Notes
Insert	~50k	10 Poseidon hashes + storage
Verify Root	~5k	30 storage reads (worst case)
Generate Proof	0 (off-chain)	~2s on modern CPU
Verify Proof	~300k	Garaga BN254 Groth16

Garaga proof verification is expensive (~300k gas). Use relayer batching to amortize costs across multiple withdrawals.

Initialization

The tree is initialized with zero values in the constructor:

// Initialize Merkle tree with zero values
let mut current_zero: u256 = 0;
let mut i: u32 = 0;
while i < TREE_DEPTH {
    self.filled_subtrees.write(i, current_zero);
    current_zero = bn254_hash_pair(current_zero, current_zero);
    i += 1;
};
self.roots.write(0, current_zero);

The initial root (all-zero tree) is stored at index 0.

Security Properties

Collision Resistance

BN254 Poseidon provides ~128-bit collision resistance. Infeasible to find two different commitments with the same hash.

Commitment Uniqueness

Each commitment is checked against commitments map before insertion. Double-deposits are rejected on-chain.

Root Expiry

30-root history window prevents stale proofs while tolerating network delays. Users must submit proofs within ~30 deposits.

Nullifier Double-Spend

Nullifier registry (nullifier_hashes map) prevents the same proof from being used twice.

See Also

• Shielded Pool V4
• Shielded Swap Pool
• Garaga Documentation
• circomlib Poseidon