1use 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
18fn 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 #[allow(clippy::chunks_exact_to_as_chunks)] 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 if !lo_tail.is_empty() {
59 values.push(P::from_scalars(iter::zip(lo_tail, hi_tail).map(elem)));
60 }
61
62 values.resize(packed_len, P::zero());
65
66 FieldBuffer::new(n_vars, values)
67}
68
69pub 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 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 let r_z = channel.sample_many(n_vars);
110
111 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 eval_point.reverse();
128
129 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 type WordColumns = (Vec<Word>, Vec<Word>, Vec<Word>, Vec<Word>, Vec<Word>, Vec<Word>);
190
191 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 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 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 let oracle_specs: [OracleSpec; 0] = [];
250
251 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 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 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 #[test]
313 fn unpadded_columns_prove_identically_to_padded_ones() {
314 let mut rng = StdRng::seed_from_u64(2);
315
316 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 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 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 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}