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