Nova/src/spartan/spark/sparse.rs
src/spartan/spark/sparse.rsRaw
1#![allow(clippy::type_complexity)]
2#![allow(clippy::too_many_arguments)]
3#![allow(clippy::needless_range_loop)]
4use crate::{
5 errors::NovaError,
6 spartan::{
7 math::Math,
8 polynomial::{EqPolynomial, MultilinearPolynomial},
9 spark::product::{IdentityPolynomial, ProductArgumentBatched},
10 PolyEvalInstance, PolyEvalWitness, SumcheckProof,
11 },
12 traits::{commitment::CommitmentEngineTrait, Group, TranscriptEngineTrait, TranscriptReprTrait},
13 Commitment, CommitmentKey,
14};
15use ff::Field;
16use rayon::prelude::*;
17use serde::{Deserialize, Serialize};
18
19/// A type that holds a sparse polynomial in dense representation
20#[derive(Clone, Serialize, Deserialize)]
21#[serde(bound = "")]
22pub struct SparsePolynomial<G: Group> {
23 ell: (usize, usize), // number of variables in each dimension
24
25 // dense representation
26 row: Vec<G::Scalar>,
27 col: Vec<G::Scalar>,
28 val: Vec<G::Scalar>,
29
30 // timestamp polynomials
31 row_read_ts: Vec<G::Scalar>,
32 row_audit_ts: Vec<G::Scalar>,
33 col_read_ts: Vec<G::Scalar>,
34 col_audit_ts: Vec<G::Scalar>,
35}
36
37/// A type that holds a commitment to a sparse polynomial
38#[derive(Clone, Serialize, Deserialize)]
39#[serde(bound = "")]
40pub struct SparsePolynomialCommitment<G: Group> {
41 ell: (usize, usize), // number of variables
42 size: usize, // size of the dense representation
43
44 // commitments to the dense representation
45 comm_row: Commitment<G>,
46 comm_col: Commitment<G>,
47 comm_val: Commitment<G>,
48
49 // commitments to the timestamp polynomials
50 comm_row_read_ts: Commitment<G>,
51 comm_row_audit_ts: Commitment<G>,
52 comm_col_read_ts: Commitment<G>,
53 comm_col_audit_ts: Commitment<G>,
54}
55
56impl<G: Group> TranscriptReprTrait<G> for SparsePolynomialCommitment<G> {
57 fn to_transcript_bytes(&self) -> Vec<u8> {
58 [
59 self.comm_row,
60 self.comm_col,
61 self.comm_val,
62 self.comm_row_read_ts,
63 self.comm_row_audit_ts,
64 self.comm_col_read_ts,
65 self.comm_col_audit_ts,
66 ]
67 .as_slice()
68 .to_transcript_bytes()
69 }
70}
71
72impl<G: Group> SparsePolynomial<G> {
73 pub fn new(ell: (usize, usize), M: &[(usize, usize, G::Scalar)]) -> Self {
74 let mut row = M.iter().map(|(r, _, _)| *r).collect::<Vec<usize>>();
75 let mut col = M.iter().map(|(_, c, _)| *c).collect::<Vec<usize>>();
76 let mut val = M.iter().map(|(_, _, v)| *v).collect::<Vec<G::Scalar>>();
77
78 let num_ops = M.len().next_power_of_two();
79 let num_cells_row = ell.0.pow2();
80 let num_cells_col = ell.1.pow2();
81 row.resize(num_ops, 0usize);
82 col.resize(num_ops, 0usize);
83 val.resize(num_ops, G::Scalar::zero());
84
85 // timestamp calculation routine
86 let timestamp_calc =
87 |num_ops: usize, num_cells: usize, addr_trace: &[usize]| -> (Vec<usize>, Vec<usize>) {
88 let mut read_ts = vec![0usize; num_ops];
89 let mut audit_ts = vec![0usize; num_cells];
90
91 assert!(num_ops >= addr_trace.len());
92 for i in 0..addr_trace.len() {
93 let addr = addr_trace[i];
94 assert!(addr < num_cells);
95 let r_ts = audit_ts[addr];
96 read_ts[i] = r_ts;
97
98 let w_ts = r_ts + 1;
99 audit_ts[addr] = w_ts;
100 }
101 (read_ts, audit_ts)
102 };
103
104 // timestamp polynomials for row
105 let (row_read_ts, row_audit_ts) = timestamp_calc(num_ops, num_cells_row, &row);
106 let (col_read_ts, col_audit_ts) = timestamp_calc(num_ops, num_cells_col, &col);
107
108 let to_vec_scalar = |v: &[usize]| -> Vec<G::Scalar> {
109 (0..v.len())
110 .map(|i| G::Scalar::from(v[i] as u64))
111 .collect::<Vec<G::Scalar>>()
112 };
113
114 Self {
115 ell,
116 // dense representation
117 row: to_vec_scalar(&row),
118 col: to_vec_scalar(&col),
119 val,
120
121 // timestamp polynomials
122 row_read_ts: to_vec_scalar(&row_read_ts),
123 row_audit_ts: to_vec_scalar(&row_audit_ts),
124 col_read_ts: to_vec_scalar(&col_read_ts),
125 col_audit_ts: to_vec_scalar(&col_audit_ts),
126 }
127 }
128
129 pub fn commit(&self, ck: &CommitmentKey<G>) -> SparsePolynomialCommitment<G> {
130 let comm_vec: Vec<Commitment<G>> = [
131 &self.row,
132 &self.col,
133 &self.val,
134 &self.row_read_ts,
135 &self.row_audit_ts,
136 &self.col_read_ts,
137 &self.col_audit_ts,
138 ]
139 .par_iter()
140 .map(|v| G::CE::commit(ck, v))
141 .collect();
142
143 SparsePolynomialCommitment {
144 ell: self.ell,
145 size: self.row.len(),
146 comm_row: comm_vec[0],
147 comm_col: comm_vec[1],
148 comm_val: comm_vec[2],
149 comm_row_read_ts: comm_vec[3],
150 comm_row_audit_ts: comm_vec[4],
151 comm_col_read_ts: comm_vec[5],
152 comm_col_audit_ts: comm_vec[6],
153 }
154 }
155
156 pub fn multi_evaluate(
157 M_vec: &[&[(usize, usize, G::Scalar)]],
158 r_x: &[G::Scalar],
159 r_y: &[G::Scalar],
160 ) -> Vec<G::Scalar> {
161 let evaluate_with_table =
162 |M: &[(usize, usize, G::Scalar)], T_x: &[G::Scalar], T_y: &[G::Scalar]| -> G::Scalar {
163 (0..M.len())
164 .collect::<Vec<usize>>()
165 .par_iter()
166 .map(|&i| {
167 let (row, col, val) = M[i];
168 T_x[row] * T_y[col] * val
169 })
170 .reduce(G::Scalar::zero, |acc, x| acc + x)
171 };
172
173 let (T_x, T_y) = rayon::join(
174 || EqPolynomial::new(r_x.to_vec()).evals(),
175 || EqPolynomial::new(r_y.to_vec()).evals(),
176 );
177
178 (0..M_vec.len())
179 .collect::<Vec<usize>>()
180 .par_iter()
181 .map(|&i| evaluate_with_table(M_vec[i], &T_x, &T_y))
182 .collect()
183 }
184
185 fn evaluation_oracles(
186 M: &[(usize, usize, G::Scalar)],
187 r_x: &[G::Scalar],
188 r_y: &[G::Scalar],
189 ) -> (
190 Vec<G::Scalar>,
191 Vec<G::Scalar>,
192 Vec<G::Scalar>,
193 Vec<G::Scalar>,
194 ) {
195 let evaluation_oracles_with_table = |M: &[(usize, usize, G::Scalar)],
196 T_x: &[G::Scalar],
197 T_y: &[G::Scalar]|
198 -> (Vec<G::Scalar>, Vec<G::Scalar>) {
199 (0..M.len())
200 .collect::<Vec<usize>>()
201 .par_iter()
202 .map(|&i| {
203 let (row, col, _val) = M[i];
204 (T_x[row], T_y[col])
205 })
206 .collect::<Vec<(G::Scalar, G::Scalar)>>()
207 .into_par_iter()
208 .unzip()
209 };
210
211 let (T_x, T_y) = rayon::join(
212 || EqPolynomial::new(r_x.to_vec()).evals(),
213 || EqPolynomial::new(r_y.to_vec()).evals(),
214 );
215
216 let (mut E_row, mut E_col) = evaluation_oracles_with_table(M, &T_x, &T_y);
217
218 // resize the returned vectors
219 E_row.resize(M.len().next_power_of_two(), T_x[0]); // we place T_x[0] since resized row is appended with 0s
220 E_col.resize(M.len().next_power_of_two(), T_y[0]);
221 (E_row, E_col, T_x, T_y)
222 }
223}
224
225#[derive(Clone, Debug, Serialize, Deserialize)]
226#[serde(bound = "")]
227pub struct SparseEvaluationArgument<G: Group> {
228 // claimed evaluation
229 eval: G::Scalar,
230
231 // oracles
232 comm_E_row: Commitment<G>,
233 comm_E_col: Commitment<G>,
234
235 // proof of correct evaluation wrt oracles
236 sc_proof_eval: SumcheckProof<G>,
237 eval_E_row: G::Scalar,
238 eval_E_col: G::Scalar,
239 eval_val: G::Scalar,
240
241 // proof that E_row is well-formed
242 eval_init_row: G::Scalar,
243 eval_read_row: G::Scalar,
244 eval_write_row: G::Scalar,
245 eval_audit_row: G::Scalar,
246 eval_init_col: G::Scalar,
247 eval_read_col: G::Scalar,
248 eval_write_col: G::Scalar,
249 eval_audit_col: G::Scalar,
250 sc_prod_init_audit_row: ProductArgumentBatched<G>,
251 sc_prod_read_write_row_col: ProductArgumentBatched<G>,
252 sc_prod_init_audit_col: ProductArgumentBatched<G>,
253 eval_row: G::Scalar,
254 eval_row_read_ts: G::Scalar,
255 eval_E_row2: G::Scalar,
256 eval_row_audit_ts: G::Scalar,
257 eval_col: G::Scalar,
258 eval_col_read_ts: G::Scalar,
259 eval_E_col2: G::Scalar,
260 eval_col_audit_ts: G::Scalar,
261}
262
263impl<G: Group> SparseEvaluationArgument<G> {
264 pub fn prove(
265 ck: &CommitmentKey<G>,
266 poly: &SparsePolynomial<G>,
267 sparse: &[(usize, usize, G::Scalar)],
268 comm: &SparsePolynomialCommitment<G>,
269 r: &(&[G::Scalar], &[G::Scalar]),
270 transcript: &mut G::TE,
271 ) -> Result<(Self, Vec<(PolyEvalWitness<G>, PolyEvalInstance<G>)>), NovaError> {
272 let (r_x, r_y) = r;
273 let eval = SparsePolynomial::<G>::multi_evaluate(&[sparse], r_x, r_y)[0];
274
275 // keep track of evaluation claims
276 let mut w_u_vec: Vec<(PolyEvalWitness<G>, PolyEvalInstance<G>)> = Vec::new();
277
278 // compute oracles to prove the correctness of `eval`
279 let (E_row, E_col, T_x, T_y) = SparsePolynomial::<G>::evaluation_oracles(sparse, r_x, r_y);
280 let val = poly.val.clone();
281
282 // commit to the two oracles
283 let comm_E_row = G::CE::commit(ck, &E_row);
284 let comm_E_col = G::CE::commit(ck, &E_col);
285
286 // absorb the commitments and the claimed evaluation
287 transcript.absorb(b"E", &vec![comm_E_row, comm_E_col].as_slice());
288 transcript.absorb(b"e", &eval);
289
290 let comb_func_eval = |poly_A_comp: &G::Scalar,
291 poly_B_comp: &G::Scalar,
292 poly_C_comp: &G::Scalar|
293 -> G::Scalar { *poly_A_comp * *poly_B_comp * *poly_C_comp };
294 let (sc_proof_eval, r_eval, claims_eval) = SumcheckProof::<G>::prove_cubic(
295 &eval,
296 E_row.len().log_2(), // number of rounds
297 &mut MultilinearPolynomial::new(E_row.clone()),
298 &mut MultilinearPolynomial::new(E_col.clone()),
299 &mut MultilinearPolynomial::new(val.clone()),
300 comb_func_eval,
301 transcript,
302 )?;
303
304 // prove evaluations of E_row, E_col and val at r_eval
305 let rho = transcript.squeeze(b"r")?;
306 let comm_joint = comm_E_row + comm_E_col * rho + comm.comm_val * rho * rho;
307 let eval_joint = claims_eval[0] + rho * claims_eval[1] + rho * rho * claims_eval[2];
308 let poly_eval = E_row
309 .iter()
310 .zip(E_col.iter())
311 .zip(val.iter())
312 .map(|((a, b), c)| *a + rho * *b + rho * rho * *c)
313 .collect::<Vec<G::Scalar>>();
314
315 // add the claim to prove for later
316 w_u_vec.push((
317 PolyEvalWitness { p: poly_eval },
318 PolyEvalInstance {
319 c: comm_joint,
320 x: r_eval,
321 e: eval_joint,
322 },
323 ));
324
325 // we now need to prove that E_row and E_col are well-formed
326 // we use memory checking: H(INIT) * H(WS) =? H(RS) * H(FINAL)
327 let gamma_1 = transcript.squeeze(b"g1")?;
328 let gamma_2 = transcript.squeeze(b"g2")?;
329
330 let gamma_1_sqr = gamma_1 * gamma_1;
331 let hash_func = |addr: &G::Scalar, val: &G::Scalar, ts: &G::Scalar| -> G::Scalar {
332 (*ts * gamma_1_sqr + *val * gamma_1 + *addr) - gamma_2
333 };
334
335 let init_row = (0..T_x.len())
336 .map(|i| hash_func(&G::Scalar::from(i as u64), &T_x[i], &G::Scalar::zero()))
337 .collect::<Vec<G::Scalar>>();
338 let read_row = (0..E_row.len())
339 .map(|i| hash_func(&poly.row[i], &E_row[i], &poly.row_read_ts[i]))
340 .collect::<Vec<G::Scalar>>();
341 let write_row = (0..E_row.len())
342 .map(|i| {
343 hash_func(
344 &poly.row[i],
345 &E_row[i],
346 &(poly.row_read_ts[i] + G::Scalar::one()),
347 )
348 })
349 .collect::<Vec<G::Scalar>>();
350 let audit_row = (0..T_x.len())
351 .map(|i| hash_func(&G::Scalar::from(i as u64), &T_x[i], &poly.row_audit_ts[i]))
352 .collect::<Vec<G::Scalar>>();
353 let init_col = (0..T_y.len())
354 .map(|i| hash_func(&G::Scalar::from(i as u64), &T_y[i], &G::Scalar::zero()))
355 .collect::<Vec<G::Scalar>>();
356 let read_col = (0..E_col.len())
357 .map(|i| hash_func(&poly.col[i], &E_col[i], &poly.col_read_ts[i]))
358 .collect::<Vec<G::Scalar>>();
359 let write_col = (0..E_col.len())
360 .map(|i| {
361 hash_func(
362 &poly.col[i],
363 &E_col[i],
364 &(poly.col_read_ts[i] + G::Scalar::one()),
365 )
366 })
367 .collect::<Vec<G::Scalar>>();
368 let audit_col = (0..T_y.len())
369 .map(|i| hash_func(&G::Scalar::from(i as u64), &T_y[i], &poly.col_audit_ts[i]))
370 .collect::<Vec<G::Scalar>>();
371
372 let (sc_prod_init_audit_row, eval_init_audit_row, r_init_audit_row) =
373 ProductArgumentBatched::prove(
374 &[
375 &MultilinearPolynomial::new(init_row),
376 &MultilinearPolynomial::new(audit_row),
377 ],
378 transcript,
379 )?;
380
381 assert_eq!(init_col.len(), audit_col.len());
382 let (sc_prod_init_audit_col, eval_init_audit_col, r_init_audit_col) =
383 ProductArgumentBatched::prove(
384 &[
385 &MultilinearPolynomial::new(init_col),
386 &MultilinearPolynomial::new(audit_col),
387 ],
388 transcript,
389 )?;
390
391 assert_eq!(read_row.len(), write_row.len());
392 assert_eq!(read_row.len(), read_col.len());
393 assert_eq!(read_row.len(), write_col.len());
394
395 let (sc_prod_read_write_row_col, eval_read_write_row_col, r_read_write_row_col) =
396 ProductArgumentBatched::prove(
397 &[
398 &MultilinearPolynomial::new(read_row),
399 &MultilinearPolynomial::new(write_row),
400 &MultilinearPolynomial::new(read_col),
401 &MultilinearPolynomial::new(write_col),
402 ],
403 transcript,
404 )?;
405
406 // row-related claims of polynomial evaluations to aid the final check of the sum-check
407 let eval_row = MultilinearPolynomial::evaluate_with(&poly.row, &r_read_write_row_col);
408 let eval_row_read_ts =
409 MultilinearPolynomial::evaluate_with(&poly.row_read_ts, &r_read_write_row_col);
410 let eval_E_row2 = MultilinearPolynomial::evaluate_with(&E_row, &r_read_write_row_col);
411 let eval_row_audit_ts =
412 MultilinearPolynomial::evaluate_with(&poly.row_audit_ts, &r_init_audit_row);
413
414 // col-related claims of polynomial evaluations to aid the final check of the sum-check
415 let eval_col = MultilinearPolynomial::evaluate_with(&poly.col, &r_read_write_row_col);
416 let eval_col_read_ts =
417 MultilinearPolynomial::evaluate_with(&poly.col_read_ts, &r_read_write_row_col);
418 let eval_E_col2 = MultilinearPolynomial::evaluate_with(&E_col, &r_read_write_row_col);
419 let eval_col_audit_ts =
420 MultilinearPolynomial::evaluate_with(&poly.col_audit_ts, &r_init_audit_col);
421
422 // we can batch prove the first three claims
423 transcript.absorb(
424 b"e",
425 &[
426 eval_row,
427 eval_row_read_ts,
428 eval_E_row2,
429 eval_col,
430 eval_col_read_ts,
431 eval_E_col2,
432 ]
433 .as_slice(),
434 );
435 let c = transcript.squeeze(b"c")?;
436 let eval_joint = eval_row
437 + c * eval_row_read_ts
438 + c * c * eval_E_row2
439 + c * c * c * eval_col
440 + c * c * c * c * eval_col_read_ts
441 + c * c * c * c * c * eval_E_col2;
442 let comm_joint = comm.comm_row
443 + comm.comm_row_read_ts * c
444 + comm_E_row * c * c
445 + comm.comm_col * c * c * c
446 + comm.comm_col_read_ts * c * c * c * c
447 + comm_E_col * c * c * c * c * c;
448 let poly_joint = poly
449 .row
450 .iter()
451 .zip(poly.row_read_ts.iter())
452 .zip(E_row.into_iter())
453 .zip(poly.col.iter())
454 .zip(poly.col_read_ts.iter())
455 .zip(E_col.into_iter())
456 .map(|(((((x, y), z), m), n), q)| {
457 *x + c * y + c * c * z + c * c * c * m + c * c * c * c * n + c * c * c * c * c * q
458 })
459 .collect::<Vec<_>>();
460
461 // add the claim to prove for later
462 w_u_vec.push((
463 PolyEvalWitness { p: poly_joint },
464 PolyEvalInstance {
465 c: comm_joint,
466 x: r_read_write_row_col,
467 e: eval_joint,
468 },
469 ));
470
471 transcript.absorb(b"a", &eval_row_audit_ts); // add evaluation to transcript, commitment is already in
472 w_u_vec.push((
473 PolyEvalWitness {
474 p: poly.row_audit_ts.clone(),
475 },
476 PolyEvalInstance {
477 c: comm.comm_row_audit_ts,
478 x: r_init_audit_row,
479 e: eval_row_audit_ts,
480 },
481 ));
482
483 transcript.absorb(b"a", &eval_col_audit_ts); // add evaluation to transcript, commitment is already in
484 w_u_vec.push((
485 PolyEvalWitness {
486 p: poly.col_audit_ts.clone(),
487 },
488 PolyEvalInstance {
489 c: comm.comm_col_audit_ts,
490 x: r_init_audit_col,
491 e: eval_col_audit_ts,
492 },
493 ));
494
495 let eval_arg = Self {
496 // claimed evaluation
497 eval,
498
499 // oracles
500 comm_E_row,
501 comm_E_col,
502
503 // proof of correct evaluation wrt oracles
504 sc_proof_eval,
505 eval_E_row: claims_eval[0],
506 eval_E_col: claims_eval[1],
507 eval_val: claims_eval[2],
508
509 // proof that E_row and E_row are well-formed
510 eval_init_row: eval_init_audit_row[0],
511 eval_read_row: eval_read_write_row_col[0],
512 eval_write_row: eval_read_write_row_col[1],
513 eval_audit_row: eval_init_audit_row[1],
514 eval_init_col: eval_init_audit_col[0],
515 eval_read_col: eval_read_write_row_col[2],
516 eval_write_col: eval_read_write_row_col[3],
517 eval_audit_col: eval_init_audit_col[1],
518 sc_prod_init_audit_row,
519 sc_prod_read_write_row_col,
520 sc_prod_init_audit_col,
521 eval_row,
522 eval_row_read_ts,
523 eval_E_row2,
524 eval_row_audit_ts,
525 eval_col,
526 eval_col_read_ts,
527 eval_E_col2,
528 eval_col_audit_ts,
529 };
530
531 Ok((eval_arg, w_u_vec))
532 }
533
534 pub fn verify(
535 &self,
536 comm: &SparsePolynomialCommitment<G>,
537 r: &(&[G::Scalar], &[G::Scalar]),
538 transcript: &mut G::TE,
539 ) -> Result<(G::Scalar, Vec<PolyEvalInstance<G>>), NovaError> {
540 let (r_x, r_y) = r;
541
542 // keep track of evaluation claims
543 let mut u_vec: Vec<PolyEvalInstance<G>> = Vec::new();
544
545 // append the transcript and scalar
546 transcript.absorb(b"E", &vec![self.comm_E_row, self.comm_E_col].as_slice());
547 transcript.absorb(b"e", &self.eval);
548
549 // (1) verify the correct evaluation of sparse polynomial
550 let (claim_eval_final, r_eval) = self.sc_proof_eval.verify(
551 self.eval,
552 comm.size.next_power_of_two().log_2(),
553 3,
554 transcript,
555 )?;
556 // verify the last step of the sum-check
557 if claim_eval_final != self.eval_E_row * self.eval_E_col * self.eval_val {
558 return Err(NovaError::InvalidSumcheckProof);
559 }
560
561 // prove evaluations of E_row, E_col and val at r_eval
562 let rho = transcript.squeeze(b"r")?;
563 let comm_joint = self.comm_E_row + self.comm_E_col * rho + comm.comm_val * rho * rho;
564 let eval_joint = self.eval_E_row + rho * self.eval_E_col + rho * rho * self.eval_val;
565
566 // add the claim to prove for later
567 u_vec.push(PolyEvalInstance {
568 c: comm_joint,
569 x: r_eval,
570 e: eval_joint,
571 });
572
573 // (2) verify if E_row and E_col are well formed
574 let gamma_1 = transcript.squeeze(b"g1")?;
575 let gamma_2 = transcript.squeeze(b"g2")?;
576
577 // hash function
578 let gamma_1_sqr = gamma_1 * gamma_1;
579 let hash_func = |addr: &G::Scalar, val: &G::Scalar, ts: &G::Scalar| -> G::Scalar {
580 (*ts * gamma_1_sqr + *val * gamma_1 + *addr) - gamma_2
581 };
582
583 // check the required multiset relationship
584 // row
585 if self.eval_init_row * self.eval_write_row != self.eval_read_row * self.eval_audit_row {
586 return Err(NovaError::InvalidMultisetProof);
587 }
588 // col
589 if self.eval_init_col * self.eval_write_col != self.eval_read_col * self.eval_audit_col {
590 return Err(NovaError::InvalidMultisetProof);
591 }
592
593 // verify the product proofs
594 let (claim_init_audit_row, r_init_audit_row) = self.sc_prod_init_audit_row.verify(
595 &[self.eval_init_row, self.eval_audit_row],
596 comm.ell.0.pow2(),
597 transcript,
598 )?;
599 let (claim_init_audit_col, r_init_audit_col) = self.sc_prod_init_audit_col.verify(
600 &[self.eval_init_col, self.eval_audit_col],
601 comm.ell.1.pow2(),
602 transcript,
603 )?;
604 let (claim_read_write_row_col, r_read_write_row_col) = self.sc_prod_read_write_row_col.verify(
605 &[
606 self.eval_read_row,
607 self.eval_write_row,
608 self.eval_read_col,
609 self.eval_write_col,
610 ],
611 comm.size,
612 transcript,
613 )?;
614
615 // finish the final step of the three sum-checks
616 let (claim_init_expected_row, claim_audit_expected_row) = {
617 let addr = IdentityPolynomial::new(r_init_audit_row.len()).evaluate(&r_init_audit_row);
618 let val = EqPolynomial::new(r_x.to_vec()).evaluate(&r_init_audit_row);
619
620 (
621 hash_func(&addr, &val, &G::Scalar::zero()),
622 hash_func(&addr, &val, &self.eval_row_audit_ts),
623 )
624 };
625
626 let (claim_read_expected_row, claim_write_expected_row) = {
627 (
628 hash_func(&self.eval_row, &self.eval_E_row2, &self.eval_row_read_ts),
629 hash_func(
630 &self.eval_row,
631 &self.eval_E_row2,
632 &(self.eval_row_read_ts + G::Scalar::one()),
633 ),
634 )
635 };
636
637 // multiset check for the row
638 if claim_init_expected_row != claim_init_audit_row[0]
639 || claim_audit_expected_row != claim_init_audit_row[1]
640 || claim_read_expected_row != claim_read_write_row_col[0]
641 || claim_write_expected_row != claim_read_write_row_col[1]
642 {
643 return Err(NovaError::InvalidSumcheckProof);
644 }
645
646 let (claim_init_expected_col, claim_audit_expected_col) = {
647 let addr = IdentityPolynomial::new(r_init_audit_col.len()).evaluate(&r_init_audit_col);
648 let val = EqPolynomial::new(r_y.to_vec()).evaluate(&r_init_audit_col);
649
650 (
651 hash_func(&addr, &val, &G::Scalar::zero()),
652 hash_func(&addr, &val, &self.eval_col_audit_ts),
653 )
654 };
655
656 let (claim_read_expected_col, claim_write_expected_col) = {
657 (
658 hash_func(&self.eval_col, &self.eval_E_col2, &self.eval_col_read_ts),
659 hash_func(
660 &self.eval_col,
661 &self.eval_E_col2,
662 &(self.eval_col_read_ts + G::Scalar::one()),
663 ),
664 )
665 };
666
667 // multiset check for the col
668 if claim_init_expected_col != claim_init_audit_col[0]
669 || claim_audit_expected_col != claim_init_audit_col[1]
670 || claim_read_expected_col != claim_read_write_row_col[2]
671 || claim_write_expected_col != claim_read_write_row_col[3]
672 {
673 return Err(NovaError::InvalidSumcheckProof);
674 }
675
676 transcript.absorb(
677 b"e",
678 &[
679 self.eval_row,
680 self.eval_row_read_ts,
681 self.eval_E_row2,
682 self.eval_col,
683 self.eval_col_read_ts,
684 self.eval_E_col2,
685 ]
686 .as_slice(),
687 );
688 let c = transcript.squeeze(b"c")?;
689 let eval_joint = self.eval_row
690 + c * self.eval_row_read_ts
691 + c * c * self.eval_E_row2
692 + c * c * c * self.eval_col
693 + c * c * c * c * self.eval_col_read_ts
694 + c * c * c * c * c * self.eval_E_col2;
695 let comm_joint = comm.comm_row
696 + comm.comm_row_read_ts * c
697 + self.comm_E_row * c * c
698 + comm.comm_col * c * c * c
699 + comm.comm_col_read_ts * c * c * c * c
700 + self.comm_E_col * c * c * c * c * c;
701
702 u_vec.push(PolyEvalInstance {
703 c: comm_joint,
704 x: r_read_write_row_col,
705 e: eval_joint,
706 });
707
708 transcript.absorb(b"a", &self.eval_row_audit_ts); // add evaluation to transcript, commitment is already in
709 u_vec.push(PolyEvalInstance {
710 c: comm.comm_row_audit_ts,
711 x: r_init_audit_row,
712 e: self.eval_row_audit_ts,
713 });
714
715 transcript.absorb(b"a", &self.eval_col_audit_ts); // add evaluation to transcript, commitment is already in
716 u_vec.push(PolyEvalInstance {
717 c: comm.comm_col_audit_ts,
718 x: r_init_audit_col,
719 e: self.eval_col_audit_ts,
720 });
721
722 Ok((self.eval, u_vec))
723 }
724}