Merkle Trees - Privacy Cash

What is a Merkle Tree?

A Merkle tree is a cryptographic data structure that allows efficient and secure verification of large data sets. In Privacy Cash, Merkle trees store all deposit commitments in a verifiable structure.

Key Properties:

Efficient proofs: Prove a leaf exists in a tree with only O(log n) data
Tamper-evident: Any change to a leaf changes the root
Append-only: New leaves are added but never removed
Constant verification: Proof verification takes constant time

Why Merkle Trees?

Merkle trees enable Privacy Cash’s core privacy features:

Membership Proofs

Prove a commitment exists in the tree without revealing which leaf it is.

Efficient Storage

Store millions of commitments with minimal on-chain state (only root + sparse subtrees).

Fast Verification

Verify membership in ~20,000 compute units (~0.4ms), enabling Solana-scale throughput.

Historical Proofs

Prove against old tree states using root history, allowing delayed withdrawals.

Tree Structure

Privacy Cash uses a binary sparse Merkle tree optimized for zero-knowledge proofs.

Parameters

Tree Configuration

const MERKLE_TREE_HEIGHT = 26;       // 26 levels deep
const MAX_LEAVES = 2 ** 26;          // 67,108,864 commitments
const ROOT_HISTORY_SIZE = 100;       // Store 100 recent roots
const HASH_FUNCTION = "Poseidon";     // ZK-friendly hash

Binary Tree Layout

Level 0 (Root):        [Root Hash]
                      /           \
Level 1:          [H(L,R)]      [H(L,R)]
                 /       \      /       \
Level 2:     [H(L,R)] [H(L,R)] ...   [H(L,R)]
                ...
Level 25:    [Leaf] [Leaf] [Leaf] ... [Leaf]
             (Commitments are stored here)

Each level doubles the number of nodes until reaching 2^26 leaves at the bottom.

Sparse Tree Optimization

Instead of storing all 2^27 - 1 nodes (~134M nodes), Privacy Cash stores:

Active Subtrees
Zero Values
Root History

Only the rightmost path from root to next insertion point.

From merkle_tree.rs:900

pub struct MerkleTreeAccount {
    pub authority: Pubkey,
    pub next_index: u64,               // Next leaf position
    pub subtrees: [[u8; 32]; 26],      // Only 26 subtree hashes!
    pub root: [u8; 32],                // Current root
    pub root_history: [[u8; 32]; 100], // Recent roots
    pub root_index: u64,
    // ...
}

Storage: 26 subtrees × 32 bytes = 832 bytes (instead of gigabytes!)

Empty subtrees are represented by pre-computed zero hashes.

From constants.ts:6

// Pre-computed zero hashes for each level
export const ZERO_BYTES = [
  [0, 0, 0, ...],        // Level 0: hash of two empty level-1 nodes
  [32, 152, 245, ...],   // Level 1: hash of two empty level-2 nodes
  [16, 105, 103, ...],   // Level 2: ...
  // ... (26 levels)
];

Empty subtrees don’t need to be stored—they’re computed from constants.

Store the 100 most recent roots in a circular buffer.

From merkle_tree.rs:65

let new_root_index = (tree_account.root_index as usize)
    .checked_add(1)
    .ok_or(ErrorCode::ArithmeticOverflow)? % root_history_size;
tree_account.root_index = new_root_index as u64;
tree_account.root_history[new_root_index] = current_level_hash;

This allows withdrawals using commitments from up to 100 transactions ago.

Poseidon Hash Function

Privacy Cash uses Poseidon, a hash function designed specifically for zero-knowledge proofs.

Why Poseidon?

ZK-Friendly
Security
Performance

Poseidon requires far fewer constraints in ZK circuits than traditional hashes.

Hash Function	Constraints (per hash)
SHA-256	~25,000
Keccak-256	~30,000
Poseidon	~60

Result: Faster proving, smaller circuits, lower costs.

Poseidon hashing is fast both on-chain and off-chain.

Context	Time per Hash
On-chain (Solana)	~100 compute units
Off-chain (Node.js)	~0.1ms
In ZK circuit	~60 constraints

Merkle proof verification: 26 hashes × 100 CU = ~2,600 CU

Poseidon Specification

