binius_ip/sumcheck/
batch.rs

1// Copyright 2025 Irreducible Inc.
2
3use binius_field::Field;
4use binius_math::univariate::evaluate_univariate;
5
6use crate::{
7	channel::IPVerifierChannel,
8	mlecheck,
9	sumcheck::{self, Error, SumcheckOutput},
10};
11
12/// The reduced output of a sumcheck verification.
13///
14/// The [`batch_verify`] function reduces a set of claims on multivariate polynomials over the
15/// boolean hypercube to their evaluation at a challenge point. See the function docstring for
16/// details.
17pub struct BatchSumcheckOutput<F> {
18	/// The challenge value of the batching variable.
19	pub batch_coeff: F,
20	/// The evaluation of the sumcheck multivariate at the challenge point.
21	pub eval: F,
22	/// Verifier challenges for each round of the sumcheck protocol.
23	///
24	/// One challenge is generated per variable in the multivariate polynomial,
25	/// with challenges\[i\] corresponding to the i-th round of the protocol.
26	///
27	/// Note: reverse when folding high-to-low to obtain evaluation claim.
28	pub challenges: Vec<F>,
29}
30
31/// Verify a batched sumcheck protocol interaction.
32///
33/// The batched sumcheck verifier reduces a set of claims about the sums of multivariate polynomials
34/// over the boolean hypercube to their evaluation at a (shared) challenge point. This is achieved
35/// by constructing an `n_vars + 1`-variate polynomial whose coefficients in the "new variable" are
36/// the individual sum claims and evaluating it at a random point.
37pub fn batch_verify<F, C>(
38	n_vars: usize,
39	degree: usize,
40	sums: &[C::Elem],
41	channel: &mut C,
42) -> Result<BatchSumcheckOutput<C::Elem>, Error>
43where
44	F: Field,
45	C: IPVerifierChannel<F>,
46{
47	// Random linear-combination coefficient that binds all sum claims together.
48	let batch_coeff = channel.sample();
49	// Combine the individual sum claims into a single scalar for sumcheck verification.
50	let sum = evaluate_univariate(sums, &batch_coeff);
51
52	let SumcheckOutput { eval, challenges } =
53		sumcheck::verify::<F, C>(n_vars, degree, sum, channel)?;
54
55	Ok(BatchSumcheckOutput {
56		batch_coeff,
57		challenges,
58		eval,
59	})
60}
61
62/// Verify a batched sumcheck protocol interaction for MLE-checks.
63///
64/// This is the MLE-check analog of [`batch_verify`]: it batches evaluation claims from multiple
65/// MLE-check instances that share a common evaluation point, using a single batching coefficient
66/// and shared verifier challenges to reduce all claims to one scalar verification.
67pub fn batch_verify_mle<F, C>(
68	point: &[C::Elem],
69	degree: usize,
70	evals: &[C::Elem],
71	channel: &mut C,
72) -> Result<BatchSumcheckOutput<C::Elem>, Error>
73where
74	F: Field,
75	C: IPVerifierChannel<F>,
76{
77	// Random linear-combination coefficient that binds all eval claims together.
78	let batch_coeff = channel.sample();
79	// Combine the individual eval claims into a single scalar for MLE-check verification.
80	let eval = evaluate_univariate(evals, &batch_coeff);
81
82	let SumcheckOutput { eval, challenges } =
83		mlecheck::verify::<F, C>(point, degree, eval, channel)?;
84
85	Ok(BatchSumcheckOutput {
86		batch_coeff,
87		challenges,
88		eval,
89	})
90}
binius_ip/sumcheck/batch.rs

binius_ip/sumcheck/
batch.rs
