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