A Rust implementation of the Merkle Sum Sparse Merkle Tree (MSSMT) based on Lightning Labs' implementation.
The Merkle Sum Sparse Merkle Tree combines the properties of both Merkle Sum Trees and Sparse Merkle Trees, providing:
- Efficient sparse storage with compact proofs
- Sum aggregation at each level
- Cryptographic verification
- Flexible storage backend through the
Dbtrait - Support for both regular and compact tree implementations
- Generic over hash size and hasher type
- Thread-safe with optional multi-threading support
- Memory-efficient storage with compact leaf nodes
- Proof compression and decompression
- Comprehensive test coverage including BIP test vectors
- CI/CD pipeline with code coverage reporting
Add this to your Cargo.toml:
[dependencies] mssmt = "0.0.7"Basic example using regular tree:
use mssmt::{MSSMT, MemoryDb, Leaf}; use sha2::Sha256; // Create a new tree with 32-byte hashes using SHA256 let db = Box::new(MemoryDb::<32, Sha256>::new()); let mut tree = MSSMT::<32, Sha256, ()>::new(db); // Insert a leaf let leaf = Leaf::new(vec![1, 2, 3], 100); tree.insert(&[1; 32], leaf).unwrap(); // Get and verify a merkle proof let proof = tree.merkle_proof(&[1; 32]).unwrap(); let root = tree.root().unwrap(); proof.verify_merkle_proof(&[1; 32], leaf, root.hash()).unwrap();Example using compact tree for better memory efficiency:
use mssmt::{CompactMSSMT, MemoryDb, Leaf}; use sha2::Sha256; // Create a new compact tree let db = Box::new(MemoryDb::<32, Sha256>::new()); let mut tree = CompactMSSMT::<32, Sha256, ()>::new(db); // Insert leaves let leaf = Leaf::new(vec![1, 2, 3], 100); tree.insert(&[1; 32], leaf.clone()).unwrap(); // Get and verify compressed proofs let proof = tree.merkle_proof(&[1; 32]).unwrap(); let compressed = proof.compress(); let decompressed = compressed.decompress().unwrap();cargo buildcargo testcargo llvm-cov --all-features --workspace --lcov --output-path lcov.infocargo bench