Skip to main content

binius_ip/sumcheck/
infinity.rs

1// Copyright 2026 The Binius Developers
2
3//! Sumcheck over the infinity hypercube $\{0, \infty\}^n$.
4//!
5//! This is the ordinary sumcheck with the round check $R(0) + R(\infty) = s$, where $R(\infty)$
6//! is the leading coefficient of $R$.
7//!
8//! Evaluating a multilinear on $\{0, \infty\}^n$ reads off its monomial coefficients. So for the
9//! multilinears $u^\infty$, $w^\infty$ whose monomial coefficients are the tables $u$, $w$,
10//!
11//! $$
12//! \sum_{x \in \{0, \infty\}^n} u^\infty(x) \cdot w^\infty(x) = \langle u, w \rangle
13//! $$
14//!
15//! The sumcheck reduces such a claim to the evaluations $u^\infty(r)$, $w^\infty(r)$ at the
16//! challenge point $r$, which has one coordinate per round.
17//!
18//! A claim on fewer variables than the batch needs no padding factor: summing out a coordinate the
19//! summand does not depend on leaves the claim unchanged.
20
21use binius_field::{Field, field::FieldOps};
22use binius_math::univariate::evaluate_univariate;
23
24use crate::{
25	channel::IPVerifierChannel,
26	sumcheck::{BatchSumcheckOutput, Error, RoundCoeffs, RoundProof, SumcheckOutput},
27};
28
29/// Verify a sumcheck over $\{0, \infty\}^n$.
30///
31/// This is [`super::verify()`] with each round checked as $R(0) + R(\infty) = s$.
32///
33/// ## Arguments
34///
35/// * `n_vars` - The number of variables in the multivariate polynomial
36/// * `degree` - The degree of the univariate polynomial in each round
37/// * `sum` - The claimed sum of the multivariate polynomial over $\{0, \infty\}^n$
38/// * `channel` - The channel for receiving prover messages and sampling challenges
39pub fn verify<F, C>(
40	n_vars: usize,
41	degree: usize,
42	mut sum: C::Elem,
43	channel: &mut C,
44) -> Result<SumcheckOutput<C::Elem>, Error>
45where
46	F: Field,
47	C: IPVerifierChannel<F>,
48{
49	let mut challenges = Vec::with_capacity(n_vars);
50	for _round in 0..n_vars {
51		let round_proof = RoundProof(RoundCoeffs(channel.recv_many(degree)?));
52		let challenge = channel.sample();
53
54		sum = round_proof.recover_infinity(sum).evaluate(&challenge);
55		challenges.push(challenge);
56	}
57
58	Ok(SumcheckOutput {
59		eval: sum,
60		challenges,
61	})
62}
63
64/// Verify a batched sumcheck over $\{0, \infty\}^n$.
65///
66/// The claims are combined with powers of a sampled batching coefficient, as in
67/// [`super::batch_verify`]. Claims may have fewer than `n_vars` variables: a claim on `k`
68/// variables closes at the low `k` coordinates of the evaluation point, which are the last `k`
69/// challenges.
70pub fn batch_verify<F, C>(
71	n_vars: usize,
72	degree: usize,
73	sums: &[C::Elem],
74	channel: &mut C,
75) -> Result<BatchSumcheckOutput<C::Elem>, Error>
76where
77	F: Field,
78	C: IPVerifierChannel<F>,
79{
80	let batch_coeff = channel.sample();
81	let sum = evaluate_univariate(sums, &batch_coeff);
82
83	let SumcheckOutput { eval, challenges } = verify::<F, C>(n_vars, degree, sum, channel)?;
84
85	Ok(BatchSumcheckOutput {
86		batch_coeff,
87		eval,
88		challenges,
89	})
90}
91
92/// Translates a point $\rho$ of a sumcheck over $\{0, \infty\}^n$ to the Boolean hypercube.
93///
94/// In characteristic 2, whenever no $\rho_j = 1$, the multilinear $u^\infty$ with monomial
95/// coefficients $u$ and the multilinear extension $\tilde{u}$ of $u$ agree up to a scale:
96///
97/// $$
98/// u^\infty(\rho_{<k}) = \prod_{j < k} (1 + \rho_j) \cdot \tilde{u}(\sigma_{<k}), \qquad
99/// \sigma_j = \frac{\rho_j}{1 + \rho_j}
100/// $$
101///
102/// Returns $\sigma$ and the scales $\prod_{j < k} (1 + \rho_j)$ for every $k = 0, \ldots, n$.
103///
104/// A coordinate $\rho_j = 1$ has no translation. It maps to $\sigma_j = 0$ and zeroes every scale
105/// past it, and occurs with probability $n / |F|$ over a uniform $\rho$.
106pub fn to_mle_point<F: FieldOps>(point: &[F]) -> (Vec<F>, Vec<F>) {
107	let mut scales = Vec::with_capacity(point.len() + 1);
108	scales.push(F::one());
109	let sigma = point
110		.iter()
111		.map(|rho_j| {
112			let one_plus_rho = F::one() + rho_j;
113			let scale = scales.last().expect("scales starts non-empty").clone() * &one_plus_rho;
114			scales.push(scale);
115			rho_j.clone() * one_plus_rho.invert_or_zero()
116		})
117		.collect();
118	(sigma, scales)
119}
120
121#[cfg(test)]
122mod tests {
123	use binius_field::arch::OptimalB128 as B128;
124	use binius_math::{
125		multilinear::{
126			eq::eq_ind_partial_eval_scalars,
127			hypercube::{InfCube, eq_ind_partial_eval_scalars as monomials},
128		},
129		test_utils::random_scalars,
130	};
131	use rand::prelude::*;
132
133	use super::*;
134
135	#[test]
136	fn recover_infinity_round_trips() {
137		let mut rng = StdRng::seed_from_u64(0);
138		for degree in 1..=4 {
139			let coeffs = RoundCoeffs(random_scalars::<B128>(&mut rng, degree + 1));
140			// R(0) + R(∞) is the constant plus the leading coefficient.
141			let sum = coeffs[0] + coeffs[degree];
142			assert_eq!(coeffs.clone().truncate().recover_infinity(sum), coeffs);
143		}
144	}
145
146	#[test]
147	fn to_mle_point_matches_the_monomial_evaluation() {
148		let mut rng = StdRng::seed_from_u64(0);
149		let n_vars = 4;
150		let point = random_scalars::<B128>(&mut rng, n_vars);
151		let (sigma, scales) = to_mle_point(&point);
152		for k in 0..=n_vars {
153			let u = random_scalars::<B128>(&mut rng, 1 << k);
154			let dot = |basis: Vec<B128>| u.iter().zip(basis).map(|(u, b)| *u * b).sum::<B128>();
155			let monomial_eval = dot(monomials::<InfCube, B128>(&point[..k]));
156			let mle_eval = dot(eq_ind_partial_eval_scalars(&sigma[..k]));
157			assert_eq!(monomial_eval, scales[k] * mle_eval, "k={k}");
158		}
159	}
160}