testudo/src/sumcheck.rs
src/sumcheck.rsRaw
1use super::commitments::{Commitments, MultiCommitGens};
2use super::dense_mlpoly::DensePolynomial;
3use super::errors::ProofVerifyError;
4use super::group::{CompressedGroup, GroupElement, VartimeMultiscalarMul};
5use super::nizk::DotProductProof;
6use super::scalar::Scalar;
7use super::transcript::{AppendToTranscript, ProofTranscript};
8use super::unipoly::{CompressedUniPoly, UniPoly};
9use itertools::izip;
10use merlin::Transcript;
11use serde::{Deserialize, Serialize};
12use std::iter;
13
14#[derive(Serialize, Deserialize, Debug)]
15pub struct SumcheckInstanceProof {
16 compressed_polys: Vec<CompressedUniPoly>,
17}
18
19impl SumcheckInstanceProof {
20 pub fn new(compressed_polys: Vec<CompressedUniPoly>) -> SumcheckInstanceProof {
21 SumcheckInstanceProof { compressed_polys }
22 }
23
24 pub fn verify(
25 &self,
26 claim: Scalar,
27 num_rounds: usize,
28 degree_bound: usize,
29 transcript: &mut Transcript,
30 ) -> Result<(Scalar, Vec<Scalar>), ProofVerifyError> {
31 let mut e = claim;
32 let mut r: Vec<Scalar> = Vec::new();
33
34 // verify that there is a univariate polynomial for each round
35 assert_eq!(self.compressed_polys.len(), num_rounds);
36 for i in 0..self.compressed_polys.len() {
37 let poly = self.compressed_polys[i].decompress(&e);
38
39 // verify degree bound
40 assert_eq!(poly.degree(), degree_bound);
41
42 // check if G_k(0) + G_k(1) = e
43 assert_eq!(poly.eval_at_zero() + poly.eval_at_one(), e);
44
45 // append the prover's message to the transcript
46 poly.append_to_transcript(b"poly", transcript);
47
48 //derive the verifier's challenge for the next round
49 let r_i = transcript.challenge_scalar(b"challenge_nextround");
50
51 r.push(r_i);
52
53 // evaluate the claimed degree-ell polynomial at r_i
54 e = poly.evaluate(&r_i);
55 }
56
57 Ok((e, r))
58 }
59}
60
61#[derive(Serialize, Deserialize, Debug)]
62pub struct ZKSumcheckInstanceProof {
63 comm_polys: Vec<CompressedGroup>,
64 comm_evals: Vec<CompressedGroup>,
65 proofs: Vec<DotProductProof>,
66}
67
68impl ZKSumcheckInstanceProof {
69 pub fn new(
70 comm_polys: Vec<CompressedGroup>,
71 comm_evals: Vec<CompressedGroup>,
72 proofs: Vec<DotProductProof>,
73 ) -> Self {
74 ZKSumcheckInstanceProof {
75 comm_polys,
76 comm_evals,
77 proofs,
78 }
79 }
80
81 pub fn verify(
82 &self,
83 comm_claim: &CompressedGroup,
84 num_rounds: usize,
85 degree_bound: usize,
86 gens_1: &MultiCommitGens,
87 gens_n: &MultiCommitGens,
88 transcript: &mut Transcript,
89 ) -> Result<(CompressedGroup, Vec<Scalar>), ProofVerifyError> {
90 // verify degree bound
91 assert_eq!(gens_n.n, degree_bound + 1);
92
93 // verify that there is a univariate polynomial for each round
94 assert_eq!(self.comm_polys.len(), num_rounds);
95 assert_eq!(self.comm_evals.len(), num_rounds);
96
97 let mut r: Vec<Scalar> = Vec::new();
98 for i in 0..self.comm_polys.len() {
99 let comm_poly = &self.comm_polys[i];
100
101 // append the prover's polynomial to the transcript
102 comm_poly.append_to_transcript(b"comm_poly", transcript);
103
104 //derive the verifier's challenge for the next round
105 let r_i = transcript.challenge_scalar(b"challenge_nextround");
106
107 // verify the proof of sum-check and evals
108 let res = {
109 let comm_claim_per_round = if i == 0 {
110 comm_claim
111 } else {
112 &self.comm_evals[i - 1]
113 };
114 let comm_eval = &self.comm_evals[i];
115
116 // add two claims to transcript
117 comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
118 comm_eval.append_to_transcript(b"comm_eval", transcript);
119
120 // produce two weights
121 let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
122
123 // compute a weighted sum of the RHS
124 let comm_target = GroupElement::vartime_multiscalar_mul(
125 w.iter(),
126 iter::once(&comm_claim_per_round)
127 .chain(iter::once(&comm_eval))
128 .map(|pt| pt.decompress().unwrap())
129 .collect::<Vec<GroupElement>>(),
130 )
131 .compress();
132
133 let a = {
134 // the vector to use to decommit for sum-check test
135 let a_sc = {
136 let mut a = vec![Scalar::one(); degree_bound + 1];
137 a[0] = a[0] + Scalar::one();
138 a
139 };
140
141 // the vector to use to decommit for evaluation
142 let a_eval = {
143 let mut a = vec![Scalar::one(); degree_bound + 1];
144 for j in 1..a.len() {
145 a[j] = &a[j - 1] * &r_i;
146 }
147 a
148 };
149
150 // take weighted sum of the two vectors using w
151 assert_eq!(a_sc.len(), a_eval.len());
152 (0..a_sc.len())
153 .map(|i| &w[0] * &a_sc[i] + &w[1] * &a_eval[i])
154 .collect::<Vec<Scalar>>()
155 };
156
157 self.proofs[i]
158 .verify(
159 gens_1,
160 gens_n,
161 transcript,
162 &a,
163 &self.comm_polys[i],
164 &comm_target,
165 )
166 .is_ok()
167 };
168 assert!(res);
169
170 r.push(r_i);
171 }
172
173 Ok((self.comm_evals[self.comm_evals.len() - 1], r))
174 }
175}
176
177impl SumcheckInstanceProof {
178 pub fn prove_quad<F>(
179 claim: &Scalar,
180 num_rounds: usize,
181 poly_A: &mut DensePolynomial,
182 poly_B: &mut DensePolynomial,
183 comb_func: F,
184 transcript: &mut Transcript,
185 ) -> (Self, Vec<Scalar>, Vec<Scalar>)
186 where
187 F: Fn(&Scalar, &Scalar) -> Scalar,
188 {
189 let mut e = *claim;
190 let mut r: Vec<Scalar> = Vec::new();
191 let mut quad_polys: Vec<CompressedUniPoly> = Vec::new();
192 for _j in 0..num_rounds {
193 let mut eval_point_0 = Scalar::zero();
194 let mut eval_point_2 = Scalar::zero();
195
196 let len = poly_A.len() / 2;
197 for i in 0..len {
198 // eval 0: bound_func is A(low)
199 eval_point_0 = &eval_point_0 + comb_func(&poly_A[i], &poly_B[i]);
200
201 // eval 2: bound_func is -A(low) + 2*A(high)
202 let poly_A_bound_point = &poly_A[len + i] + &poly_A[len + i] - &poly_A[i];
203 let poly_B_bound_point = &poly_B[len + i] + &poly_B[len + i] - &poly_B[i];
204 eval_point_2 = &eval_point_2 + comb_func(&poly_A_bound_point, &poly_B_bound_point);
205 }
206
207 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2];
208 let poly = UniPoly::from_evals(&evals);
209
210 // append the prover's message to the transcript
211 poly.append_to_transcript(b"poly", transcript);
212
213 //derive the verifier's challenge for the next round
214 let r_j = transcript.challenge_scalar(b"challenge_nextround");
215 r.push(r_j);
216 // bound all tables to the verifier's challenege
217 poly_A.bound_poly_var_top(&r_j);
218 poly_B.bound_poly_var_top(&r_j);
219
220 e = poly.evaluate(&r_j);
221 quad_polys.push(poly.compress());
222 }
223
224 (
225 SumcheckInstanceProof::new(quad_polys),
226 r,
227 vec![poly_A[0], poly_B[0]],
228 )
229 }
230
231 pub fn prove_cubic<F>(
232 claim: &Scalar,
233 num_rounds: usize,
234 poly_A: &mut DensePolynomial,
235 poly_B: &mut DensePolynomial,
236 poly_C: &mut DensePolynomial,
237 comb_func: F,
238 transcript: &mut Transcript,
239 ) -> (Self, Vec<Scalar>, Vec<Scalar>)
240 where
241 F: Fn(&Scalar, &Scalar, &Scalar) -> Scalar,
242 {
243 let mut e = *claim;
244 let mut r: Vec<Scalar> = Vec::new();
245 let mut cubic_polys: Vec<CompressedUniPoly> = Vec::new();
246 for _j in 0..num_rounds {
247 let mut eval_point_0 = Scalar::zero();
248 let mut eval_point_2 = Scalar::zero();
249 let mut eval_point_3 = Scalar::zero();
250
251 let len = poly_A.len() / 2;
252 for i in 0..len {
253 // eval 0: bound_func is A(low)
254 eval_point_0 = &eval_point_0 + comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
255
256 // eval 2: bound_func is -A(low) + 2*A(high)
257 let poly_A_bound_point = &poly_A[len + i] + &poly_A[len + i] - &poly_A[i];
258 let poly_B_bound_point = &poly_B[len + i] + &poly_B[len + i] - &poly_B[i];
259 let poly_C_bound_point = &poly_C[len + i] + &poly_C[len + i] - &poly_C[i];
260 eval_point_2 = &eval_point_2
261 + comb_func(
262 &poly_A_bound_point,
263 &poly_B_bound_point,
264 &poly_C_bound_point,
265 );
266
267 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
268 let poly_A_bound_point = &poly_A_bound_point + &poly_A[len + i] - &poly_A[i];
269 let poly_B_bound_point = &poly_B_bound_point + &poly_B[len + i] - &poly_B[i];
270 let poly_C_bound_point = &poly_C_bound_point + &poly_C[len + i] - &poly_C[i];
271
272 eval_point_3 = &eval_point_3
273 + comb_func(
274 &poly_A_bound_point,
275 &poly_B_bound_point,
276 &poly_C_bound_point,
277 );
278 }
279
280 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2, eval_point_3];
281 let poly = UniPoly::from_evals(&evals);
282
283 // append the prover's message to the transcript
284 poly.append_to_transcript(b"poly", transcript);
285
286 //derive the verifier's challenge for the next round
287 let r_j = transcript.challenge_scalar(b"challenge_nextround");
288 r.push(r_j);
289 // bound all tables to the verifier's challenege
290 poly_A.bound_poly_var_top(&r_j);
291 poly_B.bound_poly_var_top(&r_j);
292 poly_C.bound_poly_var_top(&r_j);
293 e = poly.evaluate(&r_j);
294 cubic_polys.push(poly.compress());
295 }
296
297 (
298 SumcheckInstanceProof::new(cubic_polys),
299 r,
300 vec![poly_A[0], poly_B[0], poly_C[0]],
301 )
302 }
303
304 pub fn prove_cubic_with_additive_term<F>(
305 claim: &Scalar,
306 num_rounds: usize,
307 poly_A: &mut DensePolynomial,
308 poly_B: &mut DensePolynomial,
309 poly_C: &mut DensePolynomial,
310 poly_D: &mut DensePolynomial,
311 comb_func: F,
312 transcript: &mut Transcript,
313 ) -> (Self, Vec<Scalar>, Vec<Scalar>)
314 where
315 F: Fn(&Scalar, &Scalar, &Scalar, &Scalar) -> Scalar,
316 {
317 let mut e = *claim;
318 let mut r: Vec<Scalar> = Vec::new();
319 let mut cubic_polys: Vec<CompressedUniPoly> = Vec::new();
320 for _j in 0..num_rounds {
321 let mut eval_point_0 = Scalar::zero();
322 let mut eval_point_2 = Scalar::zero();
323 let mut eval_point_3 = Scalar::zero();
324
325 let len = poly_A.len() / 2;
326 for i in 0..len {
327 // eval 0: bound_func is A(low)
328 eval_point_0 = &eval_point_0 + comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
329
330 // eval 2: bound_func is -A(low) + 2*A(high)
331 let poly_A_bound_point = &poly_A[len + i] + &poly_A[len + i] - &poly_A[i];
332 let poly_B_bound_point = &poly_B[len + i] + &poly_B[len + i] - &poly_B[i];
333 let poly_C_bound_point = &poly_C[len + i] + &poly_C[len + i] - &poly_C[i];
334 let poly_D_bound_point = &poly_D[len + i] + &poly_D[len + i] - &poly_D[i];
335 eval_point_2 = &eval_point_2
336 + comb_func(
337 &poly_A_bound_point,
338 &poly_B_bound_point,
339 &poly_C_bound_point,
340 &poly_D_bound_point,
341 );
342
343 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
344 let poly_A_bound_point = &poly_A_bound_point + &poly_A[len + i] - &poly_A[i];
345 let poly_B_bound_point = &poly_B_bound_point + &poly_B[len + i] - &poly_B[i];
346 let poly_C_bound_point = &poly_C_bound_point + &poly_C[len + i] - &poly_C[i];
347 let poly_D_bound_point = &poly_D_bound_point + &poly_D[len + i] - &poly_D[i];
348 eval_point_3 = &eval_point_3
349 + comb_func(
350 &poly_A_bound_point,
351 &poly_B_bound_point,
352 &poly_C_bound_point,
353 &poly_D_bound_point,
354 );
355 }
356
357 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2, eval_point_3];
358 let poly = UniPoly::from_evals(&evals);
359
360 // append the prover's message to the transcript
361 poly.append_to_transcript(b"poly", transcript);
362
363 //derive the verifier's challenge for the next round
364 let r_j = transcript.challenge_scalar(b"challenge_nextround");
365 r.push(r_j);
366 // bound all tables to the verifier's challenege
367 poly_A.bound_poly_var_top(&r_j);
368 poly_B.bound_poly_var_top(&r_j);
369 poly_C.bound_poly_var_top(&r_j);
370 poly_D.bound_poly_var_top(&r_j);
371 e = poly.evaluate(&r_j);
372 cubic_polys.push(poly.compress());
373 }
374
375 (
376 SumcheckInstanceProof::new(cubic_polys),
377 r,
378 vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
379 )
380 }
381
382 pub fn prove_cubic_batched<F>(
383 claim: &Scalar,
384 num_rounds: usize,
385 poly_vec_par: (
386 &mut Vec<&mut DensePolynomial>,
387 &mut Vec<&mut DensePolynomial>,
388 &mut DensePolynomial,
389 ),
390 poly_vec_seq: (
391 &mut Vec<&mut DensePolynomial>,
392 &mut Vec<&mut DensePolynomial>,
393 &mut Vec<&mut DensePolynomial>,
394 ),
395 coeffs: &[Scalar],
396 comb_func: F,
397 transcript: &mut Transcript,
398 ) -> (
399 Self,
400 Vec<Scalar>,
401 (Vec<Scalar>, Vec<Scalar>, Scalar),
402 (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>),
403 )
404 where
405 F: Fn(&Scalar, &Scalar, &Scalar) -> Scalar,
406 {
407 let (poly_A_vec_par, poly_B_vec_par, poly_C_par) = poly_vec_par;
408 let (poly_A_vec_seq, poly_B_vec_seq, poly_C_vec_seq) = poly_vec_seq;
409
410 //let (poly_A_vec_seq, poly_B_vec_seq, poly_C_vec_seq) = poly_vec_seq;
411 let mut e = *claim;
412 let mut r: Vec<Scalar> = Vec::new();
413 let mut cubic_polys: Vec<CompressedUniPoly> = Vec::new();
414
415 for _j in 0..num_rounds {
416 let mut evals: Vec<(Scalar, Scalar, Scalar)> = Vec::new();
417
418 for (poly_A, poly_B) in poly_A_vec_par.iter().zip(poly_B_vec_par.iter()) {
419 let mut eval_point_0 = Scalar::zero();
420 let mut eval_point_2 = Scalar::zero();
421 let mut eval_point_3 = Scalar::zero();
422
423 let len = poly_A.len() / 2;
424 for i in 0..len {
425 // eval 0: bound_func is A(low)
426 eval_point_0 = &eval_point_0 + comb_func(&poly_A[i], &poly_B[i], &poly_C_par[i]);
427
428 // eval 2: bound_func is -A(low) + 2*A(high)
429 let poly_A_bound_point = &poly_A[len + i] + &poly_A[len + i] - &poly_A[i];
430 let poly_B_bound_point = &poly_B[len + i] + &poly_B[len + i] - &poly_B[i];
431 let poly_C_bound_point = &poly_C_par[len + i] + &poly_C_par[len + i] - &poly_C_par[i];
432 eval_point_2 = &eval_point_2
433 + comb_func(
434 &poly_A_bound_point,
435 &poly_B_bound_point,
436 &poly_C_bound_point,
437 );
438
439 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
440 let poly_A_bound_point = &poly_A_bound_point + &poly_A[len + i] - &poly_A[i];
441 let poly_B_bound_point = &poly_B_bound_point + &poly_B[len + i] - &poly_B[i];
442 let poly_C_bound_point = &poly_C_bound_point + &poly_C_par[len + i] - &poly_C_par[i];
443
444 eval_point_3 = &eval_point_3
445 + comb_func(
446 &poly_A_bound_point,
447 &poly_B_bound_point,
448 &poly_C_bound_point,
449 );
450 }
451
452 evals.push((eval_point_0, eval_point_2, eval_point_3));
453 }
454
455 for (poly_A, poly_B, poly_C) in izip!(
456 poly_A_vec_seq.iter(),
457 poly_B_vec_seq.iter(),
458 poly_C_vec_seq.iter()
459 ) {
460 let mut eval_point_0 = Scalar::zero();
461 let mut eval_point_2 = Scalar::zero();
462 let mut eval_point_3 = Scalar::zero();
463 let len = poly_A.len() / 2;
464 for i in 0..len {
465 // eval 0: bound_func is A(low)
466 eval_point_0 = &eval_point_0 + comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
467 // eval 2: bound_func is -A(low) + 2*A(high)
468 let poly_A_bound_point = &poly_A[len + i] + &poly_A[len + i] - &poly_A[i];
469 let poly_B_bound_point = &poly_B[len + i] + &poly_B[len + i] - &poly_B[i];
470 let poly_C_bound_point = &poly_C[len + i] + &poly_C[len + i] - &poly_C[i];
471 eval_point_2 = &eval_point_2
472 + comb_func(
473 &poly_A_bound_point,
474 &poly_B_bound_point,
475 &poly_C_bound_point,
476 );
477 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
478 let poly_A_bound_point = &poly_A_bound_point + &poly_A[len + i] - &poly_A[i];
479 let poly_B_bound_point = &poly_B_bound_point + &poly_B[len + i] - &poly_B[i];
480 let poly_C_bound_point = &poly_C_bound_point + &poly_C[len + i] - &poly_C[i];
481 eval_point_3 = &eval_point_3
482 + comb_func(
483 &poly_A_bound_point,
484 &poly_B_bound_point,
485 &poly_C_bound_point,
486 );
487 }
488 evals.push((eval_point_0, eval_point_2, eval_point_3));
489 }
490
491 let evals_combined_0 = (0..evals.len()).map(|i| evals[i].0 * coeffs[i]).sum();
492 let evals_combined_2 = (0..evals.len()).map(|i| evals[i].1 * coeffs[i]).sum();
493 let evals_combined_3 = (0..evals.len()).map(|i| evals[i].2 * coeffs[i]).sum();
494
495 let evals = vec![
496 evals_combined_0,
497 e - evals_combined_0,
498 evals_combined_2,
499 evals_combined_3,
500 ];
501 let poly = UniPoly::from_evals(&evals);
502
503 // append the prover's message to the transcript
504 poly.append_to_transcript(b"poly", transcript);
505
506 //derive the verifier's challenge for the next round
507 let r_j = transcript.challenge_scalar(b"challenge_nextround");
508 r.push(r_j);
509
510 // bound all tables to the verifier's challenege
511 for (poly_A, poly_B) in poly_A_vec_par.iter_mut().zip(poly_B_vec_par.iter_mut()) {
512 poly_A.bound_poly_var_top(&r_j);
513 poly_B.bound_poly_var_top(&r_j);
514 }
515 poly_C_par.bound_poly_var_top(&r_j);
516
517 for (poly_A, poly_B, poly_C) in izip!(
518 poly_A_vec_seq.iter_mut(),
519 poly_B_vec_seq.iter_mut(),
520 poly_C_vec_seq.iter_mut()
521 ) {
522 poly_A.bound_poly_var_top(&r_j);
523 poly_B.bound_poly_var_top(&r_j);
524 poly_C.bound_poly_var_top(&r_j);
525 }
526
527 e = poly.evaluate(&r_j);
528 cubic_polys.push(poly.compress());
529 }
530
531 let poly_A_par_final = (0..poly_A_vec_par.len())
532 .map(|i| poly_A_vec_par[i][0])
533 .collect();
534 let poly_B_par_final = (0..poly_B_vec_par.len())
535 .map(|i| poly_B_vec_par[i][0])
536 .collect();
537 let claims_prod = (poly_A_par_final, poly_B_par_final, poly_C_par[0]);
538
539 let poly_A_seq_final = (0..poly_A_vec_seq.len())
540 .map(|i| poly_A_vec_seq[i][0])
541 .collect();
542 let poly_B_seq_final = (0..poly_B_vec_seq.len())
543 .map(|i| poly_B_vec_seq[i][0])
544 .collect();
545 let poly_C_seq_final = (0..poly_C_vec_seq.len())
546 .map(|i| poly_C_vec_seq[i][0])
547 .collect();
548 let claims_dotp = (poly_A_seq_final, poly_B_seq_final, poly_C_seq_final);
549
550 (
551 SumcheckInstanceProof::new(cubic_polys),
552 r,
553 claims_prod,
554 claims_dotp,
555 )
556 }
557}
558
559impl ZKSumcheckInstanceProof {
560 pub fn prove_quad<F>(
561 claim: &Scalar,
562 blind_claim: &Scalar,
563 num_rounds: usize,
564 poly_A: &mut DensePolynomial,
565 poly_B: &mut DensePolynomial,
566 comb_func: F,
567 gens_1: &MultiCommitGens,
568 gens_n: &MultiCommitGens,
569 transcript: &mut Transcript,
570 random_tape: &mut Transcript,
571 ) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
572 where
573 F: Fn(&Scalar, &Scalar) -> Scalar,
574 {
575 let (blinds_poly, blinds_evals) = (
576 random_tape.challenge_vector(b"blinds_poly", num_rounds),
577 random_tape.challenge_vector(b"blinds_evals", num_rounds),
578 );
579 let mut claim_per_round = *claim;
580 let mut comm_claim_per_round = claim_per_round.commit(&blind_claim, &gens_1).compress();
581
582 let mut r: Vec<Scalar> = Vec::new();
583 let mut comm_polys: Vec<CompressedGroup> = Vec::new();
584 let mut comm_evals: Vec<CompressedGroup> = Vec::new();
585 let mut proofs: Vec<DotProductProof> = Vec::new();
586
587 for j in 0..num_rounds {
588 let (poly, comm_poly) = {
589 let mut eval_point_0 = Scalar::zero();
590 let mut eval_point_2 = Scalar::zero();
591
592 let len = poly_A.len() / 2;
593 for i in 0..len {
594 // eval 0: bound_func is A(low)
595 eval_point_0 = &eval_point_0 + comb_func(&poly_A[i], &poly_B[i]);
596
597 // eval 2: bound_func is -A(low) + 2*A(high)
598 let poly_A_bound_point = &poly_A[len + i] + &poly_A[len + i] - &poly_A[i];
599 let poly_B_bound_point = &poly_B[len + i] + &poly_B[len + i] - &poly_B[i];
600 eval_point_2 = &eval_point_2 + comb_func(&poly_A_bound_point, &poly_B_bound_point);
601 }
602
603 let evals = vec![eval_point_0, claim_per_round - eval_point_0, eval_point_2];
604 let poly = UniPoly::from_evals(&evals);
605 let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
606 (poly, comm_poly)
607 };
608
609 // append the prover's message to the transcript
610 comm_poly.append_to_transcript(b"comm_poly", transcript);
611 comm_polys.push(comm_poly);
612
613 //derive the verifier's challenge for the next round
614 let r_j = transcript.challenge_scalar(b"challenge_nextround");
615
616 // bound all tables to the verifier's challenege
617 poly_A.bound_poly_var_top(&r_j);
618 poly_B.bound_poly_var_top(&r_j);
619
620 // produce a proof of sum-check and of evaluation
621 let (proof, claim_next_round, comm_claim_next_round) = {
622 let eval = poly.evaluate(&r_j);
623 let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
624
625 // we need to prove the following under homomorphic commitments:
626 // (1) poly(0) + poly(1) = claim_per_round
627 // (2) poly(r_j) = eval
628
629 // Our technique is to leverage dot product proofs:
630 // (1) we can prove: <poly_in_coeffs_form, (2, 1, 1, 1)> = claim_per_round
631 // (2) we can prove: <poly_in_coeffs_form, (1, r_j, r^2_j, ..) = eval
632 // for efficiency we batch them using random weights
633
634 // add two claims to transcript
635 comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
636 comm_eval.append_to_transcript(b"comm_eval", transcript);
637
638 // produce two weights
639 let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
640
641 // compute a weighted sum of the RHS
642 let target = &w[0] * &claim_per_round + &w[1] * &eval;
643 let comm_target = GroupElement::vartime_multiscalar_mul(
644 w.iter(),
645 iter::once(&comm_claim_per_round)
646 .chain(iter::once(&comm_eval))
647 .map(|pt| pt.decompress().unwrap())
648 .collect::<Vec<GroupElement>>(),
649 )
650 .compress();
651
652 let blind = {
653 let blind_sc = if j == 0 {
654 blind_claim
655 } else {
656 &blinds_evals[j - 1]
657 };
658
659 let blind_eval = &blinds_evals[j];
660
661 &w[0] * blind_sc + &w[1] * blind_eval
662 };
663 assert_eq!(target.commit(&blind, &gens_1).compress(), comm_target);
664
665 let a = {
666 // the vector to use to decommit for sum-check test
667 let a_sc = {
668 let mut a = vec![Scalar::one(); poly.degree() + 1];
669 a[0] = a[0] + Scalar::one();
670 a
671 };
672
673 // the vector to use to decommit for evaluation
674 let a_eval = {
675 let mut a = vec![Scalar::one(); poly.degree() + 1];
676 for j in 1..a.len() {
677 a[j] = &a[j - 1] * &r_j;
678 }
679 a
680 };
681
682 // take weighted sum of the two vectors using w
683 assert_eq!(a_sc.len(), a_eval.len());
684 (0..a_sc.len())
685 .map(|i| &w[0] * &a_sc[i] + &w[1] * &a_eval[i])
686 .collect::<Vec<Scalar>>()
687 };
688
689 let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
690 gens_1,
691 gens_n,
692 transcript,
693 random_tape,
694 &poly.as_vec(),
695 &blinds_poly[j],
696 &a,
697 &target,
698 &blind,
699 );
700
701 (proof, eval, comm_eval)
702 };
703
704 claim_per_round = claim_next_round;
705 comm_claim_per_round = comm_claim_next_round;
706
707 proofs.push(proof);
708 r.push(r_j);
709 comm_evals.push(comm_claim_per_round);
710 }
711
712 (
713 ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
714 r,
715 vec![poly_A[0], poly_B[0]],
716 blinds_evals[num_rounds - 1],
717 )
718 }
719
720 pub fn prove_cubic_with_additive_term<F>(
721 claim: &Scalar,
722 blind_claim: &Scalar,
723 num_rounds: usize,
724 poly_A: &mut DensePolynomial,
725 poly_B: &mut DensePolynomial,
726 poly_C: &mut DensePolynomial,
727 poly_D: &mut DensePolynomial,
728 comb_func: F,
729 gens_1: &MultiCommitGens,
730 gens_n: &MultiCommitGens,
731 transcript: &mut Transcript,
732 random_tape: &mut Transcript,
733 ) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
734 where
735 F: Fn(&Scalar, &Scalar, &Scalar, &Scalar) -> Scalar,
736 {
737 let (blinds_poly, blinds_evals) = (
738 random_tape.challenge_vector(b"blinds_poly", num_rounds),
739 random_tape.challenge_vector(b"blinds_evals", num_rounds),
740 );
741
742 let mut claim_per_round = *claim;
743 let mut comm_claim_per_round = claim_per_round.commit(&blind_claim, &gens_1).compress();
744
745 let mut r: Vec<Scalar> = Vec::new();
746 let mut comm_polys: Vec<CompressedGroup> = Vec::new();
747 let mut comm_evals: Vec<CompressedGroup> = Vec::new();
748 let mut proofs: Vec<DotProductProof> = Vec::new();
749
750 for j in 0..num_rounds {
751 let (poly, comm_poly) = {
752 let mut eval_point_0 = Scalar::zero();
753 let mut eval_point_2 = Scalar::zero();
754 let mut eval_point_3 = Scalar::zero();
755
756 let len = poly_A.len() / 2;
757 for i in 0..len {
758 // eval 0: bound_func is A(low)
759 eval_point_0 = &eval_point_0 + comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
760
761 // eval 2: bound_func is -A(low) + 2*A(high)
762 let poly_A_bound_point = &poly_A[len + i] + &poly_A[len + i] - &poly_A[i];
763 let poly_B_bound_point = &poly_B[len + i] + &poly_B[len + i] - &poly_B[i];
764 let poly_C_bound_point = &poly_C[len + i] + &poly_C[len + i] - &poly_C[i];
765 let poly_D_bound_point = &poly_D[len + i] + &poly_D[len + i] - &poly_D[i];
766 eval_point_2 = &eval_point_2
767 + comb_func(
768 &poly_A_bound_point,
769 &poly_B_bound_point,
770 &poly_C_bound_point,
771 &poly_D_bound_point,
772 );
773
774 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
775 let poly_A_bound_point = &poly_A_bound_point + &poly_A[len + i] - &poly_A[i];
776 let poly_B_bound_point = &poly_B_bound_point + &poly_B[len + i] - &poly_B[i];
777 let poly_C_bound_point = &poly_C_bound_point + &poly_C[len + i] - &poly_C[i];
778 let poly_D_bound_point = &poly_D_bound_point + &poly_D[len + i] - &poly_D[i];
779 eval_point_3 = &eval_point_3
780 + comb_func(
781 &poly_A_bound_point,
782 &poly_B_bound_point,
783 &poly_C_bound_point,
784 &poly_D_bound_point,
785 );
786 }
787
788 let evals = vec![
789 eval_point_0,
790 claim_per_round - eval_point_0,
791 eval_point_2,
792 eval_point_3,
793 ];
794 let poly = UniPoly::from_evals(&evals);
795 let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
796 (poly, comm_poly)
797 };
798
799 // append the prover's message to the transcript
800 comm_poly.append_to_transcript(b"comm_poly", transcript);
801 comm_polys.push(comm_poly);
802
803 //derive the verifier's challenge for the next round
804 let r_j = transcript.challenge_scalar(b"challenge_nextround");
805
806 // bound all tables to the verifier's challenege
807 poly_A.bound_poly_var_top(&r_j);
808 poly_B.bound_poly_var_top(&r_j);
809 poly_C.bound_poly_var_top(&r_j);
810 poly_D.bound_poly_var_top(&r_j);
811
812 // produce a proof of sum-check and of evaluation
813 let (proof, claim_next_round, comm_claim_next_round) = {
814 let eval = poly.evaluate(&r_j);
815 let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
816
817 // we need to prove the following under homomorphic commitments:
818 // (1) poly(0) + poly(1) = claim_per_round
819 // (2) poly(r_j) = eval
820
821 // Our technique is to leverage dot product proofs:
822 // (1) we can prove: <poly_in_coeffs_form, (2, 1, 1, 1)> = claim_per_round
823 // (2) we can prove: <poly_in_coeffs_form, (1, r_j, r^2_j, ..) = eval
824 // for efficiency we batch them using random weights
825
826 // add two claims to transcript
827 comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
828 comm_eval.append_to_transcript(b"comm_eval", transcript);
829
830 // produce two weights
831 let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
832
833 // compute a weighted sum of the RHS
834 let target = &w[0] * &claim_per_round + &w[1] * &eval;
835 let comm_target = GroupElement::vartime_multiscalar_mul(
836 w.iter(),
837 iter::once(&comm_claim_per_round)
838 .chain(iter::once(&comm_eval))
839 .map(|pt| pt.decompress().unwrap())
840 .collect::<Vec<GroupElement>>(),
841 )
842 .compress();
843
844 let blind = {
845 let blind_sc = if j == 0 {
846 blind_claim
847 } else {
848 &blinds_evals[j - 1]
849 };
850
851 let blind_eval = &blinds_evals[j];
852
853 &w[0] * blind_sc + &w[1] * blind_eval
854 };
855
856 assert_eq!(target.commit(&blind, &gens_1).compress(), comm_target);
857
858 let a = {
859 // the vector to use to decommit for sum-check test
860 let a_sc = {
861 let mut a = vec![Scalar::one(); poly.degree() + 1];
862 a[0] = a[0] + Scalar::one();
863 a
864 };
865
866 // the vector to use to decommit for evaluation
867 let a_eval = {
868 let mut a = vec![Scalar::one(); poly.degree() + 1];
869 for j in 1..a.len() {
870 a[j] = &a[j - 1] * &r_j;
871 }
872 a
873 };
874
875 // take weighted sum of the two vectors using w
876 assert_eq!(a_sc.len(), a_eval.len());
877 (0..a_sc.len())
878 .map(|i| &w[0] * &a_sc[i] + &w[1] * &a_eval[i])
879 .collect::<Vec<Scalar>>()
880 };
881
882 let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
883 gens_1,
884 gens_n,
885 transcript,
886 random_tape,
887 &poly.as_vec(),
888 &blinds_poly[j],
889 &a,
890 &target,
891 &blind,
892 );
893
894 (proof, eval, comm_eval)
895 };
896
897 proofs.push(proof);
898 claim_per_round = claim_next_round;
899 comm_claim_per_round = comm_claim_next_round;
900 r.push(r_j);
901 comm_evals.push(comm_claim_per_round);
902 }
903
904 (
905 ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
906 r,
907 vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
908 blinds_evals[num_rounds - 1],
909 )
910 }
911}