Expand description
High-performance Merkle Tree and related data structures (Merkle Mountain Range, Sparse Merkle Tree).
This crate contains several high-performance Merkle Tree implementations and related data structures, many of which are a subset of each other.
These implementations can be an order of magnitude faster than traditional implementations by leveraging the ability of hash functions like BLAKE3 to hash multiple blocks at once with SIMD. Typical Merkle Tree crates only allow customizing a hash function of two leaves, which makes it impossible to benefit from the inherent strength of such hash functions.
Currently BalancedMerkleTree, UnbalancedMerkleTree, MerkleMountainRange and
SparseMerkleTree are available.
BalancedMerkleTree is an optimized special case of UnbalancedMerkleTree, which is in
turn an optimized version of MerkleMountainRange, and all 3 will return the same results for
identical inputs and hasher.
SparseMerkleTree is a special kind of Merkle Tree, usually of intractable size, where most
of the leaves are empty (missing). It will also produce the same root as other trees in case the
tree doesn’t have any empty leaves, though it is unlikely to happen in practice.
All trees are generic over MerkleHasher, which can hash many pairs of nodes at once and
defines the size of nodes. Hashers are created with Default when they don’t depend on the
number of leaves, otherwise with NewMerkleHasherForTreeSize, which is implemented for all
hashers that implement Default. Trees that don’t know the number of leaves upfront, like
MerkleMountainRange, only support hashers that implement Default.
blake3 module contains the BLAKE3 hasher and aliases of all trees that use it (requires
blake3 feature).
Does not require a standard library (no_std), most APIs are usable without an allocator, never
panics.
Modules§
- balanced
- blake3
- BLAKE3 hasher and aliases of Merkle Trees that use it
- mmr
- sparse
- Sparse Merkle Tree and related data structures.
- unbalanced
Traits§
- Merkle
Hasher - Hash function for inner nodes of Merkle Trees.
- NewMerkle
Hasher ForTree Size - Creates hashers for trees with a known number of leaves.