Skip to main content

binius_ip_prover/sumcheck/
infinity.rs

1// Copyright 2026 The Binius Developers
2
3//! Prover for the sumcheck over the infinity hypercube $\{0, \infty\}^n$.
4//!
5//! See [`binius_ip::sumcheck::infinity`] for the protocol and the verifier.
6
7use binius_alloc::BufferData;
8use binius_field::{Field, PackedField};
9use binius_ip::sumcheck::RoundCoeffs;
10use binius_math::{
11	FieldBuffer,
12	inner_product::inner_product_par,
13	multilinear::hypercube::{InfCube, fold_highest_var_inplace},
14};
15
16use super::batch::BatchSumcheckOutput;
17use crate::channel::IPProverChannel;
18
19/// Proves a batch of claims $\sum_{x \in \{0, \infty\}^n} u^\infty(x) \cdot w^\infty(x)$, one per
20/// pair of monomial-coefficient tables $(u, w)$.
21///
22/// The claimed sum of each pair is $\langle u, w \rangle$. The pairs may have different variable
23/// counts; the batch runs on the largest, binding the top variable each round. A pair on `k`
24/// variables sits out the first rounds, contributing its unchanged claim as a constant round
25/// polynomial, and closes at the low `k` coordinates of the evaluation point.
26///
27/// Verify with [`binius_ip::sumcheck::infinity::batch_verify`] at degree 2.
28///
29/// Each prover's evaluations are $[u^\infty(r), w^\infty(r)]$, the multilinears with monomial
30/// coefficients $u$, $w$ at the claim's challenge point $r$. The evaluations are not written to the
31/// channel.
32///
33/// ## Preconditions
34///
35/// * the two tables of a pair must have the same number of variables
36pub fn batch_prove<F, P, Data>(
37	pairs: Vec<[FieldBuffer<P, Data>; 2]>,
38	channel: &mut impl IPProverChannel<F>,
39) -> BatchSumcheckOutput<F>
40where
41	F: Field,
42	P: PackedField<Scalar = F>,
43	Data: BufferData<P>,
44{
45	let mut provers = pairs
46		.into_iter()
47		.map(ProductProver::new)
48		.collect::<Vec<_>>();
49	let n_vars = provers.iter().map(|p| p.n_vars()).max().unwrap_or(0);
50
51	let batch_coeff = channel.sample();
52
53	let mut challenges = Vec::with_capacity(n_vars);
54	for round in 0..n_vars {
55		let n_vars_remaining = n_vars - round;
56		let round_coeffs = provers
57			.iter()
58			.map(|prover| {
59				if prover.n_vars() == n_vars_remaining {
60					prover.round_coeffs()
61				} else {
62					// The summand does not depend on this variable, so R(X) is the constant claim.
63					RoundCoeffs(vec![prover.claim])
64				}
65			})
66			.collect::<Vec<_>>();
67
68		// The largest prover is always active, so the batch has all degree + 1 coefficients.
69		let batched = RoundCoeffs::batch(round_coeffs.clone(), &batch_coeff);
70		channel.send_many(batched.truncate().coeffs());
71
72		let challenge = channel.sample();
73		challenges.push(challenge);
74		for (prover, coeffs) in provers.iter_mut().zip(round_coeffs) {
75			if prover.n_vars() == n_vars_remaining {
76				prover.fold(&coeffs, challenge);
77			}
78		}
79	}
80
81	BatchSumcheckOutput {
82		challenges,
83		multilinear_evals: provers.into_iter().map(ProductProver::finish).collect(),
84	}
85}
86
87/// The state of one claim $\sum_x u^\infty(x) \cdot w^\infty(x) = s$.
88///
89/// [`batch_prove`] drives these with random batching weights. A caller that needs another
90/// combination of the round polynomials drives them itself.
91pub struct ProductProver<P: PackedField, Data: BufferData<P>> {
92	tables: [FieldBuffer<P, Data>; 2],
93	claim: P::Scalar,
94}
95
96impl<F, P, Data> ProductProver<P, Data>
97where
98	F: Field,
99	P: PackedField<Scalar = F>,
100	Data: BufferData<P>,
101{
102	/// Creates the prover of $\langle u, w \rangle$ for the tables `[u, w]`.
103	///
104	/// ## Preconditions
105	///
106	/// * the two tables must have the same number of variables
107	pub fn new(tables: [FieldBuffer<P, Data>; 2]) -> Self {
108		let [u, w] = &tables;
109		assert_eq!(
110			u.log_len(),
111			w.log_len(),
112			"precondition: tables must have equal variable counts"
113		);
114		let claim = inner_product_par(u, w);
115		Self { tables, claim }
116	}
117
118	/// The number of variables not yet bound.
119	pub const fn n_vars(&self) -> usize {
120		self.tables[0].log_len()
121	}
122
123	/// The current claim $s$, the sum over the unbound variables.
124	pub const fn claim(&self) -> F {
125		self.claim
126	}
127
128	/// The round polynomial in the top variable $X$.
129	///
130	/// With $u = u_0 + X u_1$ split on the top variable, and likewise $w$,
131	///
132	/// $$
133	/// R(X) = \langle u_0, w_0 \rangle
134	///     + X (\langle u_0, w_1 \rangle + \langle u_1, w_0 \rangle)
135	///     + X^2 \langle u_1, w_1 \rangle
136	/// $$
137	///
138	/// and $R(0) = s - R(\infty)$ comes from the claim.
139	pub fn round_coeffs(&self) -> RoundCoeffs<F> {
140		let [u, w] = &self.tables;
141		let (u_0, u_1) = u.split_half();
142		let (w_0, w_1) = w.split_half();
143
144		let r_inf = inner_product_par(&u_1, &w_1);
145		let r_mid = inner_product_par(&u_0, &w_1) + inner_product_par(&u_1, &w_0);
146		RoundCoeffs(vec![self.claim - r_inf, r_mid, r_inf])
147	}
148
149	/// Binds the top variable to `challenge` $r$: $u'(v) = u(v, 0) + r \cdot u(v, 1)$.
150	pub fn fold(&mut self, round_coeffs: &RoundCoeffs<F>, challenge: F) {
151		self.claim = round_coeffs.evaluate(&challenge);
152
153		for table in &mut self.tables {
154			fold_highest_var_inplace::<InfCube, _, _>(table, challenge);
155		}
156	}
157
158	/// The evaluations $[u^\infty(r), w^\infty(r)]$ once every variable is bound.
159	pub fn finish(self) -> Vec<F> {
160		self.tables.iter().map(|table| table.get(0)).collect()
161	}
162}
163
164#[cfg(test)]
165mod tests {
166	use binius_field::arch::{OptimalB128, OptimalPackedB128};
167	use binius_ip::sumcheck::infinity::batch_verify;
168	use binius_math::{
169		multilinear::hypercube::eq_ind_partial_eval, test_utils::random_field_buffer,
170		univariate::evaluate_univariate,
171	};
172	use binius_transcript::{ProverTranscript, VerifierTranscript, fiat_shamir::HasherChallenger};
173	use rand::prelude::*;
174
175	use super::*;
176
177	type F = OptimalB128;
178	type P = OptimalPackedB128;
179	type StdChallenger = HasherChallenger<sha2::Sha256>;
180
181	const N_VARS: [usize; 5] = [5, 0, 3, 5, 1];
182
183	/// The multilinear with monomial coefficients `u`, evaluated at `point`.
184	fn monomial_eval(u: &FieldBuffer<P>, point: &[F]) -> F {
185		inner_product_par(u, &eq_ind_partial_eval::<InfCube, P>(point))
186	}
187
188	fn random_pairs() -> Vec<[FieldBuffer<P>; 2]> {
189		let mut rng = StdRng::seed_from_u64(0);
190		N_VARS
191			.iter()
192			.map(|&n| {
193				[
194					random_field_buffer(&mut rng, n),
195					random_field_buffer(&mut rng, n),
196				]
197			})
198			.collect()
199	}
200
201	/// Proves the batch and returns the sums and the proof bytes.
202	fn prove(pairs: &[[FieldBuffer<P>; 2]]) -> (Vec<F>, Vec<u8>) {
203		let sums = pairs.iter().map(|[u, w]| inner_product_par(u, w)).collect();
204		let mut transcript = ProverTranscript::new(StdChallenger::default());
205		batch_prove(pairs.to_vec(), &mut transcript);
206		(sums, transcript.finalize())
207	}
208
209	#[test]
210	fn batch_round_trip_over_mixed_sizes() {
211		let pairs = random_pairs();
212		let n_vars = *N_VARS.iter().max().unwrap();
213		let sums = pairs
214			.iter()
215			.map(|[u, w]| inner_product_par(u, w))
216			.collect::<Vec<_>>();
217
218		let mut prover_transcript = ProverTranscript::new(StdChallenger::default());
219		let output = batch_prove(pairs.clone(), &mut prover_transcript);
220
221		let mut verifier_transcript = prover_transcript.into_verifier();
222		let verified = batch_verify(n_vars, 2, &sums, &mut verifier_transcript).unwrap();
223		assert_eq!(output.challenges, verified.challenges);
224
225		// Challenges bind the top variable first, so the point reads them in reverse.
226		let mut point = verified.challenges.clone();
227		point.reverse();
228
229		let mut composed = Vec::new();
230		for ([u, w], evals) in pairs.iter().zip(&output.multilinear_evals) {
231			// A claim on k variables closes at the low k coordinates.
232			let point = &point[..u.log_len()];
233			assert_eq!(evals[0], monomial_eval(u, point));
234			assert_eq!(evals[1], monomial_eval(w, point));
235			composed.push(evals[0] * evals[1]);
236		}
237		assert_eq!(evaluate_univariate(&composed, &verified.batch_coeff), verified.eval);
238	}
239
240	#[test]
241	fn tampered_round_polynomial_is_rejected() {
242		let pairs = random_pairs();
243		let n_vars = *N_VARS.iter().max().unwrap();
244		let (sums, mut proof) = prove(&pairs);
245
246		// Flip a bit of the first round's constant coefficient.
247		proof[0] ^= 1;
248
249		let mut transcript = VerifierTranscript::new(StdChallenger::default(), proof);
250		let verified = batch_verify(n_vars, 2, &sums, &mut transcript).unwrap();
251
252		let mut point = verified.challenges.clone();
253		point.reverse();
254		let composed = pairs
255			.iter()
256			.map(|[u, w]| {
257				let point = &point[..u.log_len()];
258				monomial_eval(u, point) * monomial_eval(w, point)
259			})
260			.collect::<Vec<_>>();
261		assert_ne!(evaluate_univariate(&composed, &verified.batch_coeff), verified.eval);
262	}
263}