testudo/src/sparse_mlpoly.rs
src/sparse_mlpoly.rsRaw
1#![allow(clippy::type_complexity)]
2#![allow(clippy::too_many_arguments)]
3#![allow(clippy::needless_range_loop)]
4use super::dense_mlpoly::DensePolynomial;
5use super::dense_mlpoly::{
6 EqPolynomial, IdentityPolynomial, PolyCommitment, PolyCommitmentGens, PolyEvalProof,
7};
8use super::errors::ProofVerifyError;
9use super::math::Math;
10use super::product_tree::{DotProductCircuit, ProductCircuit, ProductCircuitEvalProofBatched};
11use super::timer::Timer;
12use crate::poseidon_transcript::{PoseidonTranscript, TranscriptWriter};
13use crate::transcript::Transcript;
14use ark_crypto_primitives::sponge::Absorb;
15use ark_ec::pairing::Pairing;
16use ark_ec::CurveGroup;
17use ark_ff::PrimeField;
18use ark_ff::{Field, One, Zero};
19use ark_serialize::*;
20use core::cmp::Ordering;
21
22#[derive(Debug, CanonicalSerialize, CanonicalDeserialize, Clone)]
23// Each SparseMatEntry is a tuple (row, col, val) representing a non-zero value
24// in an R1CS matrix.
25pub struct SparseMatEntry<F: PrimeField> {
26 row: usize,
27 col: usize,
28 val: F,
29}
30
31impl<F: PrimeField> SparseMatEntry<F> {
32 pub fn new(row: usize, col: usize, val: F) -> Self {
33 SparseMatEntry { row, col, val }
34 }
35}
36
37#[derive(Debug, CanonicalSerialize, CanonicalDeserialize, Clone)]
38// The sparse multilinearrepresentation of an R1CS matrix of size x*y
39pub struct SparseMatPolynomial<F: PrimeField> {
40 num_vars_x: usize,
41 num_vars_y: usize,
42 // The non-zero entries in the matrix, represented by the tuple (row, col,val)
43 M: Vec<SparseMatEntry<F>>,
44}
45
46pub struct Derefs<F: PrimeField> {
47 row_ops_val: Vec<DensePolynomial<F>>,
48 col_ops_val: Vec<DensePolynomial<F>>,
49 comb: DensePolynomial<F>,
50}
51
52#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
53pub struct DerefsCommitment<G: CurveGroup> {
54 comm_ops_val: PolyCommitment<G>,
55}
56
57impl<F: PrimeField> Derefs<F> {
58 pub fn new(row_ops_val: Vec<DensePolynomial<F>>, col_ops_val: Vec<DensePolynomial<F>>) -> Self {
59 assert_eq!(row_ops_val.len(), col_ops_val.len());
60
61 let derefs = {
62 // combine all polynomials into a single polynomial (used below to produce a single commitment)
63 let comb = DensePolynomial::merge(row_ops_val.iter().chain(col_ops_val.iter()));
64
65 Derefs {
66 row_ops_val,
67 col_ops_val,
68 comb,
69 }
70 };
71
72 derefs
73 }
74
75 pub fn commit<E>(&self, gens: &PolyCommitmentGens<E>) -> DerefsCommitment<E::G1>
76 where
77 E: Pairing<ScalarField = F>,
78 {
79 let (comm_ops_val, _blinds) = self.comb.commit(gens, false);
80 DerefsCommitment { comm_ops_val }
81 }
82}
83
84#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
85pub struct DerefsEvalProof<E: Pairing> {
86 proof_derefs: PolyEvalProof<E>,
87}
88
89impl<E> DerefsEvalProof<E>
90where
91 E: Pairing,
92 E::ScalarField: Absorb,
93{
94 fn prove_single(
95 joint_poly: &DensePolynomial<E::ScalarField>,
96 r: &[E::ScalarField],
97 evals: Vec<E::ScalarField>,
98 gens: &PolyCommitmentGens<E>,
99 transcript: &mut PoseidonTranscript<E::ScalarField>,
100 ) -> PolyEvalProof<E> {
101 assert_eq!(joint_poly.get_num_vars(), r.len() + evals.len().log_2());
102
103 // append the claimed evaluations to transcript
104 // evals.append_to_transcript(b"evals_ops_val", transcript);
105 transcript.append_scalar_vector(b"", &evals);
106
107 // n-to-1 reduction
108 let (r_joint, eval_joint) = {
109 let challenges = transcript.challenge_scalar_vec(b"", evals.len().log_2());
110 let mut poly_evals = DensePolynomial::new(evals);
111 for i in (0..challenges.len()).rev() {
112 poly_evals.bound_poly_var_bot(&challenges[i]);
113 }
114 assert_eq!(poly_evals.len(), 1);
115 let joint_claim_eval = poly_evals[0];
116 let mut r_joint = challenges;
117 r_joint.extend(r);
118
119 debug_assert_eq!(joint_poly.evaluate(&r_joint), joint_claim_eval);
120 (r_joint, joint_claim_eval)
121 };
122 // decommit the joint polynomial at r_joint
123 transcript.append_scalar(b"", &eval_joint);
124 let (proof_derefs, _comm_derefs_eval) = PolyEvalProof::prove(
125 joint_poly,
126 None,
127 &r_joint,
128 &eval_joint,
129 None,
130 gens,
131 transcript,
132 );
133
134 proof_derefs
135 }
136
137 // evalues both polynomials at r and produces a joint proof of opening
138 pub fn prove(
139 derefs: &Derefs<E::ScalarField>,
140 eval_row_ops_val_vec: &[E::ScalarField],
141 eval_col_ops_val_vec: &[E::ScalarField],
142 r: &[E::ScalarField],
143 gens: &PolyCommitmentGens<E>,
144 transcript: &mut PoseidonTranscript<E::ScalarField>,
145 ) -> Self {
146 // transcript.append_protocol_name(DerefsEvalProof::protocol_name());
147
148 let evals = {
149 let mut evals = eval_row_ops_val_vec.to_owned();
150 evals.extend(eval_col_ops_val_vec);
151 evals.resize(evals.len().next_power_of_two(), E::ScalarField::zero());
152 evals
153 };
154 let proof_derefs = DerefsEvalProof::prove_single(&derefs.comb, r, evals, gens, transcript);
155
156 DerefsEvalProof { proof_derefs }
157 }
158
159 fn verify_single(
160 proof: &PolyEvalProof<E>,
161 comm: &PolyCommitment<E::G1>,
162 r: &[E::ScalarField],
163 evals: Vec<E::ScalarField>,
164 gens: &PolyCommitmentGens<E>,
165 transcript: &mut PoseidonTranscript<E::ScalarField>,
166 ) -> Result<(), ProofVerifyError> {
167 // append the claimed evaluations to transcript
168 // evals.append_to_transcript(b"evals_ops_val", transcript);
169 transcript.append_scalar_vector(b"", &evals);
170
171 // n-to-1 reduction
172 let challenges = transcript.challenge_scalar_vec(b"", evals.len().log_2());
173 let mut poly_evals = DensePolynomial::new(evals);
174 for i in (0..challenges.len()).rev() {
175 poly_evals.bound_poly_var_bot(&challenges[i]);
176 }
177 assert_eq!(poly_evals.len(), 1);
178 let joint_claim_eval = poly_evals[0];
179 let mut r_joint = challenges;
180 r_joint.extend(r);
181
182 // decommit the joint polynomial at r_joint
183 // joint_claim_eval.append_to_transcript(b"joint_claim_eval", transcript);
184 transcript.append_scalar(b"", &joint_claim_eval);
185
186 proof.verify_plain(gens, transcript, &r_joint, &joint_claim_eval, comm)
187 }
188
189 // verify evaluations of both polynomials at r
190 pub fn verify(
191 &self,
192 r: &[E::ScalarField],
193 eval_row_ops_val_vec: &[E::ScalarField],
194 eval_col_ops_val_vec: &[E::ScalarField],
195 gens: &PolyCommitmentGens<E>,
196 comm: &DerefsCommitment<E::G1>,
197 transcript: &mut PoseidonTranscript<E::ScalarField>,
198 ) -> Result<(), ProofVerifyError> {
199 // transcript.append_protocol_name(DerefsEvalProof::protocol_name());
200 let mut evals = eval_row_ops_val_vec.to_owned();
201 evals.extend(eval_col_ops_val_vec);
202 evals.resize(evals.len().next_power_of_two(), E::ScalarField::zero());
203
204 DerefsEvalProof::verify_single(
205 &self.proof_derefs,
206 &comm.comm_ops_val,
207 r,
208 evals,
209 gens,
210 transcript,
211 )
212 }
213}
214
215impl<G: CurveGroup> TranscriptWriter<G::ScalarField> for DerefsCommitment<G> {
216 fn write_to_transcript(&self, transcript: &mut PoseidonTranscript<G::ScalarField>) {
217 self.comm_ops_val.write_to_transcript(transcript);
218 }
219}
220struct AddrTimestamps<F: PrimeField> {
221 ops_addr_usize: Vec<Vec<usize>>,
222 ops_addr: Vec<DensePolynomial<F>>,
223 read_ts: Vec<DensePolynomial<F>>,
224 audit_ts: DensePolynomial<F>,
225}
226
227impl<F: PrimeField> AddrTimestamps<F> {
228 pub fn new(num_cells: usize, num_ops: usize, ops_addr: Vec<Vec<usize>>) -> Self {
229 for item in ops_addr.iter() {
230 assert_eq!(item.len(), num_ops);
231 }
232
233 let mut audit_ts = vec![0usize; num_cells];
234 let mut ops_addr_vec: Vec<DensePolynomial<F>> = Vec::new();
235 let mut read_ts_vec: Vec<DensePolynomial<F>> = Vec::new();
236 for ops_addr_inst in ops_addr.iter() {
237 let mut read_ts = vec![0usize; num_ops];
238
239 // since read timestamps are trustworthy, we can simply increment the r-ts to obtain a w-ts
240 // this is sufficient to ensure that the write-set, consisting of (addr, val, ts) tuples, is a set
241 for i in 0..num_ops {
242 let addr = ops_addr_inst[i];
243 assert!(addr < num_cells);
244 let r_ts = audit_ts[addr];
245 read_ts[i] = r_ts;
246
247 let w_ts = r_ts + 1;
248 audit_ts[addr] = w_ts;
249 }
250
251 ops_addr_vec.push(DensePolynomial::from_usize(ops_addr_inst));
252 read_ts_vec.push(DensePolynomial::from_usize(&read_ts));
253 }
254
255 AddrTimestamps {
256 ops_addr: ops_addr_vec,
257 ops_addr_usize: ops_addr,
258 read_ts: read_ts_vec,
259 audit_ts: DensePolynomial::from_usize(&audit_ts),
260 }
261 }
262
263 fn deref_mem(addr: &[usize], mem_val: &[F]) -> DensePolynomial<F> {
264 DensePolynomial::new(
265 (0..addr.len())
266 .map(|i| {
267 let a = addr[i];
268 mem_val[a]
269 })
270 .collect::<Vec<F>>(),
271 )
272 }
273
274 pub fn deref(&self, mem_val: &[F]) -> Vec<DensePolynomial<F>> {
275 (0..self.ops_addr.len())
276 .map(|i| AddrTimestamps::deref_mem(&self.ops_addr_usize[i], mem_val))
277 .collect::<Vec<DensePolynomial<F>>>()
278 }
279}
280
281pub struct MultiSparseMatPolynomialAsDense<F: PrimeField> {
282 batch_size: usize,
283 val: Vec<DensePolynomial<F>>,
284 row: AddrTimestamps<F>,
285 col: AddrTimestamps<F>,
286 comb_ops: DensePolynomial<F>,
287 comb_mem: DensePolynomial<F>,
288}
289
290pub struct SparseMatPolyCommitmentGens<E: Pairing> {
291 gens_ops: PolyCommitmentGens<E>,
292 gens_mem: PolyCommitmentGens<E>,
293 gens_derefs: PolyCommitmentGens<E>,
294}
295
296impl<E: Pairing> SparseMatPolyCommitmentGens<E> {
297 pub fn setup(
298 label: &'static [u8],
299 num_vars_x: usize,
300 num_vars_y: usize,
301 num_nz_entries: usize,
302 batch_size: usize,
303 ) -> Self {
304 let num_vars_ops =
305 num_nz_entries.next_power_of_two().log_2() + (batch_size * 5).next_power_of_two().log_2();
306 let num_vars_mem = if num_vars_x > num_vars_y {
307 num_vars_x
308 } else {
309 num_vars_y
310 } + 1;
311 let num_vars_derefs =
312 num_nz_entries.next_power_of_two().log_2() + (batch_size * 2).next_power_of_two().log_2();
313
314 let gens_ops = PolyCommitmentGens::setup(num_vars_ops, label);
315 let gens_mem = PolyCommitmentGens::setup(num_vars_mem, label);
316 let gens_derefs = PolyCommitmentGens::setup(num_vars_derefs, label);
317 SparseMatPolyCommitmentGens {
318 gens_ops,
319 gens_mem,
320 gens_derefs,
321 }
322 }
323}
324
325#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
326pub struct SparseMatPolyCommitment<G: CurveGroup> {
327 batch_size: usize,
328 num_ops: usize,
329 num_mem_cells: usize,
330 comm_comb_ops: PolyCommitment<G>,
331 comm_comb_mem: PolyCommitment<G>,
332}
333
334impl<G: CurveGroup> TranscriptWriter<G::ScalarField> for SparseMatPolyCommitment<G> {
335 fn write_to_transcript(&self, transcript: &mut PoseidonTranscript<G::ScalarField>) {
336 transcript.append_u64(b"", self.batch_size as u64);
337 transcript.append_u64(b"", self.num_ops as u64);
338 transcript.append_u64(b"", self.num_mem_cells as u64);
339 self.comm_comb_ops.write_to_transcript(transcript);
340 self.comm_comb_mem.write_to_transcript(transcript);
341 }
342}
343
344impl<F: PrimeField> SparseMatPolynomial<F> {
345 pub fn new(num_vars_x: usize, num_vars_y: usize, M: Vec<SparseMatEntry<F>>) -> Self {
346 SparseMatPolynomial {
347 num_vars_x,
348 num_vars_y,
349 M,
350 }
351 }
352
353 // get the number of non_zero entries in a sparse R1CS matrix
354 pub fn get_num_nz_entries(&self) -> usize {
355 self.M.len().next_power_of_two()
356 }
357
358 fn sparse_to_dense_vecs(&self, N: usize) -> (Vec<usize>, Vec<usize>, Vec<F>) {
359 assert!(N >= self.get_num_nz_entries());
360 let mut ops_row: Vec<usize> = vec![0; N];
361 let mut ops_col: Vec<usize> = vec![0; N];
362 let mut val: Vec<F> = vec![F::zero(); N];
363
364 for i in 0..self.M.len() {
365 ops_row[i] = self.M[i].row;
366 ops_col[i] = self.M[i].col;
367 val[i] = self.M[i].val;
368 }
369 (ops_row, ops_col, val)
370 }
371
372 // Produce the dense representation of sparse matrices A, B and C.
373 fn multi_sparse_to_dense_rep(
374 sparse_polys: &[&SparseMatPolynomial<F>],
375 ) -> MultiSparseMatPolynomialAsDense<F> {
376 assert!(!sparse_polys.is_empty());
377 for i in 1..sparse_polys.len() {
378 assert_eq!(sparse_polys[i].num_vars_x, sparse_polys[0].num_vars_x);
379 assert_eq!(sparse_polys[i].num_vars_y, sparse_polys[0].num_vars_y);
380 }
381
382 let N = (0..sparse_polys.len())
383 .map(|i| sparse_polys[i].get_num_nz_entries())
384 .max()
385 .unwrap()
386 .next_power_of_two();
387
388 let mut ops_row_vec: Vec<Vec<usize>> = Vec::new();
389 let mut ops_col_vec: Vec<Vec<usize>> = Vec::new();
390 let mut val_vec: Vec<DensePolynomial<F>> = Vec::new();
391 for poly in sparse_polys {
392 let (ops_row, ops_col, val) = poly.sparse_to_dense_vecs(N);
393 // aggregate all the row and columns that contain non-zero values in the
394 // three matrices
395 ops_row_vec.push(ops_row);
396 ops_col_vec.push(ops_col);
397 // create dense polynomials, in Lagrange representation, for the non-zero
398 // values of each matrix
399 val_vec.push(DensePolynomial::new(val));
400 }
401
402 // Note: everything else from
403
404 let any_poly = &sparse_polys[0];
405
406 let num_mem_cells = if any_poly.num_vars_x > any_poly.num_vars_y {
407 any_poly.num_vars_x.pow2()
408 } else {
409 any_poly.num_vars_y.pow2()
410 };
411
412 let row = AddrTimestamps::new(num_mem_cells, N, ops_row_vec);
413 let col = AddrTimestamps::new(num_mem_cells, N, ops_col_vec);
414
415 // combine polynomials into a single polynomial for commitment purposes
416 // this is done because the commitment used has a public setup
417 let comb_ops = DensePolynomial::merge(
418 row
419 .ops_addr
420 .iter()
421 .chain(row.read_ts.iter())
422 .chain(col.ops_addr.iter())
423 .chain(col.read_ts.iter())
424 .chain(val_vec.iter()),
425 );
426 let mut comb_mem = row.audit_ts.clone();
427 comb_mem.extend(&col.audit_ts);
428
429 MultiSparseMatPolynomialAsDense {
430 batch_size: sparse_polys.len(),
431 row,
432 col,
433 val: val_vec,
434 comb_ops,
435 comb_mem,
436 }
437 }
438
439 fn evaluate_with_tables(&self, eval_table_rx: &[F], eval_table_ry: &[F]) -> F {
440 assert_eq!(self.num_vars_x.pow2(), eval_table_rx.len());
441 assert_eq!(self.num_vars_y.pow2(), eval_table_ry.len());
442
443 (0..self.M.len())
444 .map(|i| {
445 let row = self.M[i].row;
446 let col = self.M[i].col;
447 let val = &self.M[i].val;
448 eval_table_rx[row] * eval_table_ry[col] * val
449 })
450 .sum()
451 }
452
453 pub fn multi_evaluate(polys: &[&SparseMatPolynomial<F>], rx: &[F], ry: &[F]) -> Vec<F> {
454 let eval_table_rx = EqPolynomial::new(rx.to_vec()).evals();
455 let eval_table_ry = EqPolynomial::new(ry.to_vec()).evals();
456
457 (0..polys.len())
458 .map(|i| polys[i].evaluate_with_tables(&eval_table_rx, &eval_table_ry))
459 .collect::<Vec<F>>()
460 }
461
462 pub fn multiply_vec(&self, num_rows: usize, num_cols: usize, z: &[F]) -> Vec<F> {
463 assert_eq!(z.len(), num_cols);
464
465 (0..self.M.len())
466 .map(|i| {
467 let row = self.M[i].row;
468 let col = self.M[i].col;
469 let val = &self.M[i].val;
470 (row, z[col] * val)
471 })
472 .fold(vec![F::zero(); num_rows], |mut Mz, (r, v)| {
473 Mz[r] += v;
474 Mz
475 })
476 }
477
478 pub fn compute_eval_table_sparse(&self, rx: &[F], num_rows: usize, num_cols: usize) -> Vec<F> {
479 assert_eq!(rx.len(), num_rows);
480
481 let mut M_evals: Vec<F> = vec![F::zero(); num_cols];
482
483 for i in 0..self.M.len() {
484 let entry = &self.M[i];
485 M_evals[entry.col] += rx[entry.row] * entry.val;
486 }
487 M_evals
488 }
489
490 pub fn multi_commit<E>(
491 sparse_polys: &[&SparseMatPolynomial<F>],
492 gens: &SparseMatPolyCommitmentGens<E>,
493 ) -> (
494 SparseMatPolyCommitment<E::G1>,
495 MultiSparseMatPolynomialAsDense<F>,
496 )
497 where
498 E: Pairing<ScalarField = F>,
499 {
500 let batch_size = sparse_polys.len();
501 let dense = SparseMatPolynomial::multi_sparse_to_dense_rep(sparse_polys);
502
503 let (comm_comb_ops, _blinds_comb_ops) = dense.comb_ops.commit(&gens.gens_ops, false);
504 let (comm_comb_mem, _blinds_comb_mem) = dense.comb_mem.commit(&gens.gens_mem, false);
505
506 (
507 SparseMatPolyCommitment {
508 batch_size,
509 num_mem_cells: dense.row.audit_ts.len(),
510 num_ops: dense.row.read_ts[0].len(),
511 comm_comb_ops,
512 comm_comb_mem,
513 },
514 dense,
515 )
516 }
517}
518
519impl<F: PrimeField> MultiSparseMatPolynomialAsDense<F> {
520 pub fn deref(&self, row_mem_val: &[F], col_mem_val: &[F]) -> Derefs<F> {
521 let row_ops_val = self.row.deref(row_mem_val);
522 let col_ops_val = self.col.deref(col_mem_val);
523
524 Derefs::new(row_ops_val, col_ops_val)
525 }
526}
527
528#[derive(Debug)]
529struct ProductLayer<F: PrimeField> {
530 init: ProductCircuit<F>,
531 read_vec: Vec<ProductCircuit<F>>,
532 write_vec: Vec<ProductCircuit<F>>,
533 audit: ProductCircuit<F>,
534}
535
536#[derive(Debug)]
537struct Layers<F: PrimeField> {
538 prod_layer: ProductLayer<F>,
539}
540
541impl<F: PrimeField> Layers<F> {
542 fn build_hash_layer(
543 eval_table: &[F],
544 addrs_vec: &[DensePolynomial<F>],
545 derefs_vec: &[DensePolynomial<F>],
546 read_ts_vec: &[DensePolynomial<F>],
547 audit_ts: &DensePolynomial<F>,
548 r_mem_check: &(F, F),
549 ) -> (
550 DensePolynomial<F>,
551 Vec<DensePolynomial<F>>,
552 Vec<DensePolynomial<F>>,
553 DensePolynomial<F>,
554 ) {
555 let (r_hash, r_multiset_check) = r_mem_check;
556
557 //hash(addr, val, ts) = ts * r_hash_sqr + val * r_hash + addr
558 let r_hash_sqr = r_hash.square();
559 let hash_func = |addr: &F, val: &F, ts: &F| -> F { r_hash_sqr * ts + (*val) * r_hash + addr };
560
561 // hash init and audit that does not depend on #instances
562 let num_mem_cells = eval_table.len();
563 let poly_init_hashed = DensePolynomial::new(
564 (0..num_mem_cells)
565 .map(|i| {
566 // at init time, addr is given by i, init value is given by eval_table, and ts = 0
567 hash_func(&F::from(i as u64), &eval_table[i], &F::zero()) - r_multiset_check
568 })
569 .collect::<Vec<F>>(),
570 );
571 let poly_audit_hashed = DensePolynomial::new(
572 (0..num_mem_cells)
573 .map(|i| {
574 // at audit time, addr is given by i, value is given by eval_table, and ts is given by audit_ts
575 hash_func(&F::from(i as u64), &eval_table[i], &audit_ts[i]) - r_multiset_check
576 })
577 .collect::<Vec<F>>(),
578 );
579
580 // hash read and write that depends on #instances
581 let mut poly_read_hashed_vec: Vec<DensePolynomial<F>> = Vec::new();
582 let mut poly_write_hashed_vec: Vec<DensePolynomial<F>> = Vec::new();
583 for i in 0..addrs_vec.len() {
584 let (addrs, derefs, read_ts) = (&addrs_vec[i], &derefs_vec[i], &read_ts_vec[i]);
585 assert_eq!(addrs.len(), derefs.len());
586 assert_eq!(addrs.len(), read_ts.len());
587 let num_ops = addrs.len();
588 let poly_read_hashed = DensePolynomial::new(
589 (0..num_ops)
590 .map(|i| {
591 // at read time, addr is given by addrs, value is given by derefs, and ts is given by read_ts
592 hash_func(&addrs[i], &derefs[i], &read_ts[i]) - r_multiset_check
593 })
594 .collect::<Vec<F>>(),
595 );
596 poly_read_hashed_vec.push(poly_read_hashed);
597
598 let poly_write_hashed = DensePolynomial::new(
599 (0..num_ops)
600 .map(|i| {
601 // at write time, addr is given by addrs, value is given by derefs, and ts is given by write_ts = read_ts + 1
602 hash_func(&addrs[i], &derefs[i], &(read_ts[i] + F::one())) - r_multiset_check
603 })
604 .collect::<Vec<F>>(),
605 );
606 poly_write_hashed_vec.push(poly_write_hashed);
607 }
608
609 (
610 poly_init_hashed,
611 poly_read_hashed_vec,
612 poly_write_hashed_vec,
613 poly_audit_hashed,
614 )
615 }
616
617 pub fn new(
618 eval_table: &[F],
619 addr_timestamps: &AddrTimestamps<F>,
620 poly_ops_val: &[DensePolynomial<F>],
621 r_mem_check: &(F, F),
622 ) -> Self {
623 let (poly_init_hashed, poly_read_hashed_vec, poly_write_hashed_vec, poly_audit_hashed) =
624 Layers::build_hash_layer(
625 eval_table,
626 &addr_timestamps.ops_addr,
627 poly_ops_val,
628 &addr_timestamps.read_ts,
629 &addr_timestamps.audit_ts,
630 r_mem_check,
631 );
632
633 let prod_init = ProductCircuit::new(&poly_init_hashed);
634 let prod_read_vec = (0..poly_read_hashed_vec.len())
635 .map(|i| ProductCircuit::new(&poly_read_hashed_vec[i]))
636 .collect::<Vec<ProductCircuit<F>>>();
637 let prod_write_vec = (0..poly_write_hashed_vec.len())
638 .map(|i| ProductCircuit::new(&poly_write_hashed_vec[i]))
639 .collect::<Vec<ProductCircuit<F>>>();
640 let prod_audit = ProductCircuit::new(&poly_audit_hashed);
641
642 // subset audit check
643 let hashed_writes: F = (0..prod_write_vec.len())
644 .map(|i| prod_write_vec[i].evaluate())
645 .product();
646 let hashed_write_set: F = prod_init.evaluate() * hashed_writes;
647
648 let hashed_reads: F = (0..prod_read_vec.len())
649 .map(|i| prod_read_vec[i].evaluate())
650 .product();
651 let hashed_read_set: F = hashed_reads * prod_audit.evaluate();
652
653 //assert_eq!(hashed_read_set, hashed_write_set);
654 debug_assert_eq!(hashed_read_set, hashed_write_set);
655
656 Layers {
657 prod_layer: ProductLayer {
658 init: prod_init,
659 read_vec: prod_read_vec,
660 write_vec: prod_write_vec,
661 audit: prod_audit,
662 },
663 }
664 }
665}
666
667#[derive(Debug)]
668struct PolyEvalNetwork<F: PrimeField> {
669 row_layers: Layers<F>,
670 col_layers: Layers<F>,
671}
672
673impl<F: PrimeField> PolyEvalNetwork<F> {
674 pub fn new(
675 dense: &MultiSparseMatPolynomialAsDense<F>,
676 derefs: &Derefs<F>,
677 mem_rx: &[F],
678 mem_ry: &[F],
679 r_mem_check: &(F, F),
680 ) -> Self {
681 let row_layers = Layers::new(mem_rx, &dense.row, &derefs.row_ops_val, r_mem_check);
682 let col_layers = Layers::new(mem_ry, &dense.col, &derefs.col_ops_val, r_mem_check);
683
684 PolyEvalNetwork {
685 row_layers,
686 col_layers,
687 }
688 }
689}
690
691#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
692struct HashLayerProof<E: Pairing> {
693 eval_row: (Vec<E::ScalarField>, Vec<E::ScalarField>, E::ScalarField),
694 eval_col: (Vec<E::ScalarField>, Vec<E::ScalarField>, E::ScalarField),
695 eval_val: Vec<E::ScalarField>,
696 eval_derefs: (Vec<E::ScalarField>, Vec<E::ScalarField>),
697 proof_ops: PolyEvalProof<E>,
698 proof_mem: PolyEvalProof<E>,
699 proof_derefs: DerefsEvalProof<E>,
700}
701
702impl<E> HashLayerProof<E>
703where
704 E: Pairing,
705 E::ScalarField: Absorb,
706{
707 fn prove_helper(
708 rand: (&Vec<E::ScalarField>, &Vec<E::ScalarField>),
709 addr_timestamps: &AddrTimestamps<E::ScalarField>,
710 ) -> (Vec<E::ScalarField>, Vec<E::ScalarField>, E::ScalarField) {
711 let (rand_mem, rand_ops) = rand;
712
713 // decommit ops-addr at rand_ops
714 let mut eval_ops_addr_vec: Vec<E::ScalarField> = Vec::new();
715 for i in 0..addr_timestamps.ops_addr.len() {
716 let eval_ops_addr = addr_timestamps.ops_addr[i].evaluate(rand_ops);
717 eval_ops_addr_vec.push(eval_ops_addr);
718 }
719
720 // decommit read_ts at rand_ops
721 let mut eval_read_ts_vec: Vec<E::ScalarField> = Vec::new();
722 for i in 0..addr_timestamps.read_ts.len() {
723 let eval_read_ts = addr_timestamps.read_ts[i].evaluate(rand_ops);
724 eval_read_ts_vec.push(eval_read_ts);
725 }
726
727 // decommit audit-ts at rand_mem
728 let eval_audit_ts = addr_timestamps.audit_ts.evaluate(rand_mem);
729
730 (eval_ops_addr_vec, eval_read_ts_vec, eval_audit_ts)
731 }
732
733 fn prove(
734 rand: (&Vec<E::ScalarField>, &Vec<E::ScalarField>),
735 dense: &MultiSparseMatPolynomialAsDense<E::ScalarField>,
736 derefs: &Derefs<E::ScalarField>,
737 gens: &SparseMatPolyCommitmentGens<E>,
738 transcript: &mut PoseidonTranscript<E::ScalarField>,
739 ) -> Self {
740 // transcript.append_protocol_name(HashLayerProof::protocol_name());
741
742 let (rand_mem, rand_ops) = rand;
743
744 // decommit derefs at rand_ops
745 let eval_row_ops_val = (0..derefs.row_ops_val.len())
746 .map(|i| derefs.row_ops_val[i].evaluate(rand_ops))
747 .collect::<Vec<E::ScalarField>>();
748 let eval_col_ops_val = (0..derefs.col_ops_val.len())
749 .map(|i| derefs.col_ops_val[i].evaluate(rand_ops))
750 .collect::<Vec<E::ScalarField>>();
751 let proof_derefs = DerefsEvalProof::prove(
752 derefs,
753 &eval_row_ops_val,
754 &eval_col_ops_val,
755 rand_ops,
756 &gens.gens_derefs,
757 transcript,
758 );
759 let eval_derefs = (eval_row_ops_val, eval_col_ops_val);
760
761 // evaluate row_addr, row_read-ts, col_addr, col_read-ts, val at rand_ops
762 // evaluate row_audit_ts and col_audit_ts at rand_mem
763 let (eval_row_addr_vec, eval_row_read_ts_vec, eval_row_audit_ts) =
764 HashLayerProof::<E>::prove_helper((rand_mem, rand_ops), &dense.row);
765 let (eval_col_addr_vec, eval_col_read_ts_vec, eval_col_audit_ts) =
766 HashLayerProof::<E>::prove_helper((rand_mem, rand_ops), &dense.col);
767 let eval_val_vec = (0..dense.val.len())
768 .map(|i| dense.val[i].evaluate(rand_ops))
769 .collect::<Vec<E::ScalarField>>();
770
771 // form a single decommitment using comm_comb_ops
772 let mut evals_ops: Vec<E::ScalarField> = Vec::new();
773 evals_ops.extend(&eval_row_addr_vec);
774 evals_ops.extend(&eval_row_read_ts_vec);
775 evals_ops.extend(&eval_col_addr_vec);
776 evals_ops.extend(&eval_col_read_ts_vec);
777 evals_ops.extend(&eval_val_vec);
778 evals_ops.resize(evals_ops.len().next_power_of_two(), E::ScalarField::zero());
779 transcript.append_scalar_vector(b"", &evals_ops);
780 let challenges_ops = transcript.challenge_scalar_vec(b"", evals_ops.len().log_2());
781
782 let mut poly_evals_ops = DensePolynomial::new(evals_ops);
783 for i in (0..challenges_ops.len()).rev() {
784 poly_evals_ops.bound_poly_var_bot(&challenges_ops[i]);
785 }
786 assert_eq!(poly_evals_ops.len(), 1);
787 let joint_claim_eval_ops = poly_evals_ops[0];
788 let mut r_joint_ops = challenges_ops;
789 r_joint_ops.extend(rand_ops);
790 debug_assert_eq!(dense.comb_ops.evaluate(&r_joint_ops), joint_claim_eval_ops);
791 transcript.append_scalar(b"", &joint_claim_eval_ops);
792 let (proof_ops, _comm_ops_eval) = PolyEvalProof::prove(
793 &dense.comb_ops,
794 None,
795 &r_joint_ops,
796 &joint_claim_eval_ops,
797 None,
798 &gens.gens_ops,
799 transcript,
800 );
801
802 // form a single decommitment using comb_comb_mem at rand_mem
803 let evals_mem: Vec<E::ScalarField> = vec![eval_row_audit_ts, eval_col_audit_ts];
804 // evals_mem.append_to_transcript(b"claim_evals_mem", transcript);
805 transcript.append_scalar_vector(b"", &evals_mem);
806 let challenges_mem = transcript.challenge_scalar_vec(b"", evals_mem.len().log_2());
807
808 let mut poly_evals_mem = DensePolynomial::new(evals_mem);
809 for i in (0..challenges_mem.len()).rev() {
810 poly_evals_mem.bound_poly_var_bot(&challenges_mem[i]);
811 }
812 assert_eq!(poly_evals_mem.len(), 1);
813 let joint_claim_eval_mem = poly_evals_mem[0];
814 let mut r_joint_mem = challenges_mem;
815 r_joint_mem.extend(rand_mem);
816 debug_assert_eq!(dense.comb_mem.evaluate(&r_joint_mem), joint_claim_eval_mem);
817 transcript.append_scalar(b"", &joint_claim_eval_mem);
818 let (proof_mem, _comm_mem_eval) = PolyEvalProof::prove(
819 &dense.comb_mem,
820 None,
821 &r_joint_mem,
822 &joint_claim_eval_mem,
823 None,
824 &gens.gens_mem,
825 transcript,
826 );
827
828 HashLayerProof {
829 eval_row: (eval_row_addr_vec, eval_row_read_ts_vec, eval_row_audit_ts),
830 eval_col: (eval_col_addr_vec, eval_col_read_ts_vec, eval_col_audit_ts),
831 eval_val: eval_val_vec,
832 eval_derefs,
833 proof_ops,
834 proof_mem,
835 proof_derefs,
836 }
837 }
838
839 fn verify_helper(
840 rand: &(&Vec<E::ScalarField>, &Vec<E::ScalarField>),
841 claims: &(
842 E::ScalarField,
843 Vec<E::ScalarField>,
844 Vec<E::ScalarField>,
845 E::ScalarField,
846 ),
847 eval_ops_val: &[E::ScalarField],
848 eval_ops_addr: &[E::ScalarField],
849 eval_read_ts: &[E::ScalarField],
850 eval_audit_ts: &E::ScalarField,
851 r: &[E::ScalarField],
852 r_hash: &E::ScalarField,
853 r_multiset_check: &E::ScalarField,
854 ) -> Result<(), ProofVerifyError> {
855 let r_hash_sqr = r_hash.square();
856 let hash_func = |addr: &E::ScalarField,
857 val: &E::ScalarField,
858 ts: &E::ScalarField|
859 -> E::ScalarField { r_hash_sqr * ts + (*val) * r_hash + addr };
860
861 let (rand_mem, _rand_ops) = rand;
862 let (claim_init, claim_read, claim_write, claim_audit) = claims;
863
864 // init
865 let eval_init_addr = IdentityPolynomial::new(rand_mem.len()).evaluate(rand_mem);
866 let eval_init_val = EqPolynomial::new(r.to_vec()).evaluate(rand_mem);
867 let hash_init_at_rand_mem =
868 hash_func(&eval_init_addr, &eval_init_val, &E::ScalarField::zero()) - r_multiset_check; // verify the claim_last of init chunk
869 assert_eq!(&hash_init_at_rand_mem, claim_init);
870
871 // read
872 for i in 0..eval_ops_addr.len() {
873 let hash_read_at_rand_ops =
874 hash_func(&eval_ops_addr[i], &eval_ops_val[i], &eval_read_ts[i]) - r_multiset_check; // verify the claim_last of init chunk
875 assert_eq!(&hash_read_at_rand_ops, &claim_read[i]);
876 }
877
878 // write: shares addr, val component; only decommit write_ts
879 for i in 0..eval_ops_addr.len() {
880 let eval_write_ts = eval_read_ts[i] + E::ScalarField::one();
881 let hash_write_at_rand_ops =
882 hash_func(&eval_ops_addr[i], &eval_ops_val[i], &eval_write_ts) - r_multiset_check; // verify the claim_last of init chunk
883 assert_eq!(&hash_write_at_rand_ops, &claim_write[i]);
884 }
885
886 // audit: shares addr and val with init
887 let eval_audit_addr = eval_init_addr;
888 let eval_audit_val = eval_init_val;
889 let hash_audit_at_rand_mem =
890 hash_func(&eval_audit_addr, &eval_audit_val, eval_audit_ts) - r_multiset_check;
891 assert_eq!(&hash_audit_at_rand_mem, claim_audit); // verify the last step of the sum-check for audit
892
893 Ok(())
894 }
895
896 fn verify(
897 &self,
898 rand: (&Vec<E::ScalarField>, &Vec<E::ScalarField>),
899 claims_row: &(
900 E::ScalarField,
901 Vec<E::ScalarField>,
902 Vec<E::ScalarField>,
903 E::ScalarField,
904 ),
905 claims_col: &(
906 E::ScalarField,
907 Vec<E::ScalarField>,
908 Vec<E::ScalarField>,
909 E::ScalarField,
910 ),
911 claims_dotp: &[E::ScalarField],
912 comm: &SparseMatPolyCommitment<E::G1>,
913 gens: &SparseMatPolyCommitmentGens<E>,
914 comm_derefs: &DerefsCommitment<E::G1>,
915 rx: &[E::ScalarField],
916 ry: &[E::ScalarField],
917 r_hash: &E::ScalarField,
918 r_multiset_check: &E::ScalarField,
919 transcript: &mut PoseidonTranscript<E::ScalarField>,
920 ) -> Result<(), ProofVerifyError> {
921 let timer = Timer::new("verify_hash_proof");
922 // transcript.append_protocol_name(HashLayerProof::protocol_name());
923
924 let (rand_mem, rand_ops) = rand;
925
926 // verify derefs at rand_ops
927 let (eval_row_ops_val, eval_col_ops_val) = &self.eval_derefs;
928 assert_eq!(eval_row_ops_val.len(), eval_col_ops_val.len());
929 self.proof_derefs.verify(
930 rand_ops,
931 eval_row_ops_val,
932 eval_col_ops_val,
933 &gens.gens_derefs,
934 comm_derefs,
935 transcript,
936 )?;
937
938 // verify the decommitments used in evaluation sum-check
939 let eval_val_vec = &self.eval_val;
940 assert_eq!(claims_dotp.len(), 3 * eval_row_ops_val.len());
941 for i in 0..claims_dotp.len() / 3 {
942 let claim_row_ops_val = claims_dotp[3 * i];
943 let claim_col_ops_val = claims_dotp[3 * i + 1];
944 let claim_val = claims_dotp[3 * i + 2];
945
946 assert_eq!(claim_row_ops_val, eval_row_ops_val[i]);
947 assert_eq!(claim_col_ops_val, eval_col_ops_val[i]);
948 assert_eq!(claim_val, eval_val_vec[i]);
949 }
950
951 // verify addr-timestamps using comm_comb_ops at rand_ops
952 let (eval_row_addr_vec, eval_row_read_ts_vec, eval_row_audit_ts) = &self.eval_row;
953 let (eval_col_addr_vec, eval_col_read_ts_vec, eval_col_audit_ts) = &self.eval_col;
954
955 let mut evals_ops: Vec<E::ScalarField> = Vec::new();
956 evals_ops.extend(eval_row_addr_vec);
957 evals_ops.extend(eval_row_read_ts_vec);
958 evals_ops.extend(eval_col_addr_vec);
959 evals_ops.extend(eval_col_read_ts_vec);
960 evals_ops.extend(eval_val_vec);
961 evals_ops.resize(evals_ops.len().next_power_of_two(), E::ScalarField::zero());
962 transcript.append_scalar_vector(b"", &evals_ops);
963 // evals_ops.append_to_transcript(b"claim_evals_ops", transcript);
964 let challenges_ops = transcript.challenge_scalar_vec(b"", evals_ops.len().log_2());
965
966 let mut poly_evals_ops = DensePolynomial::new(evals_ops);
967 for i in (0..challenges_ops.len()).rev() {
968 poly_evals_ops.bound_poly_var_bot(&challenges_ops[i]);
969 }
970 assert_eq!(poly_evals_ops.len(), 1);
971 let joint_claim_eval_ops = poly_evals_ops[0];
972 let mut r_joint_ops = challenges_ops;
973 r_joint_ops.extend(rand_ops);
974 transcript.append_scalar(b"", &joint_claim_eval_ops);
975 assert!(self
976 .proof_ops
977 .verify_plain(
978 &gens.gens_ops,
979 transcript,
980 &r_joint_ops,
981 &joint_claim_eval_ops,
982 &comm.comm_comb_ops
983 )
984 .is_ok());
985
986 // verify proof-mem using comm_comb_mem at rand_mem
987 // form a single decommitment using comb_comb_mem at rand_mem
988 let evals_mem: Vec<E::ScalarField> = vec![*eval_row_audit_ts, *eval_col_audit_ts];
989 // evals_mem.append_to_transcript(b"claim_evals_mem", transcript);
990 transcript.append_scalar_vector(b"", &evals_mem);
991 let challenges_mem = transcript.challenge_scalar_vec(b"", evals_mem.len().log_2());
992
993 let mut poly_evals_mem = DensePolynomial::new(evals_mem);
994 for i in (0..challenges_mem.len()).rev() {
995 poly_evals_mem.bound_poly_var_bot(&challenges_mem[i]);
996 }
997 assert_eq!(poly_evals_mem.len(), 1);
998 let joint_claim_eval_mem = poly_evals_mem[0];
999 let mut r_joint_mem = challenges_mem;
1000 r_joint_mem.extend(rand_mem);
1001 // joint_claim_eval_mem.append_to_transcript(b"joint_claim_eval_mem", transcript);
1002 transcript.append_scalar(b"", &joint_claim_eval_mem);
1003 self.proof_mem.verify_plain(
1004 &gens.gens_mem,
1005 transcript,
1006 &r_joint_mem,
1007 &joint_claim_eval_mem,
1008 &comm.comm_comb_mem,
1009 )?;
1010
1011 // verify the claims from the product layer
1012 let (eval_ops_addr, eval_read_ts, eval_audit_ts) = &self.eval_row;
1013 HashLayerProof::<E>::verify_helper(
1014 &(rand_mem, rand_ops),
1015 claims_row,
1016 eval_row_ops_val,
1017 eval_ops_addr,
1018 eval_read_ts,
1019 eval_audit_ts,
1020 rx,
1021 r_hash,
1022 r_multiset_check,
1023 )?;
1024
1025 let (eval_ops_addr, eval_read_ts, eval_audit_ts) = &self.eval_col;
1026 HashLayerProof::<E>::verify_helper(
1027 &(rand_mem, rand_ops),
1028 claims_col,
1029 eval_col_ops_val,
1030 eval_ops_addr,
1031 eval_read_ts,
1032 eval_audit_ts,
1033 ry,
1034 r_hash,
1035 r_multiset_check,
1036 )?;
1037
1038 timer.stop();
1039 Ok(())
1040 }
1041}
1042
1043#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
1044struct ProductLayerProof<F: PrimeField> {
1045 eval_row: (F, Vec<F>, Vec<F>, F),
1046 eval_col: (F, Vec<F>, Vec<F>, F),
1047 eval_val: (Vec<F>, Vec<F>),
1048 proof_mem: ProductCircuitEvalProofBatched<F>,
1049 proof_ops: ProductCircuitEvalProofBatched<F>,
1050}
1051
1052impl<F: PrimeField + Absorb> ProductLayerProof<F> {
1053 pub fn prove(
1054 row_prod_layer: &mut ProductLayer<F>,
1055 col_prod_layer: &mut ProductLayer<F>,
1056 dense: &MultiSparseMatPolynomialAsDense<F>,
1057 derefs: &Derefs<F>,
1058 eval: &[F],
1059 transcript: &mut PoseidonTranscript<F>,
1060 ) -> (Self, Vec<F>, Vec<F>) {
1061 // transcript.append_protocol_name(ProductLayerProof::protocol_name());
1062
1063 let row_eval_init = row_prod_layer.init.evaluate();
1064 let row_eval_audit = row_prod_layer.audit.evaluate();
1065 let row_eval_read = (0..row_prod_layer.read_vec.len())
1066 .map(|i| row_prod_layer.read_vec[i].evaluate())
1067 .collect::<Vec<F>>();
1068 let row_eval_write = (0..row_prod_layer.write_vec.len())
1069 .map(|i| row_prod_layer.write_vec[i].evaluate())
1070 .collect::<Vec<F>>();
1071
1072 // subset check
1073 let ws: F = (0..row_eval_write.len())
1074 .map(|i| row_eval_write[i])
1075 .product();
1076 let rs: F = (0..row_eval_read.len()).map(|i| row_eval_read[i]).product();
1077 assert_eq!(row_eval_init * ws, rs * row_eval_audit);
1078
1079 transcript.append_scalar(b"", &row_eval_init);
1080 transcript.append_scalar_vector(b"", &row_eval_read);
1081 transcript.append_scalar_vector(b"", &row_eval_write);
1082 transcript.append_scalar(b"", &row_eval_audit);
1083
1084 let col_eval_init = col_prod_layer.init.evaluate();
1085 let col_eval_audit = col_prod_layer.audit.evaluate();
1086 let col_eval_read: Vec<F> = (0..col_prod_layer.read_vec.len())
1087 .map(|i| col_prod_layer.read_vec[i].evaluate())
1088 .collect();
1089 let col_eval_write: Vec<F> = (0..col_prod_layer.write_vec.len())
1090 .map(|i| col_prod_layer.write_vec[i].evaluate())
1091 .collect();
1092
1093 // subset check
1094 let ws: F = (0..col_eval_write.len())
1095 .map(|i| col_eval_write[i])
1096 .product();
1097 let rs: F = (0..col_eval_read.len()).map(|i| col_eval_read[i]).product();
1098 assert_eq!(col_eval_init * ws, rs * col_eval_audit);
1099
1100 transcript.append_scalar(b"", &col_eval_init);
1101 transcript.append_scalar_vector(b"", &col_eval_read);
1102 transcript.append_scalar_vector(b"", &col_eval_write);
1103 transcript.append_scalar(b"", &col_eval_audit);
1104
1105 // prepare dotproduct circuit for batching then with ops-related product circuits
1106 assert_eq!(eval.len(), derefs.row_ops_val.len());
1107 assert_eq!(eval.len(), derefs.col_ops_val.len());
1108 assert_eq!(eval.len(), dense.val.len());
1109 let mut dotp_circuit_left_vec: Vec<DotProductCircuit<F>> = Vec::new();
1110 let mut dotp_circuit_right_vec: Vec<DotProductCircuit<F>> = Vec::new();
1111 let mut eval_dotp_left_vec: Vec<F> = Vec::new();
1112 let mut eval_dotp_right_vec: Vec<F> = Vec::new();
1113 for i in 0..derefs.row_ops_val.len() {
1114 // evaluate sparse polynomial evaluation using two dotp checks
1115 let left = derefs.row_ops_val[i].clone();
1116 let right = derefs.col_ops_val[i].clone();
1117 let weights = dense.val[i].clone();
1118
1119 // build two dot product circuits to prove evaluation of sparse polynomial
1120 let mut dotp_circuit = DotProductCircuit::new(left, right, weights);
1121 let (dotp_circuit_left, dotp_circuit_right) = dotp_circuit.split();
1122
1123 let (eval_dotp_left, eval_dotp_right) =
1124 (dotp_circuit_left.evaluate(), dotp_circuit_right.evaluate());
1125
1126 // eval_dotp_left.append_to_transcript(b"claim_eval_dotp_left", transcript);
1127 // eval_dotp_right.append_to_transcript(b"claim_eval_dotp_right", transcript);
1128 transcript.append_scalar(b"", &eval_dotp_left);
1129 transcript.append_scalar(b"", &eval_dotp_right);
1130 assert_eq!(eval_dotp_left + eval_dotp_right, eval[i]);
1131 eval_dotp_left_vec.push(eval_dotp_left);
1132 eval_dotp_right_vec.push(eval_dotp_right);
1133
1134 dotp_circuit_left_vec.push(dotp_circuit_left);
1135 dotp_circuit_right_vec.push(dotp_circuit_right);
1136 }
1137
1138 // The number of operations into the memory encoded by rx and ry are always the same (by design)
1139 // So we can produce a batched product proof for all of them at the same time.
1140 // prove the correctness of claim_row_eval_read, claim_row_eval_write, claim_col_eval_read, and claim_col_eval_write
1141 // TODO: we currently only produce proofs for 3 batched sparse polynomial evaluations
1142 assert_eq!(row_prod_layer.read_vec.len(), 3);
1143 let (row_read_A, row_read_B, row_read_C) = {
1144 let (vec_A, vec_BC) = row_prod_layer.read_vec.split_at_mut(1);
1145 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1146 (vec_A, vec_B, vec_C)
1147 };
1148
1149 let (row_write_A, row_write_B, row_write_C) = {
1150 let (vec_A, vec_BC) = row_prod_layer.write_vec.split_at_mut(1);
1151 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1152 (vec_A, vec_B, vec_C)
1153 };
1154
1155 let (col_read_A, col_read_B, col_read_C) = {
1156 let (vec_A, vec_BC) = col_prod_layer.read_vec.split_at_mut(1);
1157 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1158 (vec_A, vec_B, vec_C)
1159 };
1160
1161 let (col_write_A, col_write_B, col_write_C) = {
1162 let (vec_A, vec_BC) = col_prod_layer.write_vec.split_at_mut(1);
1163 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1164 (vec_A, vec_B, vec_C)
1165 };
1166
1167 let (dotp_left_A, dotp_left_B, dotp_left_C) = {
1168 let (vec_A, vec_BC) = dotp_circuit_left_vec.split_at_mut(1);
1169 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1170 (vec_A, vec_B, vec_C)
1171 };
1172
1173 let (dotp_right_A, dotp_right_B, dotp_right_C) = {
1174 let (vec_A, vec_BC) = dotp_circuit_right_vec.split_at_mut(1);
1175 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1176 (vec_A, vec_B, vec_C)
1177 };
1178
1179 let (proof_ops, rand_ops) = ProductCircuitEvalProofBatched::prove(
1180 &mut vec![
1181 &mut row_read_A[0],
1182 &mut row_read_B[0],
1183 &mut row_read_C[0],
1184 &mut row_write_A[0],
1185 &mut row_write_B[0],
1186 &mut row_write_C[0],
1187 &mut col_read_A[0],
1188 &mut col_read_B[0],
1189 &mut col_read_C[0],
1190 &mut col_write_A[0],
1191 &mut col_write_B[0],
1192 &mut col_write_C[0],
1193 ],
1194 &mut vec![
1195 &mut dotp_left_A[0],
1196 &mut dotp_right_A[0],
1197 &mut dotp_left_B[0],
1198 &mut dotp_right_B[0],
1199 &mut dotp_left_C[0],
1200 &mut dotp_right_C[0],
1201 ],
1202 transcript,
1203 );
1204
1205 // produce a batched proof of memory-related product circuits
1206 let (proof_mem, rand_mem) = ProductCircuitEvalProofBatched::prove(
1207 &mut vec![
1208 &mut row_prod_layer.init,
1209 &mut row_prod_layer.audit,
1210 &mut col_prod_layer.init,
1211 &mut col_prod_layer.audit,
1212 ],
1213 &mut Vec::new(),
1214 transcript,
1215 );
1216
1217 let product_layer_proof = ProductLayerProof {
1218 eval_row: (row_eval_init, row_eval_read, row_eval_write, row_eval_audit),
1219 eval_col: (col_eval_init, col_eval_read, col_eval_write, col_eval_audit),
1220 eval_val: (eval_dotp_left_vec, eval_dotp_right_vec),
1221 proof_mem,
1222 proof_ops,
1223 };
1224
1225 let mut product_layer_proof_encoded: Vec<u8> = Vec::new();
1226 product_layer_proof
1227 .serialize_with_mode(&mut product_layer_proof_encoded, Compress::Yes)
1228 .unwrap();
1229 let msg = format!(
1230 "len_product_layer_proof {:?}",
1231 product_layer_proof_encoded.len()
1232 );
1233 Timer::print(&msg);
1234
1235 (product_layer_proof, rand_mem, rand_ops)
1236 }
1237
1238 pub fn verify(
1239 &self,
1240 num_ops: usize,
1241 num_cells: usize,
1242 eval: &[F],
1243 transcript: &mut PoseidonTranscript<F>,
1244 ) -> Result<(Vec<F>, Vec<F>, Vec<F>, Vec<F>, Vec<F>), ProofVerifyError> {
1245 // transcript.append_protocol_name(ProductLayerProof::protocol_name());
1246
1247 let timer = Timer::new("verify_prod_proof");
1248 let num_instances = eval.len();
1249
1250 // subset check
1251 let (row_eval_init, row_eval_read, row_eval_write, row_eval_audit) = &self.eval_row;
1252 assert_eq!(row_eval_write.len(), num_instances);
1253 assert_eq!(row_eval_read.len(), num_instances);
1254 let ws: F = (0..row_eval_write.len())
1255 .map(|i| row_eval_write[i])
1256 .product();
1257 let rs: F = (0..row_eval_read.len()).map(|i| row_eval_read[i]).product();
1258 assert_eq!(ws * row_eval_init, rs * row_eval_audit);
1259
1260 // row_eval_init.append_to_transcript(b"claim_row_eval_init", transcript);
1261 // row_eval_read.append_to_transcript(b"claim_row_eval_read", transcript);
1262 // row_eval_write.append_to_transcript(b"claim_row_eval_write", transcript);
1263 // row_eval_audit.append_to_transcript(b"claim_row_eval_audit", transcript);
1264
1265 transcript.append_scalar(b"", row_eval_init);
1266 transcript.append_scalar_vector(b"", row_eval_read);
1267 transcript.append_scalar_vector(b"", row_eval_write);
1268 transcript.append_scalar(b"", row_eval_audit);
1269
1270 // subset check
1271 let (col_eval_init, col_eval_read, col_eval_write, col_eval_audit) = &self.eval_col;
1272 assert_eq!(col_eval_write.len(), num_instances);
1273 assert_eq!(col_eval_read.len(), num_instances);
1274 let ws: F = (0..col_eval_write.len())
1275 .map(|i| col_eval_write[i])
1276 .product();
1277 let rs: F = (0..col_eval_read.len()).map(|i| col_eval_read[i]).product();
1278 assert_eq!(ws * col_eval_init, rs * col_eval_audit);
1279
1280 // col_eval_init.append_to_transcript(b"claim_col_eval_init", transcript);
1281 // col_eval_read.append_to_transcript(b"claim_col_eval_read", transcript);
1282 // col_eval_write.append_to_transcript(b"claim_col_eval_write", transcript);
1283 // col_eval_audit.append_to_transcript(b"claim_col_eval_audit", transcript);
1284
1285 transcript.append_scalar(b"", col_eval_init);
1286 transcript.append_scalar_vector(b"", col_eval_read);
1287 transcript.append_scalar_vector(b"", col_eval_write);
1288 transcript.append_scalar(b"", col_eval_audit);
1289
1290 // verify the evaluation of the sparse polynomial
1291 let (eval_dotp_left, eval_dotp_right) = &self.eval_val;
1292 assert_eq!(eval_dotp_left.len(), eval_dotp_left.len());
1293 assert_eq!(eval_dotp_left.len(), num_instances);
1294 let mut claims_dotp_circuit: Vec<F> = Vec::new();
1295 for i in 0..num_instances {
1296 assert_eq!(eval_dotp_left[i] + eval_dotp_right[i], eval[i]);
1297 // eval_dotp_left[i].append_to_transcript(b"claim_eval_dotp_left", transcript);
1298 // eval_dotp_right[i].append_to_transcript(b"claim_eval_dotp_right", transcript)
1299 transcript.append_scalar(b"", &eval_dotp_left[i]);
1300 transcript.append_scalar(b"", &eval_dotp_right[i]);
1301
1302 claims_dotp_circuit.push(eval_dotp_left[i]);
1303 claims_dotp_circuit.push(eval_dotp_right[i]);
1304 }
1305
1306 // verify the correctness of claim_row_eval_read, claim_row_eval_write, claim_col_eval_read, and claim_col_eval_write
1307 let mut claims_prod_circuit: Vec<F> = Vec::new();
1308 claims_prod_circuit.extend(row_eval_read);
1309 claims_prod_circuit.extend(row_eval_write);
1310 claims_prod_circuit.extend(col_eval_read);
1311 claims_prod_circuit.extend(col_eval_write);
1312
1313 let (claims_ops, claims_dotp, rand_ops) = self.proof_ops.verify(
1314 &claims_prod_circuit,
1315 &claims_dotp_circuit,
1316 num_ops,
1317 transcript,
1318 );
1319 // verify the correctness of claim_row_eval_init and claim_row_eval_audit
1320 let (claims_mem, _claims_mem_dotp, rand_mem) = self.proof_mem.verify(
1321 &[
1322 *row_eval_init,
1323 *row_eval_audit,
1324 *col_eval_init,
1325 *col_eval_audit,
1326 ],
1327 &Vec::new(),
1328 num_cells,
1329 transcript,
1330 );
1331 timer.stop();
1332
1333 Ok((claims_mem, rand_mem, claims_ops, claims_dotp, rand_ops))
1334 }
1335}
1336
1337#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
1338struct PolyEvalNetworkProof<E: Pairing> {
1339 proof_prod_layer: ProductLayerProof<E::ScalarField>,
1340 proof_hash_layer: HashLayerProof<E>,
1341}
1342
1343impl<E> PolyEvalNetworkProof<E>
1344where
1345 E: Pairing,
1346 E::ScalarField: Absorb,
1347{
1348 pub fn prove(
1349 network: &mut PolyEvalNetwork<E::ScalarField>,
1350 dense: &MultiSparseMatPolynomialAsDense<E::ScalarField>,
1351 derefs: &Derefs<E::ScalarField>,
1352 evals: &[E::ScalarField],
1353 gens: &SparseMatPolyCommitmentGens<E>,
1354 transcript: &mut PoseidonTranscript<E::ScalarField>,
1355 ) -> Self {
1356 // transcript.append_protocol_name(PolyEvalNetworkProof::protocol_name());
1357
1358 let (proof_prod_layer, rand_mem, rand_ops) = ProductLayerProof::prove(
1359 &mut network.row_layers.prod_layer,
1360 &mut network.col_layers.prod_layer,
1361 dense,
1362 derefs,
1363 evals,
1364 transcript,
1365 );
1366
1367 // proof of hash layer for row and col
1368 let proof_hash_layer =
1369 HashLayerProof::prove((&rand_mem, &rand_ops), dense, derefs, gens, transcript);
1370
1371 PolyEvalNetworkProof {
1372 proof_prod_layer,
1373 proof_hash_layer,
1374 }
1375 }
1376
1377 pub fn verify(
1378 &self,
1379 comm: &SparseMatPolyCommitment<E::G1>,
1380 comm_derefs: &DerefsCommitment<E::G1>,
1381 evals: &[E::ScalarField],
1382 gens: &SparseMatPolyCommitmentGens<E>,
1383 rx: &[E::ScalarField],
1384 ry: &[E::ScalarField],
1385 r_mem_check: &(E::ScalarField, E::ScalarField),
1386 nz: usize,
1387 transcript: &mut PoseidonTranscript<E::ScalarField>,
1388 ) -> Result<(), ProofVerifyError> {
1389 let timer = Timer::new("verify_polyeval_proof");
1390 // transcript.append_protocol_name(PolyEvalNetworkProof::protocol_name());
1391
1392 let num_instances = evals.len();
1393 let (r_hash, r_multiset_check) = r_mem_check;
1394
1395 let num_ops = nz.next_power_of_two();
1396 let num_cells = rx.len().pow2();
1397 assert_eq!(rx.len(), ry.len());
1398
1399 let (claims_mem, rand_mem, mut claims_ops, claims_dotp, rand_ops) = self
1400 .proof_prod_layer
1401 .verify(num_ops, num_cells, evals, transcript)?;
1402 assert_eq!(claims_mem.len(), 4);
1403 assert_eq!(claims_ops.len(), 4 * num_instances);
1404 assert_eq!(claims_dotp.len(), 3 * num_instances);
1405
1406 let (claims_ops_row, claims_ops_col) = claims_ops.split_at_mut(2 * num_instances);
1407 let (claims_ops_row_read, claims_ops_row_write) = claims_ops_row.split_at_mut(num_instances);
1408 let (claims_ops_col_read, claims_ops_col_write) = claims_ops_col.split_at_mut(num_instances);
1409
1410 // verify the proof of hash layer
1411 self.proof_hash_layer.verify(
1412 (&rand_mem, &rand_ops),
1413 &(
1414 claims_mem[0],
1415 claims_ops_row_read.to_vec(),
1416 claims_ops_row_write.to_vec(),
1417 claims_mem[1],
1418 ),
1419 &(
1420 claims_mem[2],
1421 claims_ops_col_read.to_vec(),
1422 claims_ops_col_write.to_vec(),
1423 claims_mem[3],
1424 ),
1425 &claims_dotp,
1426 comm,
1427 gens,
1428 comm_derefs,
1429 rx,
1430 ry,
1431 r_hash,
1432 r_multiset_check,
1433 transcript,
1434 )?;
1435 timer.stop();
1436
1437 Ok(())
1438 }
1439}
1440
1441#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
1442pub struct SparseMatPolyEvalProof<E: Pairing> {
1443 comm_derefs: DerefsCommitment<E::G1>,
1444 poly_eval_network_proof: PolyEvalNetworkProof<E>,
1445}
1446
1447impl<E> SparseMatPolyEvalProof<E>
1448where
1449 E: Pairing,
1450 E::ScalarField: Absorb,
1451{
1452 fn equalize(
1453 rx: &[E::ScalarField],
1454 ry: &[E::ScalarField],
1455 ) -> (Vec<E::ScalarField>, Vec<E::ScalarField>) {
1456 match rx.len().cmp(&ry.len()) {
1457 Ordering::Less => {
1458 let diff = ry.len() - rx.len();
1459 let mut rx_ext = vec![E::ScalarField::zero(); diff];
1460 rx_ext.extend(rx);
1461 (rx_ext, ry.to_vec())
1462 }
1463 Ordering::Greater => {
1464 let diff = rx.len() - ry.len();
1465 let mut ry_ext = vec![E::ScalarField::zero(); diff];
1466 ry_ext.extend(ry);
1467 (rx.to_vec(), ry_ext)
1468 }
1469 Ordering::Equal => (rx.to_vec(), ry.to_vec()),
1470 }
1471 }
1472
1473 pub fn prove(
1474 dense: &MultiSparseMatPolynomialAsDense<E::ScalarField>,
1475 rx: &[E::ScalarField], // point at which the polynomial is evaluated
1476 ry: &[E::ScalarField],
1477 evals: &[E::ScalarField], // a vector evaluation of \widetilde{M}(r = (rx,ry)) for each M
1478 gens: &SparseMatPolyCommitmentGens<E>,
1479 transcript: &mut PoseidonTranscript<E::ScalarField>,
1480 ) -> SparseMatPolyEvalProof<E> {
1481 // transcript.append_protocol_name(SparseMatPolyEvalProof::protocol_name());
1482
1483 // ensure there is one eval for each polynomial in dense
1484 assert_eq!(evals.len(), dense.batch_size);
1485
1486 let (mem_rx, mem_ry) = {
1487 // equalize the lengths of rx and ry
1488 let (rx_ext, ry_ext) = SparseMatPolyEvalProof::<E>::equalize(rx, ry);
1489 let poly_rx = EqPolynomial::new(rx_ext).evals();
1490 let poly_ry = EqPolynomial::new(ry_ext).evals();
1491 (poly_rx, poly_ry)
1492 };
1493
1494 let derefs = dense.deref(&mem_rx, &mem_ry);
1495
1496 // commit to non-deterministic choices of the prover
1497 let timer_commit = Timer::new("commit_nondet_witness");
1498 let comm_derefs = {
1499 let comm = derefs.commit(&gens.gens_derefs);
1500 comm.write_to_transcript(transcript);
1501 comm
1502 };
1503 timer_commit.stop();
1504
1505 let poly_eval_network_proof = {
1506 // produce a random element from the transcript for hash function
1507 let r_mem_check = transcript.challenge_scalar_vec(b"", 2);
1508
1509 // build a network to evaluate the sparse polynomial
1510 let timer_build_network = Timer::new("build_layered_network");
1511 let mut net = PolyEvalNetwork::new(
1512 dense,
1513 &derefs,
1514 &mem_rx,
1515 &mem_ry,
1516 &(r_mem_check[0], r_mem_check[1]),
1517 );
1518 timer_build_network.stop();
1519
1520 let timer_eval_network = Timer::new("evalproof_layered_network");
1521 let poly_eval_network_proof =
1522 PolyEvalNetworkProof::prove(&mut net, dense, &derefs, evals, gens, transcript);
1523 timer_eval_network.stop();
1524
1525 poly_eval_network_proof
1526 };
1527
1528 SparseMatPolyEvalProof {
1529 comm_derefs,
1530 poly_eval_network_proof,
1531 }
1532 }
1533
1534 pub fn verify(
1535 &self,
1536 comm: &SparseMatPolyCommitment<E::G1>,
1537 rx: &[E::ScalarField], // point at which the polynomial is evaluated
1538 ry: &[E::ScalarField],
1539 evals: &[E::ScalarField], // evaluation of \widetilde{M}(r = (rx,ry))
1540 gens: &SparseMatPolyCommitmentGens<E>,
1541 transcript: &mut PoseidonTranscript<E::ScalarField>,
1542 ) -> Result<(), ProofVerifyError> {
1543 // transcript.append_protocol_name(SparseMatPolyEvalProof::protocol_name());
1544
1545 // equalize the lengths of rx and ry
1546 let (rx_ext, ry_ext) = SparseMatPolyEvalProof::<E>::equalize(rx, ry);
1547
1548 let (nz, num_mem_cells) = (comm.num_ops, comm.num_mem_cells);
1549 assert_eq!(rx_ext.len().pow2(), num_mem_cells);
1550
1551 // add claims to transcript and obtain challenges for randomized mem-check circuit
1552 self.comm_derefs.write_to_transcript(transcript);
1553
1554 // produce a random element from the transcript for hash function
1555 let r_mem_check = transcript.challenge_scalar_vec(b"", 2);
1556
1557 self.poly_eval_network_proof.verify(
1558 comm,
1559 &self.comm_derefs,
1560 evals,
1561 gens,
1562 &rx_ext,
1563 &ry_ext,
1564 &(r_mem_check[0], r_mem_check[1]),
1565 nz,
1566 transcript,
1567 )
1568 }
1569}
1570
1571#[derive(Clone)]
1572pub struct SparsePolyEntry<F: PrimeField> {
1573 pub idx: usize,
1574 pub val: F,
1575}
1576
1577impl<F: PrimeField> SparsePolyEntry<F> {
1578 pub fn new(idx: usize, val: F) -> Self {
1579 SparsePolyEntry { idx, val }
1580 }
1581}
1582#[derive(Clone)]
1583pub struct SparsePolynomial<F: PrimeField> {
1584 pub num_vars: usize,
1585 pub Z: Vec<SparsePolyEntry<F>>,
1586}
1587
1588impl<F: PrimeField> SparsePolynomial<F> {
1589 pub fn new(num_vars: usize, Z: Vec<SparsePolyEntry<F>>) -> Self {
1590 SparsePolynomial { num_vars, Z }
1591 }
1592
1593 // fn compute_chi(a: &[bool], r: &[F]) -> F {
1594 // assert_eq!(a.len(), r.len());
1595 // let mut chi_i = F::one();
1596 // for j in 0..r.len() {
1597 // if a[j] {
1598 // chi_i *= r[j];
1599 // } else {
1600 // chi_i *= F::one() - r[j];
1601 // }
1602 // }
1603 // chi_i
1604 // }
1605
1606 // // Takes O(n log n). TODO: do this in O(n) where n is the number of entries in Z
1607 // pub fn evaluate(&self, r: &[F]) -> F {
1608 // assert_eq!(self.num_vars, r.len());
1609
1610 // (0..self.Z.len())
1611 // .map(|i| {
1612 // let bits = self.Z[i].idx.get_bits(r.len());
1613 // println!("{:?}", bits);
1614 // SparsePolynomial::compute_chi(&bits, r) * self.Z[i].val
1615 // })
1616 // .sum()
1617 // }
1618}
1619
1620#[cfg(test)]
1621mod tests {
1622 use crate::parameters::poseidon_params;
1623
1624 use super::*;
1625 use ark_std::UniformRand;
1626 use rand::RngCore;
1627
1628 type F = ark_bls12_377::Fr;
1629 type E = ark_bls12_377::Bls12_377;
1630 #[test]
1631 fn check_sparse_polyeval_proof() {
1632 let mut rng = ark_std::rand::thread_rng();
1633
1634 let num_nz_entries: usize = 256;
1635 let num_rows: usize = 256;
1636 let num_cols: usize = 256;
1637 let num_vars_x: usize = num_rows.log_2();
1638 let num_vars_y: usize = num_cols.log_2();
1639
1640 let mut M: Vec<SparseMatEntry<F>> = Vec::new();
1641
1642 for _i in 0..num_nz_entries {
1643 M.push(SparseMatEntry::new(
1644 (rng.next_u64() % (num_rows as u64)) as usize,
1645 (rng.next_u64() % (num_cols as u64)) as usize,
1646 F::rand(&mut rng),
1647 ));
1648 }
1649
1650 let poly_M = SparseMatPolynomial::new(num_vars_x, num_vars_y, M);
1651 let gens = SparseMatPolyCommitmentGens::<E>::setup(
1652 b"gens_sparse_poly",
1653 num_vars_x,
1654 num_vars_y,
1655 num_nz_entries,
1656 3,
1657 );
1658
1659 // commitment
1660 let (poly_comm, dense) = SparseMatPolynomial::multi_commit(&[&poly_M, &poly_M, &poly_M], &gens);
1661
1662 // evaluation
1663 let rx: Vec<F> = (0..num_vars_x)
1664 .map(|_i| F::rand(&mut rng))
1665 .collect::<Vec<F>>();
1666 let ry: Vec<F> = (0..num_vars_y)
1667 .map(|_i| F::rand(&mut rng))
1668 .collect::<Vec<F>>();
1669 let eval = SparseMatPolynomial::multi_evaluate(&[&poly_M], &rx, &ry);
1670 let evals = vec![eval[0], eval[0], eval[0]];
1671
1672 let params = poseidon_params();
1673 let mut prover_transcript = PoseidonTranscript::new(¶ms);
1674 let proof =
1675 SparseMatPolyEvalProof::prove(&dense, &rx, &ry, &evals, &gens, &mut prover_transcript);
1676
1677 let mut verifier_transcript = PoseidonTranscript::new(¶ms);
1678 assert!(proof
1679 .verify(
1680 &poly_comm,
1681 &rx,
1682 &ry,
1683 &evals,
1684 &gens,
1685 &mut verifier_transcript,
1686 )
1687 .is_ok());
1688 }
1689}