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}