binius_hash/
sha256.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! SHA-256 leaf hash and two-to-one compression for Merkle tree constructions.
5//!
6//! One block compression per node, straight through the reference implementation.
7//! The batched kernels a prover wants live in the prover-side crate, not here.
8
9use bytemuck::{bytes_of_mut, must_cast};
10use digest::Digest;
11use sha2::{Sha256, block_api::compress256, digest::Output};
12
13use crate::{compress::CompressionFunction, suite::HashSuite};
14
15/// Bytes in one SHA-256 message block.
16const BLOCK_LEN: usize = 64;
17
18/// Bytes in one SHA-256 digest.
19const DIGEST_LEN: usize = 32;
20
21/// A two-to-one compression function for SHA-256 digests.
22///
23/// One raw block compression of `left || right`, from a domain-separated initial state.
24/// This is not a full hash of the pair: there is no padding block and no length suffix.
25#[derive(Debug, Clone)]
26pub struct Sha256Compression {
27	/// Domain-separating initial state, standing in for the SHA-256 IV.
28	initial_state: [u32; 8],
29}
30
31impl Default for Sha256Compression {
32	fn default() -> Self {
33		let initial_state_bytes = Sha256::digest(b"BINIUS SHA-256 COMPRESS");
34		let mut initial_state = [0u32; 8];
35		bytes_of_mut(&mut initial_state).copy_from_slice(&initial_state_bytes);
36		Self { initial_state }
37	}
38}
39
40impl Sha256Compression {
41	/// The domain-separated state every compression starts from.
42	///
43	/// A batched implementation has to seed its lanes with exactly these words to agree with
44	/// this one, so the state is part of the public contract rather than an internal detail.
45	pub const fn initial_state(&self) -> &[u32; 8] {
46		&self.initial_state
47	}
48}
49
50impl CompressionFunction<Output<Sha256>, 2> for Sha256Compression {
51	fn compress(&self, input: [Output<Sha256>; 2]) -> Output<Sha256> {
52		// The two 32-byte children fill one 64-byte block exactly.
53		let mut block = [0u8; BLOCK_LEN];
54		block[..DIGEST_LEN].copy_from_slice(input[0].as_slice());
55		block[DIGEST_LEN..].copy_from_slice(input[1].as_slice());
56
57		let mut state = self.initial_state;
58		compress256(&mut state, std::slice::from_ref(&block));
59
60		// Native word order, not the big-endian digest order.
61		// The output only has to be a fixed 32-byte function of the pair.
62		must_cast::<[u32; 8], [u8; DIGEST_LEN]>(state).into()
63	}
64}
65
66/// SHA-256 leaves and a SHA-256 compression function for inner nodes.
67#[derive(Debug, Clone, Default)]
68pub struct Sha256HashSuite;
69
70impl HashSuite for Sha256HashSuite {
71	type LeafHash = Sha256;
72	type Compression = Sha256Compression;
73}
74
75#[cfg(test)]
76mod tests {
77	use rand::{Rng, SeedableRng, rngs::StdRng};
78
79	use super::*;
80
81	#[test]
82	fn test_compression_matches_known_answer() {
83		// The compression emits its state in native word order, not the big-endian digest order.
84		// A Merkle path committed under one order does not verify under the other, so the
85		// convention is pinned here by a vector computed from FIPS 180-4 directly.
86		//
87		// Left child all zero, right child the bytes 0..32, under the domain-separated state.
88		let left: Output<Sha256> = [0u8; DIGEST_LEN].into();
89		let right: Output<Sha256> = std::array::from_fn::<u8, DIGEST_LEN, _>(|i| i as u8).into();
90
91		let got = Sha256Compression::default().compress([left, right]);
92
93		let want = "4731c4e3a3190d19dace68db5752af1b4ecf26305e75e85db86217662bbeff74";
94		let got_hex: String = got.iter().map(|b| format!("{b:02x}")).collect();
95		assert_eq!(got_hex, want, "the compression byte order changed");
96	}
97
98	#[test]
99	fn test_compression_is_one_block_from_the_domain_state() {
100		let mut rng = StdRng::seed_from_u64(0);
101		let compression = Sha256Compression::default();
102
103		// Invariant: the compression is one raw block of `left || right` from the fixed state.
104		for _ in 0..64 {
105			let mut left = Output::<Sha256>::default();
106			let mut right = Output::<Sha256>::default();
107			rng.fill_bytes(&mut left);
108			rng.fill_bytes(&mut right);
109
110			let got = compression.compress([left, right]);
111
112			let mut block = [0u8; BLOCK_LEN];
113			block[..DIGEST_LEN].copy_from_slice(&left);
114			block[DIGEST_LEN..].copy_from_slice(&right);
115			let mut want = *compression.initial_state();
116			compress256(&mut want, std::slice::from_ref(&block));
117
118			assert_eq!(got.as_slice(), must_cast::<[u32; 8], [u8; DIGEST_LEN]>(want));
119		}
120	}
121}
binius_hash/sha256.rs

binius_hash/
sha256.rs
