Choosing a tree

MerkleForge ships three tree variants. They share the MerkleTree<H> trait but are built for different shapes of data.

Quick decision guide

• You have a list and prove items by position: use BinaryMerkleTree. It has the smallest proofs and the fastest construction.
• You have a key-value map and need to prove a key is absent: use SparseMerkleTree. Keys are 32 bytes, so hash longer keys first.
• You need roots or witnesses that Ethereum tooling understands: use MerklePatriciaTrie<Keccak256>.

Writing code that works with any variant

The shared trait lets you write generic code. Each variant also has a native API (keys for the sparse tree and trie); the trait maps leaf indices onto it.

use merkle_core::prelude::*;
use merkle_variants::{BinaryMerkleTree, MerklePatriciaTrie, SparseMerkleTree};
use merkleforge_hash::Sha256;
 
/// Insert rows through the shared trait and return a metadata snapshot.
fn commit<H, T>(tree: &mut T, rows: &[&[u8]]) -> Result<TreeMetadata, MerkleError>
where
    H: HashFunction,
    T: MerkleTree<H>,
{
    for row in rows {
        tree.insert(row)?;
    }
    Ok(tree.metadata())
}
 
fn main() -> Result<(), MerkleError> {
    let rows: &[&[u8]] = &[b"alice:100", b"bob:250", b"carol:75"];
 
    let binary = commit(&mut BinaryMerkleTree::<Sha256>::new(), rows)?;
    let sparse = commit(&mut SparseMerkleTree::<Sha256>::new(), rows)?;
    let trie = commit(&mut MerklePatriciaTrie::<Sha256>::new(), rows)?;
 
    for meta in [binary, sparse, trie] {
        println!("{:<18} leaves={} height={}", meta.variant, meta.leaf_count, meta.height);
    }
    Ok(())
}

How the trait maps onto each variant

• Binary: insert appends and returns the next LeafIndex. remove replaces the leaf with H::empty(); later indices are unchanged.
• Sparse: leaf index i is stored at a key whose last 8 bytes are i in big-endian order. insert returns the first unoccupied index at or above the leaf count, so it never overwrites a leaf after a removal. generate_proof returns a MerkleProof with 256 path nodes.
• Patricia: leaf index i is stored under the key b"merkleforge:mpt:trait-leaf:" ‖ i (8 bytes, big-endian). generate_proof through the trait returns MerkleError::UnsupportedOperation, because Patricia proofs are key-addressed. Use MerklePatriciaTrie::generate_proof(key) instead.