How l0ste/no-std-svm-merkle-tree works
This is a Rust no_std cryptographic utility library (a crate) that implements a Merkle tree with:
• a stateful API for off-chain/client-side tree building + proof generation (MerkleTree)
• a stateless/lightweight API for on-chain Solana program proof verification (compute root from leaf + proof; exposed as MerkleProof::merklize / compute_merkle_root-style functions)
So the “system” is not a deployed service—it’s a library used in two runtime environments:
On-chain Solana program (no_std, compute-unit constrained)
From the tree:
• Cargo.toml, Cargo.lock
• Signals: Rust crate, feature flags for hash implementations (sha2, keccak).
• src/lib.rs
• The public API surface: re-exports types (likely MerkleTree, MerkleProof, Sha256, Keccak, errors).
• src/merkle/ (core implementation module)
• mod.rs — module wiring / exports
• core.rs — core algorithms / shared utilities (pairing strategy, indexing, merklization walk)
• tree.rs — stateful tree structure, storage layout (breadth-first array), insertion, merklize, proof generation
• proof.rs — stateless proof verification / recomputation of root from leaf+siblings+index
• hash.rs — hashing abstraction + implementations (Sha256, Keccak, double-hash variants)
• error.rs — error types for insertion/merklize/proof bounds, etc.
• Public API (lib.rs)
• Merkle domain module (merkle/*)
• Tree (stateful)
• Proof (stateless)
• Hash (pluggable algorithms)
• Core (shared logic)
• Error (shared types)
README-driven architecture insights to reflect explicitly
• no_std + stack-only allocation: no heap; designed for Solana BPF constraints.
• Two APIs for two environments:
• MerkleTree: stores full structure for fast proof generation (O(log n)), trades memory for speed (duplicates leaf data in arrays).
• MerkleProof::merklize / stateless root computation: minimal compute for on-chain verification.
• Bitcoin-style pairing: odd nodes duplicate (hash node with itself). Important for correctness expectations.
• Compile-time sizing via const generics: e.g. MerkleTree::<32, 1024, 2048>—this affects how you label interfaces and constraints.
On-chain: compare computed root vs stored root → allow claim
Annotations to add:
• “Client uses stateful MerkleTree (stores nodes, fast proof generation)”
• “Program uses stateless MerkleProof::merklize (compute-unit optimized)”
• “Hash algorithm selectable: SHA-256 / Keccak-256 (+ double variants)”
Crate boundary: no-std-svm-merkle-tree
• lib.rs (Public API façade)
• exports: MerkleTree, MerkleProof, hash types, error types
• merkle::tree (Stateful)
• responsibilities: new, insert, merklize, root, get_proof
• notes: breadth-first arrays, const generic capacities, leaf duplication optimization
• merkle::proof (Stateless)
• responsibilities: compute root from leaf+siblings+index
• notes: on-chain optimized
• merkle::hash
• responsibilities: hashing trait/abstraction + implementations (SHA2/Keccak feature-gated)
• merkle::core
• responsibilities: shared merklization logic, pairing rules, index math
• merkle::error
• responsibilities: error enums/results
• lib.rs → (exports) → merkle::*
• tree → core, hash, error
• proof → core, hash
• core → hash
• (optional) hash → feature flags (sha2, keccak) in Cargo.toml
This is the “architecture” of the codebase.
Actors:
• Client Tooling
• Solana Program Instruction (claim)
• MerkleProof::merklize
• Hash function (Sha256/Keccak)
• Program state (AirdropState.merkle_root)
Sequence:
Program compares computed root to stored root → accept/reject
A note: “Odd node duplication (Bitcoin-style)” and “Proof length ≈ ceil(log2(n))”.
Relationships/interactions to be explicit about (don’t leave implied)
• Root crosses client → chain: [u8; 32] merkle_root stored in account state.
• Proof crosses client → chain: fixed-size buffer + proof_len + leaf_index.
• Hash selection: determined by type parameter (::<Sha256>(), ::<Keccak>()) and Cargo features; show it as a “pluggable algorithm” dependency.
• no_std compatibility: “No heap; stack-only buffers; safe for Solana BPF.”
• Const generics sizing: “MerkleTree<HASH, MAX_LEAVES, NODE_CAP> compile-time capacity.”
• Performance tradeoff (stateful tree): “duplicates leaves in arrays for O(log n) proof gen.”
• On-chain optimization (stateless): “walk proof only; minimal allocations; minimal compute.”
These are the “why” behind the module split.
Technologies/frameworks/libraries to label
Even though it’s “zero-dependency” in spirit, the README indicates feature-driven hashing support:
• Rust no_std
• Cargo features: sha2, keccak
• Solana program usage (Anchor example shown, but crate is Anchor-agnostic)
• Hash algorithms: SHA-256, Keccak-256, double-hash variants
Off-chain Client
• Uses MerkleTree → produces root + proof
Crate internals
• MerkleTree depends on core/hash/error
• MerkleProof depends on core/hash
On-chain Solana Program
• Stores root in account state
• Verifies proof via MerkleProof::merklize