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	for chunk in block.chunks_exact_mut(8) {
252		chunk.copy_from_slice(&rng.next_u64().to_le_bytes());
253	}
254	block
255}
256
257#[cfg(test)]
258mod tests {
259	use binius_frontend::CircuitBuilder;
260
261	use super::*;
262
263	fn assert_builds_and_populates<E>()
264	where
265		E: ExampleCircuit<Params = PrimitiveParams, Instance = Instance>,
266	{
267		let mut builder = CircuitBuilder::new();
268		let example = E::build(PrimitiveParams { num_primitives: 2 }, &mut builder).unwrap();
269		let circuit = builder.build();
270		let mut filler = circuit.new_witness_filler();
271
272		example
273			.populate_witness(Instance { seed: Some(7) }, &mut filler)
274			.unwrap();
275		circuit.populate_wire_witness(&mut filler).unwrap();
276		circuit
277			.constraint_system()
278			.verify(&filler.into_value_vec())
279			.unwrap();
280	}
281
282	#[test]
283	fn independent_sha256_compressions_populate_valid_witness() {
284		assert_builds_and_populates::<IndependentSha256Compressions>();
285	}
286
287	#[test]
288	fn independent_blake3_compressions_populate_valid_witness() {
289		assert_builds_and_populates::<IndependentBlake3Compressions>();
290	}
291
292	#[test]
293	fn independent_keccak_permutations_populate_valid_witness() {
294		assert_builds_and_populates::<IndependentKeccakPermutations>();
295	}
296
297	#[test]
298	fn compression_benchmarks_accept_odd_counts() {
299		let mut builder = CircuitBuilder::new();
300		IndependentSha256Compressions::build(PrimitiveParams { num_primitives: 1 }, &mut builder)
301			.unwrap();
302
303		let mut builder = CircuitBuilder::new();
304		IndependentBlake3Compressions::build(PrimitiveParams { num_primitives: 1 }, &mut builder)
305			.unwrap();
306	}
307
308	#[test]
309	fn compression_benchmarks_reject_zero_counts() {
310		let mut builder = CircuitBuilder::new();
311		assert!(
312			IndependentSha256Compressions::build(
313				PrimitiveParams { num_primitives: 0 },
314				&mut builder
315			)
316			.is_err()
317		);
318
319		let mut builder = CircuitBuilder::new();
320		assert!(
321			IndependentBlake3Compressions::build(
322				PrimitiveParams { num_primitives: 0 },
323				&mut builder
324			)
325			.is_err()
326		);
327	}
328
329	/// Guard against dead-code elimination pruning the hash logic: each primitive must emit
330	/// a non-trivial number of AND constraints per evaluation.
331	#[test]
332	fn circuits_emit_hash_constraints() {
333		fn and_count<E>() -> usize
334		where
335			E: ExampleCircuit<Params = PrimitiveParams, Instance = Instance>,
336		{
337			let mut builder = CircuitBuilder::new();
338			E::build(PrimitiveParams { num_primitives: 1 }, &mut builder).unwrap();
339			builder.build().constraint_system().and_constraints.len()
340		}
341
342		assert!(and_count::<IndependentSha256Compressions>() > 100);
343		assert!(and_count::<IndependentBlake3Compressions>() > 100);
344		assert!(and_count::<IndependentKeccakPermutations>() > 100);
345	}
346
347	/// Tampering with the expected output must fail the output assertions during wire
348	/// witness evaluation, proving they are enforced.
349	#[test]
350	fn tampered_digest_fails_output_assertion() {
351		let mut builder = CircuitBuilder::new();
352		let example = IndependentSha256Compressions::build(
353			PrimitiveParams { num_primitives: 1 },
354			&mut builder,
355		)
356		.unwrap();
357		let circuit = builder.build();
358		let mut filler = circuit.new_witness_filler();
359		example
360			.populate_witness(Instance { seed: Some(7) }, &mut filler)
361			.unwrap();
362
363		let digest_wire = example.compressions[0].digest[0];
364		filler[digest_wire] = Word(filler[digest_wire].0 ^ 1);
365		assert!(circuit.populate_wire_witness(&mut filler).is_err());
366	}
367}
binius_examples/circuits/independent_hashes.rs

binius_examples/circuits/
independent_hashes.rs