// From light-hasher crate (used by Privacy Cash)
pub struct Poseidon;

impl Hasher for Poseidon {
    fn hashv(data: &[&[u8]]) -> Result<[u8; 32]> {
        // Poseidon hash over BN254 scalar field
        // Parameters: t=3 (2 inputs + 1 output), RF=8, RP=57
    }
}

Inputs: Two 32-byte field elements Output: One 32-byte field element

Tree Operations

Initialization

When a new Merkle tree is created:

Set Empty Root

Initialize the root to the hash of two empty level-1 subtrees:

From merkle_tree.rs:9

pub fn initialize<H: Hasher>(tree_account: &mut MerkleTreeAccount) -> Result<()> {
    let height = tree_account.height as usize;
    let zero_bytes = H::zero_bytes();
    
    for i in 0..height {
        tree_account.subtrees[i] = zero_bytes[i];
    }
    
    let initial_root = H::zero_bytes()[height];
    tree_account.root = initial_root;
    tree_account.root_history[0] = initial_root;
    
    Ok(())
}

Initialize Subtrees

Set all subtrees to their zero values (empty tree state).

Add to Root History

Store the initial root at position 0 in the circular root history buffer.

Appending Commitments

When a new commitment is added:

Check Capacity

Ensure the tree isn’t full:

From merkle_tree.rs:33

let max_capacity = 1u64 << height; // 2^26 = 67,108,864
require!(
    tree_account.next_index < max_capacity,
    ErrorCode::MerkleTreeFull
);

Compute Path

Calculate the Merkle path from leaf to root:

From merkle_tree.rs:41

let mut current_index = tree_account.next_index as usize;
let mut current_level_hash = leaf;  // The commitment

for i in 0..height {
    let subtree = &mut tree_account.subtrees[i];
    let zero_byte = H::zero_bytes()[i];
    
    if current_index % 2 == 0 {
        // Left child: pair with zero (right is empty)
        left = current_level_hash;
        right = zero_byte;
        *subtree = current_level_hash;
    } else {
        // Right child: pair with stored left sibling
        left = *subtree;
        right = current_level_hash;
    }
    
    current_level_hash = H::hashv(&[&left, &right]).unwrap();
    current_index /= 2;  // Move up one level
}

This efficiently computes the new root using only stored subtrees.

Update Root

Store the new root and update root history:

From merkle_tree.rs:65

tree_account.root = current_level_hash;
tree_account.next_index += 1;

let new_root_index = (tree_account.root_index + 1) % root_history_size;
tree_account.root_index = new_root_index;
tree_account.root_history[new_root_index] = current_level_hash;

Emit Event

Emit a commitment event with the new leaf and index:

From lib.rs:351

emit!(CommitmentData {
    index: next_index_to_insert,
    commitment: proof.output_commitments[0],
    encrypted_output: encrypted_output1.to_vec(),
});

This allows clients to sync the tree and decrypt their commitments.

Root Verification

When verifying a withdrawal proof:

From merkle_tree.rs:79

pub fn is_known_root(tree_account: &MerkleTreeAccount, root: [u8; 32]) -> bool {
    if root == [0u8; 32] {
        return false;  // Reject zero root
    }
    
    let root_history_size = tree_account.root_history_size as usize;
    let current_root_index = tree_account.root_index as usize;
    let mut i = current_root_index;
    
    // Check all roots in circular buffer
    loop {
        if root == tree_account.root_history[i] {
            return true;  // Found matching root
        }
        
        if i == 0 {
            i = root_history_size - 1;
        } else {
            i -= 1;
        }
        
        if i == current_root_index {
            break;  // Checked all roots
        }
    }
    
    false  // Root not found
}

Root history allows withdrawals using commitments from up to 100 transactions ago, providing flexibility in timing.

Merkle Proofs

A Merkle proof proves that a specific leaf exists in the tree at a given index.

Proof Structure

interface MerkleProof {
  leaf: Field;                    // The commitment being proven
  pathElements: Field[];          // 26 sibling hashes
  pathIndices: number;            // Binary path (0=left, 1=right)
  root: Field;                    // Expected root after verification
}

Proof Generation (Client-Side)

Locate Leaf

