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 untractable 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    maybe_uninit_uninit_array_transpose,
41    min_generic_const_args,
42    trusted_len
43)]
44#![no_std]
45
46// TODO: Consider domains-specific internal node separator and inclusion of tree size into hashing
47//  key
48pub mod balanced;
49pub mod mmr;
50pub mod sparse;
51pub mod unbalanced;
52
53#[cfg(feature = "alloc")]
54extern crate alloc;
55
56use ab_blake3::{BLOCK_LEN, KEY_LEN, OUT_LEN};
57use core::mem;
58
59/// Used as a key in keyed blake3 hash for inner nodes of Merkle Trees.
60///
61/// This value is a blake3 hash of a string `merkle-tree-inner-node`.
62pub const INNER_NODE_DOMAIN_SEPARATOR: [u8; KEY_LEN] =
63    ab_blake3::const_hash(b"merkle-tree-inner-node");
64
65/// Helper function to hash two nodes together using [`ab_blake3::single_block_keyed_hash()`] and
66/// [`INNER_NODE_DOMAIN_SEPARATOR`]
67#[inline(always)]
68#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
69pub fn hash_pair(left: &[u8; OUT_LEN], right: &[u8; OUT_LEN]) -> [u8; OUT_LEN] {
70    let mut pair = [0u8; OUT_LEN * 2];
71    pair[..OUT_LEN].copy_from_slice(left);
72    pair[OUT_LEN..].copy_from_slice(right);
73
74    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, &pair)
75        .expect("Exactly one block worth of data; qed")
76}
77
78/// Similar to [`hash_pair()`] but already has left and right nodes concatenated
79#[inline(always)]
80#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
81pub fn hash_pair_block(pair: &[u8; BLOCK_LEN]) -> [u8; OUT_LEN] {
82    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, pair)
83        .expect("Exactly one block worth of data; qed")
84}
85
86// TODO: Combine `NUM_BLOCKS` and `NUM_LEAVES` into a single generic parameter once compiler is
87//  smart enough to deal with it
88/// Similar to [`hash_pair()`], but hashes multiple pairs at once efficiently.
89///
90/// # Panics
91/// Panics when `NUM_LEAVES != NUM_BLOCKS * BLOCK_LEN / OUT_LEN`.
92#[inline(always)]
93// TODO: Unlock on RISC-V, it started failing since https://github.com/nazar-pc/abundance/pull/551
94//  for unknown reason
95#[cfg_attr(
96    all(feature = "no-panic", not(target_arch = "riscv64")),
97    no_panic::no_panic
98)]
99fn hash_pairs<const NUM_BLOCKS: usize, const NUM_LEAVES: usize>(
100    pairs: &[[u8; OUT_LEN]; NUM_LEAVES],
101) -> [[u8; OUT_LEN]; NUM_BLOCKS] {
102    // This protects the invariant of the function
103    assert_eq!(NUM_LEAVES, NUM_BLOCKS * BLOCK_LEN / OUT_LEN);
104
105    // SAFETY: Same size (checked above) and alignment
106    let pairs = unsafe {
107        mem::transmute::<&[[u8; OUT_LEN]; NUM_LEAVES], &[[u8; BLOCK_LEN]; NUM_BLOCKS]>(pairs)
108    };
109    let mut hashes = [[0; OUT_LEN]; NUM_BLOCKS];
110    ab_blake3::single_block_keyed_hash_many_exact(&INNER_NODE_DOMAIN_SEPARATOR, pairs, &mut hashes);
111    hashes
112}
ab_merkle_tree/lib.rs

ab_merkle_tree/
lib.rs
