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

ab_merkle_tree/
lib.rs
