ab_merkle_tree/
lib.rs

1//! High-performance Merkle Tree and related data structures (Merkle Mountain Range, Sparse Merkle
2//! Tree).
3//!
4//! This crate contains several high-performance Merkle Tree implementations and related data
5//! structures, many of which are a subset of each other.
6//!
7//! These implementations can be an order of magnitude faster than traditional implementations by
8//! leveraging the ability of hash functions like BLAKE3 to hash multiple blocks at once with SIMD.
9//! Typical Merkle Tree crates only allow customizing a hash function of two leaves, which makes it
10//! impossible to benefit from the inherent strength of such hash functions.
11//!
12//! Currently [`BalancedMerkleTree`], [`UnbalancedMerkleTree`], [`MerkleMountainRange`] and
13//! [`SparseMerkleTree`] are available.
14//!
15//! [`BalancedMerkleTree`] is an optimized special case of [`UnbalancedMerkleTree`], which is in
16//! turn an optimized version of [`MerkleMountainRange`], and all 3 will return the same results for
17//! identical inputs and hasher.
18//!
19//! [`SparseMerkleTree`] is a special kind of Merkle Tree, usually of intractable size, where most
20//! of the leaves are empty (missing). It will also produce the same root as other trees in case the
21//! tree doesn't have any empty leaves, though it is unlikely to happen in practice.
22//!
23//! [`BalancedMerkleTree`]: balanced::BalancedMerkleTree
24//! [`MerkleMountainRange`]: mmr::MerkleMountainRange
25//! [`UnbalancedMerkleTree`]: unbalanced::UnbalancedMerkleTree
26//! [`SparseMerkleTree`]: sparse::SparseMerkleTree
27//!
28//! All trees are generic over [`MerkleHasher`], which can hash many pairs of nodes at once and
29//! defines the size of nodes. Hashers are created with [`Default`] when they don't depend on the
30//! number of leaves, otherwise with [`NewMerkleHasherForTreeSize`], which is implemented for all
31//! hashers that implement [`Default`]. Trees that don't know the number of leaves upfront, like
32//! [`MerkleMountainRange`], only support hashers that implement [`Default`].
33//!
34//! `blake3` module contains the BLAKE3 hasher and aliases of all trees that use it (requires
35//! `blake3` feature).
36//!
37//! Does not require a standard library (`no_std`), most APIs are usable without an allocator, never
38//! panics.
39
40#![expect(incomplete_features, reason = "generic_const_*")]
41#![feature(
42    const_block_items,
43    const_convert,
44    const_default,
45    const_trait_impl,
46    gca_const_items,
47    gca_macroless_args,
48    gca_min_const_items,
49    generic_const_items,
50    iter_advance_by,
51    maybe_uninit_uninit_array_transpose,
52    phantom_variance_markers,
53    trusted_len
54)]
55#![no_std]
56
57pub mod balanced;
58#[cfg(feature = "blake3")]
59pub mod blake3;
60pub mod mmr;
61pub mod sparse;
62pub mod unbalanced;
63
64#[cfg(feature = "alloc")]
65extern crate alloc;
66
67use core::mem;
68
69/// Hash function for inner nodes of Merkle Trees.
70///
71/// Hashing of many pairs at once is a part of the API, such that hash functions like BLAKE3 can use
72/// SIMD to hash multiple pairs in parallel.
73pub trait MerkleHasher {
74    /// Size of a node hash in bytes
75    const OUT_LEN: usize;
76
77    /// Hash a pair of nodes together
78    fn hash_pair(&self, pair: &[[u8; Self::OUT_LEN]; 2]) -> [u8; Self::OUT_LEN];
79
80    /// Similar to [`Self::hash_pair()`], but hashes multiple pairs at once.
81    ///
82    /// The default implementation hashes pairs one by one, hash functions that can do better
83    /// should override it. An override must return the same as [`Self::hash_pair()`] for each pair,
84    /// because trees mix both.
85    #[inline(always)]
86    fn hash_pairs<const NUM_PAIRS: usize>(
87        &self,
88        pairs: &[[[u8; Self::OUT_LEN]; 2]; NUM_PAIRS],
89    ) -> [[u8; Self::OUT_LEN]; NUM_PAIRS] {
90        pairs.each_ref().map(|pair| self.hash_pair(pair))
91    }
92
93    /// Root of an [`UnbalancedMerkleTree`] or [`MerkleMountainRange`] with a single leaf.
94    ///
95    /// The default implementation returns the leaf unchanged, which keeps a tree of trees the
96    /// same as a single larger tree. Hashers that depend on the tree size should hash the leaf
97    /// instead, otherwise the size isn't committed to when the tree has a single leaf and no inner
98    /// nodes.
99    ///
100    /// [`UnbalancedMerkleTree`]: unbalanced::UnbalancedMerkleTree
101    /// [`MerkleMountainRange`]: mmr::MerkleMountainRange
102    #[inline(always)]
103    fn hash_single_leaf(&self, leaf: &[u8; Self::OUT_LEN]) -> [u8; Self::OUT_LEN] {
104        *leaf
105    }
106}
107
108/// Creates hashers for trees with a known number of leaves.
109///
110/// A hasher either ignores the tree size, in which case it implements [`Default`] and gets this
111/// trait through the blanket implementation, or depends on it, in which case it implements this
112/// trait directly and must not implement [`Default`]. It can't be both: the two implementations
113/// would conflict.
114pub const trait NewMerkleHasherForTreeSize: Sized {
115    /// Create a hasher for a tree with `num_leaves` leaves
116    fn new_for_tree_size(num_leaves: u64) -> Self;
117}
118
119/// Hashers that implement [`Default`] ignore the tree size
120const impl<H> NewMerkleHasherForTreeSize for H
121where
122    H: [const] Default,
123{
124    #[inline(always)]
125    fn new_for_tree_size(_num_leaves: u64) -> Self {
126        H::default()
127    }
128}
129
130// TODO: Combine `NUM_PAIRS` and `NUM_LEAVES` into a single generic parameter once compiler is
131//  smart enough to deal with it
132/// Similar to [`MerkleHasher::hash_pairs()`], but takes pairs as a flat list of nodes.
133///
134/// # Panics
135/// Panics when `NUM_LEAVES != NUM_PAIRS * 2`.
136#[inline(always)]
137// TODO: Unlock on RISC-V, it started failing since https://github.com/nazar-pc/abundance/pull/551
138//  for unknown reason
139#[cfg_attr(
140    all(feature = "no-panic", not(target_arch = "riscv64")),
141    no_panic::no_panic
142)]
143fn hash_pairs<const NUM_PAIRS: usize, const NUM_LEAVES: usize, H>(
144    hasher: &H,
145    leaves: &[[u8; H::OUT_LEN]; NUM_LEAVES],
146) -> [[u8; H::OUT_LEN]; NUM_PAIRS]
147where
148    H: MerkleHasher,
149{
150    // This protects the invariant of the function
151    assert_eq!(NUM_LEAVES, NUM_PAIRS * 2);
152
153    // SAFETY: Same size (checked above) and alignment
154    let pairs = unsafe {
155        mem::transmute::<&[[u8; H::OUT_LEN]; NUM_LEAVES], &[[[u8; H::OUT_LEN]; 2]; NUM_PAIRS]>(
156            leaves,
157        )
158    };
159    hasher.hash_pairs(pairs)
160}
ab_merkle_tree/lib.rs

ab_merkle_tree/
lib.rs
