Nova/src/spartan/spark/product.rs
src/spartan/spark/product.rsRaw
1use crate::{
2 errors::NovaError,
3 spartan::{
4 math::Math,
5 polynomial::{EqPolynomial, MultilinearPolynomial},
6 sumcheck::{CompressedUniPoly, SumcheckProof, UniPoly},
7 },
8 traits::{Group, TranscriptEngineTrait},
9};
10use core::marker::PhantomData;
11use ff::{Field, PrimeField};
12use serde::{Deserialize, Serialize};
13
14pub(crate) struct IdentityPolynomial<Scalar: PrimeField> {
15 ell: usize,
16 _p: PhantomData<Scalar>,
17}
18
19impl<Scalar: PrimeField> IdentityPolynomial<Scalar> {
20 pub fn new(ell: usize) -> Self {
21 IdentityPolynomial {
22 ell,
23 _p: Default::default(),
24 }
25 }
26
27 pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
28 assert_eq!(self.ell, r.len());
29 (0..self.ell)
30 .map(|i| Scalar::from(2_usize.pow((self.ell - i - 1) as u32) as u64) * r[i])
31 .fold(Scalar::zero(), |acc, item| acc + item)
32 }
33}
34
35impl<G: Group> SumcheckProof<G> {
36 pub fn prove_cubic<F>(
37 claim: &G::Scalar,
38 num_rounds: usize,
39 poly_A: &mut MultilinearPolynomial<G::Scalar>,
40 poly_B: &mut MultilinearPolynomial<G::Scalar>,
41 poly_C: &mut MultilinearPolynomial<G::Scalar>,
42 comb_func: F,
43 transcript: &mut G::TE,
44 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
45 where
46 F: Fn(&G::Scalar, &G::Scalar, &G::Scalar) -> G::Scalar,
47 {
48 let mut e = *claim;
49 let mut r: Vec<G::Scalar> = Vec::new();
50 let mut cubic_polys: Vec<CompressedUniPoly<G>> = Vec::new();
51 for _j in 0..num_rounds {
52 let mut eval_point_0 = G::Scalar::zero();
53 let mut eval_point_2 = G::Scalar::zero();
54 let mut eval_point_3 = G::Scalar::zero();
55
56 let len = poly_A.len() / 2;
57 for i in 0..len {
58 // eval 0: bound_func is A(low)
59 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
60
61 // eval 2: bound_func is -A(low) + 2*A(high)
62 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
63 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
64 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
65 eval_point_2 += comb_func(
66 &poly_A_bound_point,
67 &poly_B_bound_point,
68 &poly_C_bound_point,
69 );
70
71 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
72 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
73 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
74 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
75
76 eval_point_3 += comb_func(
77 &poly_A_bound_point,
78 &poly_B_bound_point,
79 &poly_C_bound_point,
80 );
81 }
82
83 let evals = vec![eval_point_0, e - eval_point_0, eval_point_2, eval_point_3];
84 let poly = UniPoly::from_evals(&evals);
85
86 // append the prover's message to the transcript
87 transcript.absorb(b"p", &poly);
88
89 //derive the verifier's challenge for the next round
90 let r_i = transcript.squeeze(b"c")?;
91 r.push(r_i);
92
93 // bound all tables to the verifier's challenege
94 poly_A.bound_poly_var_top(&r_i);
95 poly_B.bound_poly_var_top(&r_i);
96 poly_C.bound_poly_var_top(&r_i);
97 e = poly.evaluate(&r_i);
98 cubic_polys.push(poly.compress());
99 }
100
101 Ok((
102 Self::new(cubic_polys),
103 r,
104 vec![poly_A[0], poly_B[0], poly_C[0]],
105 ))
106 }
107
108 pub fn prove_cubic_batched<F>(
109 claim: &G::Scalar,
110 num_rounds: usize,
111 poly_vec: (
112 &mut Vec<&mut MultilinearPolynomial<G::Scalar>>,
113 &mut Vec<&mut MultilinearPolynomial<G::Scalar>>,
114 &mut MultilinearPolynomial<G::Scalar>,
115 ),
116 coeffs: &[G::Scalar],
117 comb_func: F,
118 transcript: &mut G::TE,
119 ) -> Result<
120 (
121 Self,
122 Vec<G::Scalar>,
123 (Vec<G::Scalar>, Vec<G::Scalar>, G::Scalar),
124 ),
125 NovaError,
126 >
127 where
128 F: Fn(&G::Scalar, &G::Scalar, &G::Scalar) -> G::Scalar,
129 {
130 let (poly_A_vec, poly_B_vec, poly_C) = poly_vec;
131
132 let mut e = *claim;
133 let mut r: Vec<G::Scalar> = Vec::new();
134 let mut cubic_polys: Vec<CompressedUniPoly<G>> = Vec::new();
135
136 for _j in 0..num_rounds {
137 let mut evals: Vec<(G::Scalar, G::Scalar, G::Scalar)> = Vec::new();
138
139 for (poly_A, poly_B) in poly_A_vec.iter().zip(poly_B_vec.iter()) {
140 let mut eval_point_0 = G::Scalar::zero();
141 let mut eval_point_2 = G::Scalar::zero();
142 let mut eval_point_3 = G::Scalar::zero();
143
144 let len = poly_A.len() / 2;
145 for i in 0..len {
146 // eval 0: bound_func is A(low)
147 eval_point_0 += comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
148
149 // eval 2: bound_func is -A(low) + 2*A(high)
150 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
151 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
152 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
153 eval_point_2 += comb_func(
154 &poly_A_bound_point,
155 &poly_B_bound_point,
156 &poly_C_bound_point,
157 );
158
159 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
160 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
161 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
162 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
163
164 eval_point_3 += comb_func(
165 &poly_A_bound_point,
166 &poly_B_bound_point,
167 &poly_C_bound_point,
168 );
169 }
170
171 evals.push((eval_point_0, eval_point_2, eval_point_3));
172 }
173
174 let evals_combined_0 = (0..evals.len())
175 .map(|i| evals[i].0 * coeffs[i])
176 .fold(G::Scalar::zero(), |acc, item| acc + item);
177 let evals_combined_2 = (0..evals.len())
178 .map(|i| evals[i].1 * coeffs[i])
179 .fold(G::Scalar::zero(), |acc, item| acc + item);
180 let evals_combined_3 = (0..evals.len())
181 .map(|i| evals[i].2 * coeffs[i])
182 .fold(G::Scalar::zero(), |acc, item| acc + item);
183
184 let evals = vec![
185 evals_combined_0,
186 e - evals_combined_0,
187 evals_combined_2,
188 evals_combined_3,
189 ];
190 let poly = UniPoly::from_evals(&evals);
191
192 // append the prover's message to the transcript
193 transcript.absorb(b"p", &poly);
194
195 // derive the verifier's challenge for the next round
196 let r_i = transcript.squeeze(b"c")?;
197 r.push(r_i);
198
199 // bound all tables to the verifier's challenege
200 for (poly_A, poly_B) in poly_A_vec.iter_mut().zip(poly_B_vec.iter_mut()) {
201 poly_A.bound_poly_var_top(&r_i);
202 poly_B.bound_poly_var_top(&r_i);
203 }
204 poly_C.bound_poly_var_top(&r_i);
205
206 e = poly.evaluate(&r_i);
207 cubic_polys.push(poly.compress());
208 }
209
210 let poly_A_final = (0..poly_A_vec.len()).map(|i| poly_A_vec[i][0]).collect();
211 let poly_B_final = (0..poly_B_vec.len()).map(|i| poly_B_vec[i][0]).collect();
212 let claims_prod = (poly_A_final, poly_B_final, poly_C[0]);
213
214 Ok((SumcheckProof::new(cubic_polys), r, claims_prod))
215 }
216}
217
218#[derive(Debug)]
219pub struct ProductArgumentInputs<G: Group> {
220 left_vec: Vec<MultilinearPolynomial<G::Scalar>>,
221 right_vec: Vec<MultilinearPolynomial<G::Scalar>>,
222}
223
224impl<G: Group> ProductArgumentInputs<G> {
225 fn compute_layer(
226 inp_left: &MultilinearPolynomial<G::Scalar>,
227 inp_right: &MultilinearPolynomial<G::Scalar>,
228 ) -> (
229 MultilinearPolynomial<G::Scalar>,
230 MultilinearPolynomial<G::Scalar>,
231 ) {
232 let len = inp_left.len() + inp_right.len();
233 let outp_left = (0..len / 4)
234 .map(|i| inp_left[i] * inp_right[i])
235 .collect::<Vec<G::Scalar>>();
236 let outp_right = (len / 4..len / 2)
237 .map(|i| inp_left[i] * inp_right[i])
238 .collect::<Vec<G::Scalar>>();
239
240 (
241 MultilinearPolynomial::new(outp_left),
242 MultilinearPolynomial::new(outp_right),
243 )
244 }
245
246 pub fn new(poly: &MultilinearPolynomial<G::Scalar>) -> Self {
247 let mut left_vec: Vec<MultilinearPolynomial<G::Scalar>> = Vec::new();
248 let mut right_vec: Vec<MultilinearPolynomial<G::Scalar>> = Vec::new();
249 let num_layers = poly.len().log_2();
250 let (outp_left, outp_right) = poly.split(poly.len() / 2);
251
252 left_vec.push(outp_left);
253 right_vec.push(outp_right);
254
255 for i in 0..num_layers - 1 {
256 let (outp_left, outp_right) =
257 ProductArgumentInputs::<G>::compute_layer(&left_vec[i], &right_vec[i]);
258 left_vec.push(outp_left);
259 right_vec.push(outp_right);
260 }
261
262 Self {
263 left_vec,
264 right_vec,
265 }
266 }
267
268 pub fn evaluate(&self) -> G::Scalar {
269 let len = self.left_vec.len();
270 assert_eq!(self.left_vec[len - 1].get_num_vars(), 0);
271 assert_eq!(self.right_vec[len - 1].get_num_vars(), 0);
272 self.left_vec[len - 1][0] * self.right_vec[len - 1][0]
273 }
274}
275#[derive(Clone, Debug, Serialize, Deserialize)]
276#[serde(bound = "")]
277pub struct LayerProofBatched<G: Group> {
278 proof: SumcheckProof<G>,
279 claims_prod_left: Vec<G::Scalar>,
280 claims_prod_right: Vec<G::Scalar>,
281}
282
283impl<G: Group> LayerProofBatched<G> {
284 pub fn verify(
285 &self,
286 claim: G::Scalar,
287 num_rounds: usize,
288 degree_bound: usize,
289 transcript: &mut G::TE,
290 ) -> Result<(G::Scalar, Vec<G::Scalar>), NovaError> {
291 self
292 .proof
293 .verify(claim, num_rounds, degree_bound, transcript)
294 }
295}
296
297#[derive(Clone, Debug, Serialize, Deserialize)]
298#[serde(bound = "")]
299pub(crate) struct ProductArgumentBatched<G: Group> {
300 proof: Vec<LayerProofBatched<G>>,
301}
302
303impl<G: Group> ProductArgumentBatched<G> {
304 pub fn prove(
305 poly_vec: &[&MultilinearPolynomial<G::Scalar>],
306 transcript: &mut G::TE,
307 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
308 let mut prod_circuit_vec: Vec<_> = (0..poly_vec.len())
309 .map(|i| ProductArgumentInputs::<G>::new(poly_vec[i]))
310 .collect();
311
312 let mut proof_layers: Vec<LayerProofBatched<G>> = Vec::new();
313 let num_layers = prod_circuit_vec[0].left_vec.len();
314 let evals = (0..prod_circuit_vec.len())
315 .map(|i| prod_circuit_vec[i].evaluate())
316 .collect::<Vec<G::Scalar>>();
317
318 let mut claims_to_verify = evals.clone();
319 let mut rand = Vec::new();
320 for layer_id in (0..num_layers).rev() {
321 let len = prod_circuit_vec[0].left_vec[layer_id].len()
322 + prod_circuit_vec[0].right_vec[layer_id].len();
323
324 let mut poly_C = MultilinearPolynomial::new(EqPolynomial::new(rand.clone()).evals());
325 assert_eq!(poly_C.len(), len / 2);
326
327 let num_rounds_prod = poly_C.len().log_2();
328 let comb_func_prod = |poly_A_comp: &G::Scalar,
329 poly_B_comp: &G::Scalar,
330 poly_C_comp: &G::Scalar|
331 -> G::Scalar { *poly_A_comp * *poly_B_comp * *poly_C_comp };
332
333 let mut poly_A_batched: Vec<&mut MultilinearPolynomial<G::Scalar>> = Vec::new();
334 let mut poly_B_batched: Vec<&mut MultilinearPolynomial<G::Scalar>> = Vec::new();
335 for prod_circuit in prod_circuit_vec.iter_mut() {
336 poly_A_batched.push(&mut prod_circuit.left_vec[layer_id]);
337 poly_B_batched.push(&mut prod_circuit.right_vec[layer_id])
338 }
339 let poly_vec = (&mut poly_A_batched, &mut poly_B_batched, &mut poly_C);
340
341 // produce a fresh set of coeffs and a joint claim
342 let coeff_vec = {
343 let s = transcript.squeeze(b"r")?;
344 let mut s_vec = vec![s];
345 for i in 1..claims_to_verify.len() {
346 s_vec.push(s_vec[i - 1] * s);
347 }
348 s_vec
349 };
350
351 let claim = (0..claims_to_verify.len())
352 .map(|i| claims_to_verify[i] * coeff_vec[i])
353 .fold(G::Scalar::zero(), |acc, item| acc + item);
354
355 let (proof, rand_prod, claims_prod) = SumcheckProof::prove_cubic_batched(
356 &claim,
357 num_rounds_prod,
358 poly_vec,
359 &coeff_vec,
360 comb_func_prod,
361 transcript,
362 )?;
363
364 let (claims_prod_left, claims_prod_right, _claims_eq) = claims_prod;
365
366 let v = {
367 let mut v = claims_prod_left.clone();
368 v.extend(&claims_prod_right);
369 v
370 };
371 transcript.absorb(b"p", &v.as_slice());
372
373 // produce a random challenge to condense two claims into a single claim
374 let r_layer = transcript.squeeze(b"c")?;
375
376 claims_to_verify = (0..prod_circuit_vec.len())
377 .map(|i| claims_prod_left[i] + r_layer * (claims_prod_right[i] - claims_prod_left[i]))
378 .collect::<Vec<G::Scalar>>();
379
380 let mut ext = vec![r_layer];
381 ext.extend(rand_prod);
382 rand = ext;
383
384 proof_layers.push(LayerProofBatched {
385 proof,
386 claims_prod_left,
387 claims_prod_right,
388 });
389 }
390
391 Ok((
392 ProductArgumentBatched {
393 proof: proof_layers,
394 },
395 evals,
396 rand,
397 ))
398 }
399
400 pub fn verify(
401 &self,
402 claims_prod_vec: &[G::Scalar],
403 len: usize,
404 transcript: &mut G::TE,
405 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
406 let num_layers = len.log_2();
407
408 let mut rand: Vec<G::Scalar> = Vec::new();
409 if self.proof.len() != num_layers {
410 return Err(NovaError::InvalidProductProof);
411 }
412
413 let mut claims_to_verify = claims_prod_vec.to_owned();
414 for (num_rounds, i) in (0..num_layers).enumerate() {
415 // produce random coefficients, one for each instance
416 let coeff_vec = {
417 let s = transcript.squeeze(b"r")?;
418 let mut s_vec = vec![s];
419 for i in 1..claims_to_verify.len() {
420 s_vec.push(s_vec[i - 1] * s);
421 }
422 s_vec
423 };
424
425 // produce a joint claim
426 let claim = (0..claims_to_verify.len())
427 .map(|i| claims_to_verify[i] * coeff_vec[i])
428 .fold(G::Scalar::zero(), |acc, item| acc + item);
429
430 let (claim_last, rand_prod) = self.proof[i].verify(claim, num_rounds, 3, transcript)?;
431
432 let claims_prod_left = &self.proof[i].claims_prod_left;
433 let claims_prod_right = &self.proof[i].claims_prod_right;
434 if claims_prod_left.len() != claims_prod_vec.len()
435 || claims_prod_right.len() != claims_prod_vec.len()
436 {
437 return Err(NovaError::InvalidProductProof);
438 }
439
440 let v = {
441 let mut v = claims_prod_left.clone();
442 v.extend(claims_prod_right);
443 v
444 };
445 transcript.absorb(b"p", &v.as_slice());
446
447 if rand.len() != rand_prod.len() {
448 return Err(NovaError::InvalidProductProof);
449 }
450
451 let eq: G::Scalar = (0..rand.len())
452 .map(|i| {
453 rand[i] * rand_prod[i] + (G::Scalar::one() - rand[i]) * (G::Scalar::one() - rand_prod[i])
454 })
455 .fold(G::Scalar::one(), |acc, item| acc * item);
456 let claim_expected: G::Scalar = (0..claims_prod_vec.len())
457 .map(|i| coeff_vec[i] * (claims_prod_left[i] * claims_prod_right[i] * eq))
458 .fold(G::Scalar::zero(), |acc, item| acc + item);
459
460 if claim_expected != claim_last {
461 return Err(NovaError::InvalidProductProof);
462 }
463
464 // produce a random challenge
465 let r_layer = transcript.squeeze(b"c")?;
466
467 claims_to_verify = (0..claims_prod_left.len())
468 .map(|i| claims_prod_left[i] + r_layer * (claims_prod_right[i] - claims_prod_left[i]))
469 .collect::<Vec<G::Scalar>>();
470
471 let mut ext = vec![r_layer];
472 ext.extend(rand_prod);
473 rand = ext;
474 }
475 Ok((claims_to_verify, rand))
476 }
477}