Skip to main content

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}