no-std-svm-merkle-tree

Zero-dependency Merkle tree implementation for Solana programs and off-chain clients.

Built for airdrops, NFT collections, and any verification scenario where you need efficient on-chain proof validation.

Why this exists

Most Merkle tree libraries don't work in Solana programs because they need the standard library. This one is built from scratch with no_std support and optimized for both client-side convenience and on-chain efficiency.

Two APIs for two use cases:

• Stateful tree (MerkleTree) - Client-side proof generation with easy insertion API
• Stateless functions (compute_merkle_root) - On-chain verification with minimal compute units

Installation

[dependencies]
no-std-svm-merkle-tree = "0.1"

Features:

• sha2 - SHA-256 support (default)
• keccak - Keccak-256 support for Ethereum compatibility (default)

Quick Start

Client-Side: Building a Tree and Generating Proofs

Use MerkleTree when you're generating proofs off-chain. It stores the full tree structure so proof generation is fast.

use no_std_svm_merkle_tree::{MerkleTree, Sha256};

// Create tree with capacity for 1024 leaves
let mut tree = MerkleTree::<32, 1024, 2048>::new::<Sha256>();

// Add your data (automatically hashed)
tree.insert::<Sha256>(b"alice:100").unwrap();
tree.insert::<Sha256>(b"bob:200").unwrap();
tree.insert::<Sha256>(b"charlie:300").unwrap();

// Merklize the tree (call this after all inserts)
tree.merklize::<Sha256>().unwrap();

// Get the root to store on-chain
let root = tree.root().unwrap();

// Generate proof for alice (index 0)
let mut proof = [[0u8; 32]; 10];
let proof_len = tree.get_proof(0, &mut proof).unwrap();

// proof[..proof_len] contains the sibling hashes needed for verification

The tree size parameters:

• First 32 - Hash size in bytes (32 for SHA-256)
• Second 1024 - Max number of leaves
• Third 2048 - Total node capacity (should be 2x max leaves)

On-Chain: Verifying Proofs

In your Solana program, use MerkleProof::merklize to verify proofs with minimal compute:

use no_std_svm_merkle_tree::{MerkleProof, Sha256};

#[derive(Accounts)]
pub struct Claim<'info> {
    #[account(mut)]
    pub airdrop_state: Account<'info, AirdropState>,
    // ... other accounts
}

#[account]
pub struct AirdropState {
    pub merkle_root: [u8; 32],
}

pub fn claim(
    ctx: Context<Claim>,
    recipient_data: [u8; 40],      // pubkey (32) + amount (8)
    proof: [[u8; 32]; 14],         // max 14 siblings for 10k leaves
    proof_len: u8,
    leaf_index: u32,
) -> Result<()> {
    // Build proof slices from the provided proof array
    let proof_slices: [&[u8]; 14] = [
        &proof[0], &proof[1], &proof[2], &proof[3],
        &proof[4], &proof[5], &proof[6], &proof[7],
        &proof[8], &proof[9], &proof[10], &proof[11],
        &proof[12], &proof[13],
    ];

    // Compute root from leaf + proof
    let computed_root = MerkleProof::<32>::merklize::<Sha256>(
        &recipient_data,
        &proof_slices[..proof_len as usize],
        leaf_index
    );

    // Verify against stored root
    require!(
        computed_root == ctx.accounts.airdrop_state.merkle_root,
        ErrorCode::InvalidProof
    );

    // Process claim...
    Ok(())
}

The merklize function is lightweight - it just hashes the leaf and walks up the tree. Perfect for on-chain verification.

Hash Algorithms

Switch between SHA-256 (Solana standard) and Keccak-256 (Ethereum standard):

use no_std_svm_merkle_tree::{MerkleTree, Sha256, Keccak};

// SHA-256 tree
let mut sha_tree = MerkleTree::<32, 100, 200>::new::<Sha256>();

// Keccak-256 tree (for Ethereum compatibility)
let mut keccak_tree = MerkleTree::<32, 100, 200>::new::<Keccak>();

Both Sha256d (double SHA-256, Bitcoin-style) and Keccakd are also available.

Proof Size Reference

Your proof buffer needs to fit ceil(log2(num_leaves)) siblings:

Allocate your proof buffer based on your maximum expected tree size.

Implementation Notes

• Bitcoin-style pairing: Odd nodes are duplicated (hash with themselves)
• Breadth-first layout: Tree stored as array for cache efficiency
• Stack-only allocation: No heap usage, works in constrained environments
• Compile-time sizing: Const generics eliminate runtime overhead

The stateful MerkleTree duplicates leaf data (stored in both leaves and branches arrays) to enable O(log n) proof generation. This is a deliberate tradeoff - memory for speed.

Testing

Includes test vectors from real Bitcoin blocks (100000 and 100002) to verify correctness.

cargo test