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