Skip to main content

binius_examples/circuits/
independent_hashes.rs

1// Copyright 2026 The Binius Developers
2// Copyright 2025 Irreducible Inc.
3
4//! Batches of independent hash primitive evaluations.
5//!
6//! Each circuit proves `n` independent compression-function or permutation evaluations. The
7//! primitive outputs are exposed as public inout wires and asserted equal to the gadget
8//! outputs: dead-code elimination keeps only gates that feed assertions or public IO, so
9//! without observing the outputs the entire hash computation would be pruned and the
10//! benchmarks would measure an empty circuit.
11
12use anyhow::{Result, ensure};
13use binius_circuits::{
14	blake3::{blake3_compress, ref_compress},
15	keccak::permutation::keccak_f1600,
16	sha256::{State as Sha256State, populate_message_block, sha256_compress},
17	util::clear_high_bits,
18};
19use binius_core::word::Word;
20use binius_frontend::{CircuitBuilder, Wire, WitnessFiller};
21use clap::Args;
22use rand::prelude::*;
23
24use super::utils::DEFAULT_RANDOM_SEED;
25use crate::ExampleCircuit;
26
27/// Default number of logical compression/permutation primitives for CLI use.
28///
29/// Benchmark harnesses override this with environment variables.
30pub const DEFAULT_NUM_PRIMITIVES: usize = 16;
31
32/// SHA-256 initial hash value (FIPS 180-4), matching [`Sha256State::iv`].
33const SHA256_IV: [u32; 8] = [
34	0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
35];
36
37#[derive(Debug, Clone, Args)]
38pub struct PrimitiveParams {
39	/// Number of independent primitive evaluations.
40	#[arg(short = 'n', long, default_value_t = DEFAULT_NUM_PRIMITIVES)]
41	pub num_primitives: usize,
42}
43
44#[derive(Debug, Clone, Args)]
45pub struct Instance {
46	/// RNG seed for deterministic witness values.
47	#[arg(long)]
48	pub seed: Option<u64>,
49}
50
51/// Independent SHA-256 compression evaluations.
52///
53/// Each circuit component runs `compress(IV, m_i)` for a fresh 64-byte message block and
54/// asserts the resulting digest against a public inout copy.
55pub struct IndependentSha256Compressions {
56	compressions: Vec<Sha256Compression>,
57}
58
59struct Sha256Compression {
60	block: [Wire; 16],
61	digest: [Wire; 8],
62}
63
64impl ExampleCircuit for IndependentSha256Compressions {
65	type Params = PrimitiveParams;
66	type Instance = Instance;
67
68	fn build(params: PrimitiveParams, builder: &mut CircuitBuilder) -> Result<Self> {
69		ensure!(params.num_primitives > 0, "num_primitives must be positive");
70
71		let compressions = (0..params.num_primitives)
72			.map(|i| {
73				let block = std::array::from_fn(|_| builder.add_witness());
74				let out = sha256_compress(builder, Sha256State::iv(builder), block);
75				let digest = std::array::from_fn(|_| builder.add_inout());
76				// The raw 64-bit equality holds because honest witness population
77				// zero-extends every 32-bit input and the gadget preserves empty high
78				// halves.
79				builder.assert_eq_v(format!("sha256_compression_out[{i}]"), out.0, digest);
80				Sha256Compression { block, digest }
81			})
82			.collect();
83
84		Ok(Self { compressions })
85	}
86
87	fn populate_witness(&self, instance: Instance, w: &mut WitnessFiller<'_>) -> Result<()> {
88		let mut rng = StdRng::seed_from_u64(instance.seed.unwrap_or(DEFAULT_RANDOM_SEED));
89		for compression in &self.compressions {
90			let block_bytes = next_block(&mut rng);
91			populate_message_block(w, &compression.block, block_bytes);
92
93			let mut state = SHA256_IV;
94			sha2::block_api::compress256(&mut state, &[block_bytes]);
95			for (wire, value) in compression.digest.iter().zip(state) {
96				w[*wire] = Word(value as u64);
97			}
98		}
99		Ok(())
100	}
101
102	fn param_summary(params: &Self::Params) -> Option<String> {
103		Some(format!("{}c", params.num_primitives))
104	}
105}
106
107/// Independent BLAKE3 compression evaluations.
108///
109/// Each circuit component runs one independent BLAKE3 compression function and asserts the
110/// resulting chaining value against a public inout copy.
111pub struct IndependentBlake3Compressions {
112	compressions: Vec<Blake3Compression>,
113}
114
115struct Blake3Compression {
116	cv: [Wire; 8],
117	block: [Wire; 16],
118	counter: Wire,
119	block_len: Wire,
120	flags: Wire,
121	out_cv: [Wire; 8],
122}
123
124impl ExampleCircuit for IndependentBlake3Compressions {
125	type Params = PrimitiveParams;
126	type Instance = Instance;
127
128	fn build(params: PrimitiveParams, builder: &mut CircuitBuilder) -> Result<Self> {
129		ensure!(params.num_primitives > 0, "num_primitives must be positive");
130
131		let compressions = (0..params.num_primitives)
132			.map(|i| {
133				let cv = std::array::from_fn(|_| builder.add_witness());
134				let block = std::array::from_fn(|_| builder.add_witness());
135				let counter = builder.add_witness();
136				let block_len = builder.add_witness();
137				let flags = builder.add_witness();
138				let out = blake3_compress(builder, cv, block, counter, block_len, flags);
139				// Unlike SHA-256, this gadget splits its rounds across the two 32-bit lanes and
140				// leaves the discarded one in each word's high half, so the comparison masks it.
141				let out = out.map(|word| clear_high_bits(builder, word, 32));
142				let out_cv = std::array::from_fn(|_| builder.add_inout());
143				builder.assert_eq_v(format!("blake3_compression_out[{i}]"), out, out_cv);
144				Blake3Compression {
145					cv,
146					block,
147					counter,
148					block_len,
149					flags,
150					out_cv,
151				}
152			})
153			.collect();
154
155		Ok(Self { compressions })
156	}
157
158	fn populate_witness(&self, instance: Instance, w: &mut WitnessFiller<'_>) -> Result<()> {
159		let mut rng = StdRng::seed_from_u64(instance.seed.unwrap_or(DEFAULT_RANDOM_SEED));
160		for compression in &self.compressions {
161			let cv: [u32; 8] = std::array::from_fn(|_| rng.next_u32());
162			let block: [u32; 16] = std::array::from_fn(|_| rng.next_u32());
163			let counter = rng.next_u64();
164			let block_len = rng.next_u32() % 65;
165			let flags = rng.next_u32();
166
167			for (wire, value) in compression.cv.iter().zip(cv) {
168				w[*wire] = Word(value as u64);
169			}
170			for (wire, value) in compression.block.iter().zip(block) {
171				w[*wire] = Word(value as u64);
172			}
173			w[compression.counter] = Word(counter);
174			w[compression.block_len] = Word(block_len as u64);
175			w[compression.flags] = Word(flags as u64);
176
177			let expected = ref_compress(&cv, &block, counter, block_len, flags);
178			for (wire, value) in compression.out_cv.iter().zip(expected) {
179				w[*wire] = Word(value as u64);
180			}
181		}
182		Ok(())
183	}
184
185	fn param_summary(params: &Self::Params) -> Option<String> {
186		Some(format!("{}c", params.num_primitives))
187	}
188}
189
190/// Independent Keccak-f\[1600\] permutation evaluations.
191///
192/// Each circuit component runs one independent permutation and asserts the output state
193/// against a public inout copy.
194pub struct IndependentKeccakPermutations {
195	permutations: Vec<KeccakPermutation>,
196}
197
198struct KeccakPermutation {
199	input: [Wire; 25],
200	output: [Wire; 25],
201}
202
203impl ExampleCircuit for IndependentKeccakPermutations {
204	type Params = PrimitiveParams;
205	type Instance = Instance;
206
207	fn build(params: PrimitiveParams, builder: &mut CircuitBuilder) -> Result<Self> {
208		ensure!(params.num_primitives > 0, "num_primitives must be positive");
209
210		let permutations = (0..params.num_primitives)
211			.map(|i| {
212				let input: [Wire; 25] = std::array::from_fn(|_| builder.add_witness());
213				let mut output = input;
214				keccak_f1600(builder, &mut output);
215				let expected = std::array::from_fn(|_| builder.add_inout());
216				builder.assert_eq_v(format!("keccak_permutation_out[{i}]"), output, expected);
217				KeccakPermutation {
218					input,
219					output: expected,
220				}
221			})
222			.collect();
223
224		Ok(Self { permutations })
225	}
226
227	fn populate_witness(&self, instance: Instance, w: &mut WitnessFiller<'_>) -> Result<()> {
228		let mut rng = StdRng::seed_from_u64(instance.seed.unwrap_or(DEFAULT_RANDOM_SEED));
229		for permutation in &self.permutations {
230			let state: [u64; 25] = std::array::from_fn(|_| rng.next_u64());
231			for (wire, value) in permutation.input.iter().zip(state) {
232				w[*wire] = Word(value);
233			}
234
235			let mut expected = state;
236			keccak::Keccak::new().with_f1600(|f1600| f1600(&mut expected));
237			for (wire, value) in permutation.output.iter().zip(expected) {
238				w[*wire] = Word(value);
239			}
240		}
241		Ok(())
242	}
243
244	fn param_summary(params: &Self::Params) -> Option<String> {
245		Some(format!("{}p", params.num_primitives))
246	}
247}
248
249fn next_block(rng: &mut StdRng) -> [u8; 64] {
250	let mut block = [0; 64];
251	let (chunks, _) = block.as_chunks_mut::<8>();
252	for chunk in chunks {
253		chunk.copy_from_slice(&rng.next_u64().to_le_bytes());
254	}
255	block
256}
257
258#[cfg(test)]
259mod tests {
260	use binius_frontend::CircuitBuilder;
261
262	use super::*;
263
264	fn assert_builds_and_populates<E>()
265	where
266		E: ExampleCircuit<Params = PrimitiveParams, Instance = Instance>,
267	{
268		let mut builder = CircuitBuilder::new();
269		let example = E::build(PrimitiveParams { num_primitives: 2 }, &mut builder).unwrap();
270		let circuit = builder.build();
271		let mut filler = circuit.new_witness_filler();
272
273		example
274			.populate_witness(Instance { seed: Some(7) }, &mut filler)
275			.unwrap();
276		circuit.populate_wire_witness(&mut filler).unwrap();
277		circuit
278			.constraint_system()
279			.verify(&filler.into_value_vec())
280			.unwrap();
281	}
282
283	#[test]
284	fn independent_sha256_compressions_populate_valid_witness() {
285		assert_builds_and_populates::<IndependentSha256Compressions>();
286	}
287
288	#[test]
289	fn independent_blake3_compressions_populate_valid_witness() {
290		assert_builds_and_populates::<IndependentBlake3Compressions>();
291	}
292
293	#[test]
294	fn independent_keccak_permutations_populate_valid_witness() {
295		assert_builds_and_populates::<IndependentKeccakPermutations>();
296	}
297
298	#[test]
299	fn compression_benchmarks_accept_odd_counts() {
300		let mut builder = CircuitBuilder::new();
301		IndependentSha256Compressions::build(PrimitiveParams { num_primitives: 1 }, &mut builder)
302			.unwrap();
303
304		let mut builder = CircuitBuilder::new();
305		IndependentBlake3Compressions::build(PrimitiveParams { num_primitives: 1 }, &mut builder)
306			.unwrap();
307	}
308
309	#[test]
310	fn compression_benchmarks_reject_zero_counts() {
311		let mut builder = CircuitBuilder::new();
312		assert!(
313			IndependentSha256Compressions::build(
314				PrimitiveParams { num_primitives: 0 },
315				&mut builder
316			)
317			.is_err()
318		);
319
320		let mut builder = CircuitBuilder::new();
321		assert!(
322			IndependentBlake3Compressions::build(
323				PrimitiveParams { num_primitives: 0 },
324				&mut builder
325			)
326			.is_err()
327		);
328	}
329
330	/// Guard against dead-code elimination pruning the hash logic: each primitive must emit
331	/// a non-trivial number of AND constraints per evaluation.
332	#[test]
333	fn circuits_emit_hash_constraints() {
334		fn and_count<E>() -> usize
335		where
336			E: ExampleCircuit<Params = PrimitiveParams, Instance = Instance>,
337		{
338			let mut builder = CircuitBuilder::new();
339			E::build(PrimitiveParams { num_primitives: 1 }, &mut builder).unwrap();
340			builder.build().constraint_system().and_constraints.len()
341		}
342
343		assert!(and_count::<IndependentSha256Compressions>() > 100);
344		assert!(and_count::<IndependentBlake3Compressions>() > 100);
345		assert!(and_count::<IndependentKeccakPermutations>() > 100);
346	}
347
348	/// Tampering with the expected output must fail the output assertions during wire
349	/// witness evaluation, proving they are enforced.
350	#[test]
351	fn tampered_digest_fails_output_assertion() {
352		let mut builder = CircuitBuilder::new();
353		let example = IndependentSha256Compressions::build(
354			PrimitiveParams { num_primitives: 1 },
355			&mut builder,
356		)
357		.unwrap();
358		let circuit = builder.build();
359		let mut filler = circuit.new_witness_filler();
360		example
361			.populate_witness(Instance { seed: Some(7) }, &mut filler)
362			.unwrap();
363
364		let digest_wire = example.compressions[0].digest[0];
365		filler[digest_wire] = Word(filler[digest_wire].0 ^ 1);
366		assert!(circuit.populate_wire_witness(&mut filler).is_err());
367	}
368}