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