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

ab_merkle_tree/
lib.rs
