Nova/src/spartan/pp/mod.rs
src/spartan/pp/mod.rsRaw
1//! This module implements RelaxedR1CSSNARK traits using a spark-based approach to prove evaluations of
2//! sparse multilinear polynomials involved in Spartan's sum-check protocol, thereby providing a preprocessing SNARK
3use crate::{
4 errors::NovaError,
5 r1cs::{R1CSShape, RelaxedR1CSInstance, RelaxedR1CSWitness},
6 spartan::{
7 math::Math,
8 polynomial::{EqPolynomial, MultilinearPolynomial, SparsePolynomial},
9 sumcheck::SumcheckProof,
10 PolyEvalInstance, PolyEvalWitness,
11 },
12 traits::{
13 commitment::CommitmentEngineTrait, evaluation::EvaluationEngineTrait,
14 snark::RelaxedR1CSSNARKTrait, Group, TranscriptEngineTrait, TranscriptReprTrait,
15 },
16 Commitment, CommitmentKey,
17};
18use core::cmp::max;
19use ff::Field;
20use itertools::concat;
21use rayon::prelude::*;
22use serde::{Deserialize, Serialize};
23
24mod product;
25
26use product::{IdentityPolynomial, ProductArgument};
27
28/// A type that holds R1CSShape in a form amenable to memory checking
29#[derive(Clone, Serialize, Deserialize)]
30#[serde(bound = "")]
31pub struct R1CSShapeSparkRepr<G: Group> {
32 N: usize, // size of the vectors
33
34 // dense representation
35 row: Vec<G::Scalar>,
36 col: Vec<G::Scalar>,
37 val_A: Vec<G::Scalar>,
38 val_B: Vec<G::Scalar>,
39 val_C: Vec<G::Scalar>,
40
41 // timestamp polynomials
42 row_read_ts: Vec<G::Scalar>,
43 row_audit_ts: Vec<G::Scalar>,
44 col_read_ts: Vec<G::Scalar>,
45 col_audit_ts: Vec<G::Scalar>,
46}
47
48/// A type that holds a commitment to a sparse polynomial
49#[derive(Clone, Serialize, Deserialize)]
50#[serde(bound = "")]
51pub struct R1CSShapeSparkCommitment<G: Group> {
52 N: usize, // size of each vector
53
54 // commitments to the dense representation
55 comm_row: Commitment<G>,
56 comm_col: Commitment<G>,
57 comm_val_A: Commitment<G>,
58 comm_val_B: Commitment<G>,
59 comm_val_C: Commitment<G>,
60
61 // commitments to the timestamp polynomials
62 comm_row_read_ts: Commitment<G>,
63 comm_row_audit_ts: Commitment<G>,
64 comm_col_read_ts: Commitment<G>,
65 comm_col_audit_ts: Commitment<G>,
66}
67
68impl<G: Group> TranscriptReprTrait<G> for R1CSShapeSparkCommitment<G> {
69 fn to_transcript_bytes(&self) -> Vec<u8> {
70 [
71 self.comm_row,
72 self.comm_col,
73 self.comm_val_A,
74 self.comm_val_B,
75 self.comm_val_C,
76 self.comm_row_read_ts,
77 self.comm_row_audit_ts,
78 self.comm_col_read_ts,
79 self.comm_col_audit_ts,
80 ]
81 .as_slice()
82 .to_transcript_bytes()
83 }
84}
85
86impl<G: Group> R1CSShapeSparkRepr<G> {
87 /// represents R1CSShape in a Spark-friendly format amenable to memory checking
88 pub fn new(S: &R1CSShape<G>) -> R1CSShapeSparkRepr<G> {
89 let N = {
90 let total_nz = S.A.len() + S.B.len() + S.C.len();
91 max(total_nz, max(2 * S.num_vars, S.num_cons)).next_power_of_two()
92 };
93
94 let row = {
95 let mut r = S
96 .A
97 .iter()
98 .chain(S.B.iter())
99 .chain(S.C.iter())
100 .map(|(r, _, _)| *r)
101 .collect::<Vec<usize>>();
102 r.resize(N, 0usize);
103 r
104 };
105
106 let col = {
107 let mut c = S
108 .A
109 .iter()
110 .chain(S.B.iter())
111 .chain(S.C.iter())
112 .map(|(_, c, _)| *c)
113 .collect::<Vec<usize>>();
114 c.resize(N, 0usize);
115 c
116 };
117
118 let val_A = {
119 let mut val = S.A.iter().map(|(_, _, v)| *v).collect::<Vec<G::Scalar>>();
120 val.resize(N, G::Scalar::zero());
121 val
122 };
123
124 let val_B = {
125 // prepend zeros
126 let mut val = vec![G::Scalar::zero(); S.A.len()];
127 val.extend(S.B.iter().map(|(_, _, v)| *v).collect::<Vec<G::Scalar>>());
128 // append zeros
129 val.resize(N, G::Scalar::zero());
130 val
131 };
132
133 let val_C = {
134 // prepend zeros
135 let mut val = vec![G::Scalar::zero(); S.A.len() + S.B.len()];
136 val.extend(S.C.iter().map(|(_, _, v)| *v).collect::<Vec<G::Scalar>>());
137 // append zeros
138 val.resize(N, G::Scalar::zero());
139 val
140 };
141
142 // timestamp calculation routine
143 let timestamp_calc =
144 |num_ops: usize, num_cells: usize, addr_trace: &[usize]| -> (Vec<usize>, Vec<usize>) {
145 let mut read_ts = vec![0usize; num_ops];
146 let mut audit_ts = vec![0usize; num_cells];
147
148 assert!(num_ops >= addr_trace.len());
149 for i in 0..addr_trace.len() {
150 let addr = addr_trace[i];
151 assert!(addr < num_cells);
152 let r_ts = audit_ts[addr];
153 read_ts[i] = r_ts;
154
155 let w_ts = r_ts + 1;
156 audit_ts[addr] = w_ts;
157 }
158 (read_ts, audit_ts)
159 };
160
161 // timestamp polynomials for row
162 let (row_read_ts, row_audit_ts) = timestamp_calc(N, N, &row);
163 let (col_read_ts, col_audit_ts) = timestamp_calc(N, N, &col);
164
165 // a routine to turn a vector of usize into a vector scalars
166 let to_vec_scalar = |v: &[usize]| -> Vec<G::Scalar> {
167 (0..v.len())
168 .map(|i| G::Scalar::from(v[i] as u64))
169 .collect::<Vec<G::Scalar>>()
170 };
171
172 R1CSShapeSparkRepr {
173 N,
174
175 // dense representation
176 row: to_vec_scalar(&row),
177 col: to_vec_scalar(&col),
178 val_A,
179 val_B,
180 val_C,
181
182 // timestamp polynomials
183 row_read_ts: to_vec_scalar(&row_read_ts),
184 row_audit_ts: to_vec_scalar(&row_audit_ts),
185 col_read_ts: to_vec_scalar(&col_read_ts),
186 col_audit_ts: to_vec_scalar(&col_audit_ts),
187 }
188 }
189
190 fn commit(&self, ck: &CommitmentKey<G>) -> R1CSShapeSparkCommitment<G> {
191 let comm_vec: Vec<Commitment<G>> = [
192 &self.row,
193 &self.col,
194 &self.val_A,
195 &self.val_B,
196 &self.val_C,
197 &self.row_read_ts,
198 &self.row_audit_ts,
199 &self.col_read_ts,
200 &self.col_audit_ts,
201 ]
202 .par_iter()
203 .map(|v| G::CE::commit(ck, v))
204 .collect();
205
206 R1CSShapeSparkCommitment {
207 N: self.row.len(),
208 comm_row: comm_vec[0],
209 comm_col: comm_vec[1],
210 comm_val_A: comm_vec[2],
211 comm_val_B: comm_vec[3],
212 comm_val_C: comm_vec[4],
213 comm_row_read_ts: comm_vec[5],
214 comm_row_audit_ts: comm_vec[6],
215 comm_col_read_ts: comm_vec[7],
216 comm_col_audit_ts: comm_vec[8],
217 }
218 }
219
220 /// evaluates the the provided R1CSShape at (r_x, r_y)
221 pub fn multi_evaluate(
222 M_vec: &[&[(usize, usize, G::Scalar)]],
223 r_x: &[G::Scalar],
224 r_y: &[G::Scalar],
225 ) -> Vec<G::Scalar> {
226 let evaluate_with_table =
227 |M: &[(usize, usize, G::Scalar)], T_x: &[G::Scalar], T_y: &[G::Scalar]| -> G::Scalar {
228 (0..M.len())
229 .collect::<Vec<usize>>()
230 .par_iter()
231 .map(|&i| {
232 let (row, col, val) = M[i];
233 T_x[row] * T_y[col] * val
234 })
235 .reduce(G::Scalar::zero, |acc, x| acc + x)
236 };
237
238 let (T_x, T_y) = rayon::join(
239 || EqPolynomial::new(r_x.to_vec()).evals(),
240 || EqPolynomial::new(r_y.to_vec()).evals(),
241 );
242
243 (0..M_vec.len())
244 .collect::<Vec<usize>>()
245 .par_iter()
246 .map(|&i| evaluate_with_table(M_vec[i], &T_x, &T_y))
247 .collect()
248 }
249
250 // computes evaluation oracles
251 fn evaluation_oracles(
252 &self,
253 S: &R1CSShape<G>,
254 r_x: &[G::Scalar],
255 z: &[G::Scalar],
256 ) -> (
257 Vec<G::Scalar>,
258 Vec<G::Scalar>,
259 Vec<G::Scalar>,
260 Vec<G::Scalar>,
261 ) {
262 let r_x_padded = {
263 let mut x = vec![G::Scalar::zero(); self.N.log_2() - r_x.len()];
264 x.extend(r_x);
265 x
266 };
267
268 let mem_row = EqPolynomial::new(r_x_padded).evals();
269 let mem_col = {
270 let mut z = z.to_vec();
271 z.resize(self.N, G::Scalar::zero());
272 z
273 };
274
275 let mut E_row = S
276 .A
277 .iter()
278 .chain(S.B.iter())
279 .chain(S.C.iter())
280 .map(|(r, _, _)| mem_row[*r])
281 .collect::<Vec<G::Scalar>>();
282
283 let mut E_col = S
284 .A
285 .iter()
286 .chain(S.B.iter())
287 .chain(S.C.iter())
288 .map(|(_, c, _)| mem_col[*c])
289 .collect::<Vec<G::Scalar>>();
290
291 E_row.resize(self.N, mem_row[0]); // we place mem_row[0] since resized row is appended with 0s
292 E_col.resize(self.N, mem_col[0]);
293
294 (mem_row, mem_col, E_row, E_col)
295 }
296}
297
298/// A type that represents the memory-checking argument
299#[derive(Serialize, Deserialize)]
300#[serde(bound = "")]
301pub struct MemcheckProof<G: Group> {
302 sc_prod: ProductArgument<G>,
303
304 eval_init_row: G::Scalar,
305 eval_read_row: G::Scalar,
306 eval_write_row: G::Scalar,
307 eval_audit_row: G::Scalar,
308 eval_init_col: G::Scalar,
309 eval_read_col: G::Scalar,
310 eval_write_col: G::Scalar,
311 eval_audit_col: G::Scalar,
312
313 eval_row: G::Scalar,
314 eval_row_read_ts: G::Scalar,
315 eval_E_row: G::Scalar,
316 eval_row_audit_ts: G::Scalar,
317 eval_col: G::Scalar,
318 eval_col_read_ts: G::Scalar,
319 eval_E_col: G::Scalar,
320 eval_col_audit_ts: G::Scalar,
321 eval_z: G::Scalar,
322}
323
324impl<G: Group> MemcheckProof<G> {
325 #[allow(clippy::too_many_arguments)]
326 /// proves a memory-checking relation
327 fn prove(
328 ck: &CommitmentKey<G>,
329 S_repr: &R1CSShapeSparkRepr<G>,
330 S_comm: &R1CSShapeSparkCommitment<G>,
331 mem_row: &[G::Scalar],
332 comm_E_row: &Commitment<G>,
333 E_row: &[G::Scalar],
334 mem_col: &[G::Scalar],
335 comm_E_col: &Commitment<G>,
336 E_col: &[G::Scalar],
337 transcript: &mut G::TE,
338 ) -> Result<
339 (
340 MemcheckProof<G>,
341 Vec<(PolyEvalWitness<G>, PolyEvalInstance<G>)>,
342 G::Scalar,
343 Vec<G::Scalar>,
344 ),
345 NovaError,
346 > {
347 // we now need to prove that E_row and E_col are well-formed
348 // we use memory checking: H(INIT) * H(WS) =? H(RS) * H(FINAL)
349 let gamma_1 = transcript.squeeze(b"g1")?;
350 let gamma_2 = transcript.squeeze(b"g2")?;
351
352 let gamma_1_sqr = gamma_1 * gamma_1;
353 let hash_func = |addr: &G::Scalar, val: &G::Scalar, ts: &G::Scalar| -> G::Scalar {
354 (*ts * gamma_1_sqr + *val * gamma_1 + *addr) - gamma_2
355 };
356
357 let init_row = (0..mem_row.len())
358 .map(|i| hash_func(&G::Scalar::from(i as u64), &mem_row[i], &G::Scalar::zero()))
359 .collect::<Vec<G::Scalar>>();
360 let read_row = (0..E_row.len())
361 .map(|i| hash_func(&S_repr.row[i], &E_row[i], &S_repr.row_read_ts[i]))
362 .collect::<Vec<G::Scalar>>();
363 let write_row = (0..E_row.len())
364 .map(|i| {
365 hash_func(
366 &S_repr.row[i],
367 &E_row[i],
368 &(S_repr.row_read_ts[i] + G::Scalar::one()),
369 )
370 })
371 .collect::<Vec<G::Scalar>>();
372 let audit_row = (0..mem_row.len())
373 .map(|i| {
374 hash_func(
375 &G::Scalar::from(i as u64),
376 &mem_row[i],
377 &S_repr.row_audit_ts[i],
378 )
379 })
380 .collect::<Vec<G::Scalar>>();
381
382 let init_col = (0..mem_col.len())
383 .map(|i| hash_func(&G::Scalar::from(i as u64), &mem_col[i], &G::Scalar::zero()))
384 .collect::<Vec<G::Scalar>>();
385 let read_col = (0..E_col.len())
386 .map(|i| hash_func(&S_repr.col[i], &E_col[i], &S_repr.col_read_ts[i]))
387 .collect::<Vec<G::Scalar>>();
388 let write_col = (0..E_col.len())
389 .map(|i| {
390 hash_func(
391 &S_repr.col[i],
392 &E_col[i],
393 &(S_repr.col_read_ts[i] + G::Scalar::one()),
394 )
395 })
396 .collect::<Vec<G::Scalar>>();
397 let audit_col = (0..mem_col.len())
398 .map(|i| {
399 hash_func(
400 &G::Scalar::from(i as u64),
401 &mem_col[i],
402 &S_repr.col_audit_ts[i],
403 )
404 })
405 .collect::<Vec<G::Scalar>>();
406
407 let (sc_prod, evals_prod, r_prod, _evals_input_vec, mut w_u_vec) = ProductArgument::prove(
408 ck,
409 &[
410 init_row, read_row, write_row, audit_row, init_col, read_col, write_col, audit_col,
411 ],
412 transcript,
413 )?;
414
415 // row-related and col-related claims of polynomial evaluations to aid the final check of the sum-check
416 let evals = [
417 &S_repr.row,
418 &S_repr.row_read_ts,
419 E_row,
420 &S_repr.row_audit_ts,
421 &S_repr.col,
422 &S_repr.col_read_ts,
423 E_col,
424 &S_repr.col_audit_ts,
425 mem_col,
426 ]
427 .into_par_iter()
428 .map(|p| MultilinearPolynomial::evaluate_with(p, &r_prod))
429 .collect::<Vec<G::Scalar>>();
430
431 let eval_row = evals[0];
432 let eval_row_read_ts = evals[1];
433 let eval_E_row = evals[2];
434 let eval_row_audit_ts = evals[3];
435 let eval_col = evals[4];
436 let eval_col_read_ts = evals[5];
437 let eval_E_col = evals[6];
438 let eval_col_audit_ts = evals[7];
439 let eval_z = evals[8];
440
441 // we can batch all the claims
442 transcript.absorb(
443 b"e",
444 &[
445 eval_row,
446 eval_row_read_ts,
447 eval_E_row,
448 eval_row_audit_ts,
449 eval_col,
450 eval_col_read_ts,
451 eval_E_col,
452 eval_col_audit_ts,
453 ]
454 .as_slice(),
455 );
456 let c = transcript.squeeze(b"c")?;
457 let eval_joint = eval_row
458 + c * eval_row_read_ts
459 + c * c * eval_E_row
460 + c * c * c * eval_row_audit_ts
461 + c * c * c * c * eval_col
462 + c * c * c * c * c * eval_col_read_ts
463 + c * c * c * c * c * c * eval_E_col
464 + c * c * c * c * c * c * c * eval_col_audit_ts;
465 let comm_joint = S_comm.comm_row
466 + S_comm.comm_row_read_ts * c
467 + *comm_E_row * c * c
468 + S_comm.comm_row_audit_ts * c * c * c
469 + S_comm.comm_col * c * c * c * c
470 + S_comm.comm_col_read_ts * c * c * c * c * c
471 + *comm_E_col * c * c * c * c * c * c
472 + S_comm.comm_col_audit_ts * c * c * c * c * c * c * c;
473 let poly_joint = S_repr
474 .row
475 .iter()
476 .zip(S_repr.row_read_ts.iter())
477 .zip(E_row.iter())
478 .zip(S_repr.row_audit_ts.iter())
479 .zip(S_repr.col.iter())
480 .zip(S_repr.col_read_ts.iter())
481 .zip(E_col.iter())
482 .zip(S_repr.col_audit_ts.iter())
483 .map(|(((((((x, y), z), m), n), q), s), t)| {
484 *x + c * y
485 + c * c * z
486 + c * c * c * m
487 + c * c * c * c * n
488 + c * c * c * c * c * q
489 + c * c * c * c * c * c * s
490 + c * c * c * c * c * c * c * t
491 })
492 .collect::<Vec<_>>();
493
494 // add the claim to prove for later
495 w_u_vec.push((
496 PolyEvalWitness { p: poly_joint },
497 PolyEvalInstance {
498 c: comm_joint,
499 x: r_prod.clone(),
500 e: eval_joint,
501 },
502 ));
503
504 let eval_arg = Self {
505 eval_init_row: evals_prod[0],
506 eval_read_row: evals_prod[1],
507 eval_write_row: evals_prod[2],
508 eval_audit_row: evals_prod[3],
509 eval_init_col: evals_prod[4],
510 eval_read_col: evals_prod[5],
511 eval_write_col: evals_prod[6],
512 eval_audit_col: evals_prod[7],
513 sc_prod,
514
515 eval_row,
516 eval_row_read_ts,
517 eval_E_row,
518 eval_row_audit_ts,
519 eval_col,
520 eval_col_read_ts,
521 eval_E_col,
522 eval_col_audit_ts,
523 eval_z,
524 };
525
526 Ok((eval_arg, w_u_vec, eval_z, r_prod))
527 }
528
529 /// verifies a memory-checking relation
530 fn verify(
531 &self,
532 S_comm: &R1CSShapeSparkCommitment<G>,
533 comm_E_row: &Commitment<G>,
534 comm_E_col: &Commitment<G>,
535 r_x: &[G::Scalar],
536 transcript: &mut G::TE,
537 ) -> Result<(Vec<PolyEvalInstance<G>>, G::Scalar, Vec<G::Scalar>), NovaError> {
538 let r_x_padded = {
539 let mut x = vec![G::Scalar::zero(); S_comm.N.log_2() - r_x.len()];
540 x.extend(r_x);
541 x
542 };
543
544 // verify if E_row and E_col are well formed
545 let gamma_1 = transcript.squeeze(b"g1")?;
546 let gamma_2 = transcript.squeeze(b"g2")?;
547
548 // hash function
549 let gamma_1_sqr = gamma_1 * gamma_1;
550 let hash_func = |addr: &G::Scalar, val: &G::Scalar, ts: &G::Scalar| -> G::Scalar {
551 (*ts * gamma_1_sqr + *val * gamma_1 + *addr) - gamma_2
552 };
553
554 // check the required multiset relationship
555 // row
556 if self.eval_init_row * self.eval_write_row != self.eval_read_row * self.eval_audit_row {
557 return Err(NovaError::InvalidMultisetProof);
558 }
559 // col
560 if self.eval_init_col * self.eval_write_col != self.eval_read_col * self.eval_audit_col {
561 return Err(NovaError::InvalidMultisetProof);
562 }
563
564 // verify the product proofs
565 let (claims_final, r_prod, mut u_vec) = self.sc_prod.verify(
566 &[
567 self.eval_init_row,
568 self.eval_read_row,
569 self.eval_write_row,
570 self.eval_audit_row,
571 self.eval_init_col,
572 self.eval_read_col,
573 self.eval_write_col,
574 self.eval_audit_col,
575 ],
576 S_comm.N,
577 transcript,
578 )?;
579
580 // finish the final step of the sum-check
581 let (claim_init_expected_row, claim_audit_expected_row) = {
582 let addr = IdentityPolynomial::new(r_prod.len()).evaluate(&r_prod);
583 let val = EqPolynomial::new(r_x_padded.to_vec()).evaluate(&r_prod);
584 (
585 hash_func(&addr, &val, &G::Scalar::zero()),
586 hash_func(&addr, &val, &self.eval_row_audit_ts),
587 )
588 };
589
590 let (claim_read_expected_row, claim_write_expected_row) = {
591 (
592 hash_func(&self.eval_row, &self.eval_E_row, &self.eval_row_read_ts),
593 hash_func(
594 &self.eval_row,
595 &self.eval_E_row,
596 &(self.eval_row_read_ts + G::Scalar::one()),
597 ),
598 )
599 };
600
601 // multiset check for the row
602 if claim_init_expected_row != claims_final[0]
603 || claim_read_expected_row != claims_final[1]
604 || claim_write_expected_row != claims_final[2]
605 || claim_audit_expected_row != claims_final[3]
606 {
607 return Err(NovaError::InvalidSumcheckProof);
608 }
609
610 let (claim_init_expected_col, claim_audit_expected_col) = {
611 let addr = IdentityPolynomial::new(r_prod.len()).evaluate(&r_prod);
612 let val = self.eval_z; // this value is later checked against U.comm_W and u.X
613 (
614 hash_func(&addr, &val, &G::Scalar::zero()),
615 hash_func(&addr, &val, &self.eval_col_audit_ts),
616 )
617 };
618
619 let (claim_read_expected_col, claim_write_expected_col) = {
620 (
621 hash_func(&self.eval_col, &self.eval_E_col, &self.eval_col_read_ts),
622 hash_func(
623 &self.eval_col,
624 &self.eval_E_col,
625 &(self.eval_col_read_ts + G::Scalar::one()),
626 ),
627 )
628 };
629
630 // multiset check for the col
631 if claim_init_expected_col != claims_final[4]
632 || claim_read_expected_col != claims_final[5]
633 || claim_write_expected_col != claims_final[6]
634 || claim_audit_expected_col != claims_final[7]
635 {
636 return Err(NovaError::InvalidSumcheckProof);
637 }
638
639 transcript.absorb(
640 b"e",
641 &[
642 self.eval_row,
643 self.eval_row_read_ts,
644 self.eval_E_row,
645 self.eval_row_audit_ts,
646 self.eval_col,
647 self.eval_col_read_ts,
648 self.eval_E_col,
649 self.eval_col_audit_ts,
650 ]
651 .as_slice(),
652 );
653 let c = transcript.squeeze(b"c")?;
654 let eval_joint = self.eval_row
655 + c * self.eval_row_read_ts
656 + c * c * self.eval_E_row
657 + c * c * c * self.eval_row_audit_ts
658 + c * c * c * c * self.eval_col
659 + c * c * c * c * c * self.eval_col_read_ts
660 + c * c * c * c * c * c * self.eval_E_col
661 + c * c * c * c * c * c * c * self.eval_col_audit_ts;
662 let comm_joint = S_comm.comm_row
663 + S_comm.comm_row_read_ts * c
664 + *comm_E_row * c * c
665 + S_comm.comm_row_audit_ts * c * c * c
666 + S_comm.comm_col * c * c * c * c
667 + S_comm.comm_col_read_ts * c * c * c * c * c
668 + *comm_E_col * c * c * c * c * c * c
669 + S_comm.comm_col_audit_ts * c * c * c * c * c * c * c;
670
671 u_vec.push(PolyEvalInstance {
672 c: comm_joint,
673 x: r_prod.clone(),
674 e: eval_joint,
675 });
676
677 Ok((u_vec, self.eval_z, r_prod))
678 }
679}
680
681/// A type that represents the prover's key
682#[derive(Serialize, Deserialize)]
683#[serde(bound = "")]
684pub struct ProverKey<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
685 pk_ee: EE::ProverKey,
686 S: R1CSShape<G>,
687 S_repr: R1CSShapeSparkRepr<G>,
688 S_comm: R1CSShapeSparkCommitment<G>,
689}
690
691/// A type that represents the verifier's key
692#[derive(Serialize, Deserialize)]
693#[serde(bound = "")]
694pub struct VerifierKey<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
695 num_cons: usize,
696 num_vars: usize,
697 vk_ee: EE::VerifierKey,
698 S_comm: R1CSShapeSparkCommitment<G>,
699}
700
701/// A succinct proof of knowledge of a witness to a relaxed R1CS instance
702/// The proof is produced using Spartan's combination of the sum-check and
703/// the commitment to a vector viewed as a polynomial commitment
704#[derive(Serialize, Deserialize)]
705#[serde(bound = "")]
706pub struct RelaxedR1CSSNARK<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
707 // outer sum-check
708 sc_proof_outer: SumcheckProof<G>,
709
710 // claims from the end of the outer sum-check
711 eval_Az: G::Scalar,
712 eval_Bz: G::Scalar,
713 eval_Cz: G::Scalar,
714 eval_E: G::Scalar,
715
716 // commitment to oracles for the inner sum-check
717 comm_E_row: Commitment<G>,
718 comm_E_col: Commitment<G>,
719
720 // inner sum-check
721 sc_proof_inner: SumcheckProof<G>,
722
723 // claims from the end of inner sum-check
724 eval_E_row: G::Scalar,
725 eval_E_col: G::Scalar,
726 eval_val_A: G::Scalar,
727 eval_val_B: G::Scalar,
728 eval_val_C: G::Scalar,
729
730 // memory-checking proof
731 mc_proof: MemcheckProof<G>,
732
733 // claim about W evaluation
734 eval_W: G::Scalar,
735
736 // batch openings of all multilinear polynomials
737 sc_proof_batch: SumcheckProof<G>,
738 evals_batch: Vec<G::Scalar>,
739 eval_arg: EE::EvaluationArgument,
740}
741
742impl<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> RelaxedR1CSSNARKTrait<G>
743 for RelaxedR1CSSNARK<G, EE>
744{
745 type ProverKey = ProverKey<G, EE>;
746 type VerifierKey = VerifierKey<G, EE>;
747
748 fn setup(
749 ck: &CommitmentKey<G>,
750 S: &R1CSShape<G>,
751 ) -> Result<(Self::ProverKey, Self::VerifierKey), NovaError> {
752 let (pk_ee, vk_ee) = EE::setup(ck);
753
754 // pad the R1CS matrices
755 let S = S.pad();
756
757 let S_repr = R1CSShapeSparkRepr::new(&S);
758 let S_comm = S_repr.commit(ck);
759
760 let vk = VerifierKey {
761 num_cons: S.num_cons,
762 num_vars: S.num_vars,
763 S_comm: S_comm.clone(),
764 vk_ee,
765 };
766
767 let pk = ProverKey {
768 pk_ee,
769 S,
770 S_repr,
771 S_comm,
772 };
773
774 Ok((pk, vk))
775 }
776
777 /// produces a succinct proof of satisfiability of a RelaxedR1CS instance
778 fn prove(
779 ck: &CommitmentKey<G>,
780 pk: &Self::ProverKey,
781 U: &RelaxedR1CSInstance<G>,
782 W: &RelaxedR1CSWitness<G>,
783 ) -> Result<Self, NovaError> {
784 let W = W.pad(&pk.S); // pad the witness
785 let mut transcript = G::TE::new(b"RelaxedR1CSSNARK");
786
787 // a list of polynomial evaluation claims that will be batched
788 let mut w_u_vec = Vec::new();
789
790 // sanity check that R1CSShape has certain size characteristics
791 assert_eq!(pk.S.num_cons.next_power_of_two(), pk.S.num_cons);
792 assert_eq!(pk.S.num_vars.next_power_of_two(), pk.S.num_vars);
793 assert_eq!(pk.S.num_io.next_power_of_two(), pk.S.num_io);
794 assert!(pk.S.num_io < pk.S.num_vars);
795
796 // append the commitment to R1CS matrices and the RelaxedR1CSInstance to the transcript
797 transcript.absorb(b"C", &pk.S_comm);
798 transcript.absorb(b"U", U);
799
800 // compute the full satisfying assignment by concatenating W.W, U.u, and U.X
801 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
802
803 let (num_rounds_x, _num_rounds_y) = (
804 (pk.S.num_cons as f64).log2() as usize,
805 ((pk.S.num_vars as f64).log2() as usize + 1),
806 );
807
808 // outer sum-check
809 let tau = (0..num_rounds_x)
810 .map(|_i| transcript.squeeze(b"t"))
811 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
812
813 let mut poly_tau = MultilinearPolynomial::new(EqPolynomial::new(tau).evals());
814 let (mut poly_Az, mut poly_Bz, poly_Cz, mut poly_uCz_E) = {
815 let (poly_Az, poly_Bz, poly_Cz) = pk.S.multiply_vec(&z)?;
816 let poly_uCz_E = (0..pk.S.num_cons)
817 .map(|i| U.u * poly_Cz[i] + W.E[i])
818 .collect::<Vec<G::Scalar>>();
819 (
820 MultilinearPolynomial::new(poly_Az),
821 MultilinearPolynomial::new(poly_Bz),
822 MultilinearPolynomial::new(poly_Cz),
823 MultilinearPolynomial::new(poly_uCz_E),
824 )
825 };
826
827 let comb_func_outer =
828 |poly_A_comp: &G::Scalar,
829 poly_B_comp: &G::Scalar,
830 poly_C_comp: &G::Scalar,
831 poly_D_comp: &G::Scalar|
832 -> G::Scalar { *poly_A_comp * (*poly_B_comp * *poly_C_comp - *poly_D_comp) };
833 let (sc_proof_outer, r_x, claims_outer) = SumcheckProof::prove_cubic_with_additive_term(
834 &G::Scalar::zero(), // claim is zero
835 num_rounds_x,
836 &mut poly_tau,
837 &mut poly_Az,
838 &mut poly_Bz,
839 &mut poly_uCz_E,
840 comb_func_outer,
841 &mut transcript,
842 )?;
843
844 // claims from the end of sum-check
845 let (eval_Az, eval_Bz): (G::Scalar, G::Scalar) = (claims_outer[1], claims_outer[2]);
846 let eval_Cz = poly_Cz.evaluate(&r_x);
847 let eval_E = MultilinearPolynomial::new(W.E.clone()).evaluate(&r_x);
848 transcript.absorb(b"o", &[eval_Az, eval_Bz, eval_Cz, eval_E].as_slice());
849
850 // add claim about eval_E to be proven
851 w_u_vec.push((
852 PolyEvalWitness { p: W.E.clone() },
853 PolyEvalInstance {
854 c: U.comm_E,
855 x: r_x.clone(),
856 e: eval_E,
857 },
858 ));
859
860 // send oracles to aid the inner sum-check
861 // E_row(i) = eq(r_x, row(i)) for all i
862 // E_col(i) = z(col(i)) for all i
863 let (mem_row, z, E_row, E_col) = pk.S_repr.evaluation_oracles(&pk.S, &r_x, &z);
864 let (comm_E_row, comm_E_col) =
865 rayon::join(|| G::CE::commit(ck, &E_row), || G::CE::commit(ck, &E_col));
866
867 // add E_row and E_col to transcript
868 transcript.absorb(b"e", &vec![comm_E_row, comm_E_col].as_slice());
869
870 let r = transcript.squeeze(b"r")?;
871 let val = pk
872 .S_repr
873 .val_A
874 .iter()
875 .zip(pk.S_repr.val_B.iter())
876 .zip(pk.S_repr.val_C.iter())
877 .map(|((a, b), c)| *a + r * *b + r * r * *c)
878 .collect::<Vec<G::Scalar>>();
879
880 // inner sum-check
881 let claim_inner_joint = eval_Az + r * eval_Bz + r * r * eval_Cz;
882 let num_rounds_y = pk.S_repr.N.log_2();
883 let comb_func = |poly_A_comp: &G::Scalar,
884 poly_B_comp: &G::Scalar,
885 poly_C_comp: &G::Scalar|
886 -> G::Scalar { *poly_A_comp * *poly_B_comp * *poly_C_comp };
887
888 debug_assert_eq!(
889 E_row
890 .iter()
891 .zip(val.iter())
892 .zip(E_col.iter())
893 .map(|((a, b), c)| *a * *b * *c)
894 .fold(G::Scalar::zero(), |acc, item| acc + item),
895 claim_inner_joint
896 );
897
898 let (sc_proof_inner, r_y, claims_inner) = SumcheckProof::prove_cubic(
899 &claim_inner_joint,
900 num_rounds_y,
901 &mut MultilinearPolynomial::new(E_row.clone()),
902 &mut MultilinearPolynomial::new(E_col.clone()),
903 &mut MultilinearPolynomial::new(val),
904 comb_func,
905 &mut transcript,
906 )?;
907
908 let eval_E_row = claims_inner[0];
909 let eval_E_col = claims_inner[1];
910 let eval_val_A = MultilinearPolynomial::evaluate_with(&pk.S_repr.val_A, &r_y);
911 let eval_val_B = MultilinearPolynomial::evaluate_with(&pk.S_repr.val_B, &r_y);
912 let eval_val_C = MultilinearPolynomial::evaluate_with(&pk.S_repr.val_C, &r_y);
913
914 // since all the five polynomials are opened at r_y,
915 // we can combine them into a single polynomial opened at r_y
916 transcript.absorb(
917 b"e",
918 &[eval_E_row, eval_E_col, eval_val_A, eval_val_B, eval_val_C].as_slice(),
919 );
920 let c = transcript.squeeze(b"c")?;
921 let eval_sc_inner = eval_E_row
922 + c * eval_E_col
923 + c * c * eval_val_A
924 + c * c * c * eval_val_B
925 + c * c * c * c * eval_val_C;
926 let comm_sc_inner = comm_E_row
927 + comm_E_col * c
928 + pk.S_comm.comm_val_A * c * c
929 + pk.S_comm.comm_val_B * c * c * c
930 + pk.S_comm.comm_val_C * c * c * c * c;
931 let poly_sc_inner = E_row
932 .iter()
933 .zip(E_col.iter())
934 .zip(pk.S_repr.val_A.iter())
935 .zip(pk.S_repr.val_B.iter())
936 .zip(pk.S_repr.val_C.iter())
937 .map(|((((x, y), z), m), n)| *x + c * y + c * c * z + c * c * c * m + c * c * c * c * n)
938 .collect::<Vec<_>>();
939
940 w_u_vec.push((
941 PolyEvalWitness { p: poly_sc_inner },
942 PolyEvalInstance {
943 c: comm_sc_inner,
944 x: r_y,
945 e: eval_sc_inner,
946 },
947 ));
948
949 // we need to prove that E_row and E_col are well-formed
950 let (mc_proof, w_u_vec_mem, _eval_z, r_prod) = MemcheckProof::prove(
951 ck,
952 &pk.S_repr,
953 &pk.S_comm,
954 &mem_row,
955 &comm_E_row,
956 &E_row,
957 &z,
958 &comm_E_col,
959 &E_col,
960 &mut transcript,
961 )?;
962
963 // add claims from memory-checking
964 w_u_vec.extend(w_u_vec_mem);
965
966 // we need to prove that eval_z = z(r_prod) = (1-r_prod[0]) * W.w(r_prod[1..]) + r_prod[0] * U.x(r_prod[1..]).
967 // r_prod was padded, so we now remove the padding
968 let r_prod_unpad = {
969 let l = pk.S_repr.N.log_2() - (2 * pk.S.num_vars).log_2();
970 r_prod[l..].to_vec()
971 };
972
973 let eval_W = MultilinearPolynomial::evaluate_with(&W.W, &r_prod_unpad[1..]);
974 w_u_vec.push((
975 PolyEvalWitness { p: W.W },
976 PolyEvalInstance {
977 c: U.comm_W,
978 x: r_prod_unpad[1..].to_vec(),
979 e: eval_W,
980 },
981 ));
982
983 // We will now reduce a vector of claims of evaluations at different points into claims about them at the same point.
984 // For example, eval_W =? W(r_y[1..]) and eval_W =? E(r_x) into
985 // two claims: eval_W_prime =? W(rz) and eval_E_prime =? E(rz)
986 // We can them combine the two into one: eval_W_prime + gamma * eval_E_prime =? (W + gamma*E)(rz),
987 // where gamma is a public challenge
988 // Since commitments to W and E are homomorphic, the verifier can compute a commitment
989 // to the batched polynomial.
990 assert!(w_u_vec.len() >= 2);
991
992 let (w_vec, u_vec): (Vec<PolyEvalWitness<G>>, Vec<PolyEvalInstance<G>>) =
993 w_u_vec.into_iter().unzip();
994 let w_vec_padded = PolyEvalWitness::pad(&w_vec); // pad the polynomials to be of the same size
995 let u_vec_padded = PolyEvalInstance::pad(&u_vec); // pad the evaluation points
996
997 let powers = |s: &G::Scalar, n: usize| -> Vec<G::Scalar> {
998 assert!(n >= 1);
999 let mut powers = Vec::new();
1000 powers.push(G::Scalar::one());
1001 for i in 1..n {
1002 powers.push(powers[i - 1] * s);
1003 }
1004 powers
1005 };
1006
1007 // generate a challenge
1008 let rho = transcript.squeeze(b"r")?;
1009 let num_claims = w_vec_padded.len();
1010 let powers_of_rho = powers(&rho, num_claims);
1011 let claim_batch_joint = u_vec_padded
1012 .iter()
1013 .zip(powers_of_rho.iter())
1014 .map(|(u, p)| u.e * p)
1015 .fold(G::Scalar::zero(), |acc, item| acc + item);
1016
1017 let mut polys_left: Vec<MultilinearPolynomial<G::Scalar>> = w_vec_padded
1018 .iter()
1019 .map(|w| MultilinearPolynomial::new(w.p.clone()))
1020 .collect();
1021 let mut polys_right: Vec<MultilinearPolynomial<G::Scalar>> = u_vec_padded
1022 .iter()
1023 .map(|u| MultilinearPolynomial::new(EqPolynomial::new(u.x.clone()).evals()))
1024 .collect();
1025
1026 let num_rounds_z = u_vec_padded[0].x.len();
1027 let comb_func = |poly_A_comp: &G::Scalar, poly_B_comp: &G::Scalar| -> G::Scalar {
1028 *poly_A_comp * *poly_B_comp
1029 };
1030 let (sc_proof_batch, r_z, claims_batch) = SumcheckProof::prove_quad_batch(
1031 &claim_batch_joint,
1032 num_rounds_z,
1033 &mut polys_left,
1034 &mut polys_right,
1035 &powers_of_rho,
1036 comb_func,
1037 &mut transcript,
1038 )?;
1039
1040 let (claims_batch_left, _): (Vec<G::Scalar>, Vec<G::Scalar>) = claims_batch;
1041
1042 transcript.absorb(b"l", &claims_batch_left.as_slice());
1043
1044 // we now combine evaluation claims at the same point rz into one
1045 let gamma = transcript.squeeze(b"g")?;
1046 let powers_of_gamma: Vec<G::Scalar> = powers(&gamma, num_claims);
1047 let comm_joint = u_vec_padded
1048 .iter()
1049 .zip(powers_of_gamma.iter())
1050 .map(|(u, g_i)| u.c * *g_i)
1051 .fold(Commitment::<G>::default(), |acc, item| acc + item);
1052 let poly_joint = PolyEvalWitness::weighted_sum(&w_vec_padded, &powers_of_gamma);
1053 let eval_joint = claims_batch_left
1054 .iter()
1055 .zip(powers_of_gamma.iter())
1056 .map(|(e, g_i)| *e * *g_i)
1057 .fold(G::Scalar::zero(), |acc, item| acc + item);
1058
1059 let eval_arg = EE::prove(
1060 ck,
1061 &pk.pk_ee,
1062 &mut transcript,
1063 &comm_joint,
1064 &poly_joint.p,
1065 &r_z,
1066 &eval_joint,
1067 )?;
1068
1069 Ok(RelaxedR1CSSNARK {
1070 sc_proof_outer,
1071 eval_Az,
1072 eval_Bz,
1073 eval_Cz,
1074 eval_E,
1075 comm_E_row,
1076 comm_E_col,
1077 sc_proof_inner,
1078 eval_E_row,
1079 eval_val_A,
1080 eval_val_B,
1081 eval_val_C,
1082 eval_E_col,
1083
1084 mc_proof,
1085
1086 eval_W,
1087
1088 sc_proof_batch,
1089 evals_batch: claims_batch_left,
1090 eval_arg,
1091 })
1092 }
1093
1094 /// verifies a proof of satisfiability of a RelaxedR1CS instance
1095 fn verify(&self, vk: &Self::VerifierKey, U: &RelaxedR1CSInstance<G>) -> Result<(), NovaError> {
1096 let mut transcript = G::TE::new(b"RelaxedR1CSSNARK");
1097 let mut u_vec: Vec<PolyEvalInstance<G>> = Vec::new();
1098
1099 // append the commitment to R1CS matrices and the RelaxedR1CSInstance to the transcript
1100 transcript.absorb(b"C", &vk.S_comm);
1101 transcript.absorb(b"U", U);
1102
1103 let num_rounds_x = (vk.num_cons as f64).log2() as usize;
1104
1105 // outer sum-check
1106 let tau = (0..num_rounds_x)
1107 .map(|_i| transcript.squeeze(b"t"))
1108 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
1109
1110 let (claim_outer_final, r_x) =
1111 self
1112 .sc_proof_outer
1113 .verify(G::Scalar::zero(), num_rounds_x, 3, &mut transcript)?;
1114
1115 // verify claim_outer_final
1116 let taus_bound_rx = EqPolynomial::new(tau).evaluate(&r_x);
1117 let claim_outer_final_expected =
1118 taus_bound_rx * (self.eval_Az * self.eval_Bz - U.u * self.eval_Cz - self.eval_E);
1119 if claim_outer_final != claim_outer_final_expected {
1120 return Err(NovaError::InvalidSumcheckProof);
1121 }
1122
1123 // absorb the claim about eval_E to be checked later
1124 u_vec.push(PolyEvalInstance {
1125 c: U.comm_E,
1126 x: r_x.clone(),
1127 e: self.eval_E,
1128 });
1129
1130 transcript.absorb(
1131 b"o",
1132 &[self.eval_Az, self.eval_Bz, self.eval_Cz, self.eval_E].as_slice(),
1133 );
1134
1135 // add claimed oracles
1136 transcript.absorb(b"e", &vec![self.comm_E_row, self.comm_E_col].as_slice());
1137
1138 // inner sum-check
1139 let r = transcript.squeeze(b"r")?;
1140 let claim_inner_joint = self.eval_Az + r * self.eval_Bz + r * r * self.eval_Cz;
1141 let num_rounds_y = vk.S_comm.N.log_2();
1142
1143 let (claim_inner_final, r_y) =
1144 self
1145 .sc_proof_inner
1146 .verify(claim_inner_joint, num_rounds_y, 3, &mut transcript)?;
1147
1148 // verify claim_inner_final
1149 let claim_inner_final_expected = self.eval_E_row
1150 * self.eval_E_col
1151 * (self.eval_val_A + r * self.eval_val_B + r * r * self.eval_val_C);
1152 if claim_inner_final != claim_inner_final_expected {
1153 return Err(NovaError::InvalidSumcheckProof);
1154 }
1155
1156 // add claims about five polynomials used at the end of the inner sum-check
1157 // since they are all evaluated at r_y, we can batch them into one
1158 transcript.absorb(
1159 b"e",
1160 &[
1161 self.eval_E_row,
1162 self.eval_E_col,
1163 self.eval_val_A,
1164 self.eval_val_B,
1165 self.eval_val_C,
1166 ]
1167 .as_slice(),
1168 );
1169 let c = transcript.squeeze(b"c")?;
1170 let eval_sc_inner = self.eval_E_row
1171 + c * self.eval_E_col
1172 + c * c * self.eval_val_A
1173 + c * c * c * self.eval_val_B
1174 + c * c * c * c * self.eval_val_C;
1175 let comm_sc_inner = self.comm_E_row
1176 + self.comm_E_col * c
1177 + vk.S_comm.comm_val_A * c * c
1178 + vk.S_comm.comm_val_B * c * c * c
1179 + vk.S_comm.comm_val_C * c * c * c * c;
1180
1181 u_vec.push(PolyEvalInstance {
1182 c: comm_sc_inner,
1183 x: r_y,
1184 e: eval_sc_inner,
1185 });
1186
1187 let (u_vec_mem, eval_Z, r_prod) = self.mc_proof.verify(
1188 &vk.S_comm,
1189 &self.comm_E_row,
1190 &self.comm_E_col,
1191 &r_x,
1192 &mut transcript,
1193 )?;
1194
1195 u_vec.extend(u_vec_mem);
1196
1197 // we verify that eval_z = z(r_prod) = (1-r_prod[0]) * W.w(r_prod[1..]) + r_prod[0] * U.x(r_prod[1..]).
1198 let (eval_Z_expected, r_prod_unpad) = {
1199 // r_prod was padded, so we now remove the padding
1200 let (factor, r_prod_unpad) = {
1201 let l = vk.S_comm.N.log_2() - (2 * vk.num_vars).log_2();
1202
1203 let mut factor = G::Scalar::one();
1204 for r_p in r_prod.iter().take(l) {
1205 factor *= G::Scalar::one() - r_p
1206 }
1207
1208 (factor, r_prod[l..].to_vec())
1209 };
1210
1211 let eval_X = {
1212 // constant term
1213 let mut poly_X = vec![(0, U.u)];
1214 //remaining inputs
1215 poly_X.extend(
1216 (0..U.X.len())
1217 .map(|i| (i + 1, U.X[i]))
1218 .collect::<Vec<(usize, G::Scalar)>>(),
1219 );
1220 SparsePolynomial::new((vk.num_vars as f64).log2() as usize, poly_X)
1221 .evaluate(&r_prod_unpad[1..])
1222 };
1223 let eval_Z =
1224 factor * ((G::Scalar::one() - r_prod_unpad[0]) * self.eval_W + r_prod_unpad[0] * eval_X);
1225
1226 (eval_Z, r_prod_unpad)
1227 };
1228
1229 if eval_Z != eval_Z_expected {
1230 return Err(NovaError::IncorrectWitness);
1231 }
1232
1233 u_vec.push(PolyEvalInstance {
1234 c: U.comm_W,
1235 x: r_prod_unpad[1..].to_vec(),
1236 e: self.eval_W,
1237 });
1238
1239 let u_vec_padded = PolyEvalInstance::pad(&u_vec); // pad the evaluation points
1240
1241 let powers = |s: &G::Scalar, n: usize| -> Vec<G::Scalar> {
1242 assert!(n >= 1);
1243 let mut powers = Vec::new();
1244 powers.push(G::Scalar::one());
1245 for i in 1..n {
1246 powers.push(powers[i - 1] * s);
1247 }
1248 powers
1249 };
1250
1251 // generate a challenge
1252 let rho = transcript.squeeze(b"r")?;
1253 let num_claims = u_vec.len();
1254 let powers_of_rho = powers(&rho, num_claims);
1255 let claim_batch_joint = u_vec
1256 .iter()
1257 .zip(powers_of_rho.iter())
1258 .map(|(u, p)| u.e * p)
1259 .fold(G::Scalar::zero(), |acc, item| acc + item);
1260
1261 let num_rounds_z = u_vec_padded[0].x.len();
1262 let (claim_batch_final, r_z) =
1263 self
1264 .sc_proof_batch
1265 .verify(claim_batch_joint, num_rounds_z, 2, &mut transcript)?;
1266
1267 let claim_batch_final_expected = {
1268 let poly_rz = EqPolynomial::new(r_z.clone());
1269 let evals = u_vec_padded
1270 .iter()
1271 .map(|u| poly_rz.evaluate(&u.x))
1272 .collect::<Vec<G::Scalar>>();
1273
1274 evals
1275 .iter()
1276 .zip(self.evals_batch.iter())
1277 .zip(powers_of_rho.iter())
1278 .map(|((e_i, p_i), rho_i)| *e_i * *p_i * rho_i)
1279 .fold(G::Scalar::zero(), |acc, item| acc + item)
1280 };
1281
1282 if claim_batch_final != claim_batch_final_expected {
1283 return Err(NovaError::InvalidSumcheckProof);
1284 }
1285
1286 transcript.absorb(b"l", &self.evals_batch.as_slice());
1287
1288 // we now combine evaluation claims at the same point rz into one
1289 let gamma = transcript.squeeze(b"g")?;
1290 let powers_of_gamma: Vec<G::Scalar> = powers(&gamma, num_claims);
1291 let comm_joint = u_vec_padded
1292 .iter()
1293 .zip(powers_of_gamma.iter())
1294 .map(|(u, g_i)| u.c * *g_i)
1295 .fold(Commitment::<G>::default(), |acc, item| acc + item);
1296 let eval_joint = self
1297 .evals_batch
1298 .iter()
1299 .zip(powers_of_gamma.iter())
1300 .map(|(e, g_i)| *e * *g_i)
1301 .fold(G::Scalar::zero(), |acc, item| acc + item);
1302
1303 // verify
1304 EE::verify(
1305 &vk.vk_ee,
1306 &mut transcript,
1307 &comm_joint,
1308 &r_z,
1309 &eval_joint,
1310 &self.eval_arg,
1311 )?;
1312
1313 Ok(())
1314 }
1315}
1316
1317// provides direct interfaces to call the SNARK implemented in this module