A small but usable implementation of Merkle trees, generic over digest algorithm with some low-hanging performance optimizations.
cargo build will do the trick.
All public API is documented; cargo doc to build it.
cargo test will run unit, integration, and property tests.
cargo bench will run Criterion
benchmarks for the public API on a range of input sizes.
use merkle::Tree;
use sha2::Sha256;
// Build a tree from byte-like items.
let tree: Tree<Sha256> = ["alpha", "beta", "gamma"].into_iter().collect();
// Generate and verify a proof for a leaf.
let proof = tree.prove(1).unwrap();
let valid = proof.preproof.verify().unwrap();Preproof also supports the serde::{Serialize, Deserialize} traits, so can be
used to transfer Merkle proofs as e.g. JSON.
The tree is generic over its digest algorithm using
digest::Digest, a
trait that collects cryptographically secure digest algorithms.
The tree is stored internally in a flat tree using the Eytzinger breadth-first implicit tree layout, which is memory-compact and cache-friendly, and allows us to access contiguous slices of leaves and sibling nodes, which is particularly helpful when recalculating the tree.
Two concerns are separated: the internal module tree deals with the implicit
tree representation and manipulation, while cryptographic applications are
represented in the top-level lib.rs.
Odd leaves are promoted to leaves on the level above, which is natural for the layout, though incompatible with some other Merkle tree implementations. This means that all Merkle trees generated by this library are complete and perfect, though not necessarily full.
Trees need not have items. A tree without any items will yield None from its
root() function, and an attempt to generate a proof at any index will always
result in Error::IndexOutOfBounds.
All library code was written by hand. Test and benchmark code was largely
generated from natural language and kept up-to-date using Claude Code (via
Zed), and documentation (excluding this README, which is
artisanal) was partly hand-written and partly generated: I wrote terse
documentation of surprising or non-local facts and used Claude to expand it with
more obvious information, then passed over it myself to check for correctness
and improve phrasing and formatting.