Merkle Tree Implementation

Privacy Cash uses a sparse Merkle tree to store commitments on-chain. The tree enables efficient membership proofs while maintaining constant-size state.

Overview

The Merkle tree implementation is adapted from Light Protocol and provides:

Efficient append-only operations
Poseidon hashing for zk-SNARK compatibility
Root history for asynchronous proof generation
Optimized storage using subtree caching

Tree Structure

Height: 26 levels (configurable) Capacity: 2^26 = 67,108,864 leaves Hash function: Poseidon (2-to-1 compression) The tree stores commitment values as leaves and maintains:

Current root
Root history (circular buffer)
Subtree cache for efficient appends
Next available leaf index

Account Structure

pub struct MerkleTreeAccount {
    pub height: u32,
    pub next_index: u64,
    pub root: [u8; 32],
    pub root_index: u64,
    pub root_history_size: u32,
    pub root_history: Vec<[u8; 32]>,
    pub subtrees: Vec<[u8; 32]>,
}

Fields:

height: Tree depth (26 for Privacy Cash)
next_index: Next available leaf position
root: Current Merkle root
root_index: Position in circular root history buffer
root_history_size: Size of root history buffer
root_history: Circular buffer of recent roots
subtrees: Cache of rightmost subtree hashes at each level

Initialization

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

Zero bytes: The tree uses pre-computed hashes of empty subtrees:

zero_bytes[0] = 0  (empty leaf)
zero_bytes[1] = H(zero_bytes[0], zero_bytes[0])
zero_bytes[2] = H(zero_bytes[1], zero_bytes[1])
...
zero_bytes[height] = H(zero_bytes[height-1], zero_bytes[height-1])

This allows efficient handling of empty branches without computing hashes.

Appending Leaves

The append function adds a new commitment to the tree:

pub fn append<H: Hasher>(
    leaf: [u8; 32],
    tree_account: &mut MerkleTreeAccount,
) -> Result<Vec<[u8; 32]>> {
    let height = tree_account.height as usize;
    let root_history_size = tree_account.root_history_size as usize;
    
    // Check if tree is full before appending
    let max_capacity = 1u64 << height; // 2^height
    require!(
        tree_account.next_index < max_capacity,
        ErrorCode::MerkleTreeFull
    );
    
    let mut current_index = tree_account.next_index as usize;
    let mut current_level_hash = leaf;
    let mut left;
    let mut right;
    let mut proof: Vec<[u8; 32]> = vec![[0u8; 32]; height];
    
    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 = current_level_hash;
            right = zero_byte;
            *subtree = current_level_hash;
            proof[i] = right;
        } else {
            left = *subtree;
            right = current_level_hash;
            proof[i] = left;
        }
        current_level_hash = H::hashv(&[&left, &right]).unwrap();
        current_index /= 2;
    }
    
    tree_account.root = current_level_hash;
    tree_account.next_index = tree_account.next_index
        .checked_add(1)
        .ok_or(ErrorCode::ArithmeticOverflow)?;
    
    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;
    
    Ok(proof)
}

Algorithm Walkthrough

Example: Appending the 5th leaf (index 4) to a height-3 tree

Initial state (4 leaves):
         root
        /    \
      h01    h23
     /  \   /  \
   L0  L1 L2  L3

Index 4 in binary: 100

Level 0: (rightmost bit = 0)

index = 4 (even)
left = L4 (new leaf)
right = zero_bytes[0] (empty sibling)
subtrees[0] = L4
proof[0] = zero_bytes[0]
hash = H(L4, zero_bytes[0])

Level 1: (middle bit = 0)

index = 2 (even)
left = H(L4, zero_bytes[0])
right = zero_bytes[1] (empty sibling)
subtrees[1] = H(L4, zero_bytes[0])
proof[1] = zero_bytes[1]
hash = H(H(L4, zero_bytes[0]), zero_bytes[1])

Level 2: (leftmost bit = 1)

index = 1 (odd)
left = subtrees[2] = h01 (existing left subtree)
right = H(H(L4, zero_bytes[0]), zero_bytes[1])
proof[2] = h01
hash = H(h01, H(H(L4, zero_bytes[0]), zero_bytes[1]))

Result:

New root computed and stored
Subtree cache updated for future appends
Merkle proof returned for immediate use

Key Optimizations

1. Subtree Caching The subtrees array stores the rightmost filled subtree at each level. This allows O(height) append operations instead of O(n log n) for n leaves. 2. Index-Based Path Selection The algorithm uses the binary representation of the leaf index to determine left/right positioning:

Bit 0: Level 0 position
Bit 1: Level 1 position
Bit i: Level i position

If current_index % 2 == 0, the new node goes on the left. 3. Zero Byte Precomputation Empty subtrees use precomputed hashes instead of computing them on the fly. 4. Proof Generation The append function returns the Merkle proof, allowing users to immediately generate zero-knowledge proofs without a separate query.

Root History

The tree maintains a circular buffer of recent roots to support asynchronous proof generation.

Why Root History?

In a blockchain environment:

User generates a proof using root R at time T
Other transactions modify the tree between T and submission
By time user submits, the current root is R’

The root history allows the user’s proof (using old root R) to still be valid if R is in the history.

Root Lookup

