testudo/src/sumcheck.rs
src/sumcheck.rsRaw
1#![allow(clippy::too_many_arguments)]
2#![allow(clippy::type_complexity)]
3use super::dense_mlpoly::DensePolynomial;
4use super::errors::ProofVerifyError;
5use crate::poseidon_transcript::{PoseidonTranscript, TranscriptWriter};
6use crate::transcript::Transcript;
7
8use super::unipoly::UniPoly;
9use ark_crypto_primitives::sponge::Absorb;
10use ark_ff::PrimeField;
11
12use ark_serialize::*;
13
14use itertools::izip;
15
16#[derive(CanonicalSerialize, CanonicalDeserialize, Debug)]
17pub struct SumcheckInstanceProof<F: PrimeField> {
18 pub polys: Vec<UniPoly<F>>,
19}
20
21impl<F: PrimeField + Absorb> SumcheckInstanceProof<F> {
22 pub fn new(polys: Vec<UniPoly<F>>) -> Self {
23 SumcheckInstanceProof { polys }
24 }
25
26 pub fn verify(
27 &self,
28 claim: F,
29 num_rounds: usize,
30 degree_bound: usize,
31 transcript: &mut PoseidonTranscript<F>,
32 ) -> Result<(F, Vec<F>), ProofVerifyError> {
33 let mut e = claim;
34 let mut r: Vec<F> = Vec::new();
35
36 // verify that there is a univariate polynomial for each round
37 assert_eq!(self.polys.len(), num_rounds);
38 for i in 0..self.polys.len() {
39 let poly = self.polys[i].clone();
40
41 // verify degree bound
42 assert_eq!(poly.degree(), degree_bound);
43 // check if G_k(0) + G_k(1) = e
44
45 assert_eq!(poly.eval_at_zero() + poly.eval_at_one(), e);
46
47 // append the prover's message to the transcript
48 poly.write_to_transcript(transcript);
49
50 //derive the verifier's challenge for the next round
51 let r_i = transcript.challenge_scalar(b"");
52
53 r.push(r_i);
54
55 // evaluate the claimed degree-ell polynomial at r_i
56 e = poly.evaluate(&r_i);
57 }
58
59 Ok((e, r))
60 }
61}
62
63impl<F: PrimeField + Absorb> SumcheckInstanceProof<F> {
64 pub fn prove_cubic_with_additive_term<C>(
65 claim: &F,
66 num_rounds: usize,
67 poly_tau: &mut DensePolynomial<F>,
68 poly_A: &mut DensePolynomial<F>,
69 poly_B: &mut DensePolynomial<F>,
70 poly_C: &mut DensePolynomial<F>,
71 comb_func: C,
72 transcript: &mut PoseidonTranscript<F>,
73 ) -> (Self, Vec<F>, Vec<F>)
74 where
75 C: Fn(&F, &F, &F, &F) -> F,
76 {
77 let mut e = *claim;
78 let mut r: Vec<F> = Vec::new();
79 let mut cubic_polys: Vec<UniPoly<F>> = Vec::new();
80 for _j in 0..num_rounds {
81 let mut eval_point_0 = F::zero();
82 let mut eval_point_2 = F::zero();
83 let mut eval_point_3 = F::zero();
84
85 let len = poly_tau.len() / 2;
86 for i in 0..len {
87 // eval 0: bound_func is A(low)
88 eval_point_0 += comb_func(&poly_tau[i], &poly_A[i], &poly_B[i], &poly_C[i]);
89
90 // eval 2: bound_func is -A(low) + 2*A(high)
91 let poly_tau_bound_point = poly_tau[len + i] + poly_tau[len + i] - poly_tau[i];
92 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
93 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
94 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
95
96 eval_point_2 += comb_func(
97 &poly_tau_bound_point,
98 &poly_A_bound_point,
99 &poly_B_bound_point,
100 &poly_C_bound_point,
101 );
102
103 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
104 let poly_tau_bound_point = poly_tau_bound_point + poly_tau[len + i] - poly_tau[i];
105 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
106 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
107 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
108
109 eval_point_3 += comb_func(
110 &poly_tau_bound_point,
111 &poly_A_bound_point,
112 &poly_B_bound_point,
113 &poly_C_bound_point,
114 );
115 }
116
117 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2, eval_point_3];
118 let poly = UniPoly::from_evals(&evals);
119
120 // append the prover's message to the transcript
121 poly.write_to_transcript(transcript);
122 //derive the verifier's challenge for the next round
123 let r_j = transcript.challenge_scalar(b"");
124 r.push(r_j);
125
126 // bound all tables to the verifier's challenege
127 poly_tau.bound_poly_var_top(&r_j);
128 poly_A.bound_poly_var_top(&r_j);
129 poly_B.bound_poly_var_top(&r_j);
130 poly_C.bound_poly_var_top(&r_j);
131
132 e = poly.evaluate(&r_j);
133 cubic_polys.push(poly);
134 }
135 (
136 SumcheckInstanceProof::new(cubic_polys),
137 r,
138 vec![poly_tau[0], poly_A[0], poly_B[0], poly_C[0]],
139 )
140 }
141 pub fn prove_cubic<C>(
142 claim: &F,
143 num_rounds: usize,
144 poly_A: &mut DensePolynomial<F>,
145 poly_B: &mut DensePolynomial<F>,
146 poly_C: &mut DensePolynomial<F>,
147 comb_func: C,
148 transcript: &mut PoseidonTranscript<F>,
149 ) -> (Self, Vec<F>, Vec<F>)
150 where
151 C: Fn(&F, &F, &F) -> F,
152 {
153 let mut e = *claim;
154 let mut r: Vec<F> = Vec::new();
155 let mut cubic_polys: Vec<UniPoly<F>> = Vec::new();
156 for _j in 0..num_rounds {
157 let mut eval_point_0 = F::zero();
158 let mut eval_point_2 = F::zero();
159 let mut eval_point_3 = F::zero();
160
161 let len = poly_A.len() / 2;
162 for i in 0..len {
163 // eval 0: bound_func is A(low)
164 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
165
166 // eval 2: bound_func is -A(low) + 2*A(high)
167 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
168 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
169 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
170 eval_point_2 += comb_func(
171 &poly_A_bound_point,
172 &poly_B_bound_point,
173 &poly_C_bound_point,
174 );
175
176 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
177 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
178 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
179 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
180
181 eval_point_3 += comb_func(
182 &poly_A_bound_point,
183 &poly_B_bound_point,
184 &poly_C_bound_point,
185 );
186 }
187
188 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2, eval_point_3];
189 let poly = UniPoly::from_evals(&evals);
190
191 // append the prover's message to the transcript
192 poly.write_to_transcript(transcript);
193
194 //derive the verifier's challenge for the next round
195 let r_j = transcript.challenge_scalar(b"");
196 r.push(r_j);
197 // bound all tables to the verifier's challenege
198 poly_A.bound_poly_var_top(&r_j);
199 poly_B.bound_poly_var_top(&r_j);
200 poly_C.bound_poly_var_top(&r_j);
201 e = poly.evaluate(&r_j);
202 cubic_polys.push(poly);
203 }
204
205 (
206 SumcheckInstanceProof::new(cubic_polys),
207 r,
208 vec![poly_A[0], poly_B[0], poly_C[0]],
209 )
210 }
211
212 pub fn prove_cubic_batched<C>(
213 claim: &F,
214 num_rounds: usize,
215 poly_vec_par: (
216 &mut Vec<&mut DensePolynomial<F>>,
217 &mut Vec<&mut DensePolynomial<F>>,
218 &mut DensePolynomial<F>,
219 ),
220 poly_vec_seq: (
221 &mut Vec<&mut DensePolynomial<F>>,
222 &mut Vec<&mut DensePolynomial<F>>,
223 &mut Vec<&mut DensePolynomial<F>>,
224 ),
225 coeffs: &[F],
226 comb_func: C,
227 transcript: &mut PoseidonTranscript<F>,
228 ) -> (Self, Vec<F>, (Vec<F>, Vec<F>, F), (Vec<F>, Vec<F>, Vec<F>))
229 where
230 C: Fn(&F, &F, &F) -> F,
231 {
232 let (poly_A_vec_par, poly_B_vec_par, poly_C_par) = poly_vec_par;
233 let (poly_A_vec_seq, poly_B_vec_seq, poly_C_vec_seq) = poly_vec_seq;
234
235 //let (poly_A_vec_seq, poly_B_vec_seq, poly_C_vec_seq) = poly_vec_seq;
236 let mut e = *claim;
237 let mut r: Vec<F> = Vec::new();
238 let mut cubic_polys: Vec<UniPoly<F>> = Vec::new();
239
240 for _j in 0..num_rounds {
241 let mut evals: Vec<(F, F, F)> = Vec::new();
242
243 for (poly_A, poly_B) in poly_A_vec_par.iter().zip(poly_B_vec_par.iter()) {
244 let mut eval_point_0 = F::zero();
245 let mut eval_point_2 = F::zero();
246 let mut eval_point_3 = F::zero();
247
248 let len = poly_A.len() / 2;
249 for i in 0..len {
250 // eval 0: bound_func is A(low)
251 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C_par[i]);
252
253 // eval 2: bound_func is -A(low) + 2*A(high)
254 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
255 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
256 let poly_C_bound_point = poly_C_par[len + i] + poly_C_par[len + i] - poly_C_par[i];
257 eval_point_2 += comb_func(
258 &poly_A_bound_point,
259 &poly_B_bound_point,
260 &poly_C_bound_point,
261 );
262
263 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
264 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
265 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
266 let poly_C_bound_point = poly_C_bound_point + poly_C_par[len + i] - poly_C_par[i];
267
268 eval_point_3 += comb_func(
269 &poly_A_bound_point,
270 &poly_B_bound_point,
271 &poly_C_bound_point,
272 );
273 }
274
275 evals.push((eval_point_0, eval_point_2, eval_point_3));
276 }
277
278 for (poly_A, poly_B, poly_C) in izip!(
279 poly_A_vec_seq.iter(),
280 poly_B_vec_seq.iter(),
281 poly_C_vec_seq.iter()
282 ) {
283 let mut eval_point_0 = F::zero();
284 let mut eval_point_2 = F::zero();
285 let mut eval_point_3 = F::zero();
286 let len = poly_A.len() / 2;
287 for i in 0..len {
288 // eval 0: bound_func is A(low)
289 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
290 // eval 2: bound_func is -A(low) + 2*A(high)
291 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
292 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
293 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
294 eval_point_2 += comb_func(
295 &poly_A_bound_point,
296 &poly_B_bound_point,
297 &poly_C_bound_point,
298 );
299 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
300 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
301 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
302 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
303 eval_point_3 += comb_func(
304 &poly_A_bound_point,
305 &poly_B_bound_point,
306 &poly_C_bound_point,
307 );
308 }
309 evals.push((eval_point_0, eval_point_2, eval_point_3));
310 }
311
312 let evals_combined_0 = (0..evals.len()).map(|i| evals[i].0 * coeffs[i]).sum();
313 let evals_combined_2 = (0..evals.len()).map(|i| evals[i].1 * coeffs[i]).sum();
314 let evals_combined_3 = (0..evals.len()).map(|i| evals[i].2 * coeffs[i]).sum();
315
316 let evals = vec![
317 evals_combined_0,
318 e - evals_combined_0,
319 evals_combined_2,
320 evals_combined_3,
321 ];
322 let poly = UniPoly::from_evals(&evals);
323
324 // append the prover's message to the transcript
325 poly.write_to_transcript(transcript);
326
327 //derive the verifier's challenge for the next round
328 let r_j = transcript.challenge_scalar(b"");
329 r.push(r_j);
330
331 // bound all tables to the verifier's challenege
332 for (poly_A, poly_B) in poly_A_vec_par.iter_mut().zip(poly_B_vec_par.iter_mut()) {
333 poly_A.bound_poly_var_top(&r_j);
334 poly_B.bound_poly_var_top(&r_j);
335 }
336 poly_C_par.bound_poly_var_top(&r_j);
337
338 for (poly_A, poly_B, poly_C) in izip!(
339 poly_A_vec_seq.iter_mut(),
340 poly_B_vec_seq.iter_mut(),
341 poly_C_vec_seq.iter_mut()
342 ) {
343 poly_A.bound_poly_var_top(&r_j);
344 poly_B.bound_poly_var_top(&r_j);
345 poly_C.bound_poly_var_top(&r_j);
346 }
347
348 e = poly.evaluate(&r_j);
349 cubic_polys.push(poly);
350 }
351
352 let poly_A_par_final = (0..poly_A_vec_par.len())
353 .map(|i| poly_A_vec_par[i][0])
354 .collect();
355 let poly_B_par_final = (0..poly_B_vec_par.len())
356 .map(|i| poly_B_vec_par[i][0])
357 .collect();
358 let claims_prod = (poly_A_par_final, poly_B_par_final, poly_C_par[0]);
359
360 let poly_A_seq_final = (0..poly_A_vec_seq.len())
361 .map(|i| poly_A_vec_seq[i][0])
362 .collect();
363 let poly_B_seq_final = (0..poly_B_vec_seq.len())
364 .map(|i| poly_B_vec_seq[i][0])
365 .collect();
366 let poly_C_seq_final = (0..poly_C_vec_seq.len())
367 .map(|i| poly_C_vec_seq[i][0])
368 .collect();
369 let claims_dotp = (poly_A_seq_final, poly_B_seq_final, poly_C_seq_final);
370
371 (
372 SumcheckInstanceProof::new(cubic_polys),
373 r,
374 claims_prod,
375 claims_dotp,
376 )
377 }
378
379 pub fn prove_quad<C>(
380 claim: &F,
381 num_rounds: usize,
382 poly_A: &mut DensePolynomial<F>,
383 poly_B: &mut DensePolynomial<F>,
384 comb_func: C,
385 transcript: &mut PoseidonTranscript<F>,
386 ) -> (Self, Vec<F>, Vec<F>)
387 where
388 C: Fn(&F, &F) -> F,
389 {
390 let mut e = *claim;
391 let mut r: Vec<F> = Vec::new();
392 let mut quad_polys: Vec<UniPoly<F>> = Vec::new();
393
394 for _j in 0..num_rounds {
395 let mut eval_point_0 = F::zero();
396 let mut eval_point_2 = F::zero();
397
398 let len = poly_A.len() / 2;
399 for i in 0..len {
400 // eval 0: bound_func is A(low)
401 eval_point_0 += comb_func(&poly_A[i], &poly_B[i]);
402
403 // eval 2: bound_func is -A(low) + 2*A(high)
404 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
405 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
406 eval_point_2 += comb_func(&poly_A_bound_point, &poly_B_bound_point);
407 }
408
409 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2];
410 let poly = UniPoly::from_evals(&evals);
411
412 // append the prover's message to the transcript
413 poly.write_to_transcript(transcript);
414
415 //derive the verifier's challenge for the next round
416 let r_j = transcript.challenge_scalar(b"");
417 r.push(r_j);
418
419 // bound all tables to the verifier's challenege
420 poly_A.bound_poly_var_top(&r_j);
421 poly_B.bound_poly_var_top(&r_j);
422 e = poly.evaluate(&r_j);
423 quad_polys.push(poly);
424 }
425
426 (
427 SumcheckInstanceProof::new(quad_polys),
428 r,
429 vec![poly_A[0], poly_B[0]],
430 )
431 }
432}