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