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