Find the commitment’s index in the tree:

const leafIndex = await findCommitmentIndex(commitment);
// Example: leafIndex = 42

Collect Siblings

For each level, collect the sibling hash:

const pathElements: bigint[] = [];
let index = leafIndex;

for (let level = 0; level < MERKLE_TREE_HEIGHT; level++) {
  const isLeft = index % 2 === 0;
  const siblingIndex = isLeft ? index + 1 : index - 1;
  
  const sibling = await getLeafAtIndex(siblingIndex, level);
  pathElements.push(sibling);
  
  index = Math.floor(index / 2);  // Move up
}

Encode Path

Convert the path to a binary number:

// pathIndices encodes the path as a single number
// Bit i = 0 if leaf is left child at level i, 1 if right

// Example: leafIndex = 42 (binary: 101010)
const pathIndices = leafIndex;  // Use index directly

Package Proof

Create the proof object:

const proof: MerkleProof = {
  leaf: commitment,
  pathElements: pathElements,
  pathIndices: pathIndices,
  root: merkleTree.root,
};

Proof Verification (Circuit)

The zero-knowledge circuit verifies the Merkle proof:

From merkleProof.circom:9

template MerkleProof(levels) {
    signal input leaf;
    signal input pathElements[levels];
    signal input pathIndices;
    signal output root;
    
    component switcher[levels];
    component hasher[levels];
    
    // Convert pathIndices to bits (one per level)
    component indexBits = Num2Bits(levels);
    indexBits.in <== pathIndices;
    
    for (var i = 0; i < levels; i++) {
        // Determine if leaf is left or right child
        switcher[i] = Switcher();
        switcher[i].L <== i == 0 ? leaf : hasher[i - 1].out;
        switcher[i].R <== pathElements[i];
        switcher[i].sel <== indexBits.out[i];
        
        // Hash left and right children
        hasher[i] = Poseidon(2);
        hasher[i].inputs[0] <== switcher[i].outL;
        hasher[i].inputs[1] <== switcher[i].outR;
    }
    
    // Output the computed root
    root <== hasher[levels - 1].out;
}

Verification steps:

Extract path direction bits from pathIndices
For each level, place leaf/hash on correct side based on bit
Hash left and right children using Poseidon
Compare final computed root with expected root

Proof size: 26 siblings × 32 bytes = 832 bytesVerification cost: 26 hashes × ~60 constraints = ~1,560 constraints

Multi-Token Trees

Privacy Cash maintains separate Merkle trees for different token types.

Tree Organization

SOL Tree
SPL Token Trees

Native SOL has a dedicated tree:

// PDA seeds for SOL tree
seeds = [b"merkle_tree"]

// Accounts structure
pub struct Transact {
    #[account(
        mut,
        seeds = [b"merkle_tree"],
        bump
    )]
    pub tree_account: AccountLoader<'info, MerkleTreeAccount>,
    // ...
}

Each SPL token gets its own tree:

// PDA seeds include mint address
seeds = [b"merkle_tree", mint.key().as_ref()]

// Accounts structure for SPL
pub struct TransactSpl {
    #[account(
        mut,
        seeds = [b"merkle_tree", mint.key().as_ref()],
        bump
    )]
    pub tree_account: AccountLoader<'info, MerkleTreeAccount>,
    pub mint: Account<'info, Mint>,
    // ...
}

Each token’s tree must be initialized by the authority before use via initialize_tree_account_for_spl_token.

Why Separate Trees?

Type Safety

Prevents mixing token types in proofs. You can’t withdraw USDC using a SOL commitment.

Independent Limits

Each token can have different deposit limits and fee structures.

Parallel Growth

Trees grow independently based on token usage, not artificially coupled.

Simplified Proofs

Circuit doesn’t need to verify mint addresses match across inputs/outputs.

Tree Synchronization

Clients must keep a local copy of the Merkle tree to generate proofs.

Sync Strategies

Event Listening
Batch Sync
Checkpoint Sync

Subscribe to commitment events and update tree in real-time:

const connection = new Connection(RPC_URL);

// Listen for commitment events
connection.onLogs(
  PRIVACY_CASH_PROGRAM_ID,
  (logs) => {
    const events = parseCommitmentEvents(logs);
    for (const event of events) {
      merkleTree.append(event.commitment);
    }
  },
  'confirmed'
);

