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