binius_hash/
blake3.rs

1// Copyright 2026 The Binius Developers
2
3//! Blake3 hash and compression functions for use in Merkle tree constructions.
4
5use digest::Output;
6
7use super::{
8	binary_merkle_tree::HashSuite,
9	blake3_portable::{PortableBlake3ParallelCompression, PortableBlake3ParallelDigest},
10	compress::CompressionFunction,
11};
12
13/// A two-to-one compression function that hashes the concatenation of its inputs with Blake3.
14#[derive(Debug, Clone, Default)]
15pub struct Blake3Compression;
16
17impl CompressionFunction<Output<blake3::Hasher>, 2> for Blake3Compression {
18	fn compress(&self, input: [Output<blake3::Hasher>; 2]) -> Output<blake3::Hasher> {
19		let mut hasher = blake3::Hasher::new();
20		hasher.update(input[0].as_slice());
21		hasher.update(input[1].as_slice());
22		(*hasher.finalize().as_bytes()).into()
23	}
24}
25
26/// Blake3 [`HashSuite`]: Blake3 leaves and a Blake3 compression function for inner nodes.
27///
28/// Both parallel compute paths use the portable auto-vectorized kernel, not the scalar loop:
29/// - Leaves within one 1024-byte chunk are hashed by the batch kernel.
30/// - Larger leaves fall back to the scalar adapter that walks the tree.
31/// - Every inner-node level folds its node pairs through the batched two-to-one compression.
32///
33/// The batch width is fixed at 16 lanes for both paths:
34/// - The throughput sweet spot on NEON in the portable-kernel benchmark.
35/// - The width the AVX2 / AVX-512 vectorizer fills.
36/// - 4 and 8 lanes both measure slower.
37#[derive(Debug, Clone, Default)]
38pub struct Blake3HashSuite;
39
40impl HashSuite for Blake3HashSuite {
41	type LeafHash = blake3::Hasher;
42	type Compression = Blake3Compression;
43	type ParLeafHash = PortableBlake3ParallelDigest<16>;
44	type ParCompression = PortableBlake3ParallelCompression<16>;
45}
46
47#[cfg(test)]
48mod tests {
49	use std::{iter::repeat_with, mem::MaybeUninit};
50
51	use binius_utils::rayon::iter::{IntoParallelRefIterator, ParallelIterator};
52	use rand::{RngExt, SeedableRng, rngs::StdRng};
53
54	use super::*;
55	use crate::{ParallelDigest, parallel_digest::ParallelDigestAdapter};
56
57	/// Checks that the compression function matches `blake3::hash` of the concatenated inputs.
58	#[test]
59	fn test_blake3_compression_matches_reference() {
60		let mut rng = StdRng::seed_from_u64(0);
61		let left: [u8; 32] = rng.random();
62		let right: [u8; 32] = rng.random();
63
64		let compressed = Blake3Compression.compress([left.into(), right.into()]);
65
66		let mut concatenated = [0u8; 64];
67		concatenated[..32].copy_from_slice(&left);
68		concatenated[32..].copy_from_slice(&right);
69		let expected = blake3::hash(&concatenated);
70
71		assert_eq!(compressed.as_slice(), expected.as_bytes());
72	}
73
74	/// Checks that the parallel leaf digest matches `blake3::hash` over the serialized leaf bytes.
75	#[test]
76	fn test_parallel_blake3_matches_serial() {
77		let mut rng = StdRng::seed_from_u64(0);
78		let n_leaves = 50;
79		// `u128` serializes to 16 little-endian bytes.
80		let leaves: Vec<Vec<u128>> = (0..n_leaves)
81			.map(|_| (0..4).map(|_| rng.random::<u128>()).collect())
82			.collect();
83
84		let digest = <ParallelDigestAdapter<blake3::Hasher> as ParallelDigest>::new();
85		let mut results = repeat_with(MaybeUninit::<Output<blake3::Hasher>>::uninit)
86			.take(n_leaves)
87			.collect::<Vec<_>>();
88		digest.digest(leaves.par_iter().map(|leaf| leaf.iter().copied()), &mut results);
89
90		for (result, leaf) in results.into_iter().zip(&leaves) {
91			let mut bytes = Vec::new();
92			for &item in leaf {
93				bytes.extend_from_slice(&item.to_le_bytes());
94			}
95			let expected = blake3::hash(&bytes);
96			assert_eq!(unsafe { result.assume_init() }.as_slice(), expected.as_bytes());
97		}
98	}
99
100	#[test]
101	fn test_portable_leaf_hash_matches_scalar_reference() {
102		// The suite's parallel leaf path is the portable vectorized kernel.
103		//
104		// Pin it equal to the scalar adapter and to `blake3::hash` across the routing boundary.
105		let mut rng = StdRng::seed_from_u64(1);
106		let n_leaves = 50;
107
108		// Leaves are `u8` items (BYTE_SIZE = 1), so `leaf_len` bytes == `leaf_len` items.
109		let mut check = |leaf_len: usize| {
110			let leaves: Vec<Vec<u8>> = (0..n_leaves)
111				.map(|_| (0..leaf_len).map(|_| rng.random::<u8>()).collect())
112				.collect();
113
114			// The scalar adapter that walks the Blake3 tree — the reference path.
115			let mut scalar = repeat_with(MaybeUninit::<Output<blake3::Hasher>>::uninit)
116				.take(n_leaves)
117				.collect::<Vec<_>>();
118			ParallelDigestAdapter::<blake3::Hasher>::default().digest_with_const_len(
119				leaf_len,
120				leaves.par_iter().map(|leaf| leaf.iter().copied()),
121				&mut scalar,
122			);
123
124			// The suite's parallel leaf path — the portable batch kernel.
125			let mut portable = repeat_with(MaybeUninit::<Output<blake3::Hasher>>::uninit)
126				.take(n_leaves)
127				.collect::<Vec<_>>();
128			<Blake3HashSuite as HashSuite>::ParLeafHash::default().digest_with_const_len(
129				leaf_len,
130				leaves.par_iter().map(|leaf| leaf.iter().copied()),
131				&mut portable,
132			);
133
134			// Invariant: both reproduce `blake3::hash`, so their leaf digests match.
135			for ((s, p), leaf) in scalar.into_iter().zip(portable).zip(&leaves) {
136				let expected = blake3::hash(leaf);
137				let (s, p) = unsafe { (s.assume_init(), p.assume_init()) };
138				assert_eq!(s.as_slice(), expected.as_bytes(), "scalar, leaf_len {leaf_len}");
139				assert_eq!(p.as_slice(), expected.as_bytes(), "portable, leaf_len {leaf_len}");
140			}
141		};
142
143		// Straddle the 1024-byte routing boundary:
144		// - 0, 1, 63, 100, 1000, 1024 : within one chunk -> portable batch route.
145		// - 1025, 4096                : multi-chunk       -> scalar adapter fallback.
146		for leaf_len in [0, 1, 63, 100, 1000, 1024, 1025, 4096] {
147			check(leaf_len);
148		}
149	}
150}
binius_hash/blake3.rs

binius_hash/
blake3.rs
