Skip to main content

binius_verifier/protocols/intmul/
verify.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use std::iter;
5
6use binius_core::word::Word;
7use binius_field::{BinaryField, Field, field::FieldOps};
8use binius_iop::{
9	channel::IOPVerifierChannel,
10	logup_star::{self, TransparentTableLookup},
11};
12use binius_ip::{
13	channel::IPVerifierChannel,
14	logup_star::{LookerClaim, TableLookup},
15	prodcheck::{self, MultilinearEvalClaim},
16	sumcheck::{BatchSumcheckOutput, batch_verify},
17};
18use binius_math::{
19	multilinear::{eq::eq_ind, evaluate::evaluate_inplace_scalars},
20	univariate::evaluate_univariate,
21};
22use binius_utils::checked_arithmetics::log2_ceil_usize;
23
24use super::{
25	common::{
26		IntMulOutput, LIMB_BITS, LOG_N_LIMBS, N_LIMB_COLUMNS, N_LIMBS, Phase1Output, Phase2Output,
27		Phase3Output, Phase4Output, eval_power_table_mle, frobenius_twist, limb_column_twists,
28		twist_limb_claim,
29	},
30	error::Error,
31};
32
33/// Verify Phase 1: GKR step on the exponentiation product tree.
34///
35/// Runs prodcheck verification to reduce the root claim on $\widetilde{Q}$ to $2^k$ leaf
36/// evaluation claims, then verifies the leaf evaluations against the prover's claimed values.
37fn verify_phase_1<F, C>(
38	initial_eval_point: &[C::Elem],
39	initial_b_eval: C::Elem,
40	channel: &mut C,
41) -> Result<Phase1Output<C::Elem>, Error>
42where
43	F: Field,
44	C: IPVerifierChannel<F>,
45{
46	let n_vars = initial_eval_point.len();
47
48	// Run prodcheck verification
49	let claim = MultilinearEvalClaim {
50		eval: initial_b_eval,
51		point: initial_eval_point.to_vec(),
52	};
53	let output_claim = prodcheck::verify(Word::LOG_BITS, claim, channel)?;
54
55	// Split output point: first n are x-point, last k are z-challenges
56	let (eval_point, z_suffix) = output_claim.point.split_at(n_vars);
57
58	// Read 2^k leaf evaluations from channel
59	let b_leaves_evals = channel.recv_many(Word::BITS)?;
60
61	// Verify: output_claim.eval = multilinear_eval(b_leaves_evals, z_suffix)
62	// The leaf evals form a multilinear over Word::LOG_BITS variables; evaluate at z_suffix
63	let expected_eval = evaluate_inplace_scalars(b_leaves_evals.clone(), z_suffix);
64
65	channel.assert_zero(expected_eval - output_claim.eval)?;
66
67	Ok(Phase1Output {
68		eval_point: eval_point.to_vec(),
69		b_leaves_evals,
70	})
71}
72
73/// Verify Phase 3: batched Frobenius selector sumcheck and LO * HI product sumcheck.
74///
75/// Batches two sumchecks: (a) the Frobenius-twisted selector sumcheck reducing the Phase 2
76/// claims to exponent evaluations on $\widetilde{b}$ and a selector on $\widetilde{P}$, and
77/// (b) the product claim $\widetilde{\textsf{LO}} \cdot \widetilde{\textsf{HI}}$.
78fn verify_phase_3<F, C>(
79	twisted_eval_points: Vec<Vec<C::Elem>>,
80	twisted_evals: Vec<C::Elem>,
81	c_eval_point: &[C::Elem],
82	c_eval: C::Elem,
83	channel: &mut C,
84) -> Result<Phase3Output<C::Elem>, Error>
85where
86	F: Field,
87	C: IPVerifierChannel<F>,
88{
89	let n_vars = c_eval_point.len();
90
91	assert_eq!(twisted_eval_points.len(), Word::BITS);
92
93	for twisted_eval_point in &twisted_eval_points {
94		assert_eq!(twisted_eval_point.len(), c_eval_point.len());
95	}
96
97	// Batch the 2^k Frobenius-twisted leaf claims with eq_k(γ, i): sample γ in K^k and take the
98	// multilinear evaluation of the 2^k claims at γ, matching the prover's CombineClaimsDecorator.
99	// The aggregate and the LO·HI claim are then combined into the same sumcheck by the univariate
100	// batch coefficient. γ is sampled before the sumcheck so its round polynomials are fixed
101	// against it.
102	//
103	// The two batched terms (each degree 3) are:
104	// - the 2^k aggregate: Σ_i eq_k(γ, i) * (b(i, X) * (A(X) - 1) + 1) * eq(φ⁻ⁱ(x) ; X)
105	// - LO(X) * HI(X) * eq(c_eval_point ; X)
106	let gamma = channel.sample_many(Word::LOG_BITS);
107	let selector_agg_eval = evaluate_inplace_scalars(twisted_evals, &gamma);
108	let evals = [selector_agg_eval, c_eval];
109
110	let BatchSumcheckOutput {
111		batch_coeff,
112		mut challenges,
113		eval,
114	} = batch_verify(n_vars, 3, &evals, channel)?;
115	challenges.reverse();
116
117	// b(i, r) for i in 0..2^k
118	let b_evals = channel.recv_many(Word::BITS)?;
119
120	// A(r)
121	let gpow_a_eval = channel.recv_one()?;
122
123	// C_lo(r), C_hi(r)
124	let [gpow_c_lo_eval, gpow_c_hi_eval] = channel.recv_array::<2>()?;
125
126	// Recombine the 2^k per-bit exponent claims b(i, r) into a single claim b(r_I^b, r) by
127	// sampling a recombination point r_I^b in K^k. This carries one exponent claim (rather than
128	// 2^k) into Phases 4 and 5.
129	let r_ib = channel.sample_many(Word::LOG_BITS);
130	let b_recomb = evaluate_inplace_scalars(b_evals.clone(), &r_ib);
131
132	let eval_point = challenges;
133
134	let expected_selected_terms = iter::zip(twisted_eval_points, &b_evals)
135		.map(|(twisted_eval_point, b_eval)| {
136			let one = C::Elem::one();
137			(b_eval.clone() * (gpow_a_eval.clone() - one.clone()) + one)
138				* eq_ind(&twisted_eval_point, &eval_point)
139		})
140		.collect::<Vec<_>>();
141	// Combine the 2^k selector terms with eq_k(γ, i) — the multilinear evaluation at γ — mirroring
142	// the prover's CombineClaimsDecorator.
143	let expected_selected_agg = evaluate_inplace_scalars(expected_selected_terms, &gamma);
144
145	// - c_lo(r) * c_hi(r) * eq(c_eval_point ; r)
146	let expected_c_prod_eval =
147		gpow_c_lo_eval.clone() * gpow_c_hi_eval.clone() * eq_ind(c_eval_point, &eval_point);
148
149	let expected_terms = [expected_selected_agg, expected_c_prod_eval];
150	let expected_batched_eval = evaluate_univariate(&expected_terms, &batch_coeff);
151
152	channel.assert_zero(expected_batched_eval - eval)?;
153
154	Ok(Phase3Output {
155		eval_point,
156		r_ib,
157		b_recomb,
158		gpow_a_eval,
159		gpow_c_lo_eval,
160		gpow_c_hi_eval,
161	})
162}
163
164/// Verify Phase 4: the GKR product trees for $\widetilde{a}$, $\widetilde{c}_{\textsf{lo}}$, and
165/// $\widetilde{c}_{\textsf{hi}}$, reduced to per-limb evaluation claims.
166///
167/// Each tree's leaf layer is the concatenation of its `N_LIMBS` limb columns. A single batched
168/// prodcheck over the three trees (batched with $\lceil \log_2 3 \rceil = 2$ selector variables)
169/// runs the all-but-last reduction layer; the final (widest) layer of each tree is then proven by
170/// a batched bivariate-product sumcheck seeded by the three per-tree reduced claims. The prover
171/// sends the per-limb evaluations at the shared content point, which the verifier binds to the
172/// final-layer sumcheck by recombining each tree's two leaf halves via `eq(r_limb)`.
173fn verify_phase_4<F, C>(
174	eval_point: &[C::Elem],
175	a_root_eval: C::Elem,
176	gpow_c_lo_eval: C::Elem,
177	gpow_c_hi_eval: C::Elem,
178	channel: &mut C,
179) -> Result<Phase4Output<C::Elem>, Error>
180where
181	F: Field,
182	C: IPVerifierChannel<F>,
183{
184	let n_vars = eval_point.len();
185
186	let log_n_trees = log2_ceil_usize(3); // = 2 selector variables
187
188	// Sample the selector challenges that batch the three trees (padded to 4).
189	let selector = channel.sample_many(log_n_trees);
190
191	// Combined initial claim: eq(selector)-weighted sum of the three root evals (padded to 4 with a
192	// zero), at the point selector ++ eval_point (the Phase-3 content point).
193	let root_evals = vec![a_root_eval, gpow_c_lo_eval, gpow_c_hi_eval, C::Elem::zero()];
194	let combined_root_eval = evaluate_inplace_scalars(root_evals, &selector);
195
196	let claim = MultilinearEvalClaim {
197		eval: combined_root_eval,
198		point: [selector, eval_point.to_vec()].concat(),
199	};
200
201	// Run the batched prodcheck verification over all LOG_N_LIMBS layers.
202	let output_claim = prodcheck::verify(LOG_N_LIMBS, claim, channel)?;
203
204	// The reduced point is [selector (log_n_trees), r_content (n_vars), r_limb (LOG_N_LIMBS)]:
205	//  - selector: the batching coordinates for the three trees, reduced through the selector
206	//    rounds,
207	//  - r_content: the shared point at which the limb columns are claimed,
208	//  - r_limb: the limb-index coordinates of each tree's leaf layer.
209	assert_eq!(output_claim.point.len(), log_n_trees + n_vars + LOG_N_LIMBS);
210	let (selector_point, rest) = output_claim.point.split_at(log_n_trees);
211	let (r_content, r_limb) = rest.split_at(n_vars);
212
213	// The prover sends the per-limb evaluations at r_content for each tree. Each tree's leaf
214	// multilinear stacks its limb columns over the limb coordinates, so its evaluation is the
215	// eq(r_limb)-fold of the per-limb evals; the batched output claim is the eq(selector)-weighted
216	// combination of the tree evaluations (the padding tree slot is zero).
217	let a_limb_evals = channel.recv_many(N_LIMBS)?;
218	let c_lo_limb_evals = channel.recv_many(N_LIMBS)?;
219	let c_hi_limb_evals = channel.recv_many(N_LIMBS)?;
220
221	let tree_eval = |limb_evals: &[C::Elem]| evaluate_inplace_scalars(limb_evals.to_vec(), r_limb);
222	let per_tree = vec![
223		tree_eval(&a_limb_evals),
224		tree_eval(&c_lo_limb_evals),
225		tree_eval(&c_hi_limb_evals),
226		C::Elem::zero(),
227	];
228	let combined = evaluate_inplace_scalars(per_tree, selector_point);
229	channel.assert_zero(combined - output_claim.eval)?;
230
231	Ok(Phase4Output {
232		eval_point: r_content.to_vec(),
233		a_limb_evals,
234		c_lo_limb_evals,
235		c_hi_limb_evals,
236	})
237}
238
239/// Verify Phase 5: the logup* fixed-base exponentiation lookup, $\widetilde{b}$ rerandomization,
240/// and parity zerocheck.
241///
242/// The per-limb claims from Phase 4 are Frobenius-twisted onto the shared table of generator
243/// powers `i ↦ g^i`, batched to a single stacked lookup claim, and read from the table via a
244/// committed logup* reduction. The table is succinct, so the reduction's transparent variant runs:
245/// the pushforward oracle carries both its claims into the channel opening, one against `eq_z` and
246/// one against the table's own MLE, and no table claim is left over. The reduced index claims are
247/// carried into a final batched sumcheck — together with the $\widetilde{b}(r_I^b, \cdot)$
248/// rerandomization and the parity zerocheck $a_0 \cdot b_0 = c_{\textsf{lo},0}$ — that brings every
249/// output claim to one shared point.
250fn verify_phase_5<F, C>(
251	phase_4_output: &Phase4Output<C::Elem>,
252	b_eval_point: &[C::Elem],
253	r_ib: &[C::Elem],
254	b_recomb: C::Elem,
255	channel: &mut C,
256) -> Result<IntMulOutput<C::Elem>, Error>
257where
258	F: BinaryField,
259	C: IOPVerifierChannel<F>,
260	C::Elem: FieldOps<Scalar = F> + From<F>,
261{
262	let n_vars = b_eval_point.len();
263	assert_eq!(phase_4_output.eval_point.len(), n_vars);
264
265	// Twist the per-limb claims onto the shared table: column (t, l) is the Frobenius power
266	// φ^{twist} of the looked-up column U_{t,l}(x) = T[e_{t,l}(x)], so its claim becomes a claim on
267	// U_{t,l} at the twisted point.
268	let twists = limb_column_twists();
269	let limb_evals = [
270		&phase_4_output.a_limb_evals,
271		&phase_4_output.c_lo_limb_evals,
272		&phase_4_output.c_hi_limb_evals,
273	];
274	let twisted_claims = iter::zip(&twists, limb_evals.into_iter().flatten())
275		.map(|(&twist, eval)| twist_limb_claim(twist, &phase_4_output.eval_point, eval.clone()))
276		.collect::<Vec<_>>();
277
278	// Read the N_LIMB_COLUMNS looked-up columns from the shared table via the committed multi-
279	// looker logup* reduction. The pushforward oracle is received inside; its opening relations are
280	// returned to the caller. The reduction returns one index claim per column, all at the shared
281	// content point.
282	let looker_claims = twisted_claims
283		.iter()
284		.map(|(twisted_point, twisted_eval)| LookerClaim {
285			eval_point: twisted_point,
286			eval_claim: twisted_eval.clone(),
287		})
288		.collect::<Vec<_>>();
289	let log_cols = log2_ceil_usize(N_LIMB_COLUMNS);
290	// The power table is succinct, so the transparent reduction runs: it weighs the pushforward
291	// against the table's own MLE in the oracle opening rather than through a sumcheck, which
292	// leaves no table claim to check here. Every limb column reads that one shared table.
293	let logup_proof = logup_star::verify_transparent::<F, C>(
294		[TransparentTableLookup {
295			lookup: TableLookup {
296				n_vars: LIMB_BITS,
297				lookers: looker_claims,
298			},
299			table_eval: Box::new(eval_power_table_mle::<F, C::Elem>),
300		}],
301		channel,
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 reduction hands back the per-column embedded-index claims directly, all at the shared
308	// content point (padding columns read row 0, whose embedding is zero).
309	let index_content_point = logup_proof.index_eval_point.as_slice();
310	let mut padded_column_evals = column_index_evals.clone();
311	padded_column_evals.resize(1 << log_cols, C::Elem::zero());
312
313	// Collapse the per-column claims into a single claim on the eq(ρ)-folded column V by sampling
314	// ρ, so the final unification runs over the content variables only.
315	let rho = channel.sample_many(log_cols);
316	let folded_index_claim = evaluate_inplace_scalars(padded_column_evals, &rho);
317
318	// Final unification: one batched sumcheck brings the folded index claim, the recombined b
319	// exponent claim, and the parity zerocheck to a shared output point.
320	let evals = [folded_index_claim, C::Elem::zero(), b_recomb];
321	let BatchSumcheckOutput {
322		batch_coeff,
323		mut challenges,
324		eval,
325	} = batch_verify(n_vars, 3, &evals, channel)?;
326	challenges.reverse();
327	let r_out = challenges.as_slice();
328
329	// The prover sends the raw per-bit evaluations at r_out.
330	let a_evals = channel.recv_array::<{ Word::BITS }>()?;
331	let c_lo_evals = channel.recv_array::<{ Word::BITS }>()?;
332	let c_hi_evals = channel.recv_array::<{ Word::BITS }>()?;
333	let b_evals = channel.recv_array::<{ Word::BITS }>()?;
334
335	// Bind the per-bit evals to the folded index claim. The index entries are the GF(2)-linear
336	// embeddings iota(e_{t,l}) = Σ_u basis(u) · bit_u(e_{t,l}), and bit u of limb l is bit
337	// (LIMB_BITS·l + u) of the word, so each column's MLE is a fixed basis-weighted combination of
338	// the word's per-bit column MLEs.
339	let per_word_evals = [&a_evals, &c_lo_evals, &c_hi_evals];
340	let mut column_evals = (0..N_LIMB_COLUMNS)
341		.map(|j| {
342			let (tree, limb) = (j / N_LIMBS, j % N_LIMBS);
343			(0..LIMB_BITS)
344				.map(|u| {
345					let basis = F::basis(u);
346					per_word_evals[tree][limb * LIMB_BITS + u].clone() * C::Elem::from(basis)
347				})
348				.fold(C::Elem::zero(), |acc, term| acc + term)
349		})
350		.collect::<Vec<_>>();
351	column_evals.resize(1 << log_cols, C::Elem::zero());
352	let folded_index_eval = evaluate_inplace_scalars(column_evals, &rho);
353	let expected_index_eval = eq_ind(index_content_point, r_out) * folded_index_eval;
354
355	let b_eq_eval = eq_ind(b_eval_point, r_out);
356
357	// We must check that `a_0 * b_0 = c_lo_0` across all rows, where these represent the least
358	// significant bits of `a_exponents`, `b_exponents`, and `c_lo_exponents` respectively.
359	// This check is performed in GF(2) (interpreting bits as field elements 0 and 1).
360	//
361	// Purpose: This prevents an attack when `a*b = 0` (due to `a=0` or `b=0`). A malicious
362	// prover could set `c = 2^128 - 1`, which satisfies `a*b ≡ c (mod 2^128-1)` since
363	// `0 ≡ 2^128-1 (mod 2^128-1)`. However, we need `a*b = c (mod 2^128)` where `0 ≠ 2^128-1`.
364	// This check catches the attack: if `c = 2^128-1` then `c_lo_0 = 1` (since 2^128-1 is odd),
365	// but `a_0 * b_0 = 0` when `a=0` or `b=0`, so the check `a_0 * b_0 = c_lo_0` fails.
366	//
367	// Implementation: A zerocheck on `a_0 * b_0 - c_lo_0 = 0`, reusing the Phase-2 constraint point
368	// `b_eval_point` (r_2) as the zerocheck challenge — available for free because the `b`
369	// re-randomization already evaluates at r_2.
370	let expected_overflow_eval =
371		b_eq_eval.clone() * (a_evals[0].clone() * &b_evals[0] - &c_lo_evals[0]);
372
373	// Bind the prover's raw per-bit evals to the single recombined rerandomization claim:
374	// b(r_I^b, r_out) = sum_i eq(r_I^b, i) * b(i, r_out).
375	let b_at_rx = evaluate_inplace_scalars(&mut b_evals.clone()[..], r_ib);
376	let expected_b_rerand_eval = b_eq_eval * &b_at_rx;
377
378	let expected_unbatched_evals = [
379		expected_index_eval,
380		expected_overflow_eval,
381		expected_b_rerand_eval,
382	];
383	let expected_batched_eval = evaluate_univariate(&expected_unbatched_evals, &batch_coeff);
384
385	// Compare expected evaluation against given evaluation `eval`.
386	channel.assert_zero(expected_batched_eval - eval)?;
387
388	Ok(IntMulOutput {
389		eval_point: r_out.to_vec(),
390		a_evals,
391		b_evals,
392		c_lo_evals,
393		c_hi_evals,
394	})
395}
396
397/// Verify the integer multiplication check (IntMul) protocol.
398///
399/// The IntMul protocol is a reduction that checks a relation on four virtual multilinear
400/// polynomials: $\widetilde{a}, \widetilde{b}, \widetilde{c}_{\textsf{lo}},
401/// \widetilde{c}_{\textsf{hi}}$. These multilinear polynomials are over $\mathbb{F}_2$ and have
402/// $k + n$ variables. We write $a, b, c_{\textsf{lo}}, c_{\textsf{hi}} \in \mathbb{F}_2^{n \times
403/// k}$ for their boolean hypercube evaluations. Let $\textsf{int}(M) \in \mathbb{N}^n$ map one of
404/// the four matrices, $M$, to a vector of their interpretations as a $k$-bit unsigned integer. That
405/// is, it embeds the $\mathbb{F}_2$ elements into $\mathbb{N}$ and multiplies by $(2^0, 2^1,
406/// \ldots, 2^{k-1})$.
407///
408/// ## Protocol
409///
410/// The IntMul protocol reduces this relation to claims on the partial multilinear evaluations of
411/// $\widetilde{a}, \widetilde{b}, \widetilde{c}_{\textsf{lo}}, \widetilde{c}_{\textsf{hi}}$ at a
412/// common $n$-coordinate random evaluation point.
413///
414/// ### Exponentiation identity
415///
416/// The core technique reduces integer multiplication to field arithmetic via exponentiation. Let
417/// $g$ be a generator of the multiplicative group of $\mathbb{F}_{2^{2k}}$, which has order
418/// $2^{2k} - 1$. Then $\textsf{int}(a) \cdot \textsf{int}(b) = \textsf{int}(c_{\textsf{hi}})
419/// \cdot 2^k + \textsf{int}(c_{\textsf{lo}})$ over the integers is equivalent to
420///
421/// $$\widetilde{Q}(x) = \widetilde{\textsf{LO}}(x) \cdot \widetilde{\textsf{HI}}(x) \quad
422/// \forall x \in \{0, 1\}^n$$
423///
424/// where $\widetilde{Q}$ is obtained by exponentiating $g^{\widetilde{a}}$ by $\widetilde{b}$,
425/// $\widetilde{\textsf{LO}} = g^{\widetilde{c}_{\textsf{lo}}}$, and $\widetilde{\textsf{HI}} =
426/// (g^{2^k})^{\widetilde{c}_{\textsf{hi}}}$.
427///
428/// There is a wraparound edge case: when $a \cdot b = 0$, a malicious prover could set
429/// $c_{\textsf{hi}} \| c_{\textsf{lo}} = 2^{2k} - 1$, which satisfies the exponentiation
430/// identity modulo $2^{2k} - 1$ but not over the integers. A parity check on the least
431/// significant bits ($a_0 \cdot b_0 = c_{\textsf{lo},0}$) rules this out.
432///
433/// ### Phases
434///
435/// - **Phase 1 — GKR step on $\widetilde{Q}$:** The verifier samples a random evaluation point $r$
436///   and the prover sends the claimed evaluation $s = \widetilde{Q}(r)$. The parties run a GKR step
437///   ($k$-layer balanced binary tree of bivariate products) reducing $s$ to $2^k$ leaf claims
438///   $s'_{Q,i} = \widetilde{Q_i}(r')$.
439///
440/// - **Phase 2 — Frobenius step:** The verifier applies $\varphi^{-i}$ (inverse Frobenius) to each
441///   leaf claim, reducing degree-$2^i$ expressions to degree-1. This is a local verifier
442///   computation with no interaction.
443///
444/// - **Phase 3 — Batched Frobenius sumcheck + $\widetilde{\textsf{LO}} \cdot
445///   \widetilde{\textsf{HI}}$ product sumcheck:** Two sumchecks batched into one: (a) The
446///   Frobenius-twisted selector sumcheck on the $\widetilde{Q_i}$ claims, reducing to claims on
447///   $\widetilde{b}$ exponent evaluations and the base $\widetilde{P}$ (i.e. $g^{\widetilde{a}}$).
448///   (b) The deferred product claim $s = \sum \textsf{eq}(r, x) \cdot \widetilde{\textsf{LO}}(x)
449///   \cdot \widetilde{\textsf{HI}}(x)$. This yields root claims on $\widetilde{P}$ (the
450///   $\widetilde{a}$ selector), $\widetilde{\textsf{LO}}$, $\widetilde{\textsf{HI}}$, plus $2^k$
451///   exponent claims on $\widetilde{b}$. The verifier then samples a recombination point $r_I^b \in
452///   K^k$ and collapses the $2^k$ exponent claims into a single claim $\widetilde{b}(r_I^b, r) =
453///   \sum_i \textsf{eq}(r_I^b, i) \cdot \widetilde{b}(i, r)$, carried into Phases 4 and 5.
454///
455/// - **Phase 4 — GKR on $\widetilde{a}$, $\widetilde{c}_{\textsf{lo}}$,
456///   $\widetilde{c}_{\textsf{hi}}$, down to per-limb claims:** Each exponent word splits into
457///   `N_LIMBS` limbs, so each of the three constant-base exponentiations factors as a product of
458///   `N_LIMBS` limb columns. A batched GKR product check over the three (depth-`LOG_N_LIMBS`) trees
459///   reduces the root claims to one evaluation claim per limb column at a shared content point.
460///
461/// - **Phase 5 — logup* lookup + $\widetilde{b}$ rerandomization + parity check:** Limb column $(t,
462///   l)$ is the Frobenius power $\varphi^{ws}$ of the looked-up column $T[e_{t,l}(\cdot)]$ over the
463///   shared table $T\colon i \mapsto g^i$ of $2^w$ generator powers (where $w$ is the limb bit
464///   width). The per-limb claims are Frobenius-twisted onto $T$, batched to one stacked lookup
465///   claim, and reduced via committed logup* ([Soukhanov25]): the pushforward oracle is committed
466///   mid-protocol and its two opening relations returned to the caller, the second weighing it
467///   against the table's succinct product-of-selects MLE, so the table needs no claim of its own;
468///   the index claim is bound to the per-bit output evals in a final batched sumcheck, together
469///   with (a) a single-claim rerandomization of the recombined $\widetilde{b}(r_I^b, \cdot)$
470///   exponent claim from Phase 3 and (b) a zerocheck verifying $a_0 \cdot b_0 = c_{\textsf{lo},0}$
471///   (least significant bits), ruling out the wraparound edge case.
472///
473/// [Soukhanov25]: <https://eprint.iacr.org/2025/946>
474///
475/// ### Output
476///
477/// The protocol outputs evaluation claims on $\widetilde{a}_i$, $\widetilde{b}_i$,
478/// $\widetilde{c}_{\textsf{lo},i}$, $\widetilde{c}_{\textsf{hi},i}$ (for $i \in \{0, \ldots,
479/// 2^k - 1\}$) at a common $n$-dimensional evaluation point. The claims are passed to the shift
480/// reduction; the logup* pushforward commitment carries its two relations into the channel inside
481/// phase 5.
482///
483/// ### Parameters
484///
485/// - `n_vars`: Number of variables in the row dimension — the $\log_2$ of the operand column
486///   length, which the prover zero-pads up to a power of two. The single-instance verifier passes
487///   $\lceil \log_2 n \rceil$ for $n$ IMUL constraints; the batched M4 verifier adds its $\log_2$
488///   instance count.
489///
490/// The integer operands are fixed at the `Word::BITS` bit width.
491pub fn verify<F, C>(n_vars: usize, channel: &mut C) -> Result<IntMulOutput<C::Elem>, Error>
492where
493	F: BinaryField,
494	C: IOPVerifierChannel<F>,
495	C::Elem: FieldOps<Scalar = F> + From<F>,
496{
497	const {
498		assert!(2 * Word::BITS <= F::N_BITS, "F must be wide enough to hold a 128-bit product");
499	}
500
501	let initial_eval_point = channel.sample_many(n_vars);
502
503	// Read the evaluation of the multilinear extension of the powers of the generator.
504	let exp_eval = channel.recv_one()?;
505
506	// Phase 1
507	let Phase1Output {
508		eval_point: phase_1_eval_point,
509		b_leaves_evals,
510	} = verify_phase_1(&initial_eval_point, exp_eval.clone(), channel)?;
511
512	assert_eq!(phase_1_eval_point.len(), n_vars);
513	assert_eq!(b_leaves_evals.len(), Word::BITS);
514
515	// Phase 2
516	let Phase2Output {
517		twisted_eval_points,
518		twisted_evals,
519	} = frobenius_twist(Word::LOG_BITS, &phase_1_eval_point, &b_leaves_evals);
520
521	// Phase 3
522	let Phase3Output {
523		eval_point: phase_3_eval_point,
524		r_ib,
525		b_recomb,
526		gpow_a_eval,
527		gpow_c_lo_eval,
528		gpow_c_hi_eval,
529	} = verify_phase_3(twisted_eval_points, twisted_evals, &initial_eval_point, exp_eval, channel)?;
530
531	// Phase 4
532	let phase_4_output =
533		verify_phase_4(&phase_3_eval_point, gpow_a_eval, gpow_c_lo_eval, gpow_c_hi_eval, channel)?;
534
535	// Phase 5
536	verify_phase_5(&phase_4_output, &phase_3_eval_point, &r_ib, b_recomb, channel)
537}