pub fn is_known_root(tree_account: &MerkleTreeAccount, root: [u8; 32]) -> bool {
    if root == [0u8; 32] {
        return false;
    }
    
    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;
    
    loop {
        if root == tree_account.root_history[i] {
            return true;
        }
        
        if i == 0 {
            i = root_history_size - 1;
        } else {
            i -= 1;
        }
        
        if i == current_root_index {
            break;
        }
    }
    
    false
}

Algorithm:

Reject zero roots (invalid)
Start at current root index
Walk backwards through circular buffer
Return true if root found
Return false if we wrap around to start

Complexity: O(root_history_size)

Root History Size

Typical configuration: 100-1000 roots Trade-offs:

Larger history: More flexibility for async proofs, more storage
Smaller history: Less storage, but proofs must be submitted quickly

For Privacy Cash:

Root history size: 100
Allows ~10-15 minutes for proof submission (assuming ~10s per transaction)

Poseidon Hashing

The tree uses Poseidon hash for zk-SNARK compatibility:

H::hashv(&[&left, &right])

Where H: Hasher is typically Poseidon with 2 inputs. Properties:

Field arithmetic: Operates in BN254 scalar field
Efficient circuits: ~200 constraints per hash
Domain separation: Hashes at different levels use different parameters

Storage Costs

For a height-26 tree with 100-root history:

Fixed fields: 32 bytes (height, next_index, root_index, root_history_size)
Root: 32 bytes
Root history: 100 × 32 = 3,200 bytes
Subtrees: 26 × 32 = 832 bytes

Total: ~4,100 bytes

Solana rent: ~0.028 SOL for 4,100 bytes

Proof Verification

While proof generation happens off-chain, verification occurs in the circuit:

template MerkleProof(levels) {
    signal input leaf;
    signal input pathElements[levels];
    signal input pathIndices;
    signal output root;
    
    // Convert path indices to binary
    component indexBits = Num2Bits(levels);
    indexBits.in <== pathIndices;
    
    // Hash up the tree
    for (var i = 0; i < levels; i++) {
        switcher[i] = Switcher();
        switcher[i].L <== i == 0 ? leaf : hasher[i - 1].out;
        switcher[i].R <== pathElements[i];
        switcher[i].sel <== indexBits.out[i];
        
        hasher[i] = Poseidon(2);
        hasher[i].inputs[0] <== switcher[i].outL;
        hasher[i].inputs[1] <== switcher[i].outR;
    }
    
    root <== hasher[levels - 1].out;
}

The circuit recomputes the root from the leaf and path elements, verifying membership.

Performance Characteristics

Append operation:

Compute units: ~2,000-3,000 CU
Time: O(height) = O(26) hashes
Storage writes: 1 root + 26 subtrees + 1 history entry

Root lookup:

Compute units: ~100-500 CU
Time: O(root_history_size)
Storage reads: No writes

Proof generation (off-chain):

Time: O(height) tree traversal
Data: 26 × 32 = 832 bytes (path elements)

Security Considerations

Collision Resistance

Poseidon provides ~128 bits of collision resistance, sufficient for cryptographic applications.

Preimage Resistance

Given a root R, it is computationally infeasible to find a leaf L and path that produces R (without knowing a valid leaf).

Second Preimage Resistance

Given a leaf L with path P producing root R, it is computationally infeasible to find a different L’ and P’ producing the same R.

Tree Full Protection

require!(
    tree_account.next_index < max_capacity,
    ErrorCode::MerkleTreeFull
);

The tree rejects appends once full, preventing overflow.

Root History Expiration

Old roots naturally expire from the history. Users must submit proofs before their root is evicted, or regenerate with a newer root.

Implementation Source

The Merkle tree implementation is adapted from Light Protocol’s sparse merkle tree, which has been audited and battle-tested in production.

Architecture

Configuration

Merkle Tree Implementation

Merkle Tree Implementation

Overview

Tree Structure

Account Structure

Initialization

Appending Leaves

Algorithm Walkthrough

Key Optimizations

Root History

Why Root History?

Root Lookup

Root History Size

Poseidon Hashing

Storage Costs

Proof Verification

Performance Characteristics

Security Considerations

Collision Resistance

Preimage Resistance

Second Preimage Resistance

Tree Full Protection

Root History Expiration

Implementation Source

Build docs developers (and LLMs) love

Architecture

Configuration

Documentation Index

​Merkle Tree Implementation

​Overview

​Tree Structure

​Account Structure

​Initialization

​Appending Leaves

​Algorithm Walkthrough

​Key Optimizations

​Root History

​Why Root History?

​Root Lookup

​Root History Size

​Poseidon Hashing

​Storage Costs

​Proof Verification

​Performance Characteristics

​Security Considerations

​Collision Resistance

​Preimage Resistance

​Second Preimage Resistance

​Tree Full Protection

​Root History Expiration

​Implementation Source

Build docs developers (and LLMs) love

Merkle Tree Implementation

Overview

Tree Structure

Account Structure

Initialization

Appending Leaves

Algorithm Walkthrough

Key Optimizations

Root History

Why Root History?

Root Lookup

Root History Size

Poseidon Hashing

Storage Costs

Proof Verification

Performance Characteristics

Security Considerations

Collision Resistance

Preimage Resistance

Second Preimage Resistance

Tree Full Protection

Root History Expiration

Implementation Source