binius_ip_prover/sumcheck/
infinity.rs1use 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
19pub 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 RoundCoeffs(vec![prover.claim])
64 }
65 })
66 .collect::<Vec<_>>();
67
68 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
87pub 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 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 pub const fn n_vars(&self) -> usize {
120 self.tables[0].log_len()
121 }
122
123 pub const fn claim(&self) -> F {
125 self.claim
126 }
127
128 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 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 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 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 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 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 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 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}