Crate ab_merkle_tree 

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 BLAKE3 hash function to hash multiple blocks at once with SIMD. Traditionally, most Merkle Tree implementations are generic over the hash function with API that hashes two leaves at a time, which makes it impossible to benefit from the inherent strength of BLAKE3 hash function.

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.

SparseMerkleTree is a special kind of Merkle Tree, usually of untractable 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.

Does not require a standard library (no_std), most APIs are usable without an allocator.

Modules

balanced

mmr

sparse

Sparse Merkle Tree and related data structures.

unbalanced

Constants

INNER_NODE_DOMAIN_SEPARATOR

Used as a key in keyed blake3 hash for inner nodes of Merkle Trees.

Functions

hash_pair

Helper function to hash two nodes together using [ab_blake3::single_block_keyed_hash()] and INNER_NODE_DOMAIN_SEPARATOR

hash_pair_block

Similar to hash_pair() but already has left and right nodes concatenated

hash_pairs

Similar to hash_pair(), but hashes multiple pairs at once efficiently.