binius_ip/sumcheck/common.rs
1// Copyright 2023-2025 Irreducible Inc.
2
3use std::ops::{Add, AddAssign, Index, Mul, MulAssign};
4
5use binius_field::{Field, field::FieldOps};
6use binius_math::univariate::evaluate_univariate;
7
8/// A univariate polynomial in monomial basis.
9///
10/// The coefficient at position `i` in the inner vector corresponds to the term $X^i$.
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct RoundCoeffs<F>(pub Vec<F>);
13
14// The empty coefficient vector is the zero polynomial, a valid default for any element type.
15// Deriving the default would instead demand that every element type have its own default value.
16impl<F> Default for RoundCoeffs<F> {
17 fn default() -> Self {
18 // The zero polynomial has no coefficients.
19 Self(Vec::new())
20 }
21}
22
23impl<F> RoundCoeffs<F> {
24 /// Truncate the highest-degree coefficient to produce a more compact round proof.
25 ///
26 /// # Pre-conditions
27 ///
28 /// - The coefficient vector must be non-empty.
29 /// - A round polynomial always has degree at least one, so an empty vector signals a bug.
30 pub fn truncate(mut self) -> RoundProof<F> {
31 // Drop the highest-degree coefficient; the verifier reconstructs it from the claimed sum.
32 self.0.pop();
33 RoundProof(self)
34 }
35
36 /// The coefficients ordered from the constant term to the highest-degree term.
37 pub fn as_slice(&self) -> &[F] {
38 // Position `i` holds the coefficient of X^i, so the constant term comes first.
39 &self.0
40 }
41}
42
43impl<F: FieldOps> RoundCoeffs<F> {
44 /// Evaluate the polynomial at a point.
45 pub fn evaluate(&self, x: &F) -> F {
46 // Horner's method over the monomial coefficients.
47 evaluate_univariate(&self.0, x)
48 }
49
50 /// Batches round polynomials into one, weighting polynomial `i` by `batch_coeff^i`.
51 ///
52 /// The verifier weights the matching claims with the same coefficient.
53 /// Each claim therefore stays tied to its own round polynomial.
54 ///
55 /// An empty input is the zero polynomial.
56 pub fn batch(polys: Vec<Self>, batch_coeff: &F) -> Self {
57 // Horner from the highest weight down: acc <- acc * batch_coeff + poly.
58 polys
59 .into_iter()
60 .rfold(Self::default(), |acc, poly| acc * batch_coeff.clone() + &poly)
61 }
62
63 /// The endpoint values $(R(0), R(1))$ of the round polynomial.
64 ///
65 /// $R(0)$ is the constant coefficient $a_0$.
66 /// $R(1) = \sum_j a_j$ is the sum of all coefficients.
67 /// An empty coefficient vector is the zero polynomial, whose endpoints are both zero.
68 fn endpoints(&self) -> (F, F) {
69 // R(0) is the constant term, or zero when there are no coefficients.
70 let r_0 = self.0.first().cloned().unwrap_or_else(F::zero);
71 // R(1) is the polynomial at one, which sums every coefficient.
72 let r_1 = self.0.iter().cloned().sum();
73 (r_0, r_1)
74 }
75
76 /// The claimed sum $R(0) + R(1)$ that this round polynomial encodes.
77 ///
78 /// For a sumcheck round polynomial, this is the round's claimed sum.
79 /// The verifier expects the identity $s = R(0) + R(1)$ (see [`RoundProof::recover`]).
80 pub fn sum_over_endpoints(&self) -> F {
81 // The sumcheck claim is s = R(0) + R(1).
82 let (r_0, r_1) = self.endpoints();
83 r_0 + r_1
84 }
85
86 /// The claimed value $(1 - \alpha) R(0) + \alpha R(1)$ that this round polynomial encodes in an
87 /// MLE-check.
88 ///
89 /// This is the MLE-check analogue of [`Self::sum_over_endpoints`].
90 /// An MLE-check round polynomial satisfies $s = (1 - \alpha) R(0) + \alpha R(1)$.
91 /// Here $\alpha$ is the round's evaluation-point coordinate (see
92 /// [`crate::mlecheck::RoundProof::recover`]). Equivalently, this is the linear extrapolation
93 /// of $R$ from the endpoints $0$ and $1$ to $\alpha$.
94 pub fn lerp_over_endpoints(&self, alpha: F) -> F {
95 let (r_0, r_1) = self.endpoints();
96 // Line through the endpoints, sampled at alpha: R(0) + alpha * (R(1) - R(0)).
97 r_0.clone() + alpha * (r_1 - r_0)
98 }
99}
100
101impl<F: Field> RoundCoeffs<F> {
102 /// Multiplies this polynomial by the equality factor $\text{eq}(X, \alpha)$.
103 ///
104 /// $$
105 /// \text{eq}(X, \alpha) = (1 - \alpha) + (2 \alpha - 1) X
106 /// $$
107 ///
108 /// An MLE-check prover interpolates the prime polynomial, which carries no equality factor.
109 /// This multiplies the factor back in.
110 ///
111 /// Monomial form makes that one scaling and one shift.
112 /// Sampling the factored polynomial instead would cost an extra evaluation point.
113 ///
114 /// The factor is linear, so the result has one more coefficient than `self`.
115 pub fn mul_by_eq(&self, alpha: F) -> Self {
116 // NB: In characteristic 2, eq(X, alpha) simplifies to (1 + alpha) + X.
117 let (by_constant_term, mut by_linear_term) = if F::CHARACTERISTIC == 2 {
118 (self.clone() * (F::ONE + alpha), self.clone())
119 } else {
120 (self.clone() * (F::ONE - alpha), self.clone() * (alpha.double() - F::ONE))
121 };
122
123 // Prepending a zero coefficient multiplies the polynomial by X.
124 by_linear_term.0.insert(0, F::ZERO);
125 by_constant_term + &by_linear_term
126 }
127}
128
129impl<F: FieldOps> Add<&Self> for RoundCoeffs<F> {
130 type Output = Self;
131
132 fn add(mut self, rhs: &Self) -> Self::Output {
133 // Reuse the in-place addition and return the grown accumulator.
134 self += rhs;
135 self
136 }
137}
138
139impl<F: FieldOps> AddAssign<&Self> for RoundCoeffs<F> {
140 fn add_assign(&mut self, rhs: &Self) {
141 // The two polynomials may have different degrees, hence different coefficient counts.
142 // Pad the shorter accumulator with zeros so every addend coefficient has a partner.
143 if self.0.len() < rhs.0.len() {
144 self.0.resize(rhs.0.len(), F::zero());
145 }
146
147 // Add coefficient by coefficient at matching degrees.
148 for (lhs_i, rhs_i) in self.0.iter_mut().zip(rhs.0.iter()) {
149 *lhs_i += rhs_i;
150 }
151 }
152}
153
154impl<F: FieldOps> Mul<F> for RoundCoeffs<F> {
155 type Output = Self;
156
157 fn mul(mut self, rhs: F) -> Self::Output {
158 // Reuse the in-place scaling.
159 self *= rhs;
160 self
161 }
162}
163
164impl<F: FieldOps> MulAssign<F> for RoundCoeffs<F> {
165 fn mul_assign(&mut self, rhs: F) {
166 // Scaling a polynomial by a constant scales every coefficient.
167 for coeff in &mut self.0 {
168 *coeff *= &rhs;
169 }
170 }
171}
172
173impl<F: FieldOps> std::iter::Sum for RoundCoeffs<F> {
174 fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
175 // Start from the zero polynomial and accumulate by polynomial addition.
176 iter.fold(Self::default(), |acc, x| acc + &x)
177 }
178}
179
180impl<F> Index<usize> for RoundCoeffs<F> {
181 type Output = F;
182
183 fn index(&self, index: usize) -> &F {
184 // Position `i` selects the coefficient of X^i.
185 &self.0[index]
186 }
187}
188
189/// A sumcheck round proof is a univariate polynomial in monomial basis with the coefficient of the
190/// highest-degree term truncated off.
191///
192/// Since the verifier knows the claimed sum of the polynomial values at the points 0 and 1, the
193/// high-degree term coefficient can be easily recovered. Truncating the coefficient off saves a
194/// small amount of proof data.
195#[derive(Debug, Clone, PartialEq, Eq)]
196pub struct RoundProof<F>(pub RoundCoeffs<F>);
197
198// The empty proof is a valid default for any element type.
199// Deriving the default would instead demand that every element type have its own default value.
200impl<F> Default for RoundProof<F> {
201 fn default() -> Self {
202 // Mirror the empty (zero) polynomial default.
203 Self(RoundCoeffs::default())
204 }
205}
206
207impl<F> RoundProof<F> {
208 /// The truncated polynomial coefficients.
209 pub fn coeffs(&self) -> &[F] {
210 // Every coefficient except the truncated highest-degree term.
211 self.0.as_slice()
212 }
213}
214
215impl<F: FieldOps> RoundProof<F> {
216 /// Recovers all univariate polynomial coefficients from the compressed round proof.
217 ///
218 /// The prover has sent coefficients for the purported ith round polynomial
219 /// $r_i(X) = \sum_{j=0}^d a_j * X^j$.
220 /// However, the prover has not sent the highest degree coefficient $a_d$.
221 /// The verifier will need to recover this missing coefficient.
222 ///
223 /// Let $s$ denote the current round's claimed sum.
224 /// The verifier expects the round polynomial $r_i$ to satisfy the identity
225 /// $s = r_i(0) + r_i(1)$.
226 /// Using
227 /// $r_i(0) = a_0$
228 /// $r_i(1) = \sum_{j=0}^d a_j$
229 /// There is a unique $a_d$ that allows $r_i$ to satisfy the above identity.
230 /// Specifically
231 /// $a_d = s - a_0 - \sum_{j=0}^{d-1} a_j$
232 ///
233 /// Not sending the whole round polynomial is an optimization.
234 /// In the unoptimized version of the protocol, the verifier will halt and reject
235 /// if given a round polynomial that does not satisfy the above identity.
236 pub fn recover(self, sum: F) -> RoundCoeffs<F> {
237 let Self(RoundCoeffs(mut coeffs)) = self;
238 // The received coefficients are a_0 through a_{d-1}; the top term a_d was truncated.
239 // The claimed sum expands to s = R(0) + R(1) = a_0 + (a_0 + a_1 + ... + a_d).
240 // Solving for the missing term gives a_d = s - a_0 - (a_0 + a_1 + ... + a_{d-1}).
241 //
242 // The constant term a_0 is subtracted twice on purpose.
243 // The two copies cancel in characteristic 2 yet keep the identity correct over any field.
244
245 // a_0, or zero for the degenerate empty proof.
246 let first_coeff = coeffs.first().cloned().unwrap_or_else(F::zero);
247 // a_d = s - a_0 - sum_{j=0}^{d-1} a_j.
248 let last_coeff = sum - first_coeff - coeffs.iter().cloned().sum::<F>();
249 // Append the recovered top coefficient to rebuild the full polynomial.
250 coeffs.push(last_coeff);
251 RoundCoeffs(coeffs)
252 }
253
254 /// Recovers all coefficients from a round proof whose claim is $s = r_i(0) + r_i(\infty)$.
255 ///
256 /// This is the counterpart of [`Self::recover`] for a sumcheck over $\{0, \infty\}^n$.
257 /// Here $r_i(\infty)$ is the leading coefficient $a_d$ and $r_i(0) = a_0$, so the truncated
258 /// coefficient is $a_d = s - a_0$.
259 pub fn recover_infinity(self, sum: F) -> RoundCoeffs<F> {
260 let Self(RoundCoeffs(mut coeffs)) = self;
261 // a_0, or zero for the degenerate empty proof.
262 let first_coeff = coeffs.first().cloned().unwrap_or_else(F::zero);
263 coeffs.push(sum - first_coeff);
264 RoundCoeffs(coeffs)
265 }
266}
267
268#[cfg(test)]
269mod tests {
270 use binius_field::{Field, Random, arch::OptimalB128 as B128};
271 use binius_math::{multilinear::eq::eq_one_var, test_utils::random_scalars};
272 use rand::prelude::*;
273
274 use super::*;
275
276 // Sumcheck round polynomials have small degree.
277 // Degrees 1 through 4 cover the range the round provers in this workspace produce.
278 const DEGREES: [usize; 4] = [1, 2, 3, 4];
279
280 // Deterministic RNG seeded to a fixed value so any failure reproduces exactly.
281 fn rng() -> StdRng {
282 StdRng::seed_from_u64(0)
283 }
284
285 #[test]
286 fn recover_round_trips_with_the_claimed_sum() {
287 let mut rng = rng();
288 // Invariant: truncating the top coefficient then recovering it rebuilds the polynomial,
289 // as long as recovery is given the true claimed sum s = R(0) + R(1).
290 for degree in DEGREES {
291 // A random round polynomial with degree + 1 coefficients.
292 let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, degree + 1));
293
294 // The verifier only learns the claimed sum s = R(0) + R(1).
295 let sum = coeffs.sum_over_endpoints();
296 // The proof drops the highest-degree coefficient to save transcript space.
297 let proof = coeffs.clone().truncate();
298
299 // Stripping one coefficient leaves exactly `degree` of them.
300 assert_eq!(proof.coeffs().len(), degree);
301 // The claimed sum uniquely determines the missing coefficient, so recovery is exact.
302 assert_eq!(proof.recover(sum), coeffs);
303 }
304 }
305
306 #[test]
307 fn recovered_polynomial_satisfies_the_sumcheck_identity() {
308 let mut rng = rng();
309 // Invariant: the recovered polynomial must satisfy the verifier's check s = R(0) + R(1).
310 for degree in DEGREES {
311 let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, degree + 1));
312 // Claimed sum taken from the original polynomial.
313 let sum = coeffs.sum_over_endpoints();
314 // Round-trip through truncation and recovery.
315 let recovered = coeffs.truncate().recover(sum);
316
317 // Evaluate the recovered polynomial at both endpoints and confirm they sum to s.
318 assert_eq!(recovered.evaluate(&B128::ZERO) + recovered.evaluate(&B128::ONE), sum);
319 }
320 }
321
322 #[test]
323 fn batch_commutes_with_evaluation() {
324 let mut rng = rng();
325 // Invariant: the prover's batched polynomial agrees with the verifier's batched claim.
326 //
327 // batch(R_0, .., R_{n-1})(x) == sum_i batch_coeff^i * R_i(x)
328 //
329 // The prover folds the round polynomials, the verifier folds the claim scalars.
330 // A mismatch would send a batched round proof the verifier cannot reproduce.
331 for degree in DEGREES {
332 // Mixed lengths, since batched provers need not all reach the same degree.
333 let polys = (1..=degree)
334 .map(|len| RoundCoeffs(random_scalars::<B128>(&mut rng, len + 1)))
335 .collect::<Vec<_>>();
336 let batch_coeff = B128::random(&mut rng);
337
338 let batched = RoundCoeffs::batch(polys.clone(), &batch_coeff);
339
340 // The batched polynomial reaches the degree of the longest input.
341 assert_eq!(batched.0.len(), degree + 1);
342 for x in random_scalars::<B128>(&mut rng, 4) {
343 // The verifier's side: Horner-fold the per-claim evaluations.
344 let evals = polys
345 .iter()
346 .map(|poly| poly.evaluate(&x))
347 .collect::<Vec<_>>();
348 assert_eq!(batched.evaluate(&x), evaluate_univariate(&evals, &batch_coeff));
349 }
350 }
351 }
352
353 #[test]
354 fn batching_nothing_gives_the_zero_polynomial() {
355 // A batched group with no provers must contribute nothing to the round proof.
356 let batched = RoundCoeffs::batch(Vec::new(), &B128::random(&mut rng()));
357 assert_eq!(batched, RoundCoeffs::<B128>::default());
358 }
359
360 #[test]
361 fn mul_by_eq_multiplies_pointwise() {
362 let mut rng = rng();
363 // Invariant: scaling by the equality factor is exact at every point.
364 //
365 // (R * eq)(x) == R(x) * eq(x, alpha)
366 //
367 // The prover interpolates the prime polynomial and multiplies the factor back in here,
368 // so a discrepancy would send a round polynomial the verifier cannot reproduce.
369 for degree in DEGREES {
370 let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, degree + 1));
371 let alpha = B128::random(&mut rng);
372
373 let scaled = coeffs.mul_by_eq(alpha);
374
375 // The equality factor is linear, so the product gains exactly one degree.
376 assert_eq!(scaled.0.len(), coeffs.0.len() + 1);
377 for x in random_scalars::<B128>(&mut rng, 4) {
378 let eq_at_x = eq_one_var(x, alpha);
379 assert_eq!(scaled.evaluate(&x), coeffs.evaluate(&x) * eq_at_x);
380 }
381 }
382 }
383
384 #[test]
385 fn sum_over_endpoints_equals_evaluation_at_zero_and_one() {
386 let mut rng = rng();
387 // Invariant: the endpoint-sum shortcut equals R(0) + R(1) computed by direct evaluation.
388 for degree in DEGREES {
389 let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, degree + 1));
390 // Direct evaluation at the two endpoints.
391 let expected = coeffs.evaluate(&B128::ZERO) + coeffs.evaluate(&B128::ONE);
392 // The shortcut must agree with direct evaluation.
393 assert_eq!(coeffs.sum_over_endpoints(), expected);
394 }
395 }
396
397 #[test]
398 fn lerp_over_endpoints_is_the_line_through_the_endpoints() {
399 let mut rng = rng();
400 // Invariant: the extrapolation is the straight line joining R(0) and R(1),
401 // sampled at the round coordinate alpha.
402 for degree in DEGREES {
403 let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, degree + 1));
404 let alpha = B128::random(&mut rng);
405
406 // The two endpoint values that define the line.
407 let r_0 = coeffs.evaluate(&B128::ZERO);
408 let r_1 = coeffs.evaluate(&B128::ONE);
409 // The point on that line at alpha: R(0) + alpha * (R(1) - R(0)).
410 let expected = r_0 + alpha * (r_1 - r_0);
411
412 // The helper must reproduce that point.
413 assert_eq!(coeffs.lerp_over_endpoints(alpha), expected);
414 // alpha = 0 lands exactly on R(0).
415 assert_eq!(coeffs.lerp_over_endpoints(B128::ZERO), r_0);
416 // alpha = 1 lands exactly on R(1).
417 assert_eq!(coeffs.lerp_over_endpoints(B128::ONE), r_1);
418 }
419 }
420
421 #[test]
422 fn addition_is_pointwise_across_ragged_lengths() {
423 let mut rng = rng();
424 // Invariant: adding polynomials adds their evaluations at every point,
425 // even when the two operands have different degrees.
426 //
427 // Fixture: a degree-4 polynomial (5 coefficients) and a degree-1 polynomial (2).
428 //
429 // long : [a_0, a_1, a_2, a_3, a_4]
430 // short: [b_0, b_1]
431 // sum : [a_0+b_0, a_1+b_1, a_2, a_3, a_4]
432 let long = RoundCoeffs(random_scalars::<B128>(&mut rng, 5));
433 let short = RoundCoeffs(random_scalars::<B128>(&mut rng, 2));
434 let x = B128::random(&mut rng);
435
436 // Longer accumulator, shorter addend: the accumulator keeps its high-degree tail.
437 assert_eq!((long.clone() + &short).evaluate(&x), long.evaluate(&x) + short.evaluate(&x));
438 // Shorter accumulator, longer addend: the accumulator is padded up to the larger degree.
439 assert_eq!((short.clone() + &long).evaluate(&x), short.evaluate(&x) + long.evaluate(&x));
440 }
441
442 #[test]
443 fn scaling_multiplies_every_evaluation() {
444 let mut rng = rng();
445 // Invariant: scaling a polynomial by a constant scales its value at every point.
446 let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, 4));
447 let scalar = B128::random(&mut rng);
448 let x = B128::random(&mut rng);
449
450 // (c * R)(x) must equal c * R(x).
451 assert_eq!((coeffs.clone() * scalar).evaluate(&x), coeffs.evaluate(&x) * scalar);
452 }
453
454 #[test]
455 fn sum_of_round_coeffs_adds_the_polynomials() {
456 let mut rng = rng();
457 // Invariant: summing polynomials sums their evaluations at every point.
458 // Fixture: three degree-2 polynomials (3 coefficients each).
459 let parts: Vec<_> = (0..3)
460 .map(|_| RoundCoeffs(random_scalars::<B128>(&mut rng, 3)))
461 .collect();
462 let x = B128::random(&mut rng);
463
464 // Fold the polynomials together with the iterator sum.
465 let total: RoundCoeffs<B128> = parts.iter().cloned().sum();
466 // Reference: add the individual evaluations at x.
467 let expected: B128 = parts.iter().map(|c| c.evaluate(&x)).sum();
468
469 assert_eq!(total.evaluate(&x), expected);
470 }
471
472 #[test]
473 fn empty_round_coeffs_is_the_zero_polynomial() {
474 // A polynomial with no coefficients is the zero polynomial.
475 let coeffs = RoundCoeffs::<B128>(vec![]);
476 // It evaluates to zero everywhere.
477 assert_eq!(coeffs.evaluate(&B128::random(rng())), B128::ZERO);
478 // Both endpoints are zero, so their sum is zero.
479 assert_eq!(coeffs.sum_over_endpoints(), B128::ZERO);
480 // The line through (0, 0) and (1, 0) is zero at every alpha.
481 assert_eq!(coeffs.lerp_over_endpoints(B128::random(rng())), B128::ZERO);
482 }
483}