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 assert!(res);
172
173 r.push(r_i);
174 }
175
176 Ok((self.comm_evals[self.comm_evals.len() - 1], r))
177 }
178}
179
180impl SumcheckInstanceProof {
181 pub fn prove_cubic<F>(
182 claim: &Scalar,
183 num_rounds: usize,
184 poly_A: &mut DensePolynomial,
185 poly_B: &mut DensePolynomial,
186 poly_C: &mut DensePolynomial,
187 comb_func: F,
188 transcript: &mut Transcript,
189 ) -> (Self, Vec<Scalar>, Vec<Scalar>)
190 where
191 F: Fn(&Scalar, &Scalar, &Scalar) -> Scalar,
192 {
193 let mut e = *claim;
194 let mut r: Vec<Scalar> = Vec::new();
195 let mut cubic_polys: Vec<CompressedUniPoly> = Vec::new();
196 for _j in 0..num_rounds {
197 let mut eval_point_0 = Scalar::zero();
198 let mut eval_point_2 = Scalar::zero();
199 let mut eval_point_3 = Scalar::zero();
200
201 let len = poly_A.len() / 2;
202 for i in 0..len {
203 // eval 0: bound_func is A(low)
204 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
205
206 // eval 2: bound_func is -A(low) + 2*A(high)
207 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
208 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
209 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
210 eval_point_2 += comb_func(
211 &poly_A_bound_point,
212 &poly_B_bound_point,
213 &poly_C_bound_point,
214 );
215
216 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
217 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
218 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
219 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
220
221 eval_point_3 += comb_func(
222 &poly_A_bound_point,
223 &poly_B_bound_point,
224 &poly_C_bound_point,
225 );
226 }
227
228 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2, eval_point_3];
229 let poly = UniPoly::from_evals(&evals);
230
231 // append the prover's message to the transcript
232 poly.append_to_transcript(b"poly", transcript);
233
234 //derive the verifier's challenge for the next round
235 let r_j = transcript.challenge_scalar(b"challenge_nextround");
236 r.push(r_j);
237 // bound all tables to the verifier's challenege
238 poly_A.bound_poly_var_top(&r_j);
239 poly_B.bound_poly_var_top(&r_j);
240 poly_C.bound_poly_var_top(&r_j);
241 e = poly.evaluate(&r_j);
242 cubic_polys.push(poly.compress());
243 }
244
245 (
246 SumcheckInstanceProof::new(cubic_polys),
247 r,
248 vec![poly_A[0], poly_B[0], poly_C[0]],
249 )
250 }
251
252 pub fn prove_cubic_batched<F>(
253 claim: &Scalar,
254 num_rounds: usize,
255 poly_vec_par: (
256 &mut Vec<&mut DensePolynomial>,
257 &mut Vec<&mut DensePolynomial>,
258 &mut DensePolynomial,
259 ),
260 poly_vec_seq: (
261 &mut Vec<&mut DensePolynomial>,
262 &mut Vec<&mut DensePolynomial>,
263 &mut Vec<&mut DensePolynomial>,
264 ),
265 coeffs: &[Scalar],
266 comb_func: F,
267 transcript: &mut Transcript,
268 ) -> (
269 Self,
270 Vec<Scalar>,
271 (Vec<Scalar>, Vec<Scalar>, Scalar),
272 (Vec<Scalar>, Vec<Scalar>, Vec<Scalar>),
273 )
274 where
275 F: Fn(&Scalar, &Scalar, &Scalar) -> Scalar,
276 {
277 let (poly_A_vec_par, poly_B_vec_par, poly_C_par) = poly_vec_par;
278 let (poly_A_vec_seq, poly_B_vec_seq, poly_C_vec_seq) = poly_vec_seq;
279
280 //let (poly_A_vec_seq, poly_B_vec_seq, poly_C_vec_seq) = poly_vec_seq;
281 let mut e = *claim;
282 let mut r: Vec<Scalar> = Vec::new();
283 let mut cubic_polys: Vec<CompressedUniPoly> = Vec::new();
284
285 for _j in 0..num_rounds {
286 let mut evals: Vec<(Scalar, Scalar, Scalar)> = Vec::new();
287
288 for (poly_A, poly_B) in poly_A_vec_par.iter().zip(poly_B_vec_par.iter()) {
289 let mut eval_point_0 = Scalar::zero();
290 let mut eval_point_2 = Scalar::zero();
291 let mut eval_point_3 = Scalar::zero();
292
293 let len = poly_A.len() / 2;
294 for i in 0..len {
295 // eval 0: bound_func is A(low)
296 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C_par[i]);
297
298 // eval 2: bound_func is -A(low) + 2*A(high)
299 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
300 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
301 let poly_C_bound_point = poly_C_par[len + i] + poly_C_par[len + i] - poly_C_par[i];
302 eval_point_2 += comb_func(
303 &poly_A_bound_point,
304 &poly_B_bound_point,
305 &poly_C_bound_point,
306 );
307
308 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
309 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
310 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
311 let poly_C_bound_point = poly_C_bound_point + poly_C_par[len + i] - poly_C_par[i];
312
313 eval_point_3 += comb_func(
314 &poly_A_bound_point,
315 &poly_B_bound_point,
316 &poly_C_bound_point,
317 );
318 }
319
320 evals.push((eval_point_0, eval_point_2, eval_point_3));
321 }
322
323 for (poly_A, poly_B, poly_C) in izip!(
324 poly_A_vec_seq.iter(),
325 poly_B_vec_seq.iter(),
326 poly_C_vec_seq.iter()
327 ) {
328 let mut eval_point_0 = Scalar::zero();
329 let mut eval_point_2 = Scalar::zero();
330 let mut eval_point_3 = Scalar::zero();
331 let len = poly_A.len() / 2;
332 for i in 0..len {
333 // eval 0: bound_func is A(low)
334 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
335 // eval 2: bound_func is -A(low) + 2*A(high)
336 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
337 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
338 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
339 eval_point_2 += comb_func(
340 &poly_A_bound_point,
341 &poly_B_bound_point,
342 &poly_C_bound_point,
343 );
344 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
345 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
346 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
347 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
348 eval_point_3 += comb_func(
349 &poly_A_bound_point,
350 &poly_B_bound_point,
351 &poly_C_bound_point,
352 );
353 }
354 evals.push((eval_point_0, eval_point_2, eval_point_3));
355 }
356
357 let evals_combined_0 = (0..evals.len()).map(|i| evals[i].0 * coeffs[i]).sum();
358 let evals_combined_2 = (0..evals.len()).map(|i| evals[i].1 * coeffs[i]).sum();
359 let evals_combined_3 = (0..evals.len()).map(|i| evals[i].2 * coeffs[i]).sum();
360
361 let evals = vec![
362 evals_combined_0,
363 e - evals_combined_0,
364 evals_combined_2,
365 evals_combined_3,
366 ];
367 let poly = UniPoly::from_evals(&evals);
368
369 // append the prover's message to the transcript
370 poly.append_to_transcript(b"poly", transcript);
371
372 //derive the verifier's challenge for the next round
373 let r_j = transcript.challenge_scalar(b"challenge_nextround");
374 r.push(r_j);
375
376 // bound all tables to the verifier's challenege
377 for (poly_A, poly_B) in poly_A_vec_par.iter_mut().zip(poly_B_vec_par.iter_mut()) {
378 poly_A.bound_poly_var_top(&r_j);
379 poly_B.bound_poly_var_top(&r_j);
380 }
381 poly_C_par.bound_poly_var_top(&r_j);
382
383 for (poly_A, poly_B, poly_C) in izip!(
384 poly_A_vec_seq.iter_mut(),
385 poly_B_vec_seq.iter_mut(),
386 poly_C_vec_seq.iter_mut()
387 ) {
388 poly_A.bound_poly_var_top(&r_j);
389 poly_B.bound_poly_var_top(&r_j);
390 poly_C.bound_poly_var_top(&r_j);
391 }
392
393 e = poly.evaluate(&r_j);
394 cubic_polys.push(poly.compress());
395 }
396
397 let poly_A_par_final = (0..poly_A_vec_par.len())
398 .map(|i| poly_A_vec_par[i][0])
399 .collect();
400 let poly_B_par_final = (0..poly_B_vec_par.len())
401 .map(|i| poly_B_vec_par[i][0])
402 .collect();
403 let claims_prod = (poly_A_par_final, poly_B_par_final, poly_C_par[0]);
404
405 let poly_A_seq_final = (0..poly_A_vec_seq.len())
406 .map(|i| poly_A_vec_seq[i][0])
407 .collect();
408 let poly_B_seq_final = (0..poly_B_vec_seq.len())
409 .map(|i| poly_B_vec_seq[i][0])
410 .collect();
411 let poly_C_seq_final = (0..poly_C_vec_seq.len())
412 .map(|i| poly_C_vec_seq[i][0])
413 .collect();
414 let claims_dotp = (poly_A_seq_final, poly_B_seq_final, poly_C_seq_final);
415
416 (
417 SumcheckInstanceProof::new(cubic_polys),
418 r,
419 claims_prod,
420 claims_dotp,
421 )
422 }
423}
424
425impl ZKSumcheckInstanceProof {
426 pub fn prove_quad<F>(
427 claim: &Scalar,
428 blind_claim: &Scalar,
429 num_rounds: usize,
430 poly_A: &mut DensePolynomial,
431 poly_B: &mut DensePolynomial,
432 comb_func: F,
433 gens_1: &MultiCommitGens,
434 gens_n: &MultiCommitGens,
435 transcript: &mut Transcript,
436 random_tape: &mut RandomTape,
437 ) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
438 where
439 F: Fn(&Scalar, &Scalar) -> Scalar,
440 {
441 let (blinds_poly, blinds_evals) = (
442 random_tape.random_vector(b"blinds_poly", num_rounds),
443 random_tape.random_vector(b"blinds_evals", num_rounds),
444 );
445 let mut claim_per_round = *claim;
446 let mut comm_claim_per_round = claim_per_round.commit(blind_claim, gens_1).compress();
447
448 let mut r: Vec<Scalar> = Vec::new();
449 let mut comm_polys: Vec<CompressedGroup> = Vec::new();
450 let mut comm_evals: Vec<CompressedGroup> = Vec::new();
451 let mut proofs: Vec<DotProductProof> = Vec::new();
452
453 for j in 0..num_rounds {
454 let (poly, comm_poly) = {
455 let mut eval_point_0 = Scalar::zero();
456 let mut eval_point_2 = Scalar::zero();
457
458 let len = poly_A.len() / 2;
459 for i in 0..len {
460 // eval 0: bound_func is A(low)
461 eval_point_0 += comb_func(&poly_A[i], &poly_B[i]);
462
463 // eval 2: bound_func is -A(low) + 2*A(high)
464 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
465 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
466 eval_point_2 += comb_func(&poly_A_bound_point, &poly_B_bound_point);
467 }
468
469 let evals = vec![eval_point_0, claim_per_round - eval_point_0, eval_point_2];
470 let poly = UniPoly::from_evals(&evals);
471 let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
472 (poly, comm_poly)
473 };
474
475 // append the prover's message to the transcript
476 comm_poly.append_to_transcript(b"comm_poly", transcript);
477 comm_polys.push(comm_poly);
478
479 //derive the verifier's challenge for the next round
480 let r_j = transcript.challenge_scalar(b"challenge_nextround");
481
482 // bound all tables to the verifier's challenege
483 poly_A.bound_poly_var_top(&r_j);
484 poly_B.bound_poly_var_top(&r_j);
485
486 // produce a proof of sum-check and of evaluation
487 let (proof, claim_next_round, comm_claim_next_round) = {
488 let eval = poly.evaluate(&r_j);
489 let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
490
491 // we need to prove the following under homomorphic commitments:
492 // (1) poly(0) + poly(1) = claim_per_round
493 // (2) poly(r_j) = eval
494
495 // Our technique is to leverage dot product proofs:
496 // (1) we can prove: <poly_in_coeffs_form, (2, 1, 1, 1)> = claim_per_round
497 // (2) we can prove: <poly_in_coeffs_form, (1, r_j, r^2_j, ..) = eval
498 // for efficiency we batch them using random weights
499
500 // add two claims to transcript
501 comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
502 comm_eval.append_to_transcript(b"comm_eval", transcript);
503
504 // produce two weights
505 let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
506
507 // compute a weighted sum of the RHS
508 let target = w[0] * claim_per_round + w[1] * eval;
509 let comm_target = GroupElement::vartime_multiscalar_mul(
510 w.iter(),
511 iter::once(&comm_claim_per_round)
512 .chain(iter::once(&comm_eval))
513 .map(|pt| pt.decompress().unwrap())
514 .collect::<Vec<GroupElement>>(),
515 )
516 .compress();
517
518 let blind = {
519 let blind_sc = if j == 0 {
520 blind_claim
521 } else {
522 &blinds_evals[j - 1]
523 };
524
525 let blind_eval = &blinds_evals[j];
526
527 w[0] * blind_sc + w[1] * blind_eval
528 };
529 assert_eq!(target.commit(&blind, gens_1).compress(), comm_target);
530
531 let a = {
532 // the vector to use to decommit for sum-check test
533 let a_sc = {
534 let mut a = vec![Scalar::one(); poly.degree() + 1];
535 a[0] += Scalar::one();
536 a
537 };
538
539 // the vector to use to decommit for evaluation
540 let a_eval = {
541 let mut a = vec![Scalar::one(); poly.degree() + 1];
542 for j in 1..a.len() {
543 a[j] = a[j - 1] * r_j;
544 }
545 a
546 };
547
548 // take weighted sum of the two vectors using w
549 assert_eq!(a_sc.len(), a_eval.len());
550 (0..a_sc.len())
551 .map(|i| w[0] * a_sc[i] + w[1] * a_eval[i])
552 .collect::<Vec<Scalar>>()
553 };
554
555 let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
556 gens_1,
557 gens_n,
558 transcript,
559 random_tape,
560 &poly.as_vec(),
561 &blinds_poly[j],
562 &a,
563 &target,
564 &blind,
565 );
566
567 (proof, eval, comm_eval)
568 };
569
570 claim_per_round = claim_next_round;
571 comm_claim_per_round = comm_claim_next_round;
572
573 proofs.push(proof);
574 r.push(r_j);
575 comm_evals.push(comm_claim_per_round);
576 }
577
578 (
579 ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
580 r,
581 vec![poly_A[0], poly_B[0]],
582 blinds_evals[num_rounds - 1],
583 )
584 }
585
586 pub fn prove_cubic_with_additive_term<F>(
587 claim: &Scalar,
588 blind_claim: &Scalar,
589 num_rounds: usize,
590 poly_A: &mut DensePolynomial,
591 poly_B: &mut DensePolynomial,
592 poly_C: &mut DensePolynomial,
593 poly_D: &mut DensePolynomial,
594 comb_func: F,
595 gens_1: &MultiCommitGens,
596 gens_n: &MultiCommitGens,
597 transcript: &mut Transcript,
598 random_tape: &mut RandomTape,
599 ) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
600 where
601 F: Fn(&Scalar, &Scalar, &Scalar, &Scalar) -> Scalar,
602 {
603 let (blinds_poly, blinds_evals) = (
604 random_tape.random_vector(b"blinds_poly", num_rounds),
605 random_tape.random_vector(b"blinds_evals", num_rounds),
606 );
607
608 let mut claim_per_round = *claim;
609 let mut comm_claim_per_round = claim_per_round.commit(blind_claim, gens_1).compress();
610
611 let mut r: Vec<Scalar> = Vec::new();
612 let mut comm_polys: Vec<CompressedGroup> = Vec::new();
613 let mut comm_evals: Vec<CompressedGroup> = Vec::new();
614 let mut proofs: Vec<DotProductProof> = Vec::new();
615
616 for j in 0..num_rounds {
617 let (poly, comm_poly) = {
618 let mut eval_point_0 = Scalar::zero();
619 let mut eval_point_2 = Scalar::zero();
620 let mut eval_point_3 = Scalar::zero();
621
622 let len = poly_A.len() / 2;
623 for i in 0..len {
624 // eval 0: bound_func is A(low)
625 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
626
627 // eval 2: bound_func is -A(low) + 2*A(high)
628 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
629 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
630 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
631 let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
632 eval_point_2 += comb_func(
633 &poly_A_bound_point,
634 &poly_B_bound_point,
635 &poly_C_bound_point,
636 &poly_D_bound_point,
637 );
638
639 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
640 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
641 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
642 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
643 let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
644 eval_point_3 += comb_func(
645 &poly_A_bound_point,
646 &poly_B_bound_point,
647 &poly_C_bound_point,
648 &poly_D_bound_point,
649 );
650 }
651
652 let evals = vec![
653 eval_point_0,
654 claim_per_round - eval_point_0,
655 eval_point_2,
656 eval_point_3,
657 ];
658 let poly = UniPoly::from_evals(&evals);
659 let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
660 (poly, comm_poly)
661 };
662
663 // append the prover's message to the transcript
664 comm_poly.append_to_transcript(b"comm_poly", transcript);
665 comm_polys.push(comm_poly);
666
667 //derive the verifier's challenge for the next round
668 let r_j = transcript.challenge_scalar(b"challenge_nextround");
669
670 // bound all tables to the verifier's challenege
671 poly_A.bound_poly_var_top(&r_j);
672 poly_B.bound_poly_var_top(&r_j);
673 poly_C.bound_poly_var_top(&r_j);
674 poly_D.bound_poly_var_top(&r_j);
675
676 // produce a proof of sum-check and of evaluation
677 let (proof, claim_next_round, comm_claim_next_round) = {
678 let eval = poly.evaluate(&r_j);
679 let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
680
681 // we need to prove the following under homomorphic commitments:
682 // (1) poly(0) + poly(1) = claim_per_round
683 // (2) poly(r_j) = eval
684
685 // Our technique is to leverage dot product proofs:
686 // (1) we can prove: <poly_in_coeffs_form, (2, 1, 1, 1)> = claim_per_round
687 // (2) we can prove: <poly_in_coeffs_form, (1, r_j, r^2_j, ..) = eval
688 // for efficiency we batch them using random weights
689
690 // add two claims to transcript
691 comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
692 comm_eval.append_to_transcript(b"comm_eval", transcript);
693
694 // produce two weights
695 let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
696
697 // compute a weighted sum of the RHS
698 let target = w[0] * claim_per_round + w[1] * eval;
699 let comm_target = GroupElement::vartime_multiscalar_mul(
700 w.iter(),
701 iter::once(&comm_claim_per_round)
702 .chain(iter::once(&comm_eval))
703 .map(|pt| pt.decompress().unwrap())
704 .collect::<Vec<GroupElement>>(),
705 )
706 .compress();
707
708 let blind = {
709 let blind_sc = if j == 0 {
710 blind_claim
711 } else {
712 &blinds_evals[j - 1]
713 };
714
715 let blind_eval = &blinds_evals[j];
716
717 w[0] * blind_sc + w[1] * blind_eval
718 };
719
720 assert_eq!(target.commit(&blind, gens_1).compress(), comm_target);
721
722 let a = {
723 // the vector to use to decommit for sum-check test
724 let a_sc = {
725 let mut a = vec![Scalar::one(); poly.degree() + 1];
726 a[0] += Scalar::one();
727 a
728 };
729
730 // the vector to use to decommit for evaluation
731 let a_eval = {
732 let mut a = vec![Scalar::one(); poly.degree() + 1];
733 for j in 1..a.len() {
734 a[j] = a[j - 1] * r_j;
735 }
736 a
737 };
738
739 // take weighted sum of the two vectors using w
740 assert_eq!(a_sc.len(), a_eval.len());
741 (0..a_sc.len())
742 .map(|i| w[0] * a_sc[i] + w[1] * a_eval[i])
743 .collect::<Vec<Scalar>>()
744 };
745
746 let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
747 gens_1,
748 gens_n,
749 transcript,
750 random_tape,
751 &poly.as_vec(),
752 &blinds_poly[j],
753 &a,
754 &target,
755 &blind,
756 );
757
758 (proof, eval, comm_eval)
759 };
760
761 proofs.push(proof);
762 claim_per_round = claim_next_round;
763 comm_claim_per_round = comm_claim_next_round;
764 r.push(r_j);
765 comm_evals.push(comm_claim_per_round);
766 }
767
768 (
769 ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
770 r,
771 vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
772 blinds_evals[num_rounds - 1],
773 )
774 }
775}