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