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