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