Skip to main content

binius_prover/protocols/intmul/
prove.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use 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
50/// Proves the integer multiplication (IntMul) reduction over the four operand columns.
51///
52/// The four `columns` are the multiplicand `a`, the multiplicand `b`, and the product's low and
53/// high words, in the order `[a, b, lo, hi]`, all of equal length. This builds the [`Witness`],
54/// drives an [`IntMulProver`], and reduces the multiplication relation to per-bit evaluation claims
55/// on the four columns at a common point. See [`IntMulProver::prove`] for the protocol description
56/// and [`IntMulOutput`] for the output shape.
57///
58/// # Padding
59///
60/// The columns' length need not be a power of two. The reduction runs over the constraint axis of
61/// `2^ceil(log2(n))` rows, with the rows past the columns' end read as `Word::ZERO`; a zero row
62/// satisfies `0 * 0 = 0 || 0`, so no claim moves. The padding is never materialized as words:
63/// every buffer built from the columns spans the whole axis and derives its own padding value,
64/// which is the multiplicative identity in the product-check trees and zero elsewhere.
65///
66/// # Errors
67///
68/// Returns an error when the operand columns' lengths disagree.
69pub 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
89/// A helper structure that encapsulates the prover channel for the integer multiplication
90/// protocol.
91pub struct IntMulProver<'a, 'alloc, A: Allocator, P, Channel> {
92	_p_marker: PhantomData<P>,
93
94	channel: &'a mut Channel,
95	/// Pool the GKR working buffers are drawn from.
96	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	/// Prove an integer multiplication statement.
117	///
118	/// This method consumes a `Witness` in order to reduce integer multiplication statement to
119	/// evaluation claims on 1-bit multilinears. More formally:
120	///  * `witness` contains po2-sized integer arrays `a`, `b`, `c_lo` and `c_hi` that satisfy `a *
121	///    b = c_lo | c_hi << Word::BITS`, as well as the layers of the constant- and variable-base
122	///    GKR product check circuits
123	///  * The proving consists of five phases:
124	///    - Phase 1: GKR tree roots for B & C are evaluated at a sampled point, after which
125	///      reductions are performed to obtain evaluation claims on $(b * (G^{a_i} - 1) + 1)^{2^i}$
126	///    - Phase 2: Frobenius twist is applied to obtain claims on $b * (G^{a_i} - 1) + 1$
127	///    - Phase 3: Two batched sumchecks:
128	///      - Selector mlecheck to reduce claims on $b * (G^{a_i} - 1) + 1$ to claims on $G^{a_i}$
129	///        and $b$, then recombine the $2^k$ per-bit `b` claims into one via a sampled $r_I^b$
130	///      - First layer of GPA reduction for the `c_lo || c_hi` combined `c` tree
131	///    - Phase 4: Batched product check over the three depth-`LOG_N_LIMBS` constant-base trees
132	///      (`a`, `c_lo`, `c_hi`), reducing the roots to per-limb evaluation claims
133	///    - Phase 5: The per-limb claims are Frobenius-twisted onto the shared power table `i ↦
134	///      G^i` and read from it via a committed logup* lookup; a final batched sumcheck brings
135	///      the reduced index claim, a single-claim rerandomization (MLE-eval) of the recombined
136	///      `b` exponent claim from phase 3, and the overflow parity zerocheck to one shared point
137	///
138	/// The output of this protocol is a set of evaluation claims on the `b` selectors representing
139	/// all of `a`, `b`, `c_lo` and `c_hi` as column-major bit matrices, at a common evaluation
140	/// point. The logup* pushforward commitment carries its two relations into the channel inside
141	/// phase 5.
142	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		// `b_root` (the variable-base `b`-exponent tree root) equals the full product `c` root, so
161		// it serves as the MLE root that opens the protocol.
162		let n_vars = b_root.log_len();
163
164		let initial_eval_point = self.channel.sample_many(n_vars);
165
166		// `b_root` is not needed after this, so fold it in place rather than allocating a copy.
167		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		// Phase 1: Prodcheck reduction on b_leaves
173		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		// Phase 2
179		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		// Phase 3
186		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		// Phase 4
204		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		// Phase 5
214		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)] // exposed for benchmarking (`benches/intmul.rs`), not a stable API
228	#[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		// The exponents supply the lookup indices, the overflow zerocheck bits (`a_0`, `c_lo_0`),
237		// and the raw per-bit output evaluations.
238		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		// Twist each per-limb claim onto the shared table: column (t, l) is the Frobenius power
248		// φ^{twist} of the looked-up column U_{t,l}(x) = T[e_{t,l}(x)], so its claim becomes a
249		// claim on U_{t,l} at the twisted point.
250		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		// The columns are independent, so they gather in parallel.
260		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				// The columns' padding rows are `Word::ZERO`, whose every limb index is 0 — the
265				// shared table's row 0. So a padding row looks up `base^0 = 1`, as it does in the
266				// product-check trees.
267				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		// Read the N_LIMB_COLUMNS looked-up columns from the shared table via the committed multi-
284		// looker logup* reduction. The pushforward oracle is committed inside; its opening
285		// relations are returned to the caller. The reduction returns one index claim per column,
286		// all at the shared content point.
287		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		// The power table is succinct, so the transparent reduction runs: the pushforward is opened
296		// against the table itself instead of a sumcheck reducing the two to a shared point. Every
297		// limb column reads that one shared table.
298		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		// The index entries are the GF(2)-linear embeddings iota(e) = Σ_u basis(u) · bit_u(e),
308		// materialized by a table of all 2^LIMB_BITS embeddings.
309		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		// Collapse the per-column claims into a single claim on the eq(ρ)-folded column V by
321		// sampling ρ, so the final unification runs over the content variables only.
322		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		// Each row folds through the embedding table directly, in parallel:
330		//     V[i] = sum_j rho_tensor[j] * iota(index_j[i])
331		// so no embedded column is ever materialized.
332		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		// The overflow parity zerocheck `a_0 · b_0 − c_lo_0` runs over the low bit columns, which
350		// stay packed in words until the switchover. It binds at the Phase-2 constraint point
351		// `b_eval_point` (r_2) — reused for free from the `b` re-randomization.
352		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		// Fold the 2^k b bit-columns by the recombination tensor into a single field multilinear
361		// B(x) = sum_i eq(r_I^b, i) * b(i, x), then re-randomize its claim B(r_2) = b_recomb from
362		// `b_eval_point` (r_2) to the shared point via a single-claim MLE-eval check.
363		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		// `batch_prove` returns binding-order challenges; reversed, they are the shared output
388		// point for all output claims.
389		challenges.reverse();
390		let r_out = challenges.as_slice();
391
392		// Send the raw per-bit output evals at `r_out`, computed directly from the exponents. The
393		// verifier binds the stacked-index claim via the GF(2)-linearity of the embedding, the `b`
394		// evals via sum_i eq(r_I^b, i) * b(i, r_out) = B(r_out), and the parity bits directly.
395		let output_guard = tracing::debug_span!("Compute output bit evals").entered();
396		// All four columns fold against the same point, so the lookup tables and the per-chunk
397		// weights are built once and shared.
398		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)] // exposed for benchmarking (`benches/intmul.rs`), not a stable API
431	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		// Create initial claim
441		let claim = MultilinearEvalClaim {
442			eval: b_root_eval,
443			point: eval_point.to_vec(),
444		};
445
446		// Run prodcheck - reduces to claim on concatenated b_leaves
447		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		// Split output point: first n are x-point, last k are z-challenges
454		let (x_point, _z_suffix) = reduced_point.split_at(n_vars);
455
456		// Compute leaf evaluations at x_point
457		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		// Write leaf evaluations to channel
466		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)] // exposed for benchmarking (`benches/intmul.rs`), not a stable API
475	#[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		// Batch the 2^k Frobenius-twisted leaf claims with eq_k(γ, i): sample γ in K^k and pass the
503		// eq_k(γ, ·) weights to the selector prover, which combines its 2^k per-claim round
504		// polynomials into a single weighted one. This replaces a univariate-power batch over the
505		// 2^k claims with a multilinear one; the verifier mirrors it by weighting the corresponding
506		// terms by eq_k(γ, ·). γ is sampled before the batched sumcheck so the round polynomials
507		// are fixed against it.
508		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		// `batch_prove` returns binding-order challenges; reverse to variable-indexed to match
525		// the verifier's phase-3 evaluation point.
526		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		// Recombine the 2^k per-bit b(i, r) claims into a single claim b(r_I^b, r) by sampling a
544		// recombination point r_I^b in K^k, matching the verifier. This carries one exponent claim
545		// (rather than 2^k) into Phases 4 and 5.
546		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)] // exposed for benchmarking (`benches/intmul.rs`), not a stable API
560	#[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		// Each prover is over the full (widest) leaf layer of `N_LIMBS` limb columns.
573		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		// Sample the selector challenges that batch the 3 trees (padded to 4).
578		let selector = self.channel.sample_many(log2_ceil_usize(3));
579
580		// Run the batched prodcheck over all LOG_N_LIMBS layers: content point is the Phase-3
581		// evaluation point at which the three roots are claimed. The output pairs each tree with
582		// its reduced leaf evaluation at the shared reduced point.
583		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		// The reduced point is [selector (2), r_content (n_vars), r_limb (LOG_N_LIMBS)]:
597		// `r_content` is the shared point at which the limb columns are claimed; `r_limb`
598		// collapses the limb dimension.
599		let selector_len = log2_ceil_usize(3);
600		let (r_content, _r_limb) = reduced_point[selector_len..].split_at(n_vars);
601
602		// Send the per-limb evaluations at `r_content`, computed by re-gathering each limb column
603		// from its twisted power table. The verifier recombines each tree's two leaf halves via
604		// eq(r_limb) to bind them to the final-layer sumchecks.
605		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					// As in `limb_leaves`, the columns' padding rows are `Word::ZERO`, which
613					// indexes row 0 of the table — `base^0 = 1`.
614					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}