Nova/src/spartan/pp/product.rs
src/spartan/pp/product.rsRaw
1use crate::{
2 errors::NovaError,
3 spartan::{
4 math::Math,
5 polynomial::{EqPolynomial, MultilinearPolynomial},
6 sumcheck::{CompressedUniPoly, SumcheckProof, UniPoly},
7 PolyEvalInstance, PolyEvalWitness,
8 },
9 traits::{commitment::CommitmentEngineTrait, Group, TranscriptEngineTrait},
10 Commitment, CommitmentKey,
11};
12use core::marker::PhantomData;
13use ff::{Field, PrimeField};
14use rayon::prelude::*;
15use serde::{Deserialize, Serialize};
16
17pub(crate) struct IdentityPolynomial<Scalar: PrimeField> {
18 ell: usize,
19 _p: PhantomData<Scalar>,
20}
21
22impl<Scalar: PrimeField> IdentityPolynomial<Scalar> {
23 pub fn new(ell: usize) -> Self {
24 IdentityPolynomial {
25 ell,
26 _p: Default::default(),
27 }
28 }
29
30 pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
31 assert_eq!(self.ell, r.len());
32 (0..self.ell)
33 .map(|i| Scalar::from(2_usize.pow((self.ell - i - 1) as u32) as u64) * r[i])
34 .fold(Scalar::zero(), |acc, item| acc + item)
35 }
36}
37
38impl<G: Group> SumcheckProof<G> {
39 pub fn prove_cubic_with_additive_term_batched<F>(
40 claim: &G::Scalar,
41 num_rounds: usize,
42 poly_vec: (
43 &mut MultilinearPolynomial<G::Scalar>,
44 &mut Vec<MultilinearPolynomial<G::Scalar>>,
45 &mut Vec<MultilinearPolynomial<G::Scalar>>,
46 &mut Vec<MultilinearPolynomial<G::Scalar>>,
47 ),
48 coeffs: &[G::Scalar],
49 comb_func: F,
50 transcript: &mut G::TE,
51 ) -> Result<
52 (
53 Self,
54 Vec<G::Scalar>,
55 (G::Scalar, Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>),
56 ),
57 NovaError,
58 >
59 where
60 F: Fn(&G::Scalar, &G::Scalar, &G::Scalar, &G::Scalar) -> G::Scalar,
61 {
62 let (poly_A, poly_B_vec, poly_C_vec, poly_D_vec) = poly_vec;
63
64 let mut e = *claim;
65 let mut r: Vec<G::Scalar> = Vec::new();
66 let mut cubic_polys: Vec<CompressedUniPoly<G>> = Vec::new();
67
68 for _j in 0..num_rounds {
69 let mut evals: Vec<(G::Scalar, G::Scalar, G::Scalar)> = Vec::new();
70
71 for ((poly_B, poly_C), poly_D) in poly_B_vec
72 .iter()
73 .zip(poly_C_vec.iter())
74 .zip(poly_D_vec.iter())
75 {
76 let mut eval_point_0 = G::Scalar::zero();
77 let mut eval_point_2 = G::Scalar::zero();
78 let mut eval_point_3 = G::Scalar::zero();
79
80 let len = poly_A.len() / 2;
81 for i in 0..len {
82 // eval 0: bound_func is A(low)
83 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
84
85 // eval 2: bound_func is -A(low) + 2*A(high)
86 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
87 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
88 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
89 let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
90
91 eval_point_2 += comb_func(
92 &poly_A_bound_point,
93 &poly_B_bound_point,
94 &poly_C_bound_point,
95 &poly_D_bound_point,
96 );
97
98 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
99 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
100 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
101 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
102 let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
103
104 eval_point_3 += comb_func(
105 &poly_A_bound_point,
106 &poly_B_bound_point,
107 &poly_C_bound_point,
108 &poly_D_bound_point,
109 );
110 }
111
112 evals.push((eval_point_0, eval_point_2, eval_point_3));
113 }
114
115 let evals_combined_0 = (0..evals.len())
116 .map(|i| evals[i].0 * coeffs[i])
117 .fold(G::Scalar::zero(), |acc, item| acc + item);
118 let evals_combined_2 = (0..evals.len())
119 .map(|i| evals[i].1 * coeffs[i])
120 .fold(G::Scalar::zero(), |acc, item| acc + item);
121 let evals_combined_3 = (0..evals.len())
122 .map(|i| evals[i].2 * coeffs[i])
123 .fold(G::Scalar::zero(), |acc, item| acc + item);
124
125 let evals = vec![
126 evals_combined_0,
127 e - evals_combined_0,
128 evals_combined_2,
129 evals_combined_3,
130 ];
131 let poly = UniPoly::from_evals(&evals);
132
133 // append the prover's message to the transcript
134 transcript.absorb(b"p", &poly);
135
136 // derive the verifier's challenge for the next round
137 let r_i = transcript.squeeze(b"c")?;
138 r.push(r_i);
139
140 // bound all tables to the verifier's challenege
141 poly_A.bound_poly_var_top(&r_i);
142 for ((poly_B, poly_C), poly_D) in poly_B_vec
143 .iter_mut()
144 .zip(poly_C_vec.iter_mut())
145 .zip(poly_D_vec.iter_mut())
146 {
147 poly_B.bound_poly_var_top(&r_i);
148 poly_C.bound_poly_var_top(&r_i);
149 poly_D.bound_poly_var_top(&r_i);
150 }
151
152 e = poly.evaluate(&r_i);
153 cubic_polys.push(poly.compress());
154 }
155
156 let poly_B_final = (0..poly_B_vec.len()).map(|i| poly_B_vec[i][0]).collect();
157 let poly_C_final = (0..poly_C_vec.len()).map(|i| poly_C_vec[i][0]).collect();
158 let poly_D_final = (0..poly_D_vec.len()).map(|i| poly_D_vec[i][0]).collect();
159 let claims_prod = (poly_A[0], poly_B_final, poly_C_final, poly_D_final);
160
161 Ok((SumcheckProof::new(cubic_polys), r, claims_prod))
162 }
163}
164
165/// Provides a product argument using the algorithm described by Setty-Lee, 2020
166#[derive(Clone, Serialize, Deserialize)]
167#[serde(bound = "")]
168pub struct ProductArgument<G: Group> {
169 comm_output_vec: Vec<Commitment<G>>,
170 sc_proof: SumcheckProof<G>,
171 eval_left_vec: Vec<G::Scalar>,
172 eval_right_vec: Vec<G::Scalar>,
173 eval_output_vec: Vec<G::Scalar>,
174 eval_input_vec: Vec<G::Scalar>,
175 eval_output2_vec: Vec<G::Scalar>,
176}
177
178impl<G: Group> ProductArgument<G> {
179 pub fn prove(
180 ck: &CommitmentKey<G>,
181 input_vec: &[Vec<G::Scalar>], // a commitment to the input and the input vector to multiplied together
182 transcript: &mut G::TE,
183 ) -> Result<
184 (
185 Self,
186 Vec<G::Scalar>,
187 Vec<G::Scalar>,
188 Vec<G::Scalar>,
189 Vec<(PolyEvalWitness<G>, PolyEvalInstance<G>)>,
190 ),
191 NovaError,
192 > {
193 let num_claims = input_vec.len();
194
195 let compute_layer = |input: &[G::Scalar]| -> (Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>) {
196 let left = (0..input.len() / 2)
197 .map(|i| input[2 * i])
198 .collect::<Vec<G::Scalar>>();
199
200 let right = (0..input.len() / 2)
201 .map(|i| input[2 * i + 1])
202 .collect::<Vec<G::Scalar>>();
203
204 assert_eq!(left.len(), right.len());
205
206 let output = (0..left.len())
207 .map(|i| left[i] * right[i])
208 .collect::<Vec<G::Scalar>>();
209
210 (left, right, output)
211 };
212
213 // a closure that returns left, right, output, product
214 let prepare_inputs =
215 |input: &[G::Scalar]| -> (Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>, G::Scalar) {
216 let mut left: Vec<G::Scalar> = Vec::new();
217 let mut right: Vec<G::Scalar> = Vec::new();
218 let mut output: Vec<G::Scalar> = Vec::new();
219
220 let mut out = input.to_vec();
221 for _i in 0..input.len().log_2() {
222 let (l, r, o) = compute_layer(&out);
223 out = o.clone();
224
225 left.extend(l);
226 right.extend(r);
227 output.extend(o);
228 }
229
230 // add a dummy product operation to make the left.len() == right.len() == output.len() == input.len()
231 left.push(output[output.len() - 1]);
232 right.push(G::Scalar::zero());
233 output.push(G::Scalar::zero());
234
235 // output is stored at the last but one position
236 let product = output[output.len() - 2];
237
238 assert_eq!(left.len(), right.len());
239 assert_eq!(left.len(), output.len());
240 (left, right, output, product)
241 };
242
243 let mut left_vec = Vec::new();
244 let mut right_vec = Vec::new();
245 let mut output_vec = Vec::new();
246 let mut prod_vec = Vec::new();
247 for input in input_vec {
248 let (l, r, o, p) = prepare_inputs(input);
249 left_vec.push(l);
250 right_vec.push(r);
251 output_vec.push(o);
252 prod_vec.push(p);
253 }
254
255 // commit to the outputs
256 let comm_output_vec = (0..output_vec.len())
257 .into_par_iter()
258 .map(|i| G::CE::commit(ck, &output_vec[i]))
259 .collect::<Vec<_>>();
260
261 // absorb the output commitment and the claimed product
262 transcript.absorb(b"o", &comm_output_vec.as_slice());
263 transcript.absorb(b"r", &prod_vec.as_slice());
264
265 // this assumes all vectors passed have the same length
266 let num_rounds = output_vec[0].len().log_2();
267
268 // produce a fresh set of coeffs and a joint claim
269 let coeff_vec = {
270 let s = transcript.squeeze(b"r")?;
271 let mut s_vec = vec![s];
272 for i in 1..num_claims {
273 s_vec.push(s_vec[i - 1] * s);
274 }
275 s_vec
276 };
277
278 // generate randomness for the eq polynomial
279 let rand_eq = (0..num_rounds)
280 .map(|_i| transcript.squeeze(b"e"))
281 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
282
283 let mut poly_A = MultilinearPolynomial::new(EqPolynomial::new(rand_eq).evals());
284 let mut poly_B_vec = left_vec
285 .clone()
286 .into_par_iter()
287 .map(MultilinearPolynomial::new)
288 .collect::<Vec<_>>();
289 let mut poly_C_vec = right_vec
290 .clone()
291 .into_par_iter()
292 .map(MultilinearPolynomial::new)
293 .collect::<Vec<_>>();
294 let mut poly_D_vec = output_vec
295 .clone()
296 .into_par_iter()
297 .map(MultilinearPolynomial::new)
298 .collect::<Vec<_>>();
299
300 let comb_func =
301 |poly_A_comp: &G::Scalar,
302 poly_B_comp: &G::Scalar,
303 poly_C_comp: &G::Scalar,
304 poly_D_comp: &G::Scalar|
305 -> G::Scalar { *poly_A_comp * (*poly_B_comp * *poly_C_comp - *poly_D_comp) };
306
307 let (sc_proof, rand, _claims) = SumcheckProof::prove_cubic_with_additive_term_batched(
308 &G::Scalar::zero(),
309 num_rounds,
310 (
311 &mut poly_A,
312 &mut poly_B_vec,
313 &mut poly_C_vec,
314 &mut poly_D_vec,
315 ),
316 &coeff_vec,
317 comb_func,
318 transcript,
319 )?;
320
321 // claims[0] is about the Eq polynomial, which the verifier computes directly
322 // claims[1] =? weighed sum of left(rand)
323 // claims[2] =? weighted sum of right(rand)
324 // claims[3] =? weighetd sum of output(rand), which is easy to verify by querying output
325 // we also need to prove that output(output.len()-2) = claimed_product
326 let eval_left_vec = (0..left_vec.len())
327 .into_par_iter()
328 .map(|i| MultilinearPolynomial::evaluate_with(&left_vec[i], &rand))
329 .collect::<Vec<G::Scalar>>();
330 let eval_right_vec = (0..right_vec.len())
331 .into_par_iter()
332 .map(|i| MultilinearPolynomial::evaluate_with(&right_vec[i], &rand))
333 .collect::<Vec<G::Scalar>>();
334 let eval_output_vec = (0..output_vec.len())
335 .into_par_iter()
336 .map(|i| MultilinearPolynomial::evaluate_with(&output_vec[i], &rand))
337 .collect::<Vec<G::Scalar>>();
338
339 // we now combine eval_left = left(rand) and eval_right = right(rand)
340 // into claims about input and output
341 transcript.absorb(b"l", &eval_left_vec.as_slice());
342 transcript.absorb(b"r", &eval_right_vec.as_slice());
343 transcript.absorb(b"o", &eval_output_vec.as_slice());
344
345 let c = transcript.squeeze(b"c")?;
346
347 // eval = (G::Scalar::one() - c) * eval_left + c * eval_right
348 // eval is claimed evaluation of input||output(r, c), which can be proven by proving input(r[1..], c) and output(r[1..], c)
349 let rand_ext = {
350 let mut r = rand.clone();
351 r.extend(&[c]);
352 r
353 };
354 let eval_input_vec = (0..input_vec.len())
355 .into_par_iter()
356 .map(|i| MultilinearPolynomial::evaluate_with(&input_vec[i], &rand_ext[1..]))
357 .collect::<Vec<G::Scalar>>();
358
359 let eval_output2_vec = (0..output_vec.len())
360 .into_par_iter()
361 .map(|i| MultilinearPolynomial::evaluate_with(&output_vec[i], &rand_ext[1..]))
362 .collect::<Vec<G::Scalar>>();
363
364 // add claimed evaluations to the transcript
365 transcript.absorb(b"i", &eval_input_vec.as_slice());
366 transcript.absorb(b"o", &eval_output2_vec.as_slice());
367
368 // squeeze a challenge to combine multiple claims into one
369 let powers_of_rho = {
370 let s = transcript.squeeze(b"r")?;
371 let mut s_vec = vec![s];
372 for i in 1..num_claims {
373 s_vec.push(s_vec[i - 1] * s);
374 }
375 s_vec
376 };
377
378 // take weighted sum of input, output, and their commitments
379 let product = prod_vec
380 .iter()
381 .zip(powers_of_rho.iter())
382 .map(|(e, p)| *e * p)
383 .fold(G::Scalar::zero(), |acc, item| acc + item);
384
385 let eval_output = eval_output_vec
386 .iter()
387 .zip(powers_of_rho.iter())
388 .map(|(e, p)| *e * p)
389 .fold(G::Scalar::zero(), |acc, item| acc + item);
390
391 let comm_output = comm_output_vec
392 .iter()
393 .zip(powers_of_rho.iter())
394 .map(|(c, r_i)| *c * *r_i)
395 .fold(Commitment::<G>::default(), |acc, item| acc + item);
396
397 let weighted_sum = |W: &[Vec<G::Scalar>], s: &[G::Scalar]| -> Vec<G::Scalar> {
398 assert_eq!(W.len(), s.len());
399 let mut p = vec![G::Scalar::zero(); W[0].len()];
400 for i in 0..W.len() {
401 for (j, item) in W[i].iter().enumerate().take(W[i].len()) {
402 p[j] += *item * s[i]
403 }
404 }
405 p
406 };
407
408 let poly_output = weighted_sum(&output_vec, &powers_of_rho);
409
410 let eval_output2 = eval_output2_vec
411 .iter()
412 .zip(powers_of_rho.iter())
413 .map(|(e, p)| *e * p)
414 .fold(G::Scalar::zero(), |acc, item| acc + item);
415
416 let mut w_u_vec = Vec::new();
417
418 // eval_output = output(rand)
419 w_u_vec.push((
420 PolyEvalWitness {
421 p: poly_output.clone(),
422 },
423 PolyEvalInstance {
424 c: comm_output,
425 x: rand.clone(),
426 e: eval_output,
427 },
428 ));
429
430 // claimed_product = output(1, ..., 1, 0)
431 let x = {
432 let mut x = vec![G::Scalar::one(); rand.len()];
433 x[rand.len() - 1] = G::Scalar::zero();
434 x
435 };
436 w_u_vec.push((
437 PolyEvalWitness {
438 p: poly_output.clone(),
439 },
440 PolyEvalInstance {
441 c: comm_output,
442 x,
443 e: product,
444 },
445 ));
446
447 // eval_output2 = output(rand_ext[1..])
448 w_u_vec.push((
449 PolyEvalWitness { p: poly_output },
450 PolyEvalInstance {
451 c: comm_output,
452 x: rand_ext[1..].to_vec(),
453 e: eval_output2,
454 },
455 ));
456
457 let prod_arg = Self {
458 comm_output_vec,
459 sc_proof,
460
461 // claimed evaluations at rand
462 eval_left_vec,
463 eval_right_vec,
464 eval_output_vec,
465
466 // claimed evaluations at rand_ext[1..]
467 eval_input_vec: eval_input_vec.clone(),
468 eval_output2_vec,
469 };
470
471 Ok((
472 prod_arg,
473 prod_vec,
474 rand_ext[1..].to_vec(),
475 eval_input_vec,
476 w_u_vec,
477 ))
478 }
479
480 pub fn verify(
481 &self,
482 prod_vec: &[G::Scalar], // claimed products
483 len: usize,
484 transcript: &mut G::TE,
485 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<PolyEvalInstance<G>>), NovaError> {
486 // absorb the provided commitment and claimed output
487 transcript.absorb(b"o", &self.comm_output_vec.as_slice());
488 transcript.absorb(b"r", &prod_vec.to_vec().as_slice());
489
490 let num_rounds = len.log_2();
491 let num_claims = prod_vec.len();
492
493 // produce a fresh set of coeffs and a joint claim
494 let coeff_vec = {
495 let s = transcript.squeeze(b"r")?;
496 let mut s_vec = vec![s];
497 for i in 1..num_claims {
498 s_vec.push(s_vec[i - 1] * s);
499 }
500 s_vec
501 };
502
503 // generate randomness for the eq polynomial
504 let rand_eq = (0..num_rounds)
505 .map(|_i| transcript.squeeze(b"e"))
506 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
507
508 let (final_claim, rand) = self.sc_proof.verify(
509 G::Scalar::zero(), // claim
510 num_rounds,
511 3, // degree bound
512 transcript,
513 )?;
514
515 // verify the final claim along with output[output.len() - 2 ] = claim
516 let eq = EqPolynomial::new(rand_eq).evaluate(&rand);
517 let final_claim_expected = (0..num_claims)
518 .map(|i| {
519 coeff_vec[i]
520 * eq
521 * (self.eval_left_vec[i] * self.eval_right_vec[i] - self.eval_output_vec[i])
522 })
523 .fold(G::Scalar::zero(), |acc, item| acc + item);
524
525 if final_claim != final_claim_expected {
526 return Err(NovaError::InvalidSumcheckProof);
527 }
528
529 transcript.absorb(b"l", &self.eval_left_vec.as_slice());
530 transcript.absorb(b"r", &self.eval_right_vec.as_slice());
531 transcript.absorb(b"o", &self.eval_output_vec.as_slice());
532
533 let c = transcript.squeeze(b"c")?;
534 let eval_vec = self
535 .eval_left_vec
536 .iter()
537 .zip(self.eval_right_vec.iter())
538 .map(|(l, r)| (G::Scalar::one() - c) * l + c * r)
539 .collect::<Vec<G::Scalar>>();
540
541 // eval is claimed evaluation of input||output(r, c), which can be proven by proving input(r[1..], c) and output(r[1..], c)
542 let rand_ext = {
543 let mut r = rand.clone();
544 r.extend(&[c]);
545 r
546 };
547
548 for (i, eval) in eval_vec.iter().enumerate() {
549 if *eval
550 != (G::Scalar::one() - rand_ext[0]) * self.eval_input_vec[i]
551 + rand_ext[0] * self.eval_output2_vec[i]
552 {
553 return Err(NovaError::InvalidSumcheckProof);
554 }
555 }
556
557 transcript.absorb(b"i", &self.eval_input_vec.as_slice());
558 transcript.absorb(b"o", &self.eval_output2_vec.as_slice());
559
560 // squeeze a challenge to combine multiple claims into one
561 let powers_of_rho = {
562 let s = transcript.squeeze(b"r")?;
563 let mut s_vec = vec![s];
564 for i in 1..num_claims {
565 s_vec.push(s_vec[i - 1] * s);
566 }
567 s_vec
568 };
569
570 // take weighted sum of input, output, and their commitments
571 let product = prod_vec
572 .iter()
573 .zip(powers_of_rho.iter())
574 .map(|(e, p)| *e * p)
575 .fold(G::Scalar::zero(), |acc, item| acc + item);
576
577 let eval_output = self
578 .eval_output_vec
579 .iter()
580 .zip(powers_of_rho.iter())
581 .map(|(e, p)| *e * p)
582 .fold(G::Scalar::zero(), |acc, item| acc + item);
583
584 let comm_output = self
585 .comm_output_vec
586 .iter()
587 .zip(powers_of_rho.iter())
588 .map(|(c, r_i)| *c * *r_i)
589 .fold(Commitment::<G>::default(), |acc, item| acc + item);
590
591 let eval_output2 = self
592 .eval_output2_vec
593 .iter()
594 .zip(powers_of_rho.iter())
595 .map(|(e, p)| *e * p)
596 .fold(G::Scalar::zero(), |acc, item| acc + item);
597
598 let mut u_vec = Vec::new();
599
600 // eval_output = output(rand)
601 u_vec.push(PolyEvalInstance {
602 c: comm_output,
603 x: rand.clone(),
604 e: eval_output,
605 });
606
607 // claimed_product = output(1, ..., 1, 0)
608 let x = {
609 let mut x = vec![G::Scalar::one(); rand.len()];
610 x[rand.len() - 1] = G::Scalar::zero();
611 x
612 };
613 u_vec.push(PolyEvalInstance {
614 c: comm_output,
615 x,
616 e: product,
617 });
618
619 // eval_output2 = output(rand_ext[1..])
620 u_vec.push(PolyEvalInstance {
621 c: comm_output,
622 x: rand_ext[1..].to_vec(),
623 e: eval_output2,
624 });
625
626 // input-related claims are checked by the caller
627 Ok((self.eval_input_vec.clone(), rand_ext[1..].to_vec(), u_vec))
628 }
629}