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 BLAKE3 hash function to hash multiple blocks at once with SIMD.
9//! Traditionally, most Merkle Tree implementations are generic over the hash function with API that
10//! hashes two leaves at a time, which makes it impossible to benefit from the inherent strength of
11//! BLAKE3 hash function.
12//!
13//! Currently [`BalancedMerkleTree`], [`UnbalancedMerkleTree`], [`MerkleMountainRange`] and
14//! [`SparseMerkleTree`] are available.
15//!
16//! [`BalancedMerkleTree`] is an optimized special case of [`UnbalancedMerkleTree`], which is in
17//! turn an optimized version of [`MerkleMountainRange`], and all 3 will return the same results for
18//! identical inputs.
19//!
20//! [`SparseMerkleTree`] is a special kind of Merkle Tree, usually of intractable size, where most
21//! of the leaves are empty (missing). It will also produce the same root as other trees in case the
22//! tree doesn't have any empty leaves, though it is unlikely to happen in practice.
23//!
24//! [`BalancedMerkleTree`]: balanced::BalancedMerkleTree
25//! [`MerkleMountainRange`]: mmr::MerkleMountainRange
26//! [`UnbalancedMerkleTree`]: unbalanced::UnbalancedMerkleTree
27//! [`SparseMerkleTree`]: sparse::SparseMerkleTree
28//!
29//! Does not require a standard library (`no_std`), most APIs are usable without an allocator, never
30//! panics.
31
32#![expect(incomplete_features, reason = "generic_const_*")]
33#![feature(
34    const_block_items,
35    const_convert,
36    const_trait_impl,
37    generic_const_args,
38    generic_const_items,
39    iter_advance_by,
40    macroless_generic_const_args,
41    maybe_uninit_uninit_array_transpose,
42    min_generic_const_args,
43    trusted_len
44)]
45#![no_std]
46
47// TODO: Consider domains-specific internal node separator and inclusion of tree size into hashing
48//  key
49pub mod balanced;
50pub mod mmr;
51pub mod sparse;
52pub mod unbalanced;
53
54#[cfg(feature = "alloc")]
55extern crate alloc;
56
57use ab_blake3::{BLOCK_LEN, KEY_LEN, OUT_LEN};
58use core::mem;
59
60/// Used as a key in keyed blake3 hash for inner nodes of Merkle Trees.
61///
62/// This value is a blake3 hash of a string `merkle-tree-inner-node`.
63pub const INNER_NODE_DOMAIN_SEPARATOR: [u8; KEY_LEN] =
64    ab_blake3::const_hash(b"merkle-tree-inner-node");
65
66/// Helper function to hash two nodes together using [`ab_blake3::single_block_keyed_hash()`] and
67/// [`INNER_NODE_DOMAIN_SEPARATOR`]
68#[inline(always)]
69#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
70pub fn hash_pair(left: &[u8; OUT_LEN], right: &[u8; OUT_LEN]) -> [u8; OUT_LEN] {
71    let mut pair = [0u8; OUT_LEN * 2];
72    pair[..OUT_LEN].copy_from_slice(left);
73    pair[OUT_LEN..].copy_from_slice(right);
74
75    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, &pair)
76        .expect("Exactly one block worth of data; qed")
77}
78
79/// Similar to [`hash_pair()`] but already has left and right nodes concatenated
80#[inline(always)]
81#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
82pub fn hash_pair_block(pair: &[u8; BLOCK_LEN]) -> [u8; OUT_LEN] {
83    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, pair)
84        .expect("Exactly one block worth of data; qed")
85}
86
87// TODO: Combine `NUM_BLOCKS` and `NUM_LEAVES` into a single generic parameter once compiler is
88//  smart enough to deal with it
89/// Similar to [`hash_pair()`], but hashes multiple pairs at once efficiently.
90///
91/// # Panics
92/// Panics when `NUM_LEAVES != NUM_BLOCKS * BLOCK_LEN / OUT_LEN`.
93#[inline(always)]
94// TODO: Unlock on RISC-V, it started failing since https://github.com/nazar-pc/abundance/pull/551
95//  for unknown reason
96#[cfg_attr(
97    all(feature = "no-panic", not(target_arch = "riscv64")),
98    no_panic::no_panic
99)]
100fn hash_pairs<const NUM_BLOCKS: usize, const NUM_LEAVES: usize>(
101    pairs: &[[u8; OUT_LEN]; NUM_LEAVES],
102) -> [[u8; OUT_LEN]; NUM_BLOCKS] {
103    // This protects the invariant of the function
104    assert_eq!(NUM_LEAVES, NUM_BLOCKS * BLOCK_LEN / OUT_LEN);
105
106    // SAFETY: Same size (checked above) and alignment
107    let pairs = unsafe {
108        mem::transmute::<&[[u8; OUT_LEN]; NUM_LEAVES], &[[u8; BLOCK_LEN]; NUM_BLOCKS]>(pairs)
109    };
110    let mut hashes = [[0; OUT_LEN]; NUM_BLOCKS];
111    ab_blake3::single_block_keyed_hash_many_exact(&INNER_NODE_DOMAIN_SEPARATOR, pairs, &mut hashes);
112    hashes
113}
ab_merkle_tree/lib.rs

ab_merkle_tree/
lib.rs
