ab_merkle_tree/
lib.rs

1//! Merkle Tree implementations.
2//!
3//! This crate contains several Merkle Tree implementations that are a subset of each other.
4//!
5//! Currently [`BalancedHashedMerkleTree`] and [`UnbalancedHashedMerkleTree`] are available, with
6//! [`BalancedHashedMerkleTree`] being an optimized special case of [`UnbalancedHashedMerkleTree`]
7//! and both return the same results for identical inputs.
8//!
9//! [`BalancedHashedMerkleTree`]: balanced_hashed::BalancedHashedMerkleTree
10//! [`UnbalancedHashedMerkleTree`]: unbalanced_hashed::UnbalancedHashedMerkleTree
11
12#![expect(incomplete_features, reason = "generic_const_exprs")]
13#![feature(
14    array_chunks,
15    generic_arg_infer,
16    generic_const_exprs,
17    maybe_uninit_slice,
18    maybe_uninit_uninit_array_transpose,
19    ptr_as_ref_unchecked,
20    trusted_len
21)]
22#![no_std]
23
24// TODO: Consider domains-specific internal node separator and inclusion of tree size into hashing
25//  key
26pub mod balanced_hashed;
27pub mod unbalanced_hashed;
28
29#[cfg(feature = "alloc")]
30extern crate alloc;
31
32use blake3::{KEY_LEN, OUT_LEN};
33
34/// Used as a key in keyed blake3 hash for inner nodes of Merkle Trees.
35///
36/// This value is a blake3 hash of as string `merkle-tree-inner-node`.
37// TODO: Replace with hashing once https://github.com/BLAKE3-team/BLAKE3/issues/440 is resolved
38pub const INNER_NODE_DOMAIN_SEPARATOR: [u8; KEY_LEN] = [
39    0x53, 0x11, 0x7d, 0x4d, 0xa8, 0x1a, 0x34, 0x35, 0x0b, 0x1a, 0x30, 0xd4, 0x28, 0x6d, 0x7e, 0x5a,
40    0x1e, 0xb0, 0xa2, 0x0f, 0x5e, 0x5e, 0x26, 0x94, 0x47, 0x4b, 0x4f, 0xbd, 0x86, 0xc3, 0xc0, 0x7e,
41];
42
43/// Helper function to hash two nodes together using [`blake3::keyed_hash()`] and
44/// [`INNER_NODE_DOMAIN_SEPARATOR`]
45#[inline(always)]
46pub fn hash_pair(left: &[u8; OUT_LEN], right: &[u8; OUT_LEN]) -> [u8; OUT_LEN] {
47    let mut pair = [0u8; OUT_LEN * 2];
48    pair[..OUT_LEN].copy_from_slice(left);
49    pair[OUT_LEN..].copy_from_slice(right);
50
51    blake3::keyed_hash(&INNER_NODE_DOMAIN_SEPARATOR, &pair).into()
52}
ab_merkle_tree/lib.rs

ab_merkle_tree/
lib.rs
