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    maybe_uninit_slice,
20    maybe_uninit_uninit_array_transpose,
21    ptr_as_ref_unchecked,
22    trusted_len
23)]
24#![no_std]
25
26// TODO: Consider domains-specific internal node separator and inclusion of tree size into hashing
27//  key
28pub mod balanced;
29pub mod mmr;
30pub mod unbalanced;
31
32#[cfg(feature = "alloc")]
33extern crate alloc;
34
35use ab_blake3::{KEY_LEN, OUT_LEN};
36
37/// Used as a key in keyed blake3 hash for inner nodes of Merkle Trees.
38///
39/// This value is a blake3 hash of as string `merkle-tree-inner-node`.
40// TODO: Replace with hashing once https://github.com/BLAKE3-team/BLAKE3/issues/440 is resolved
41pub const INNER_NODE_DOMAIN_SEPARATOR: [u8; KEY_LEN] = [
42    0x53, 0x11, 0x7d, 0x4d, 0xa8, 0x1a, 0x34, 0x35, 0x0b, 0x1a, 0x30, 0xd4, 0x28, 0x6d, 0x7e, 0x5a,
43    0x1e, 0xb0, 0xa2, 0x0f, 0x5e, 0x5e, 0x26, 0x94, 0x47, 0x4b, 0x4f, 0xbd, 0x86, 0xc3, 0xc0, 0x7e,
44];
45
46/// Helper function to hash two nodes together using [`ab_blake3::single_block_keyed_hash()`] and
47/// [`INNER_NODE_DOMAIN_SEPARATOR`]
48#[inline(always)]
49#[cfg_attr(feature = "no-panic", no_panic::no_panic)]
50pub fn hash_pair(left: &[u8; OUT_LEN], right: &[u8; OUT_LEN]) -> [u8; OUT_LEN] {
51    let mut pair = [0u8; OUT_LEN * 2];
52    pair[..OUT_LEN].copy_from_slice(left);
53    pair[OUT_LEN..].copy_from_slice(right);
54
55    ab_blake3::single_block_keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, &pair)
56        .expect("Exactly one block worth of data; qed")
57}
ab_merkle_tree/lib.rs

ab_merkle_tree/
lib.rs
