From leaves to a commitment
A Merkle root commits to a collection of data. An inclusion proof lets someone check one item against that root without downloading the whole collection. I built these structures in Rust to explore how hash commitments and proofs fit together.
The library exposes both binary Merkle trees and sparse Merkle trees, alongside proof types and a generic hashing interface.
Building blocks
- Binary trees built from raw leaf data or precomputed leaf hashes.
- Single inclusion proofs and multi-proofs.
- Sparse trees with key-based state and sparse proofs.
- Interchangeable SHA-256 and Keccak-256 hashers producing 32-byte hashes.
Leaf hashes and internal node hashes use different prefixes. The binary tree promotes an unpaired node to the next layer when a level contains an odd number of nodes.
Keeping the pieces separate
Hashing, tree construction, proof handling, sparse state, and empty hashes each live in their own module. Tests cover empty input, single-leaf trees, deterministic roots, odd leaf counts, and the distinction between hash functions.
Browse the library source to follow the tree and proof implementations.