testudo/src/sparse_mlpoly.rs
src/sparse_mlpoly.rsRaw
1use super::dense_mlpoly::DensePolynomial;
2use super::dense_mlpoly::{
3 EqPolynomial, IdentityPolynomial, PolyCommitment, PolyCommitmentGens, PolyEvalProof,
4};
5use super::errors::ProofVerifyError;
6use super::math::Math;
7use super::product_tree::{DotProductCircuit, ProductCircuit, ProductCircuitEvalProofBatched};
8use super::scalar::Scalar;
9use super::timer::Timer;
10use super::transcript::{AppendToTranscript, ProofTranscript};
11use merlin::Transcript;
12use serde::{Deserialize, Serialize};
13
14#[derive(Debug)]
15pub struct SparseMatEntry {
16 row: usize,
17 col: usize,
18 val: Scalar,
19}
20
21impl SparseMatEntry {
22 pub fn new(row: usize, col: usize, val: Scalar) -> Self {
23 SparseMatEntry { row, col, val }
24 }
25}
26
27#[derive(Debug)]
28pub struct SparseMatPolynomial {
29 num_vars_x: usize,
30 num_vars_y: usize,
31 M: Vec<SparseMatEntry>,
32}
33
34pub struct Derefs {
35 row_ops_val: Vec<DensePolynomial>,
36 col_ops_val: Vec<DensePolynomial>,
37 comb: DensePolynomial,
38}
39
40#[derive(Debug, Serialize, Deserialize)]
41pub struct DerefsCommitment {
42 comm_ops_val: PolyCommitment,
43}
44
45impl Derefs {
46 pub fn new(row_ops_val: Vec<DensePolynomial>, col_ops_val: Vec<DensePolynomial>) -> Self {
47 assert_eq!(row_ops_val.len(), col_ops_val.len());
48
49 // combine all polynomials into a single polynomial (used below to produce a single commitment)
50 let comb = DensePolynomial::merge(row_ops_val.iter().chain(col_ops_val.iter()));
51
52 Derefs {
53 row_ops_val,
54 col_ops_val,
55 comb,
56 }
57 }
58
59 pub fn commit(&self, gens: &PolyCommitmentGens) -> DerefsCommitment {
60 let (comm_ops_val, _blinds) = self.comb.commit(false, gens, None);
61 DerefsCommitment { comm_ops_val }
62 }
63}
64
65#[derive(Debug, Serialize, Deserialize)]
66pub struct DerefsEvalProof {
67 proof_derefs: PolyEvalProof,
68}
69
70impl DerefsEvalProof {
71 fn protocol_name() -> &'static [u8] {
72 b"Derefs evaluation proof"
73 }
74
75 fn prove_single(
76 joint_poly: &DensePolynomial,
77 r: &Vec<Scalar>,
78 evals: Vec<Scalar>,
79 gens: &PolyCommitmentGens,
80 transcript: &mut Transcript,
81 random_tape: &mut Transcript,
82 ) -> PolyEvalProof {
83 assert_eq!(joint_poly.get_num_vars(), r.len() + evals.len().log2());
84
85 // append the claimed evaluations to transcript
86 evals.append_to_transcript(b"evals_ops_val", transcript);
87
88 // n-to-1 reduction
89 let challenges = transcript.challenge_vector(b"challenge_combine_n_to_one", evals.len().log2());
90 let mut poly_evals = DensePolynomial::new(evals);
91 for i in (0..challenges.len()).rev() {
92 poly_evals.bound_poly_var_bot(&challenges[i]);
93 }
94 assert_eq!(poly_evals.len(), 1);
95 let joint_claim_eval = poly_evals[0];
96 let mut r_joint = challenges;
97 r_joint.extend(r);
98
99 debug_assert_eq!(joint_poly.evaluate(&r_joint), joint_claim_eval);
100
101 // decommit the joint polynomial at r_joint
102 joint_claim_eval.append_to_transcript(b"joint_claim_eval", transcript);
103 let (proof_derefs, _comm_derefs_eval) = PolyEvalProof::prove(
104 joint_poly,
105 None,
106 &r_joint,
107 &joint_claim_eval,
108 None,
109 gens,
110 transcript,
111 random_tape,
112 );
113
114 proof_derefs
115 }
116
117 // evalues both polynomials at r and produces a joint proof of opening
118 pub fn prove(
119 derefs: &Derefs,
120 eval_row_ops_val_vec: &Vec<Scalar>,
121 eval_col_ops_val_vec: &Vec<Scalar>,
122 r: &Vec<Scalar>,
123 gens: &PolyCommitmentGens,
124 transcript: &mut Transcript,
125 random_tape: &mut Transcript,
126 ) -> Self {
127 transcript.append_protocol_name(DerefsEvalProof::protocol_name());
128
129 let mut evals = eval_row_ops_val_vec.clone();
130 evals.extend(eval_col_ops_val_vec);
131 evals.resize(evals.len().next_power_of_two(), Scalar::zero());
132
133 let proof_derefs =
134 DerefsEvalProof::prove_single(&derefs.comb, r, evals, gens, transcript, random_tape);
135
136 DerefsEvalProof { proof_derefs }
137 }
138
139 fn verify_single(
140 proof: &PolyEvalProof,
141 comm: &PolyCommitment,
142 r: &Vec<Scalar>,
143 evals: Vec<Scalar>,
144 gens: &PolyCommitmentGens,
145 transcript: &mut Transcript,
146 ) -> Result<(), ProofVerifyError> {
147 // append the claimed evaluations to transcript
148 evals.append_to_transcript(b"evals_ops_val", transcript);
149
150 // n-to-1 reduction
151 let challenges = transcript.challenge_vector(b"challenge_combine_n_to_one", evals.len().log2());
152 let mut poly_evals = DensePolynomial::new(evals);
153 for i in (0..challenges.len()).rev() {
154 poly_evals.bound_poly_var_bot(&challenges[i]);
155 }
156 assert_eq!(poly_evals.len(), 1);
157 let joint_claim_eval = poly_evals[0];
158 let mut r_joint = challenges;
159 r_joint.extend(r);
160
161 // decommit the joint polynomial at r_joint
162 joint_claim_eval.append_to_transcript(b"joint_claim_eval", transcript);
163 assert!(proof
164 .verify_plain(gens, transcript, &r_joint, &joint_claim_eval, &comm)
165 .is_ok());
166
167 Ok(())
168 }
169
170 // verify evaluations of both polynomials at r
171 pub fn verify(
172 &self,
173 r: &Vec<Scalar>,
174 eval_row_ops_val_vec: &Vec<Scalar>,
175 eval_col_ops_val_vec: &Vec<Scalar>,
176 gens: &PolyCommitmentGens,
177 comm: &DerefsCommitment,
178 transcript: &mut Transcript,
179 ) -> Result<(), ProofVerifyError> {
180 transcript.append_protocol_name(DerefsEvalProof::protocol_name());
181 let mut evals = eval_row_ops_val_vec.clone();
182 evals.extend(eval_col_ops_val_vec);
183 evals.resize(evals.len().next_power_of_two(), Scalar::zero());
184
185 assert!(DerefsEvalProof::verify_single(
186 &self.proof_derefs,
187 &comm.comm_ops_val,
188 r,
189 evals,
190 gens,
191 transcript,
192 )
193 .is_ok());
194
195 Ok(())
196 }
197}
198
199impl AppendToTranscript for DerefsCommitment {
200 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
201 transcript.append_message(b"derefs_commitment", b"begin_derefs_commitment");
202 self.comm_ops_val.append_to_transcript(label, transcript);
203 transcript.append_message(b"derefs_commitment", b"end_derefs_commitment");
204 }
205}
206
207struct AddrTimestamps {
208 ops_addr_usize: Vec<Vec<usize>>,
209 ops_addr: Vec<DensePolynomial>,
210 read_ts: Vec<DensePolynomial>,
211 audit_ts: DensePolynomial,
212}
213
214impl AddrTimestamps {
215 pub fn new(num_cells: usize, num_ops: usize, ops_addr: Vec<Vec<usize>>) -> Self {
216 for i in 0..ops_addr.len() {
217 assert_eq!(ops_addr[i].len(), num_ops);
218 }
219
220 let mut audit_ts = vec![0usize; num_cells];
221 let mut ops_addr_vec: Vec<DensePolynomial> = Vec::new();
222 let mut read_ts_vec: Vec<DensePolynomial> = Vec::new();
223 for i in 0..ops_addr.len() {
224 let ops_addr_inst = &ops_addr[i];
225 let mut read_ts = vec![0usize; num_ops];
226
227 // since read timestamps are trustworthy, we can simply increment the r-ts to obtain a w-ts
228 // this is sufficient to ensure that the write-set, consisting of (addr, val, ts) tuples, is a set
229 for i in 0..num_ops {
230 let addr = ops_addr_inst[i];
231 assert!(addr < num_cells);
232 let r_ts = audit_ts[addr];
233 read_ts[i] = r_ts;
234
235 let w_ts = r_ts + 1;
236 audit_ts[addr] = w_ts;
237 }
238
239 ops_addr_vec.push(DensePolynomial::from_usize(&ops_addr_inst));
240 read_ts_vec.push(DensePolynomial::from_usize(&read_ts));
241 }
242
243 AddrTimestamps {
244 ops_addr: ops_addr_vec,
245 ops_addr_usize: ops_addr,
246 read_ts: read_ts_vec,
247 audit_ts: DensePolynomial::from_usize(&audit_ts),
248 }
249 }
250
251 fn deref_mem(addr: &Vec<usize>, mem_val: &Vec<Scalar>) -> DensePolynomial {
252 DensePolynomial::new(
253 (0..addr.len())
254 .map(|i| {
255 let a = addr[i];
256 mem_val[a]
257 })
258 .collect::<Vec<Scalar>>(),
259 )
260 }
261
262 pub fn deref(&self, mem_val: &Vec<Scalar>) -> Vec<DensePolynomial> {
263 (0..self.ops_addr.len())
264 .map(|i| AddrTimestamps::deref_mem(&self.ops_addr_usize[i], mem_val))
265 .collect::<Vec<DensePolynomial>>()
266 }
267}
268
269pub struct MultiSparseMatPolynomialAsDense {
270 batch_size: usize,
271 val: Vec<DensePolynomial>,
272 row: AddrTimestamps,
273 col: AddrTimestamps,
274 comb_ops: DensePolynomial,
275 comb_mem: DensePolynomial,
276}
277
278#[derive(Debug)]
279pub struct SparseMatPolynomialSize {
280 size_ops: usize,
281 size_mem: usize,
282 size_derefs: usize,
283}
284
285impl PartialEq for SparseMatPolynomialSize {
286 #[inline]
287 fn eq(&self, other: &Self) -> bool {
288 self.size_derefs == other.size_derefs
289 && self.size_mem == other.size_mem
290 && self.size_ops == other.size_ops
291 }
292}
293
294pub struct SparseMatPolyCommitmentGens {
295 gens_ops: PolyCommitmentGens,
296 gens_mem: PolyCommitmentGens,
297 gens_derefs: PolyCommitmentGens,
298}
299
300impl SparseMatPolyCommitmentGens {
301 pub fn new(
302 size: &SparseMatPolynomialSize,
303 batch_size: usize,
304 label: &'static [u8],
305 ) -> SparseMatPolyCommitmentGens {
306 let num_vars_ops = size.size_ops + (batch_size * 5).next_power_of_two().log2();
307 let num_vars_mem = size.size_mem + 1;
308 let num_vars_derefs = size.size_derefs + (batch_size * 1).next_power_of_two().log2();
309
310 let gens_ops = PolyCommitmentGens::new(num_vars_ops, label);
311 let gens_mem = PolyCommitmentGens::new(num_vars_mem, label);
312 let gens_derefs = PolyCommitmentGens::new(num_vars_derefs, label);
313 SparseMatPolyCommitmentGens {
314 gens_ops,
315 gens_mem,
316 gens_derefs,
317 }
318 }
319}
320
321#[derive(Debug, Serialize, Deserialize)]
322pub struct SparseMatPolyCommitment {
323 batch_size: usize,
324 num_ops: usize,
325 num_mem_cells: usize,
326 comm_comb_ops: PolyCommitment,
327 comm_comb_mem: PolyCommitment,
328}
329
330impl SparseMatPolynomial {
331 pub fn new(num_vars_x: usize, num_vars_y: usize, M: Vec<SparseMatEntry>) -> Self {
332 SparseMatPolynomial {
333 num_vars_x,
334 num_vars_y,
335 M,
336 }
337 }
338
339 pub fn get_num_nz_entries(&self) -> usize {
340 self.M.len().next_power_of_two()
341 }
342
343 fn sparse_to_dense_vecs(&self, N: usize) -> (Vec<usize>, Vec<usize>, Vec<Scalar>) {
344 assert!(N >= self.get_num_nz_entries());
345 let mut ops_row: Vec<usize> = vec![0; N];
346 let mut ops_col: Vec<usize> = vec![0; N];
347 let mut val: Vec<Scalar> = vec![Scalar::zero(); N];
348
349 for i in 0..self.M.len() {
350 ops_row[i] = self.M[i].row;
351 ops_col[i] = self.M[i].col;
352 val[i] = self.M[i].val;
353 }
354 (ops_row, ops_col, val)
355 }
356
357 fn multi_sparse_to_dense_rep(
358 sparse_polys: &Vec<&SparseMatPolynomial>,
359 ) -> MultiSparseMatPolynomialAsDense {
360 assert!(sparse_polys.len() > 0);
361 for i in 1..sparse_polys.len() {
362 assert_eq!(sparse_polys[i].num_vars_x, sparse_polys[0].num_vars_x);
363 assert_eq!(sparse_polys[i].num_vars_y, sparse_polys[0].num_vars_y);
364 }
365
366 let N = (0..sparse_polys.len())
367 .map(|i| sparse_polys[i].get_num_nz_entries())
368 .max()
369 .unwrap();
370
371 let mut ops_row_vec: Vec<Vec<usize>> = Vec::new();
372 let mut ops_col_vec: Vec<Vec<usize>> = Vec::new();
373 let mut val_vec: Vec<DensePolynomial> = Vec::new();
374 for poly in sparse_polys {
375 let (ops_row, ops_col, val) = poly.sparse_to_dense_vecs(N);
376 ops_row_vec.push(ops_row);
377 ops_col_vec.push(ops_col);
378 val_vec.push(DensePolynomial::new(val));
379 }
380
381 let any_poly = &sparse_polys[0];
382
383 let num_mem_cells = if any_poly.num_vars_x > any_poly.num_vars_y {
384 any_poly.num_vars_x.pow2()
385 } else {
386 any_poly.num_vars_y.pow2()
387 };
388
389 let row = AddrTimestamps::new(num_mem_cells, N, ops_row_vec);
390 let col = AddrTimestamps::new(num_mem_cells, N, ops_col_vec);
391
392 // combine polynomials into a single polynomial for commitment purposes
393 let comb_ops = DensePolynomial::merge(
394 row
395 .ops_addr
396 .iter()
397 .chain(row.read_ts.iter())
398 .chain(col.ops_addr.iter())
399 .chain(col.read_ts.iter())
400 .chain(val_vec.iter()),
401 );
402 let mut comb_mem = row.audit_ts.clone();
403 comb_mem.extend(&col.audit_ts);
404
405 MultiSparseMatPolynomialAsDense {
406 batch_size: sparse_polys.len(),
407 row,
408 col,
409 val: val_vec,
410 comb_ops,
411 comb_mem,
412 }
413 }
414
415 pub fn size(&self) -> SparseMatPolynomialSize {
416 let dense = SparseMatPolynomial::multi_sparse_to_dense_rep(&vec![&self]);
417
418 assert_eq!(dense.col.audit_ts.len(), dense.row.audit_ts.len());
419
420 SparseMatPolynomialSize {
421 size_mem: dense.row.audit_ts.get_num_vars(),
422 size_ops: dense.row.read_ts[0].get_num_vars(),
423 size_derefs: dense.row.read_ts[0].get_num_vars() + 1,
424 }
425 }
426
427 pub fn evaluate_with_tables(
428 &self,
429 eval_table_rx: &Vec<Scalar>,
430 eval_table_ry: &Vec<Scalar>,
431 ) -> 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: &Vec<Scalar>, ry: &Vec<Scalar>) -> Scalar {
446 let eval_table_rx = EqPolynomial::new(rx.clone()).evals();
447 let eval_table_ry = EqPolynomial::new(ry.clone()).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: &Vec<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: &Vec<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: &Vec<&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: &Vec<Scalar>, col_mem_val: &Vec<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: &Vec<Scalar>,
551 addrs_vec: &Vec<DensePolynomial>,
552 derefs_vec: &Vec<DensePolynomial>,
553 read_ts_vec: &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: &Vec<Scalar>,
628 addr_timestamps: &AddrTimestamps,
629 poly_ops_val: &Vec<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: &Vec<Scalar>,
694 mem_ry: &Vec<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 Transcript,
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();
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();
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: &Vec<Scalar>,
864 eval_ops_addr: &Vec<Scalar>,
865 eval_read_ts: &Vec<Scalar>,
866 eval_audit_ts: &Scalar,
867 r: &Vec<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.clone()).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: &Vec<Scalar>,
918 comm: &SparseMatPolyCommitment,
919 gens: &SparseMatPolyCommitmentGens,
920 comm_derefs: &DerefsCommitment,
921 rx: &Vec<Scalar>,
922 ry: &Vec<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: &Vec<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: &Vec<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 &vec![
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: &Vec<Scalar>,
1362 gens: &SparseMatPolyCommitmentGens,
1363 transcript: &mut Transcript,
1364 random_tape: &mut Transcript,
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: &Vec<Scalar>,
1398 gens: &SparseMatPolyCommitmentGens,
1399 rx: &Vec<Scalar>,
1400 ry: &Vec<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: &Vec<Scalar>, ry: &Vec<Scalar>) -> (Vec<Scalar>, Vec<Scalar>) {
1474 if rx.len() < ry.len() {
1475 let diff = ry.len() - rx.len();
1476 let mut rx_ext = vec![Scalar::zero(); diff];
1477 rx_ext.extend(rx);
1478 (rx_ext, ry.clone())
1479 } else if rx.len() > ry.len() {
1480 let diff = rx.len() - ry.len();
1481 let mut ry_ext = vec![Scalar::zero(); diff];
1482 ry_ext.extend(ry);
1483 (rx.clone(), ry_ext)
1484 } else {
1485 (rx.clone(), ry.clone())
1486 }
1487 }
1488
1489 pub fn prove(
1490 dense: &MultiSparseMatPolynomialAsDense,
1491 rx: &Vec<Scalar>, // point at which the polynomial is evaluated
1492 ry: &Vec<Scalar>,
1493 evals: &Vec<Scalar>, // a vector evaluation of \widetilde{M}(r = (rx,ry)) for each M
1494 gens: &SparseMatPolyCommitmentGens,
1495 transcript: &mut Transcript,
1496 random_tape: &mut Transcript,
1497 ) -> SparseMatPolyEvalProof {
1498 transcript.append_protocol_name(SparseMatPolyEvalProof::protocol_name());
1499
1500 // ensure there is one eval for each polynomial in dense
1501 assert_eq!(evals.len(), dense.batch_size);
1502
1503 let (mem_rx, mem_ry) = {
1504 // equalize the lengths of rx and ry
1505 let (rx_ext, ry_ext) = SparseMatPolyEvalProof::equalize(rx, ry);
1506 let poly_rx = EqPolynomial::new(rx_ext).evals();
1507 let poly_ry = EqPolynomial::new(ry_ext).evals();
1508 (poly_rx, poly_ry)
1509 };
1510
1511 let derefs = dense.deref(&mem_rx, &mem_ry);
1512
1513 // commit to non-deterministic choices of the prover
1514 let timer_commit = Timer::new("commit_nondet_witness");
1515 let comm_derefs = {
1516 let comm = derefs.commit(&gens.gens_derefs);
1517 comm.append_to_transcript(b"comm_poly_row_col_ops_val", transcript);
1518 comm
1519 };
1520 timer_commit.stop();
1521
1522 let poly_eval_network_proof = {
1523 // produce a random element from the transcript for hash function
1524 let r_mem_check = transcript.challenge_vector(b"challenge_r_hash", 2);
1525
1526 // build a network to evaluate the sparse polynomial
1527 let timer_build_network = Timer::new("build_layered_network");
1528 let mut net = PolyEvalNetwork::new(
1529 dense,
1530 &derefs,
1531 &mem_rx,
1532 &mem_ry,
1533 &(r_mem_check[0], r_mem_check[1]),
1534 );
1535 timer_build_network.stop();
1536
1537 let timer_eval_network = Timer::new("evalproof_layered_network");
1538 let poly_eval_network_proof = PolyEvalNetworkProof::prove(
1539 &mut net,
1540 &dense,
1541 &derefs,
1542 evals,
1543 gens,
1544 transcript,
1545 random_tape,
1546 );
1547 timer_eval_network.stop();
1548
1549 poly_eval_network_proof
1550 };
1551
1552 SparseMatPolyEvalProof {
1553 comm_derefs,
1554 poly_eval_network_proof,
1555 }
1556 }
1557
1558 pub fn verify(
1559 &self,
1560 comm: &SparseMatPolyCommitment,
1561 rx: &Vec<Scalar>, // point at which the polynomial is evaluated
1562 ry: &Vec<Scalar>,
1563 evals: &Vec<Scalar>, // evaluation of \widetilde{M}(r = (rx,ry))
1564 gens: &SparseMatPolyCommitmentGens,
1565 transcript: &mut Transcript,
1566 ) -> Result<(), ProofVerifyError> {
1567 transcript.append_protocol_name(SparseMatPolyEvalProof::protocol_name());
1568
1569 // equalize the lengths of rx and ry
1570 let (rx_ext, ry_ext) = SparseMatPolyEvalProof::equalize(rx, ry);
1571
1572 let (nz, num_mem_cells) = (comm.num_ops, comm.num_mem_cells);
1573 assert_eq!(rx_ext.len().pow2(), num_mem_cells);
1574
1575 // add claims to transcript and obtain challenges for randomized mem-check circuit
1576 self
1577 .comm_derefs
1578 .append_to_transcript(b"comm_poly_row_col_ops_val", transcript);
1579
1580 // produce a random element from the transcript for hash function
1581 let r_mem_check = transcript.challenge_vector(b"challenge_r_hash", 2);
1582
1583 assert!(self
1584 .poly_eval_network_proof
1585 .verify(
1586 comm,
1587 &self.comm_derefs,
1588 evals,
1589 gens,
1590 &rx_ext,
1591 &ry_ext,
1592 &(r_mem_check[0], r_mem_check[1]),
1593 nz,
1594 transcript,
1595 )
1596 .is_ok());
1597
1598 Ok(())
1599 }
1600}
1601
1602pub struct SparsePolyEntry {
1603 idx: usize,
1604 val: Scalar,
1605}
1606
1607impl SparsePolyEntry {
1608 pub fn new(idx: usize, val: Scalar) -> Self {
1609 SparsePolyEntry { idx, val }
1610 }
1611}
1612
1613pub struct SparsePolynomial {
1614 num_vars: usize,
1615 Z: Vec<SparsePolyEntry>,
1616}
1617
1618impl SparsePolynomial {
1619 pub fn new(num_vars: usize, Z: Vec<SparsePolyEntry>) -> Self {
1620 SparsePolynomial { num_vars, Z }
1621 }
1622
1623 fn compute_chi(a: &Vec<bool>, r: &Vec<Scalar>) -> Scalar {
1624 assert_eq!(a.len(), r.len());
1625 let mut chi_i = Scalar::one();
1626 for j in 0..r.len() {
1627 if a[j] {
1628 chi_i *= r[j];
1629 } else {
1630 chi_i *= Scalar::one() - r[j];
1631 }
1632 }
1633 chi_i
1634 }
1635
1636 // Takes O(n log n). TODO: do this in O(n) where n is the number of entries in Z
1637 pub fn evaluate(&self, r: &Vec<Scalar>) -> Scalar {
1638 assert_eq!(self.num_vars, r.len());
1639
1640 (0..self.Z.len())
1641 .map(|i| {
1642 let bits = self.Z[i].idx.get_bits(r.len());
1643 SparsePolynomial::compute_chi(&bits, r) * self.Z[i].val
1644 })
1645 .sum()
1646 }
1647}
1648
1649#[cfg(test)]
1650mod tests {
1651 use super::*;
1652 use rand::rngs::OsRng;
1653 use rand::RngCore;
1654 #[test]
1655 fn check_sparse_polyeval_proof() {
1656 let mut csprng: OsRng = OsRng;
1657
1658 let num_nz_entries = 256;
1659 let num_rows = 256;
1660 let num_cols = 256;
1661 let num_vars_x = num_rows.log2();
1662 let num_vars_y = num_cols.log2();
1663
1664 let mut M: Vec<SparseMatEntry> = Vec::new();
1665
1666 for _i in 0..num_nz_entries {
1667 M.push(SparseMatEntry::new(
1668 (csprng.next_u64() % (num_rows as u64)) as usize,
1669 (csprng.next_u64() % (num_cols as u64)) as usize,
1670 Scalar::random(&mut csprng),
1671 ));
1672 }
1673
1674 let poly_M = SparseMatPolynomial::new(num_vars_x, num_vars_y, M);
1675 let poly_M_size = poly_M.size();
1676 let gens = SparseMatPolyCommitmentGens::new(&poly_M_size, 3, b"gens_sparse_poly");
1677
1678 // commitment
1679 let (poly_comm, dense) =
1680 SparseMatPolynomial::multi_commit(&vec![&poly_M, &poly_M, &poly_M], &gens);
1681
1682 // evaluation
1683 let rx: Vec<Scalar> = (0..num_vars_x)
1684 .map(|_i| Scalar::random(&mut csprng))
1685 .collect::<Vec<Scalar>>();
1686 let ry: Vec<Scalar> = (0..num_vars_y)
1687 .map(|_i| Scalar::random(&mut csprng))
1688 .collect::<Vec<Scalar>>();
1689 let eval = poly_M.evaluate(&rx, &ry);
1690 let evals = vec![eval, eval, eval];
1691
1692 let mut random_tape = {
1693 let mut csprng: OsRng = OsRng;
1694 let mut tape = Transcript::new(b"proof");
1695 tape.append_scalar(b"init_randomness", &Scalar::random(&mut csprng));
1696 tape
1697 };
1698 let mut prover_transcript = Transcript::new(b"example");
1699 let proof = SparseMatPolyEvalProof::prove(
1700 &dense,
1701 &rx,
1702 &ry,
1703 &evals,
1704 &gens,
1705 &mut prover_transcript,
1706 &mut random_tape,
1707 );
1708
1709 let mut verifier_transcript = Transcript::new(b"example");
1710 assert!(proof
1711 .verify(
1712 &poly_comm,
1713 &rx,
1714 &ry,
1715 &evals,
1716 &gens,
1717 &mut verifier_transcript,
1718 )
1719 .is_ok());
1720 }
1721}