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 = poly_C_par[len + i] + poly_C_par[len + i] - poly_C_par[i];
381 eval_point_2 += comb_func(
382 &poly_A_bound_point,
383 &poly_B_bound_point,
384 &poly_C_bound_point,
385 );
386
387 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
388 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
389 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
390 let poly_C_bound_point = poly_C_bound_point + poly_C_par[len + i] - poly_C_par[i];
391
392 eval_point_3 += comb_func(
393 &poly_A_bound_point,
394 &poly_B_bound_point,
395 &poly_C_bound_point,
396 );
397 }
398
399 evals.push((eval_point_0, eval_point_2, eval_point_3));
400 }
401
402 for (poly_A, poly_B, poly_C) in izip!(
403 poly_A_vec_seq.iter(),
404 poly_B_vec_seq.iter(),
405 poly_C_vec_seq.iter()
406 ) {
407 let mut eval_point_0 = Scalar::zero();
408 let mut eval_point_2 = Scalar::zero();
409 let mut eval_point_3 = Scalar::zero();
410 let len = poly_A.len() / 2;
411 for i in 0..len {
412 // eval 0: bound_func is A(low)
413 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
414 // eval 2: bound_func is -A(low) + 2*A(high)
415 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
416 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
417 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
418 eval_point_2 += comb_func(
419 &poly_A_bound_point,
420 &poly_B_bound_point,
421 &poly_C_bound_point,
422 );
423 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
424 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
425 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
426 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
427 eval_point_3 += comb_func(
428 &poly_A_bound_point,
429 &poly_B_bound_point,
430 &poly_C_bound_point,
431 );
432 }
433 evals.push((eval_point_0, eval_point_2, eval_point_3));
434 }
435
436 let evals_combined_0 = (0..evals.len()).map(|i| evals[i].0 * coeffs[i]).sum();
437 let evals_combined_2 = (0..evals.len()).map(|i| evals[i].1 * coeffs[i]).sum();
438 let evals_combined_3 = (0..evals.len()).map(|i| evals[i].2 * coeffs[i]).sum();
439
440 let evals = vec![
441 evals_combined_0,
442 e - evals_combined_0,
443 evals_combined_2,
444 evals_combined_3,
445 ];
446 let poly = UniPoly::from_evals(&evals);
447
448 // append the prover's message to the transcript
449 poly.append_to_poseidon(transcript);
450
451 //derive the verifier's challenge for the next round
452 let r_j = transcript.challenge_scalar();
453 r.push(r_j);
454
455 // bound all tables to the verifier's challenege
456 for (poly_A, poly_B) in poly_A_vec_par.iter_mut().zip(poly_B_vec_par.iter_mut()) {
457 poly_A.bound_poly_var_top(&r_j);
458 poly_B.bound_poly_var_top(&r_j);
459 }
460 poly_C_par.bound_poly_var_top(&r_j);
461
462 for (poly_A, poly_B, poly_C) in izip!(
463 poly_A_vec_seq.iter_mut(),
464 poly_B_vec_seq.iter_mut(),
465 poly_C_vec_seq.iter_mut()
466 ) {
467 poly_A.bound_poly_var_top(&r_j);
468 poly_B.bound_poly_var_top(&r_j);
469 poly_C.bound_poly_var_top(&r_j);
470 }
471
472 e = poly.evaluate(&r_j);
473 cubic_polys.push(poly);
474 }
475
476 let poly_A_par_final = (0..poly_A_vec_par.len())
477 .map(|i| poly_A_vec_par[i][0])
478 .collect();
479 let poly_B_par_final = (0..poly_B_vec_par.len())
480 .map(|i| poly_B_vec_par[i][0])
481 .collect();
482 let claims_prod = (poly_A_par_final, poly_B_par_final, poly_C_par[0]);
483
484 let poly_A_seq_final = (0..poly_A_vec_seq.len())
485 .map(|i| poly_A_vec_seq[i][0])
486 .collect();
487 let poly_B_seq_final = (0..poly_B_vec_seq.len())
488 .map(|i| poly_B_vec_seq[i][0])
489 .collect();
490 let poly_C_seq_final = (0..poly_C_vec_seq.len())
491 .map(|i| poly_C_vec_seq[i][0])
492 .collect();
493 let claims_dotp = (poly_A_seq_final, poly_B_seq_final, poly_C_seq_final);
494
495 (
496 SumcheckInstanceProof::new(cubic_polys),
497 r,
498 claims_prod,
499 claims_dotp,
500 )
501 }
502
503 pub fn prove_quad<F>(
504 claim: &Scalar,
505 num_rounds: usize,
506 poly_A: &mut DensePolynomial,
507 poly_B: &mut DensePolynomial,
508 comb_func: F,
509 transcript: &mut PoseidonTranscript,
510 ) -> (Self, Vec<Scalar>, Vec<Scalar>)
511 where
512 F: Fn(&Scalar, &Scalar) -> Scalar,
513 {
514 let mut e = *claim;
515 let mut r: Vec<Scalar> = Vec::new();
516 let mut quad_polys: Vec<UniPoly> = Vec::new();
517
518 for _j in 0..num_rounds {
519 let mut eval_point_0 = Scalar::zero();
520 let mut eval_point_2 = Scalar::zero();
521
522 let len = poly_A.len() / 2;
523 for i in 0..len {
524 // eval 0: bound_func is A(low)
525 eval_point_0 += comb_func(&poly_A[i], &poly_B[i]);
526
527 // eval 2: bound_func is -A(low) + 2*A(high)
528 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
529 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
530 eval_point_2 += comb_func(&poly_A_bound_point, &poly_B_bound_point);
531 }
532
533 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2];
534 let poly = UniPoly::from_evals(&evals);
535
536 // append the prover's message to the transcript
537 poly.append_to_poseidon(transcript);
538
539 //derive the verifier's challenge for the next round
540 let r_j = transcript.challenge_scalar();
541 r.push(r_j);
542
543 // bound all tables to the verifier's challenege
544 poly_A.bound_poly_var_top(&r_j);
545 poly_B.bound_poly_var_top(&r_j);
546 e = poly.evaluate(&r_j);
547 quad_polys.push(poly);
548 }
549
550 (
551 SumcheckInstanceProof::new(quad_polys),
552 r,
553 vec![poly_A[0], poly_B[0]],
554 )
555 }
556}
557
558// impl ZKSumcheckInstanceProof {
559// pub fn prove_quad<F>(
560// claim: &Scalar,
561// blind_claim: &Scalar,
562// num_rounds: usize,
563// poly_A: &mut DensePolynomial,
564// poly_B: &mut DensePolynomial,
565// comb_func: F,
566// gens_1: &MultiCommitGens,
567// gens_n: &MultiCommitGens,
568// transcript: &mut Transcript,
569// random_tape: &mut RandomTape,
570// ) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
571// where
572// F: Fn(&Scalar, &Scalar) -> Scalar,
573// {
574// let (blinds_poly, blinds_evals) = (
575// random_tape.random_vector(b"blinds_poly", num_rounds),
576// random_tape.random_vector(b"blinds_evals", num_rounds),
577// );
578// let mut claim_per_round = *claim;
579// let mut comm_claim_per_round = claim_per_round.commit(blind_claim, gens_1).compress();
580
581// let mut r: Vec<Scalar> = Vec::new();
582// let mut comm_polys: Vec<Group> = Vec::new();
583// let mut comm_evals: Vec<CompressedGroup> = Vec::new();
584// let mut proofs: Vec<DotProductProof> = Vec::new();
585
586// for j in 0..num_rounds {
587// let (poly, comm_poly) = {
588// let mut eval_point_0 = Scalar::zero();
589// let mut eval_point_2 = Scalar::zero();
590
591// let len = poly_A.len() / 2;
592// for i in 0..len {
593// // eval 0: bound_func is A(low)
594// eval_point_0 += comb_func(&poly_A[i], &poly_B[i]);
595
596// // eval 2: bound_func is -A(low) + 2*A(high)
597// let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
598// let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
599// eval_point_2 += comb_func(&poly_A_bound_point, &poly_B_bound_point);
600// }
601
602// let evals = vec![eval_point_0, claim_per_round - eval_point_0, eval_point_2];
603// let poly = UniPoly::from_evals(&evals);
604// let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
605// (poly, comm_poly)
606// };
607
608// // append the prover's message to the transcript
609// comm_poly.append_to_transcript(b"comm_poly", transcript);
610// comm_polys.push(comm_poly);
611
612// //derive the verifier's challenge for the next round
613// let r_j = transcript.challenge_scalar(b"challenge_nextround");
614
615// // bound all tables to the verifier's challenege
616// poly_A.bound_poly_var_top(&r_j);
617// poly_B.bound_poly_var_top(&r_j);
618
619// // produce a proof of sum-check and of evaluation
620// let (proof, claim_next_round, comm_claim_next_round) = {
621// let eval = poly.evaluate(&r_j);
622// let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
623
624// // we need to prove the following under homomorphic commitments:
625// // (1) poly(0) + poly(1) = claim_per_round
626// // (2) poly(r_j) = eval
627
628// // Our technique is to leverage dot product proofs:
629// // (1) we can prove: <poly_in_coeffs_form, (2, 1, 1, 1)> = claim_per_round
630// // (2) we can prove: <poly_in_coeffs_form, (1, r_j, r^2_j, ..) = eval
631// // for efficiency we batch them using random weights
632
633// // add two claims to transcript
634// comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
635// comm_eval.append_to_transcript(b"comm_eval", transcript);
636
637// // produce two weights
638// let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
639
640// // compute a weighted sum of the RHS
641// let target = w[0] * claim_per_round + w[1] * eval;
642// let comm_target = GroupElement::vartime_multiscalar_mul(
643// w.as_slice(),
644// iter::once(&comm_claim_per_round)
645// .chain(iter::once(&comm_eval))
646// .map(|pt| GroupElement::decompress(pt).unwrap())
647// .collect::<Vec<GroupElement>>()
648// .as_slice(),
649// )
650// .compress();
651
652// let blind = {
653// let blind_sc = if j == 0 {
654// blind_claim
655// } else {
656// &blinds_evals[j - 1]
657// };
658
659// let blind_eval = &blinds_evals[j];
660
661// w[0] * blind_sc + w[1] * blind_eval
662// };
663// assert_eq!(target.commit(&blind, gens_1).compress(), comm_target);
664
665// let a = {
666// // the vector to use to decommit for sum-check test
667// let a_sc = {
668// let mut a = vec![Scalar::one(); poly.degree() + 1];
669// a[0] += Scalar::one();
670// a
671// };
672
673// // the vector to use to decommit for evaluation
674// let a_eval = {
675// let mut a = vec![Scalar::one(); poly.degree() + 1];
676// for j in 1..a.len() {
677// a[j] = a[j - 1] * r_j;
678// }
679// a
680// };
681
682// // take weighted sum of the two vectors using w
683// assert_eq!(a_sc.len(), a_eval.len());
684// (0..a_sc.len())
685// .map(|i| w[0] * a_sc[i] + w[1] * a_eval[i])
686// .collect::<Vec<Scalar>>()
687// };
688
689// let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
690// gens_1,
691// gens_n,
692// transcript,
693// random_tape,
694// &poly.as_vec(),
695// &blinds_poly[j],
696// &a,
697// &target,
698// &blind,
699// );
700
701// (proof, eval, comm_eval)
702// };
703
704// claim_per_round = claim_next_round;
705// comm_claim_per_round = comm_claim_next_round;
706
707// proofs.push(proof);
708// r.push(r_j);
709// comm_evals.push(comm_claim_per_round.clone());
710// }
711
712// (
713// ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
714// r,
715// vec![poly_A[0], poly_B[0]],
716// blinds_evals[num_rounds - 1],
717// )
718// }
719
720// pub fn prove_cubic_with_additive_term<F>(
721// claim: &Scalar,
722// blind_claim: &Scalar,
723// num_rounds: usize,
724// poly_A: &mut DensePolynomial,
725// poly_B: &mut DensePolynomial,
726// poly_C: &mut DensePolynomial,
727// poly_D: &mut DensePolynomial,
728// comb_func: F,
729// gens_1: &MultiCommitGens,
730// gens_n: &MultiCommitGens,
731// transcript: &mut Transcript,
732// random_tape: &mut RandomTape,
733// ) -> (Self, Vec<Scalar>, Vec<Scalar>, Scalar)
734// where
735// F: Fn(&Scalar, &Scalar, &Scalar, &Scalar) -> Scalar,
736// {
737// let (blinds_poly, blinds_evals) = (
738// random_tape.random_vector(b"blinds_poly", num_rounds),
739// random_tape.random_vector(b"blinds_evals", num_rounds),
740// );
741
742// let mut claim_per_round = *claim;
743// let mut comm_claim_per_round = claim_per_round.commit(blind_claim, gens_1).compress();
744
745// let mut r: Vec<Scalar> = Vec::new();
746// let mut comm_polys: Vec<CompressedGroup> = Vec::new();
747// let mut comm_evals: Vec<CompressedGroup> = Vec::new();
748// let mut proofs: Vec<DotProductProof> = Vec::new();
749
750// for j in 0..num_rounds {
751// let (poly, comm_poly) = {
752// let mut eval_point_0 = Scalar::zero();
753// let mut eval_point_2 = Scalar::zero();
754// let mut eval_point_3 = Scalar::zero();
755
756// let len = poly_A.len() / 2;
757// for i in 0..len {
758// // eval 0: bound_func is A(low)
759// eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
760
761// // eval 2: bound_func is -A(low) + 2*A(high)
762// let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
763// let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
764// let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
765// let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
766// eval_point_2 += comb_func(
767// &poly_A_bound_point,
768// &poly_B_bound_point,
769// &poly_C_bound_point,
770// &poly_D_bound_point,
771// );
772
773// // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
774// let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
775// let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
776// let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
777// let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
778// eval_point_3 += comb_func(
779// &poly_A_bound_point,
780// &poly_B_bound_point,
781// &poly_C_bound_point,
782// &poly_D_bound_point,
783// );
784// }
785
786// let evals = vec![
787// eval_point_0,
788// claim_per_round - eval_point_0,
789// eval_point_2,
790// eval_point_3,
791// ];
792// let poly = UniPoly::from_evals(&evals);
793// let comm_poly = poly.commit(gens_n, &blinds_poly[j]).compress();
794// (poly, comm_poly)
795// };
796
797// // append the prover's message to the transcript
798// comm_poly.append_to_transcript(b"comm_poly", transcript);
799// comm_polys.push(comm_poly);
800
801// //derive the verifier's challenge for the next round
802// let r_j = transcript.challenge_scalar(b"challenge_nextround");
803
804// // bound all tables to the verifier's challenege
805// poly_A.bound_poly_var_top(&r_j);
806// poly_B.bound_poly_var_top(&r_j);
807// poly_C.bound_poly_var_top(&r_j);
808// poly_D.bound_poly_var_top(&r_j);
809
810// // produce a proof of sum-check and of evaluation
811// let (proof, claim_next_round, comm_claim_next_round) = {
812// let eval = poly.evaluate(&r_j);
813// let comm_eval = eval.commit(&blinds_evals[j], gens_1).compress();
814
815// // we need to prove the following under homomorphic commitments:
816// // (1) poly(0) + poly(1) = claim_per_round
817// // (2) poly(r_j) = eval
818
819// // Our technique is to leverage dot product proofs:
820// // (1) we can prove: <poly_in_coeffs_form, (2, 1, 1, 1)> = claim_per_round
821// // (2) we can prove: <poly_in_coeffs_form, (1, r_j, r^2_j, ..) = eval
822// // for efficiency we batch them using random weights
823
824// // add two claims to transcript
825// comm_claim_per_round.append_to_transcript(b"comm_claim_per_round", transcript);
826// comm_eval.append_to_transcript(b"comm_eval", transcript);
827
828// // produce two weights
829// let w = transcript.challenge_vector(b"combine_two_claims_to_one", 2);
830
831// // compute a weighted sum of the RHS
832// let target = w[0] * claim_per_round + w[1] * eval;
833
834// let comm_target = GroupElement::vartime_multiscalar_mul(
835// w.as_slice(),
836// iter::once(&comm_claim_per_round)
837// .chain(iter::once(&comm_eval))
838// .map(|pt| GroupElement::decompress(&pt).unwrap())
839// .collect::<Vec<GroupElement>>()
840// .as_slice(),
841// )
842// .compress();
843
844// let blind = {
845// let blind_sc = if j == 0 {
846// blind_claim
847// } else {
848// &blinds_evals[j - 1]
849// };
850
851// let blind_eval = &blinds_evals[j];
852
853// w[0] * blind_sc + w[1] * blind_eval
854// };
855
856// let res = target.commit(&blind, gens_1);
857
858// assert_eq!(res.compress(), comm_target);
859
860// let a = {
861// // the vector to use to decommit for sum-check test
862// let a_sc = {
863// let mut a = vec![Scalar::one(); poly.degree() + 1];
864// a[0] += Scalar::one();
865// a
866// };
867
868// // the vector to use to decommit for evaluation
869// let a_eval = {
870// let mut a = vec![Scalar::one(); poly.degree() + 1];
871// for j in 1..a.len() {
872// a[j] = a[j - 1] * r_j;
873// }
874// a
875// };
876
877// // take weighted sum of the two vectors using w
878// assert_eq!(a_sc.len(), a_eval.len());
879// (0..a_sc.len())
880// .map(|i| w[0] * a_sc[i] + w[1] * a_eval[i])
881// .collect::<Vec<Scalar>>()
882// };
883
884// let (proof, _comm_poly, _comm_sc_eval) = DotProductProof::prove(
885// gens_1,
886// gens_n,
887// transcript,
888// random_tape,
889// &poly.as_vec(),
890// &blinds_poly[j],
891// &a,
892// &target,
893// &blind,
894// );
895
896// (proof, eval, comm_eval)
897// };
898
899// proofs.push(proof);
900// claim_per_round = claim_next_round;
901// comm_claim_per_round = comm_claim_next_round;
902// r.push(r_j);
903// comm_evals.push(comm_claim_per_round.clone());
904// }
905
906// (
907// ZKSumcheckInstanceProof::new(comm_polys, comm_evals, proofs),
908// r,
909// vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
910// blinds_evals[num_rounds - 1],
911// )
912// }
913// }