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