ab_merkle_tree/
lib.rs

1//! Merkle Tree and related data structures.
2//!
3//! This crate contains several Merkle Tree implementations and related data structures, many of
4//! which are a subset of each other.
5//!
6//! Currently [`BalancedMerkleTree`], [`UnbalancedMerkleTree`] and [`MerkleMountainRange`] and
7//! [`SparseMerkleTree`] are available.
8//!
9//! [`BalancedMerkleTree`] is an optimized special case of [`UnbalancedMerkleTree`], which is in
10//! turn an optimized version of [`MerkleMountainRange`] and all 3 will return the same results for
11//! identical inputs.
12//!
13//! [`SparseMerkleTree`] is a special kind of Merkle Tree, usually of untractable size, where most
14//! of the leaves are empty (missing). It will also produce the same root as other trees in case the
15//! tree doesn't have any empty leaves, though it is unlikely to happen in practice.
16//!
17//!
18//! [`BalancedMerkleTree`]: balanced::BalancedMerkleTree
19//! [`MerkleMountainRange`]: mmr::MerkleMountainRange
20//! [`UnbalancedMerkleTree`]: unbalanced::UnbalancedMerkleTree
21//! [`SparseMerkleTree`]: sparse::SparseMerkleTree
22
23#![expect(incomplete_features, reason = "generic_const_exprs")]
24#![feature(
25    generic_const_exprs,
26    iter_advance_by,
27    maybe_uninit_uninit_array_transpose,
28    ptr_as_ref_unchecked,
29    trusted_len
30)]
31#![no_std]
32
33// TODO: Consider domains-specific internal node separator and inclusion of tree size into hashing
34//  key
35pub mod balanced;
36pub mod mmr;
37pub mod sparse;
38pub mod unbalanced;
39
40#[cfg(feature = "alloc")]
41extern crate alloc;
42
43use ab_blake3::{BLOCK_LEN, KEY_LEN, OUT_LEN};
44use core::mem;
45
46/// Used as a key in keyed blake3 hash for inner nodes of Merkle Trees.
47///
48/// This value is a blake3 hash of as string `merkle-tree-inner-node`.
49pub const INNER_NODE_DOMAIN_SEPARATOR: [u8; KEY_LEN] =
50    ab_blake3::const_hash(b"merkle-tree-inner-node");
51
52/// Helper function to hash two nodes together using [`ab_blake3::single_block_keyed_hash()`] and
53/// [`INNER_NODE_DOMAIN_SEPARATOR`]
54#[inline(always)]
55#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
56pub fn hash_pair(left: &[u8; OUT_LEN], right: &[u8; OUT_LEN]) -> [u8; OUT_LEN] {
57    let mut pair = [0u8; OUT_LEN * 2];
58    pair[..OUT_LEN].copy_from_slice(left);
59    pair[OUT_LEN..].copy_from_slice(right);
60
61    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, &pair)
62        .expect("Exactly one block worth of data; qed")
63}
64
65/// Similar to [`hash_pair()`] but already has left and right nodes concatenated
66#[inline(always)]
67#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
68pub fn hash_pair_block(pair: &[u8; BLOCK_LEN]) -> [u8; OUT_LEN] {
69    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, pair)
70        .expect("Exactly one block worth of data; qed")
71}
72
73// TODO: Combine `NUM_BLOCKS` and `NUM_LEAVES` into a single generic parameter once compiler is
74//  smart enough to deal with it
75/// Similar to [`hash_pair()`], but hashes multiple pairs at once efficiently.
76///
77/// # Panics
78/// Panics when `NUM_LEAVES != NUM_BLOCKS * BLOCK_LEN / OUT_LEN`.
79#[inline(always)]
80#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
81pub fn hash_pairs<const NUM_BLOCKS: usize, const NUM_LEAVES: usize>(
82    pairs: &[[u8; OUT_LEN]; NUM_LEAVES],
83) -> [[u8; OUT_LEN]; NUM_BLOCKS] {
84    // This protects the invariant of the function
85    assert_eq!(NUM_LEAVES, NUM_BLOCKS * BLOCK_LEN / OUT_LEN);
86
87    // SAFETY: Same size (checked above) and alignment
88    let pairs = unsafe {
89        mem::transmute::<&[[u8; OUT_LEN]; NUM_LEAVES], &[[u8; BLOCK_LEN]; NUM_BLOCKS]>(pairs)
90    };
91    let mut hashes = [[0; OUT_LEN]; NUM_BLOCKS];
92    ab_blake3::single_block_keyed_hash_many_exact(&INNER_NODE_DOMAIN_SEPARATOR, pairs, &mut hashes);
93    hashes
94}
ab_merkle_tree/lib.rs

ab_merkle_tree/
lib.rs
