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`] are
7//! available. [`BalancedMerkleTree`] is an optimized special case of [`UnbalancedMerkleTree`],
8//! which is in turn an optimized version of [`MerkleMountainRange`] and all 3 will return the same
9//! results for identical inputs.
10//!
11//! [`BalancedMerkleTree`]: balanced::BalancedMerkleTree
12//! [`MerkleMountainRange`]: mmr::MerkleMountainRange
13//! [`UnbalancedMerkleTree`]: unbalanced::UnbalancedMerkleTree
14
15#![expect(incomplete_features, reason = "generic_const_exprs")]
16#![feature(
17    array_chunks,
18    generic_const_exprs,
19    iter_advance_by,
20    maybe_uninit_slice,
21    maybe_uninit_uninit_array_transpose,
22    ptr_as_ref_unchecked,
23    trusted_len
24)]
25#![no_std]
26
27// TODO: Consider domains-specific internal node separator and inclusion of tree size into hashing
28//  key
29pub mod balanced;
30pub mod mmr;
31pub mod unbalanced;
32
33#[cfg(feature = "alloc")]
34extern crate alloc;
35
36use ab_blake3::{KEY_LEN, OUT_LEN};
37
38/// Used as a key in keyed blake3 hash for inner nodes of Merkle Trees.
39///
40/// This value is a blake3 hash of as string `merkle-tree-inner-node`.
41pub const INNER_NODE_DOMAIN_SEPARATOR: [u8; KEY_LEN] =
42    ab_blake3::const_hash(b"merkle-tree-inner-node");
43
44/// Helper function to hash two nodes together using [`ab_blake3::single_block_keyed_hash()`] and
45/// [`INNER_NODE_DOMAIN_SEPARATOR`]
46#[inline(always)]
47#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
48pub fn hash_pair(left: &[u8; OUT_LEN], right: &[u8; OUT_LEN]) -> [u8; OUT_LEN] {
49    let mut pair = [0u8; OUT_LEN * 2];
50    pair[..OUT_LEN].copy_from_slice(left);
51    pair[OUT_LEN..].copy_from_slice(right);
52
53    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, &pair)
54        .expect("Exactly one block worth of data; qed")
55}
ab_merkle_tree/lib.rs

ab_merkle_tree/
lib.rs
