binius_verifier/protocols/intmul/common.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::FieldOps};
8use itertools::iterate;
9
10use crate::protocols::rerand::OperandClaims;
11
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct IntMulOutput<F> {
14 pub eval_point: Vec<F>,
15 pub a_evals: [F; Word::BITS],
16 pub b_evals: [F; Word::BITS],
17 pub c_lo_evals: [F; Word::BITS],
18 pub c_hi_evals: [F; Word::BITS],
19}
20
21impl<F> IntMulOutput<F> {
22 /// The operand claims, in the shift operand order `[a, b, c_lo, c_hi]`.
23 pub fn operand_claims(&self) -> OperandClaims<'_, F> {
24 OperandClaims {
25 point: &self.eval_point,
26 columns: vec![
27 &self.a_evals,
28 &self.b_evals,
29 &self.c_lo_evals,
30 &self.c_hi_evals,
31 ],
32 }
33 }
34}
35
36/// Output of Phase 1: GKR reduction of the exponentiation product tree.
37///
38/// Contains the evaluation point after prodcheck and the $2^k$ leaf evaluations of
39/// $\widetilde{Q_i}$.
40pub struct Phase1Output<F> {
41 pub eval_point: Vec<F>,
42 pub b_leaves_evals: Vec<F>,
43}
44
45pub struct Phase2Output<F> {
46 pub twisted_eval_points: Vec<Vec<F>>,
47 pub twisted_evals: Vec<F>,
48}
49
50/// Output of Phase 3: batched Frobenius selector sumcheck and LO * HI product sumcheck.
51///
52/// Contains the new evaluation point $r$, the recombined $\widetilde{b}$ exponent claim, $A(r)$,
53/// $C_{\textsf{lo}}(r)$, and $C_{\textsf{hi}}(r)$.
54#[derive(Debug, Clone)]
55pub struct Phase3Output<F> {
56 pub eval_point: Vec<F>,
57 /// The recombination point $r_I^b \in K^k$ sampled to collapse the $2^k$ per-bit
58 /// $\widetilde{b}$ claims into one.
59 pub r_ib: Vec<F>,
60 /// The recombined exponent claim $\widetilde{b}(r_I^b, r)$, where $r$ is `eval_point`.
61 pub b_recomb: F,
62 /// $A(r)$, where $r$ is `eval_point`.
63 pub gpow_a_eval: F,
64 /// $C_{\textsf{lo}}(r)$.
65 pub gpow_c_lo_eval: F,
66 /// $C_{\textsf{hi}}(r)$.
67 pub gpow_c_hi_eval: F,
68}
69
70/// The log2 of the number of limbs each exponent word is split into for the Phase 4/5 fixed-base
71/// lookup.
72pub const LOG_N_LIMBS: usize = 2;
73
74/// The number of exponent limbs per word.
75pub const N_LIMBS: usize = 1 << LOG_N_LIMBS;
76
77/// The bit width of one exponent limb; the lookup table has `2^LIMB_BITS` rows.
78pub const LIMB_BITS: usize = 1 << (Word::LOG_BITS - LOG_N_LIMBS);
79
80/// The number of looked-up limb columns: one per limb of $\widetilde{a}$,
81/// $\widetilde{c}_{\textsf{lo}}$, and $\widetilde{c}_{\textsf{hi}}$.
82pub const N_LIMB_COLUMNS: usize = 3 * N_LIMBS;
83
84/// Output of Phase 4: the three constant-base GKR product trees reduced to per-limb evaluation
85/// claims.
86///
87/// Each tree's leaf layer is the concatenation of its `N_LIMBS` limb columns; Phase 4 reduces the
88/// three roots to one evaluation claim per limb column at the shared content point `eval_point`.
89pub struct Phase4Output<F> {
90 /// The shared content point at which the limb columns are claimed.
91 pub eval_point: Vec<F>,
92 /// The `N_LIMBS` per-limb evaluations of the $\widetilde{a}$ tree leaf columns.
93 pub a_limb_evals: Vec<F>,
94 /// The `N_LIMBS` per-limb evaluations of the $\widetilde{c}_{\textsf{lo}}$ tree leaf columns.
95 pub c_lo_limb_evals: Vec<F>,
96 /// The `N_LIMBS` per-limb evaluations of the $\widetilde{c}_{\textsf{hi}}$ tree leaf columns.
97 pub c_hi_limb_evals: Vec<F>,
98}
99
100/// Compute the inverse Frobenius endomorphism $\varphi^{-i}(x)$.
101///
102/// The Frobenius endomorphism on $\mathbb{F}_{2^d}$ is $\varphi(x) = x^2$, so $\varphi^i(x) =
103/// x^{2^i}$. Its order is $d$ (the extension degree), meaning $\varphi^d = \textsf{id}$.
104/// Therefore $\varphi^{-i} = \varphi^{d - i}$, and we compute $\varphi^{-i}(x) = x^{2^{d-i}}$
105/// by repeated squaring $d - i$ times.
106fn inv_frobenius<F>(x: F, i: usize) -> F
107where
108 F: FieldOps,
109 F::Scalar: BinaryField,
110{
111 let degree = F::Scalar::N_BITS;
112 iterate(x, |g| g.clone().square())
113 .nth(degree - i)
114 .expect("infinite iterator")
115}
116
117/// Compute the inverse Frobenius sequence $[\varphi^{0}(x), \varphi^{-1}(x), \ldots,
118/// \varphi^{-(n-1)}(x)]$ where $d$ is the extension degree of $\mathbb{F}_{2^d}$.
119fn inv_frobenius_sequence<F>(x: F, n: usize) -> Vec<F>
120where
121 F: FieldOps,
122 F::Scalar: BinaryField,
123{
124 let degree = F::Scalar::N_BITS;
125 assert!(n <= degree + 1);
126 let mut seq: Vec<F> = iterate(x, |g| g.clone().square())
127 .take(degree + 1)
128 .collect();
129 seq.reverse();
130 seq.truncate(n);
131 seq
132}
133
134/// Apply inverse Frobenius twists to the leaf evaluation claims from Phase 1.
135///
136/// This reduces $2^k$ evaluation claims on $2^k$ separate multilinears $\widetilde{Q_i}$ at a
137/// shared point $r$ to $2^k$ claims on a single multilinear $\widetilde{P}$ at $2^k$ different
138/// points. Concretely, given claims $(r, s_i)$ where $s_i = \widetilde{Q_i}(r)$ and
139/// $\widetilde{Q_i}(x) = \widetilde{P}(x)^{2^i}$, this applies $\varphi^{-i}$ (the inverse
140/// Frobenius endomorphism) to both the evaluation point and the evaluation value. This linearizes
141/// the degree-$2^i$ relation into a degree-1 claim: $\varphi^{-i}(s_i) =
142/// \widetilde{P}(\varphi^{-i}(r))$, since $\varphi^{-i}(x^{2^i}) = x$ in $\mathbb{F}_{2^d}$.
143///
144/// # Arguments
145///
146/// * `k` - The log of the bit-width; there are $2^k$ leaf claims.
147/// * `eval_point` - The shared evaluation point $r$.
148/// * `evals` - The $2^k$ evaluations $s_0, \ldots, s_{2^k - 1}$.
149pub fn frobenius_twist<F>(k: usize, eval_point: &[F], evals: &[F]) -> Phase2Output<F>
150where
151 F: FieldOps,
152 F::Scalar: BinaryField,
153{
154 let n = 1 << k;
155 assert_eq!(evals.len(), n);
156
157 // Precompute inv_frobenius_sequence for each coordinate in eval_point.
158 let coord_seqs: Vec<Vec<F>> = eval_point
159 .iter()
160 .map(|coord| inv_frobenius_sequence(coord.clone(), n))
161 .collect();
162
163 let twisted_eval_points = (0..n)
164 .map(|i| coord_seqs.iter().map(|seq| seq[i].clone()).collect())
165 .collect();
166
167 let twisted_evals = evals
168 .iter()
169 .enumerate()
170 .map(|(i, eval)| inv_frobenius(eval.clone(), i))
171 .collect();
172
173 Phase2Output {
174 twisted_eval_points,
175 twisted_evals,
176 }
177}
178
179/// The Frobenius twist amounts (numbers of squarings) mapping each looked-up limb column onto the
180/// shared generator table, ordered `[a limbs, c_lo limbs, c_hi limbs]`.
181///
182/// Limb $l$ of $\widetilde{a}$ and $\widetilde{c}_{\textsf{lo}}$ has base $g^{2^{wl}}$ (where $w$
183/// is the limb bit width); limb $l$ of $\widetilde{c}_{\textsf{hi}}$ has base
184/// $g^{2^{w(\textsf{N\_LIMBS} + l)}}$ because the $\widetilde{c}_{\textsf{hi}}$ tree exponentiates
185/// $g^{2^{2^k}}$. So column $(t, l)$ is the Frobenius power $\varphi^{ws}$ of the shared table
186/// column $g^{(\cdot)}$, with $s = l$ for $t \in \{a, c_{\textsf{lo}}\}$ and $s = \textsf{N\_LIMBS}
187/// + l$ for $t = c_{\textsf{hi}}$.
188pub fn limb_column_twists() -> [usize; N_LIMB_COLUMNS] {
189 std::array::from_fn(|j| {
190 let (tree, limb) = (j / N_LIMBS, j % N_LIMBS);
191 let s = if tree == 2 { N_LIMBS + limb } else { limb };
192 LIMB_BITS * s
193 })
194}
195
196/// Twist a limb-column evaluation claim onto the shared generator table.
197///
198/// The limb column satisfies $L = \varphi^{a} \circ U$ pointwise on the cube, where $U$ is the
199/// looked-up column of the shared table and $a$ is the twist amount. Since $\varphi$ is
200/// $\mathbb{F}_2$-linear and fixes the cube, the MLE claim twists as $\widetilde{U}
201/// (\varphi^{-a}(r)) = \varphi^{-a}(\widetilde{L}(r))$, applying $\varphi^{-a}$ to the value and
202/// every point coordinate.
203pub fn twist_limb_claim<F>(twist: usize, eval_point: &[F], eval: F) -> (Vec<F>, F)
204where
205 F: FieldOps,
206 F::Scalar: BinaryField,
207{
208 let twisted_point = eval_point
209 .iter()
210 .map(|coord| inv_frobenius(coord.clone(), twist))
211 .collect();
212 (twisted_point, inv_frobenius(eval, twist))
213}
214
215/// Evaluate the MLE of the fixed-base power table `i ↦ g^i` at a point.
216///
217/// Row $i$ is the product over the set bits $j$ of $i$ of $g^{2^j}$, so the MLE factors as
218/// $\prod_j \textsf{select}(y_j, g^{2^j})$ with $\textsf{select}(S, V) = S \cdot (V - 1) + 1$ —
219/// the same select formulation as the exponentiation tree leaves. The verifier evaluates this
220/// directly in `point.len()` multiplications, so the table needs no commitment.
221pub fn eval_power_table_mle<F, E>(point: &[E]) -> E
222where
223 F: BinaryField,
224 E: FieldOps<Scalar = F> + From<F>,
225{
226 let one = E::one();
227 iter::zip(iterate(F::MULTIPLICATIVE_GENERATOR, |g| g.square()), point)
228 .map(|(power, coord)| coord.clone() * (E::from(power) - one.clone()) + one.clone())
229 .fold(E::one(), |acc, factor| acc * factor)
230}