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