1use std::{iter, marker::PhantomData};
5
6use binius_alloc::Allocator;
7use binius_core::word::Word;
8use binius_field::{BinaryField, Divisible, PackedField};
9use binius_iop_prover::{
10 channel::IOPProverChannel,
11 logup_star::{self, Looker},
12};
13use binius_ip::prodcheck::MultilinearEvalClaim;
14use binius_ip_prover::{
15 channel::IPProverChannel,
16 prodcheck::{self, ProdcheckProver},
17 sumcheck::{
18 MleToSumCheckDecorator,
19 batch::{BatchSumcheckOutput, batch_prove, batch_prove_and_write_evals},
20 bivariate_product_mle,
21 multilinear_eval::multilinear_eval_prover,
22 },
23};
24use binius_math::{
25 FieldSlice, FieldVec,
26 field_buffer::FieldBuffer,
27 inner_product::inner_product_buffers,
28 multilinear::{
29 eq::{eq_ind_partial_eval, eq_ind_partial_eval_scalars},
30 evaluate::{evaluate, evaluate_inplace},
31 },
32};
33use binius_utils::{checked_arithmetics::log2_ceil_usize, rayon::prelude::*};
34use binius_verifier::protocols::intmul::common::{
35 IntMulOutput, LIMB_BITS, LOG_N_LIMBS, N_LIMB_COLUMNS, N_LIMBS, Phase1Output, Phase2Output,
36 Phase3Output, Phase4Output, frobenius_twist, limb_column_twists, twist_limb_claim,
37};
38use either::Either;
39use itertools::izip;
40
41use super::{
42 bit_column_mle::BitColumnMlecheckProver,
43 error::Error,
44 selector_mle::{Claim, SelectorMlecheckProver},
45 switchover::BinarySwitchover,
46 witness::{Witness, limb_index},
47};
48use crate::fold_word::{BitAxisFolder, WordAxisFolder};
49
50pub fn prove<A, F, P, Channel>(
70 columns: [&[Word]; 4],
71 channel: &mut Channel,
72 alloc: &A,
73) -> Result<IntMulOutput<F>, Error>
74where
75 A: Allocator,
76 F: BinaryField<Underlier: Divisible<u64>>,
77 P: PackedField<Scalar = F>,
78 Channel: IOPProverChannel<P, A>,
79{
80 let [a, b, lo, hi] = columns;
81
82 let witness = tracing::debug_span!("Build IntMul witness")
83 .in_scope(|| Witness::<_, P>::new(alloc, a, b, lo, hi))?;
84
85 let mut prover = IntMulProver::new(channel, alloc);
86 Ok(prover.prove(witness))
87}
88
89pub struct IntMulProver<'a, 'alloc, A: Allocator, P, Channel> {
92 _p_marker: PhantomData<P>,
93
94 channel: &'a mut Channel,
95 alloc: &'alloc A,
97}
98
99impl<'a, 'alloc, A: Allocator, P, Channel> IntMulProver<'a, 'alloc, A, P, Channel> {
100 pub const fn new(channel: &'a mut Channel, alloc: &'alloc A) -> Self {
101 Self {
102 _p_marker: PhantomData,
103 channel,
104 alloc,
105 }
106 }
107}
108
109impl<'alloc, A, F, P, Channel> IntMulProver<'_, 'alloc, A, P, Channel>
110where
111 A: Allocator,
112 F: BinaryField<Underlier: Divisible<u64>>,
113 P: PackedField<Scalar = F>,
114 Channel: IOPProverChannel<P, A>,
115{
116 pub fn prove(&mut self, witness: Witness<'_, 'alloc, A, P>) -> IntMulOutput<F> {
143 let Witness {
144 a_exponents,
145 a_prodcheck,
146 a_root,
147 b_exponents,
148 b_leaves,
149 b_prodcheck,
150 b_root,
151 c_lo_exponents,
152 c_lo_prodcheck,
153 c_lo_root,
154 c_hi_exponents,
155 c_hi_prodcheck,
156 c_hi_root,
157 tables,
158 } = witness;
159
160 let n_vars = b_root.log_len();
163
164 let initial_eval_point = self.channel.sample_many(n_vars);
165
166 let exp_eval = tracing::debug_span!("Evaluate exponent root")
168 .in_scope(|| evaluate_inplace(b_root, &initial_eval_point));
169
170 self.channel.send_one(exp_eval);
171
172 let Phase1Output {
174 eval_point: phase1_eval_point,
175 b_leaves_evals,
176 } = self.phase1(&initial_eval_point, b_prodcheck, b_leaves.as_view(), exp_eval);
177
178 let Phase2Output {
180 twisted_eval_points,
181 twisted_evals,
182 } = tracing::debug_span!("IntMul phase2 (Frobenius twist)")
183 .in_scope(|| frobenius_twist(Word::LOG_BITS, &phase1_eval_point, &b_leaves_evals));
184
185 let Phase3Output {
187 eval_point: phase3_eval_point,
188 r_ib,
189 b_recomb,
190 gpow_a_eval,
191 gpow_c_lo_eval,
192 gpow_c_hi_eval,
193 } = self.phase3(
194 &twisted_eval_points,
195 &twisted_evals,
196 a_root,
197 b_exponents,
198 [c_lo_root, c_hi_root],
199 &initial_eval_point,
200 exp_eval,
201 );
202
203 let phase_4_output = self.phase4(
205 &phase3_eval_point,
206 (gpow_a_eval, a_prodcheck),
207 (gpow_c_lo_eval, c_lo_prodcheck),
208 (gpow_c_hi_eval, c_hi_prodcheck),
209 [a_exponents, c_lo_exponents, c_hi_exponents],
210 &tables,
211 );
212
213 self.phase5(
215 &phase_4_output,
216 b_exponents,
217 &phase3_eval_point,
218 &r_ib,
219 b_recomb,
220 a_exponents,
221 c_lo_exponents,
222 c_hi_exponents,
223 tables[0].as_view(),
224 )
225 }
226
227 #[doc(hidden)] #[allow(clippy::too_many_arguments)]
229 pub fn phase5(
230 &mut self,
231 phase_4_output: &Phase4Output<F>,
232 b_exponents: &[Word],
233 b_eval_point: &[F],
234 r_ib: &[F],
235 b_recomb: F,
236 a_exponents: &[Word],
239 c_lo_exponents: &[Word],
240 c_hi_exponents: &[Word],
241 table: FieldSlice<'_, P>,
242 ) -> IntMulOutput<F> {
243 let alloc = self.alloc;
244 let n_vars = b_eval_point.len();
245 assert_eq!(phase_4_output.eval_point.len(), n_vars);
246
247 let twists = limb_column_twists();
251 let exponents = [a_exponents, c_lo_exponents, c_hi_exponents];
252 let limb_evals = [
253 &phase_4_output.a_limb_evals,
254 &phase_4_output.c_lo_limb_evals,
255 &phase_4_output.c_hi_limb_evals,
256 ];
257
258 let columns_guard = tracing::debug_span!("Gather lookup index columns").entered();
259 let index_columns = (0..N_LIMB_COLUMNS)
261 .into_par_iter()
262 .map(|j| {
263 let (tree, limb) = (j / N_LIMBS, j % N_LIMBS);
264 let n_padding = (1 << n_vars) - exponents[tree].len();
268 exponents[tree]
269 .iter()
270 .map(|&word| limb_index(word, limb))
271 .chain(iter::repeat_n(0, n_padding))
272 .collect::<Vec<_>>()
273 })
274 .collect::<Vec<_>>();
275 let twisted_claims = (0..N_LIMB_COLUMNS)
276 .map(|j| {
277 let (tree, limb) = (j / N_LIMBS, j % N_LIMBS);
278 twist_limb_claim(twists[j], &phase_4_output.eval_point, limb_evals[tree][limb])
279 })
280 .collect::<Vec<_>>();
281 drop(columns_guard);
282
283 let lookers = izip!(&index_columns, &twisted_claims)
288 .map(|(index, (twisted_point, twisted_eval))| Looker {
289 index,
290 eval_point: twisted_point,
291 eval_claim: *twisted_eval,
292 })
293 .collect::<Vec<_>>();
294 let log_cols = log2_ceil_usize(N_LIMB_COLUMNS);
295 let logup_proof = logup_star::prove_transparent(
299 [logup_star::TableLookup { table, lookers }],
300 self.channel,
301 self.alloc,
302 );
303 let [column_index_evals] = logup_proof.index_eval_claims.as_slice() else {
304 unreachable!("the reduction runs over the one power table")
305 };
306
307 let embed_guard = tracing::debug_span!("Build embedding table").entered();
310 let mut iota_table = Vec::with_capacity(1usize << LIMB_BITS);
311 iota_table.push(F::ZERO);
312 for row in 1..1usize << LIMB_BITS {
313 let low_bit_basis = F::basis(row.trailing_zeros() as usize);
314 iota_table.push(iota_table[row & (row - 1)] + low_bit_basis);
315 }
316 drop(embed_guard);
317
318 let index_content_point = logup_proof.index_eval_point.as_slice();
319
320 let rho = self.channel.sample_many(log_cols);
323 let mut padded_column_evals = column_index_evals.clone();
324 padded_column_evals.resize(1 << log_cols, F::ZERO);
325 let folded_index_claim =
326 evaluate(&FieldBuffer::<P>::from_values(&padded_column_evals), &rho);
327 let rho_tensor = eq_ind_partial_eval_scalars(&rho);
328 let fold_guard = tracing::debug_span!("Fold index columns by rho").entered();
329 let folded_column_scalars = (0..1usize << n_vars)
333 .into_par_iter()
334 .map(|i| {
335 izip!(&index_columns, &rho_tensor)
336 .map(|(column, &weight)| iota_table[column[i]] * weight)
337 .sum::<F>()
338 })
339 .collect::<Vec<_>>();
340 let folded_column = FieldBuffer::<P, _>::from_values_in(alloc, &folded_column_scalars);
341 drop(fold_guard);
342 let index_prover = MleToSumCheckDecorator::new(multilinear_eval_prover(
343 alloc,
344 folded_column,
345 index_content_point,
346 folded_index_claim,
347 ));
348
349 let low_bits = [a_exponents, b_exponents, c_lo_exponents]
353 .map(|exponents| BinarySwitchover::<P, _>::new_bit(alloc, exponents, 0, n_vars));
354 let overflow_prover = MleToSumCheckDecorator::new(BitColumnMlecheckProver::new(
355 low_bits,
356 b_eval_point.to_vec(),
357 F::ZERO,
358 ));
359
360 assert!(b_exponents.len() <= 1 << n_vars);
364 let b_tensor = eq_ind_partial_eval_scalars(r_ib);
365 let b_folded = BitAxisFolder::new(&b_tensor).fold::<P, _>(alloc, b_exponents);
366 let b_sumcheck_prover = MleToSumCheckDecorator::new(multilinear_eval_prover(
367 alloc,
368 b_folded,
369 b_eval_point,
370 b_recomb,
371 ));
372
373 let batch_guard = tracing::debug_span!("Final batched sumcheck").entered();
374 let BatchSumcheckOutput {
375 mut challenges,
376 multilinear_evals: _,
377 } = batch_prove(
378 vec![
379 Either::Left(index_prover),
380 Either::Right(Either::Left(overflow_prover)),
381 Either::Right(Either::Right(b_sumcheck_prover)),
382 ],
383 self.channel,
384 );
385 drop(batch_guard);
386
387 challenges.reverse();
390 let r_out = challenges.as_slice();
391
392 let output_guard = tracing::debug_span!("Compute output bit evals").entered();
396 let folder = WordAxisFolder::<F>::new(r_out);
399 let [a_evals, b_evals, c_lo_evals, c_hi_evals] =
400 [a_exponents, b_exponents, c_lo_exponents, c_hi_exponents]
401 .into_par_iter()
402 .map(|exponents| folder.fold_par(exponents))
403 .collect::<Vec<_>>()
404 .try_into()
405 .expect("iterator over exact number of elements");
406 drop(output_guard);
407
408 self.channel.send_many(&a_evals);
409 self.channel.send_many(&c_lo_evals);
410 self.channel.send_many(&c_hi_evals);
411 self.channel.send_many(&b_evals);
412
413 IntMulOutput {
414 eval_point: r_out.to_vec(),
415 a_evals,
416 b_evals,
417 c_lo_evals,
418 c_hi_evals,
419 }
420 }
421}
422
423impl<'alloc, A, F, P, Channel> IntMulProver<'_, 'alloc, A, P, Channel>
424where
425 A: Allocator,
426 F: BinaryField,
427 P: PackedField<Scalar = F>,
428 Channel: IPProverChannel<F>,
429{
430 #[doc(hidden)] pub fn phase1(
432 &mut self,
433 eval_point: &[F],
434 b_prover: ProdcheckProver<'alloc, A, P>,
435 b_leaves: FieldSlice<'_, P>,
436 b_root_eval: F,
437 ) -> Phase1Output<F> {
438 let n_vars = eval_point.len();
439
440 let claim = MultilinearEvalClaim {
442 eval: b_root_eval,
443 point: eval_point.to_vec(),
444 };
445
446 let MultilinearEvalClaim {
448 eval: _,
449 point: reduced_point,
450 } = tracing::debug_span!("Variable-base product check")
451 .in_scope(|| b_prover.prove(claim, self.channel));
452
453 let (x_point, _z_suffix) = reduced_point.split_at(n_vars);
455
456 let leaf_guard = tracing::debug_span!("Compute base layer partial evals").entered();
458 let x_tensor = eq_ind_partial_eval(x_point);
459 let b_leaves_evals = b_leaves
460 .par_chunks(n_vars)
461 .map(|b_leaf| inner_product_buffers(&b_leaf, &x_tensor))
462 .collect::<Vec<_>>();
463 drop(leaf_guard);
464
465 self.channel.send_many(&b_leaves_evals);
467
468 Phase1Output {
469 eval_point: x_point.to_vec(),
470 b_leaves_evals,
471 }
472 }
473
474 #[doc(hidden)] #[allow(clippy::too_many_arguments)]
476 pub fn phase3(
477 &mut self,
478 twisted_eval_points: &[Vec<F>],
479 twisted_evals: &[F],
480 selector: FieldVec<P, A>,
481 b_exponents: &[Word],
482 c_lo_hi_roots: [FieldVec<P, A>; 2],
483 c_eval_point: &[F],
484 c_root_eval: F,
485 ) -> Phase3Output<F> {
486 let alloc = self.alloc;
487 let n_vars = selector.log_len();
488 assert!(
489 twisted_eval_points
490 .iter()
491 .all(|point| point.len() == n_vars)
492 );
493 assert!(b_exponents.len() <= 1 << n_vars);
494
495 let selector_claims = izip!(twisted_eval_points, twisted_evals)
496 .map(|(point, &value)| Claim {
497 point: point.clone(),
498 value,
499 })
500 .collect();
501
502 let gamma = self.channel.sample_many(Word::LOG_BITS);
509 let eq_weights = eq_ind_partial_eval_scalars(&gamma);
510 let selector_prover =
511 SelectorMlecheckProver::new(alloc, selector, selector_claims, b_exponents, eq_weights);
512
513 let c_root_sumcheck_prover =
514 bivariate_product_mle::new(alloc, c_lo_hi_roots, c_eval_point.to_vec(), c_root_eval);
515
516 let c_root_prover = MleToSumCheckDecorator::new(c_root_sumcheck_prover);
517
518 let provers = vec![Either::Left(selector_prover), Either::Right(c_root_prover)];
519 let sumcheck_guard = tracing::debug_span!("Batched selector + C-root sumcheck").entered();
520 let BatchSumcheckOutput {
521 mut challenges,
522 multilinear_evals,
523 } = batch_prove_and_write_evals(provers, self.channel);
524 challenges.reverse();
527 drop(sumcheck_guard);
528
529 let [mut selector_prover_evals, c_root_prover_evals] = multilinear_evals
530 .try_into()
531 .expect("batch_prove with two provers returns length-2 multilinear_evals");
532
533 assert_eq!(selector_prover_evals.len(), 1 + Word::BITS);
534
535 let gpow_a_eval = selector_prover_evals
536 .pop()
537 .expect("selector_prover_evals.len() > 0");
538 let b_evals = selector_prover_evals;
539 let [gpow_c_lo_eval, gpow_c_hi_eval] = c_root_prover_evals
540 .try_into()
541 .expect("c_root_prover with two multilinears returns two evals");
542
543 let r_ib = self.channel.sample_many(Word::LOG_BITS);
547 let b_recomb = evaluate(&FieldBuffer::<P>::from_values(&b_evals), &r_ib);
548
549 Phase3Output {
550 eval_point: challenges,
551 r_ib,
552 b_recomb,
553 gpow_a_eval,
554 gpow_c_lo_eval,
555 gpow_c_hi_eval,
556 }
557 }
558
559 #[doc(hidden)] #[allow(clippy::too_many_arguments)]
561 pub fn phase4(
562 &mut self,
563 eval_point: &[F],
564 (a_root_eval, a_prover): (F, ProdcheckProver<'alloc, A, P>),
565 (gpow_c_lo_eval, c_lo_prover): (F, ProdcheckProver<'alloc, A, P>),
566 (gpow_c_hi_eval, c_hi_prover): (F, ProdcheckProver<'alloc, A, P>),
567 exponents: [&[Word]; 3],
568 tables: &[FieldVec<P, A>],
569 ) -> Phase4Output<F> {
570 let n_vars = eval_point.len();
571
572 assert_eq!(a_prover.n_layers(), LOG_N_LIMBS);
574 assert_eq!(c_lo_prover.n_layers(), LOG_N_LIMBS);
575 assert_eq!(c_hi_prover.n_layers(), LOG_N_LIMBS);
576
577 let selector = self.channel.sample_many(log2_ceil_usize(3));
579
580 let prodcheck_guard = tracing::debug_span!("Batched constant-base prodcheck").entered();
584 let prodcheck::BatchProveOutput {
585 eval_point: reduced_point,
586 evals: _tree_evals,
587 } = prodcheck::batch_prove(
588 vec![a_prover, c_lo_prover, c_hi_prover],
589 vec![a_root_eval, gpow_c_lo_eval, gpow_c_hi_eval],
590 selector,
591 eval_point.to_vec(),
592 self.channel,
593 );
594 drop(prodcheck_guard);
595
596 let selector_len = log2_ceil_usize(3);
600 let (r_content, _r_limb) = reduced_point[selector_len..].split_at(n_vars);
601
602 let regather_guard = tracing::debug_span!("Regather per-limb evals").entered();
606 let twists = limb_column_twists();
607 let x_tensor = eq_ind_partial_eval(r_content);
608 let limb_evals = |tree: usize| {
609 (0..N_LIMBS)
610 .map(|limb| {
611 let table = &tables[twists[tree * N_LIMBS + limb] / LIMB_BITS];
612 let n_padding = (1 << n_vars) - exponents[tree].len();
615 let column_scalars = exponents[tree]
616 .iter()
617 .map(|&word| table.get(limb_index(word, limb)))
618 .chain(iter::repeat_n(table.get(0), n_padding))
619 .collect::<Vec<_>>();
620 let column = FieldBuffer::<P>::from_values(&column_scalars);
621 inner_product_buffers(&column, &x_tensor)
622 })
623 .collect::<Vec<_>>()
624 };
625 let a_limb_evals = limb_evals(0);
626 let c_lo_limb_evals = limb_evals(1);
627 let c_hi_limb_evals = limb_evals(2);
628 drop(regather_guard);
629 self.channel.send_many(&a_limb_evals);
630 self.channel.send_many(&c_lo_limb_evals);
631 self.channel.send_many(&c_hi_limb_evals);
632
633 Phase4Output {
634 eval_point: r_content.to_vec(),
635 a_limb_evals,
636 c_lo_limb_evals,
637 c_hi_limb_evals,
638 }
639 }
640}