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