Skip to main content

binius_prover/protocols/
binmul.rs

1// Copyright 2026 The Binius Developers
2
3use std::iter;
4
5use binius_alloc::{Allocator, VecLike};
6use binius_core::word::Word;
7use binius_field::{BinaryField, PackedField};
8use binius_ip_prover::{
9	channel::IPProverChannel,
10	sumcheck::{ProveSingleOutput, prove_single_mlecheck, quadratic_mlecheck_prover},
11};
12use binius_math::{FieldVec, field_buffer::FieldBuffer};
13use binius_utils::{checked_arithmetics::log2_ceil_usize, rayon::prelude::*};
14pub use binius_verifier::protocols::binmul::BinMulOutput;
15
16use crate::fold_word::WordAxisFolder;
17
18/// Build a packed GHASH-field multilinear table from a `(lo, hi)` pair of word columns.
19///
20/// The scalar at hypercube index `i` is the field element carried by the pair `(lo[i], hi[i])`:
21/// `lo[i]` supplies the low 64 bits and `hi[i]` the high 64 bits of the 128-bit value.
22///
23/// The columns need not have a power-of-two length. The table spans the whole `2^n_vars` hypercube
24/// regardless, and an index at or past the columns' end reads as the zero field element. The
25/// padding therefore lives in this buffer, which is allocated at the hypercube's size either way,
26/// rather than in a `Vec<Word>` the caller has to materialize.
27///
28/// # Preconditions
29///
30/// * The two columns have equal length.
31fn build_table<A, F, P>(alloc: &A, lo: &[Word], hi: &[Word]) -> FieldVec<P, A>
32where
33	A: Allocator,
34	F: BinaryField + From<u128>,
35	P: PackedField<Scalar = F>,
36{
37	assert_eq!(lo.len(), hi.len());
38
39	let n_vars = log2_ceil_usize(lo.len());
40	let packed_len = 1 << n_vars.saturating_sub(P::LOG_WIDTH);
41	let elem =
42		|(&lo, &hi): (&Word, &Word)| F::from((lo.as_u64() as u128) | ((hi.as_u64() as u128) << 64));
43
44	let mut values = alloc.alloc::<P>(packed_len);
45
46	// The packed elements the columns fill whole. `chunks_exact` stops at the last of them, so
47	// every lane this loop packs is a real row.
48	#[allow(clippy::chunks_exact_to_as_chunks)] // `P::WIDTH` is not usable as a const generic arg
49	let (lo_chunks, hi_chunks) = (lo.chunks_exact(P::WIDTH), hi.chunks_exact(P::WIDTH));
50	let (lo_tail, hi_tail) = (lo_chunks.remainder(), hi_chunks.remainder());
51	values.extend(
52		iter::zip(lo_chunks, hi_chunks)
53			.map(|(lo_chunk, hi_chunk)| P::from_scalars(iter::zip(lo_chunk, hi_chunk).map(elem))),
54	);
55
56	// The columns' trailing words share one packed element with the start of the padding. The lanes
57	// `from_scalars` is not given default to zero, which is exactly that padding.
58	if !lo_tail.is_empty() {
59		values.push(P::from_scalars(iter::zip(lo_tail, hi_tail).map(elem)));
60	}
61
62	// The rest of the hypercube is zero padding. A zero row satisfies `0 * 0 = 0`, so it
63	// contributes nothing to the zerocheck.
64	values.resize(packed_len, P::zero());
65
66	FieldBuffer::new(n_vars, values)
67}
68
69/// Prove the binary-field multiplication check (BinMul) reduction.
70///
71/// Proves $\widetilde{A}(x) \cdot \widetilde{B}(x) = \widetilde{C}(x)$ for every $x$ on the boolean
72/// hypercube $\mathbb{B}_\ell$ over the GHASH field, where each element is carried by a `(lo, hi)`
73/// pair of 64-bit words. See [`binius_verifier::protocols::binmul::verify`] for the protocol
74/// description and output shape.
75///
76/// The six `columns` are the `(lo, hi)` word pairs of the two multiplicands and the product, in the
77/// order `[a_lo, a_hi, b_lo, b_hi, c_lo, c_hi]`, all of equal length. That length need not be a
78/// power of two: the hypercube is $\mathbb{B}_\ell$ for $\ell = \lceil \log_2 n \rceil$, and a row
79/// at or past the columns' end reads as the zero field element. A zero row satisfies
80/// $0 \cdot 0 = 0$, so it contributes nothing to the zerocheck. The GHASH-field element for row $x$
81/// is
82/// $\langle\langle z_{\textsf{lo}}, z_{\textsf{hi}} \rangle\rangle = \sum_{i=0}^{63}
83/// z_{\textsf{lo},x,i} \cdot X^i + \sum_{i=0}^{63} z_{\textsf{hi},x,i} \cdot X^{64+i}$ for each of
84/// $z \in \{a, b, c\}$.
85pub fn prove<A, F, P, Channel>(
86	columns: [&[Word]; 6],
87	channel: &mut Channel,
88	alloc: &A,
89) -> BinMulOutput<F>
90where
91	A: Allocator,
92	F: BinaryField + From<u128>,
93	P: PackedField<Scalar = F>,
94	Channel: IPProverChannel<F>,
95{
96	let [a_lo, a_hi, b_lo, b_hi, c_lo, c_hi] = columns;
97
98	let n_vars = log2_ceil_usize(a_lo.len());
99	for column in [a_hi, b_lo, b_hi, c_lo, c_hi] {
100		assert_eq!(column.len(), a_lo.len());
101	}
102
103	// Build the packed GHASH-field multilinear tables A, B, C from the (lo, hi) word pairs.
104	let a = build_table::<A, F, P>(alloc, a_lo, a_hi);
105	let b = build_table::<A, F, P>(alloc, b_lo, b_hi);
106	let c = build_table::<A, F, P>(alloc, c_lo, c_hi);
107
108	// Sample the zerocheck challenge r_z.
109	let r_z = channel.sample_many(n_vars);
110
111	// Product zerocheck: 0 = sum_x eq(r_z, x) * (A(x) * B(x) - C(x)). The composition A * B - C has
112	// degree 2; the eq factor is folded internally by the MLE-check.
113	let prover = quadratic_mlecheck_prover(
114		alloc,
115		[a, b, c],
116		|[a, b, c]| a * b - c,
117		|[a, b, _c]| a * b,
118		r_z,
119		F::ZERO,
120	);
121
122	let ProveSingleOutput {
123		multilinear_evals: _,
124		challenges: mut eval_point,
125	} = prove_single_mlecheck(prover, channel);
126	// `prove_single_mlecheck` folds high-to-low, so reverse to obtain the shared output point r_x.
127	eval_point.reverse();
128
129	// Send the raw per-bit output evaluations of each word column at r_x. One folder is built for
130	// the shared point and reused across all six columns.
131	//
132	// Six columns cannot fill a machine on their own, so each column divides its own chunk axis
133	// rather than the six being run against each other.
134	let folder = WordAxisFolder::<F>::new(&eval_point);
135	let [
136		a_lo_evals,
137		a_hi_evals,
138		b_lo_evals,
139		b_hi_evals,
140		c_lo_evals,
141		c_hi_evals,
142	] = [a_lo, a_hi, b_lo, b_hi, c_lo, c_hi]
143		.into_par_iter()
144		.map(|exponents| folder.fold_par(exponents))
145		.collect::<Vec<_>>()
146		.try_into()
147		.expect("iterator over exact number of elements");
148
149	channel.send_many(&a_lo_evals);
150	channel.send_many(&a_hi_evals);
151	channel.send_many(&b_lo_evals);
152	channel.send_many(&b_hi_evals);
153	channel.send_many(&c_lo_evals);
154	channel.send_many(&c_hi_evals);
155
156	BinMulOutput {
157		eval_point,
158		a_lo_evals,
159		a_hi_evals,
160		b_lo_evals,
161		b_hi_evals,
162		c_lo_evals,
163		c_hi_evals,
164	}
165}
166
167#[cfg(test)]
168mod tests {
169	use binius_alloc::GlobalAllocator;
170	use binius_core::word::Word;
171	use binius_field::{Ghash128b, PackedGhash2x128b, Random};
172	use binius_iop::channel::{OracleSpec, naive::NaiveVerifierChannel};
173	use binius_iop_prover::channel::naive::NaiveProverChannel;
174	use binius_math::{inner_product::inner_product_buffers, multilinear::eq::eq_ind_partial_eval};
175	use binius_transcript::{ProverTranscript, VerifierTranscript};
176	use binius_verifier::{
177		config::StdChallenger,
178		protocols::binmul::{BinMulOutput, verify},
179	};
180	use itertools::izip;
181	use rand::prelude::*;
182
183	use super::{log2_ceil_usize, prove};
184
185	type F = Ghash128b;
186	type P = PackedGhash2x128b;
187
188	/// The six word columns `(a_lo, a_hi, b_lo, b_hi, c_lo, c_hi)` of a BinMul witness.
189	type WordColumns = (Vec<Word>, Vec<Word>, Vec<Word>, Vec<Word>, Vec<Word>, Vec<Word>);
190
191	/// Evaluate the multilinear extension of a per-bit word column at a point, independently of the
192	/// prover. The point's `Word::LOG_BITS`-coordinate prefix selects the bit within a word; the
193	/// suffix selects the word (constraint) index.
194	fn evaluate_witness(words: &[Word], eval_point: &[F]) -> F {
195		let (prefix, suffix) = eval_point.split_at(Word::LOG_BITS);
196		let prefix_tensor = eq_ind_partial_eval::<F>(prefix);
197		let suffix_tensor = eq_ind_partial_eval::<F>(suffix);
198
199		let partially_folded_witness = crate::fold_word::BitAxisFolder::new(prefix_tensor.as_ref())
200			.fold::<F, _>(&GlobalAllocator, words);
201
202		inner_product_buffers(&partially_folded_witness, &suffix_tensor)
203	}
204
205	/// Split a GHASH-field element into its `(lo, hi)` 64-bit word pair.
206	fn to_word_pair(elem: F) -> (Word, Word) {
207		let value = u128::from(elem);
208		(Word::from_u64(value as u64), Word::from_u64((value >> 64) as u64))
209	}
210
211	/// Build a valid BinMul witness with `n` random constraints `a * b = c`, where `c` is computed
212	/// with GHASH-field multiplication directly (an independent oracle).
213	fn random_witness(rng: &mut impl Rng, n: usize) -> WordColumns {
214		let mut a_lo = Vec::with_capacity(n);
215		let mut a_hi = Vec::with_capacity(n);
216		let mut b_lo = Vec::with_capacity(n);
217		let mut b_hi = Vec::with_capacity(n);
218		let mut c_lo = Vec::with_capacity(n);
219		let mut c_hi = Vec::with_capacity(n);
220
221		for _ in 0..n {
222			let a = F::random(&mut *rng);
223			let b = F::random(&mut *rng);
224			let c = a * b;
225
226			let (a_lo_i, a_hi_i) = to_word_pair(a);
227			let (b_lo_i, b_hi_i) = to_word_pair(b);
228			let (c_lo_i, c_hi_i) = to_word_pair(c);
229
230			a_lo.push(a_lo_i);
231			a_hi.push(a_hi_i);
232			b_lo.push(b_lo_i);
233			b_hi.push(b_hi_i);
234			c_lo.push(c_lo_i);
235			c_hi.push(c_hi_i);
236		}
237
238		(a_lo, a_hi, b_lo, b_hi, c_lo, c_hi)
239	}
240
241	#[test]
242	fn prove_and_verify() {
243		let mut rng = StdRng::seed_from_u64(0);
244
245		const LOG_N: usize = 5;
246		let (a_lo, a_hi, b_lo, b_hi, c_lo, c_hi) = random_witness(&mut rng, 1 << LOG_N);
247
248		// BinMul commits no oracles.
249		let oracle_specs: [OracleSpec; 0] = [];
250
251		// Run prover.
252		let mut prover_transcript = ProverTranscript::<StdChallenger>::default();
253		let mut prover_channel =
254			NaiveProverChannel::<F, _>::new(&mut prover_transcript, oracle_specs.to_vec());
255		let prove_output = prove::<_, F, P, _>(
256			[&a_lo, &a_hi, &b_lo, &b_hi, &c_lo, &c_hi],
257			&mut prover_channel,
258			&GlobalAllocator,
259		);
260		prover_channel.finish();
261
262		let BinMulOutput {
263			eval_point,
264			a_lo_evals,
265			a_hi_evals,
266			b_lo_evals,
267			b_hi_evals,
268			c_lo_evals,
269			c_hi_evals,
270		} = prove_output.clone();
271
272		// Independently check each column's per-bit evals against the witness MLE. We batch the bit
273		// columns with a `z_challenge` and compare at a single point
274		// `consistency_check_eval_point`.
275		let z_challenge: Vec<F> = (0..Word::LOG_BITS).map(|_| F::random(&mut rng)).collect();
276		let z_tensor = eq_ind_partial_eval::<F>(&z_challenge);
277		let consistency_check_eval_point = [z_challenge, eval_point].concat();
278		let get_consistency_check_eval =
279			|evals: [F; Word::BITS]| izip!(evals, z_tensor.as_ref()).map(|(x, y)| x * y).sum();
280
281		let test_cases = [
282			(&a_lo, a_lo_evals),
283			(&a_hi, a_hi_evals),
284			(&b_lo, b_lo_evals),
285			(&b_hi, b_hi_evals),
286			(&c_lo, c_lo_evals),
287			(&c_hi, c_hi_evals),
288		];
289		for (words, evals) in test_cases {
290			let expected_eval = evaluate_witness(words, &consistency_check_eval_point);
291			let given_eval = get_consistency_check_eval(evals);
292			assert_eq!(expected_eval, given_eval);
293		}
294
295		// Run verifier.
296		let mut verifier_transcript = prover_transcript.into_verifier();
297		let mut verifier_channel =
298			NaiveVerifierChannel::<F, _>::new(&mut verifier_transcript, &oracle_specs);
299		let verify_output = verify(LOG_N, &mut verifier_channel).unwrap();
300		verifier_channel.finish();
301
302		assert_eq!(prove_output, verify_output);
303	}
304
305	// A witness whose constraint count is not a power of two proves exactly as the same witness
306	// zero-padded up to one: byte-identical transcript, identical output claims, and the proof
307	// still verifies against the padded variable count the verifier derives from the constraint
308	// system.
309	//
310	// This is the guarantee that lets the M4 prover stop materializing the padding rows
311	// (BINIUS-388) without moving anything on the wire.
312	#[test]
313	fn unpadded_columns_prove_identically_to_padded_ones() {
314		let mut rng = StdRng::seed_from_u64(2);
315
316		// Constraint counts crossing the fold's 64-word chunk and the packed width: a single row, a
317		// sub-chunk count, a count straddling the chunk boundary, and a multi-chunk count.
318		for n in [1, 3, 65, 100] {
319			let columns = random_witness(&mut rng, n);
320			let n_vars = log2_ceil_usize(n);
321
322			// The same witness with explicit zero rows up to the hypercube's size. A zero row
323			// satisfies `0 * 0 = 0`, so the padded witness is equally valid.
324			let padded = {
325				let pad = |words: &Vec<Word>| {
326					let mut padded = words.clone();
327					padded.resize(1 << n_vars, Word::ZERO);
328					padded
329				};
330				let (a_lo, a_hi, b_lo, b_hi, c_lo, c_hi) = &columns;
331				(pad(a_lo), pad(a_hi), pad(b_lo), pad(b_hi), pad(c_lo), pad(c_hi))
332			};
333
334			// One proof per shape, each on a fresh transcript over the same challenger seed.
335			let run = |columns: &WordColumns| {
336				let (a_lo, a_hi, b_lo, b_hi, c_lo, c_hi) = columns;
337				let oracle_specs: [OracleSpec; 0] = [];
338				let mut transcript = ProverTranscript::<StdChallenger>::default();
339				let mut channel =
340					NaiveProverChannel::<F, _>::new(&mut transcript, oracle_specs.to_vec());
341				let output = prove::<_, F, P, _>(
342					[a_lo, a_hi, b_lo, b_hi, c_lo, c_hi],
343					&mut channel,
344					&GlobalAllocator,
345				);
346				channel.finish();
347				(output, transcript.finalize())
348			};
349			let (unpadded_output, unpadded_proof) = run(&columns);
350			let (padded_output, padded_proof) = run(&padded);
351
352			assert_eq!(unpadded_output, padded_output, "claims differ at n = {n}");
353			assert_eq!(unpadded_proof, padded_proof, "transcript differs at n = {n}");
354
355			let oracle_specs: [OracleSpec; 0] = [];
356			let mut verifier_transcript =
357				VerifierTranscript::new(StdChallenger::default(), unpadded_proof);
358			let mut verifier_channel =
359				NaiveVerifierChannel::<F, _>::new(&mut verifier_transcript, &oracle_specs);
360			let verify_output = verify(n_vars, &mut verifier_channel).unwrap();
361			verifier_channel.finish();
362
363			assert_eq!(unpadded_output, verify_output, "verifier disagrees at n = {n}");
364		}
365	}
366
367	#[test]
368	fn verify_rejects_tampered_c() {
369		let mut rng = StdRng::seed_from_u64(1);
370
371		const LOG_N: usize = 5;
372		let (a_lo, a_hi, b_lo, b_hi, mut c_lo, c_hi) = random_witness(&mut rng, 1 << LOG_N);
373
374		// Corrupt one c_lo word so the constraint no longer holds.
375		c_lo[3] = Word::from_u64(c_lo[3].as_u64() ^ 1);
376
377		let oracle_specs: [OracleSpec; 0] = [];
378
379		let mut prover_transcript = ProverTranscript::<StdChallenger>::default();
380		let mut prover_channel =
381			NaiveProverChannel::<F, _>::new(&mut prover_transcript, oracle_specs.to_vec());
382		let _ = prove::<_, F, P, _>(
383			[&a_lo, &a_hi, &b_lo, &b_hi, &c_lo, &c_hi],
384			&mut prover_channel,
385			&GlobalAllocator,
386		);
387		prover_channel.finish();
388
389		let mut verifier_transcript = prover_transcript.into_verifier();
390		let mut verifier_channel =
391			NaiveVerifierChannel::<F, _>::new(&mut verifier_transcript, &oracle_specs);
392		let result = verify(LOG_N, &mut verifier_channel);
393		assert!(result.is_err(), "verifier must reject a tampered witness");
394	}
395}