Periodically fetch all commitments and rebuild tree:

async function syncTree() {
  const treeAccount = await program.account.merkleTreeAccount.fetch(TREE_PDA);
  const nextIndex = treeAccount.nextIndex.toNumber();
  
  // Fetch commitment events from program logs
  const commitments = await fetchCommitments(0, nextIndex);
  
  // Rebuild tree
  merkleTree = new MerkleTree(MERKLE_TREE_HEIGHT);
  for (const commitment of commitments) {
    merkleTree.append(commitment);
  }
  
  // Verify root matches on-chain
  assert(merkleTree.root === treeAccount.root);
}

Download periodic tree snapshots for faster initial sync:

// Example: Download checkpoint from your own indexer service
const checkpoint = await fetch(`https://your-indexer.example.com/checkpoints/10000.json`);
merkleTree = MerkleTree.fromCheckpoint(checkpoint);

// Sync only new commitments since checkpoint
const newCommitments = await fetchCommitments(10000, currentIndex);
for (const commitment of newCommitments) {
  merkleTree.append(commitment);
}

Checkpoint sync requires setting up your own indexer service to periodically save tree state.

Performance Analysis

Scalability

Metric	Value
Max commitments	67,108,864 (2^26)
Commitments per transaction	2 (2 outputs)
Max transactions	~33.5 million
Current usage (SOL)	~45,000 commitments (~0.07%)
Estimated years to fill	50+ years at current rate

Cost Analysis

Operation	Compute Units	SOL Cost (at 0.000005 SOL/CU)
Append commitment	~5,000 CU	~0.000025 SOL
Verify Merkle proof	~2,600 CU	~0.000013 SOL
Full transaction	~200,000 CU	~0.001 SOL

Merkle tree operations are extremely efficient on Solana. The sparse tree design keeps costs low even with millions of commitments.

Implementation Reference

Merkle Tree

merkle_tree.rsOn-chain Merkle tree implementation with append and verification logic

Merkle Proof Circuit

merkleProof.circomZK circuit for verifying Merkle proofs

Tree Account

lib.rs:896MerkleTreeAccount struct definition

Root Verification

lib.rs:221Root history verification in transact instruction

Next Steps

Commitments & Nullifiers

Learn about the leaves stored in Merkle trees

Zero-Knowledge Proofs

Understand how Merkle proofs are used in ZK circuits

Build with SDK

Start using Merkle trees via the Privacy Cash SDK

Tree Sync Guide

Learn best practices for keeping your tree in sync

​What is a Merkle Tree?

​Why Merkle Trees?

Membership Proofs

Efficient Storage

Fast Verification

Historical Proofs

​Tree Structure

​Parameters

​Binary Tree Layout

​Sparse Tree Optimization

​Poseidon Hash Function

​Why Poseidon?

​Poseidon Specification

​Tree Operations

​Initialization

​Appending Commitments

​Root Verification

​Merkle Proofs

​Proof Structure

​Proof Generation (Client-Side)

​Proof Verification (Circuit)

​Multi-Token Trees

​Tree Organization

​Why Separate Trees?

Type Safety

Independent Limits

Parallel Growth

Simplified Proofs

​Tree Synchronization

​Sync Strategies

​Performance Analysis

​Scalability

​Cost Analysis

​Implementation Reference

Merkle Tree

Merkle Proof Circuit

Tree Account

Root Verification

​Next Steps

Commitments & Nullifiers

Zero-Knowledge Proofs

Build with SDK

Tree Sync Guide

What is a Merkle Tree?

Why Merkle Trees?

Tree Structure

Parameters

Binary Tree Layout

Sparse Tree Optimization

Poseidon Hash Function

Why Poseidon?

Poseidon Specification

Tree Operations

Initialization

Appending Commitments

Root Verification

Merkle Proofs

Proof Structure

Proof Generation (Client-Side)

Proof Verification (Circuit)

Multi-Token Trees

Tree Organization

Why Separate Trees?

Tree Synchronization

Sync Strategies

Performance Analysis

Scalability

Cost Analysis

Implementation Reference

Next Steps