Skip to main content

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}