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