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, Serialize, Deserialize)]
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, Serialize, Deserialize)]
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
182 proof.verify_plain(gens, transcript, &r_joint, &joint_claim_eval, comm)
183 }
184
185 // verify evaluations of both polynomials at r
186 pub fn verify(
187 &self,
188 r: &[Scalar],
189 eval_row_ops_val_vec: &[Scalar],
190 eval_col_ops_val_vec: &[Scalar],
191 gens: &PolyCommitmentGens,
192 comm: &DerefsCommitment,
193 transcript: &mut Transcript,
194 ) -> Result<(), ProofVerifyError> {
195 transcript.append_protocol_name(DerefsEvalProof::protocol_name());
196 let mut evals = eval_row_ops_val_vec.to_owned();
197 evals.extend(eval_col_ops_val_vec);
198 evals.resize(evals.len().next_power_of_two(), Scalar::zero());
199
200 DerefsEvalProof::verify_single(
201 &self.proof_derefs,
202 &comm.comm_ops_val,
203 r,
204 evals,
205 gens,
206 transcript,
207 )
208 }
209}
210
211impl AppendToTranscript for DerefsCommitment {
212 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
213 transcript.append_message(b"derefs_commitment", b"begin_derefs_commitment");
214 self.comm_ops_val.append_to_transcript(label, transcript);
215 transcript.append_message(b"derefs_commitment", b"end_derefs_commitment");
216 }
217}
218
219struct AddrTimestamps {
220 ops_addr_usize: Vec<Vec<usize>>,
221 ops_addr: Vec<DensePolynomial>,
222 read_ts: Vec<DensePolynomial>,
223 audit_ts: DensePolynomial,
224}
225
226impl AddrTimestamps {
227 pub fn new(num_cells: usize, num_ops: usize, ops_addr: Vec<Vec<usize>>) -> Self {
228 for item in ops_addr.iter() {
229 assert_eq!(item.len(), num_ops);
230 }
231
232 let mut audit_ts = vec![0usize; num_cells];
233 let mut ops_addr_vec: Vec<DensePolynomial> = Vec::new();
234 let mut read_ts_vec: Vec<DensePolynomial> = Vec::new();
235 for ops_addr_inst in ops_addr.iter() {
236 let mut read_ts = vec![0usize; num_ops];
237
238 // since read timestamps are trustworthy, we can simply increment the r-ts to obtain a w-ts
239 // this is sufficient to ensure that the write-set, consisting of (addr, val, ts) tuples, is a set
240 for i in 0..num_ops {
241 let addr = ops_addr_inst[i];
242 assert!(addr < num_cells);
243 let r_ts = audit_ts[addr];
244 read_ts[i] = r_ts;
245
246 let w_ts = r_ts + 1;
247 audit_ts[addr] = w_ts;
248 }
249
250 ops_addr_vec.push(DensePolynomial::from_usize(ops_addr_inst));
251 read_ts_vec.push(DensePolynomial::from_usize(&read_ts));
252 }
253
254 AddrTimestamps {
255 ops_addr: ops_addr_vec,
256 ops_addr_usize: ops_addr,
257 read_ts: read_ts_vec,
258 audit_ts: DensePolynomial::from_usize(&audit_ts),
259 }
260 }
261
262 fn deref_mem(addr: &[usize], mem_val: &[Scalar]) -> DensePolynomial {
263 DensePolynomial::new(
264 (0..addr.len())
265 .map(|i| {
266 let a = addr[i];
267 mem_val[a]
268 })
269 .collect::<Vec<Scalar>>(),
270 )
271 }
272
273 pub fn deref(&self, mem_val: &[Scalar]) -> Vec<DensePolynomial> {
274 (0..self.ops_addr.len())
275 .map(|i| AddrTimestamps::deref_mem(&self.ops_addr_usize[i], mem_val))
276 .collect::<Vec<DensePolynomial>>()
277 }
278}
279
280pub struct MultiSparseMatPolynomialAsDense {
281 batch_size: usize,
282 val: Vec<DensePolynomial>,
283 row: AddrTimestamps,
284 col: AddrTimestamps,
285 comb_ops: DensePolynomial,
286 comb_mem: DensePolynomial,
287}
288
289pub struct SparseMatPolyCommitmentGens {
290 gens_ops: PolyCommitmentGens,
291 gens_mem: PolyCommitmentGens,
292 gens_derefs: PolyCommitmentGens,
293}
294
295impl SparseMatPolyCommitmentGens {
296 pub fn new(
297 label: &'static [u8],
298 num_vars_x: usize,
299 num_vars_y: usize,
300 num_nz_entries: usize,
301 batch_size: usize,
302 ) -> SparseMatPolyCommitmentGens {
303 let num_vars_ops = num_nz_entries.next_power_of_two().log2() as usize
304 + (batch_size * 5).next_power_of_two().log2() as usize;
305 let num_vars_mem = if num_vars_x > num_vars_y {
306 num_vars_x
307 } else {
308 num_vars_y
309 } + 1;
310 let num_vars_derefs = num_nz_entries.next_power_of_two().log2() as usize
311 + (batch_size * 2).next_power_of_two().log2() as usize;
312
313 let gens_ops = PolyCommitmentGens::new(num_vars_ops, label);
314 let gens_mem = PolyCommitmentGens::new(num_vars_mem, label);
315 let gens_derefs = PolyCommitmentGens::new(num_vars_derefs, label);
316 SparseMatPolyCommitmentGens {
317 gens_ops,
318 gens_mem,
319 gens_derefs,
320 }
321 }
322}
323
324#[derive(Debug, Serialize, Deserialize)]
325pub struct SparseMatPolyCommitment {
326 batch_size: usize,
327 num_ops: usize,
328 num_mem_cells: usize,
329 comm_comb_ops: PolyCommitment,
330 comm_comb_mem: PolyCommitment,
331}
332
333impl AppendToTranscript for SparseMatPolyCommitment {
334 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
335 transcript.append_u64(b"batch_size", self.batch_size as u64);
336 transcript.append_u64(b"num_ops", self.num_ops as u64);
337 transcript.append_u64(b"num_mem_cells", self.num_mem_cells as u64);
338 self
339 .comm_comb_ops
340 .append_to_transcript(b"comm_comb_ops", transcript);
341 self
342 .comm_comb_mem
343 .append_to_transcript(b"comm_comb_mem", transcript);
344 }
345}
346
347impl SparseMatPolynomial {
348 pub fn new(num_vars_x: usize, num_vars_y: usize, M: Vec<SparseMatEntry>) -> Self {
349 SparseMatPolynomial {
350 num_vars_x,
351 num_vars_y,
352 M,
353 }
354 }
355
356 pub fn get_num_nz_entries(&self) -> usize {
357 self.M.len().next_power_of_two()
358 }
359
360 fn sparse_to_dense_vecs(&self, N: usize) -> (Vec<usize>, Vec<usize>, Vec<Scalar>) {
361 assert!(N >= self.get_num_nz_entries());
362 let mut ops_row: Vec<usize> = vec![0; N];
363 let mut ops_col: Vec<usize> = vec![0; N];
364 let mut val: Vec<Scalar> = vec![Scalar::zero(); N];
365
366 for i in 0..self.M.len() {
367 ops_row[i] = self.M[i].row;
368 ops_col[i] = self.M[i].col;
369 val[i] = self.M[i].val;
370 }
371 (ops_row, ops_col, val)
372 }
373
374 fn multi_sparse_to_dense_rep(
375 sparse_polys: &[&SparseMatPolynomial],
376 ) -> MultiSparseMatPolynomialAsDense {
377 assert!(!sparse_polys.is_empty());
378 for i in 1..sparse_polys.len() {
379 assert_eq!(sparse_polys[i].num_vars_x, sparse_polys[0].num_vars_x);
380 assert_eq!(sparse_polys[i].num_vars_y, sparse_polys[0].num_vars_y);
381 }
382
383 let N = (0..sparse_polys.len())
384 .map(|i| sparse_polys[i].get_num_nz_entries())
385 .max()
386 .unwrap()
387 .next_power_of_two();
388
389 let mut ops_row_vec: Vec<Vec<usize>> = Vec::new();
390 let mut ops_col_vec: Vec<Vec<usize>> = Vec::new();
391 let mut val_vec: Vec<DensePolynomial> = Vec::new();
392 for poly in sparse_polys {
393 let (ops_row, ops_col, val) = poly.sparse_to_dense_vecs(N);
394 ops_row_vec.push(ops_row);
395 ops_col_vec.push(ops_col);
396 val_vec.push(DensePolynomial::new(val));
397 }
398
399 let any_poly = &sparse_polys[0];
400
401 let num_mem_cells = if any_poly.num_vars_x > any_poly.num_vars_y {
402 any_poly.num_vars_x.pow2()
403 } else {
404 any_poly.num_vars_y.pow2()
405 };
406
407 let row = AddrTimestamps::new(num_mem_cells, N, ops_row_vec);
408 let col = AddrTimestamps::new(num_mem_cells, N, ops_col_vec);
409
410 // combine polynomials into a single polynomial for commitment purposes
411 let comb_ops = DensePolynomial::merge(
412 row
413 .ops_addr
414 .iter()
415 .chain(row.read_ts.iter())
416 .chain(col.ops_addr.iter())
417 .chain(col.read_ts.iter())
418 .chain(val_vec.iter()),
419 );
420 let mut comb_mem = row.audit_ts.clone();
421 comb_mem.extend(&col.audit_ts);
422
423 MultiSparseMatPolynomialAsDense {
424 batch_size: sparse_polys.len(),
425 row,
426 col,
427 val: val_vec,
428 comb_ops,
429 comb_mem,
430 }
431 }
432
433 fn evaluate_with_tables(&self, eval_table_rx: &[Scalar], eval_table_ry: &[Scalar]) -> Scalar {
434 assert_eq!(self.num_vars_x.pow2(), eval_table_rx.len());
435 assert_eq!(self.num_vars_y.pow2(), eval_table_ry.len());
436
437 (0..self.M.len())
438 .map(|i| {
439 let row = self.M[i].row;
440 let col = self.M[i].col;
441 let val = &self.M[i].val;
442 eval_table_rx[row] * eval_table_ry[col] * val
443 })
444 .sum()
445 }
446
447 pub fn multi_evaluate(
448 polys: &[&SparseMatPolynomial],
449 rx: &[Scalar],
450 ry: &[Scalar],
451 ) -> Vec<Scalar> {
452 let eval_table_rx = EqPolynomial::new(rx.to_vec()).evals();
453 let eval_table_ry = EqPolynomial::new(ry.to_vec()).evals();
454
455 (0..polys.len())
456 .map(|i| polys[i].evaluate_with_tables(&eval_table_rx, &eval_table_ry))
457 .collect::<Vec<Scalar>>()
458 }
459
460 pub fn multiply_vec(&self, num_rows: usize, num_cols: usize, z: &[Scalar]) -> Vec<Scalar> {
461 assert_eq!(z.len(), num_cols);
462
463 (0..self.M.len())
464 .map(|i| {
465 let row = self.M[i].row;
466 let col = self.M[i].col;
467 let val = &self.M[i].val;
468 (row, val * z[col])
469 })
470 .fold(vec![Scalar::zero(); num_rows], |mut Mz, (r, v)| {
471 Mz[r] += v;
472 Mz
473 })
474 }
475
476 pub fn compute_eval_table_sparse(
477 &self,
478 rx: &[Scalar],
479 num_rows: usize,
480 num_cols: usize,
481 ) -> Vec<Scalar> {
482 assert_eq!(rx.len(), num_rows);
483
484 let mut M_evals: Vec<Scalar> = vec![Scalar::zero(); num_cols];
485
486 for i in 0..self.M.len() {
487 let entry = &self.M[i];
488 M_evals[entry.col] += rx[entry.row] * entry.val;
489 }
490 M_evals
491 }
492
493 pub fn multi_commit(
494 sparse_polys: &[&SparseMatPolynomial],
495 gens: &SparseMatPolyCommitmentGens,
496 ) -> (SparseMatPolyCommitment, MultiSparseMatPolynomialAsDense) {
497 let batch_size = sparse_polys.len();
498 let dense = SparseMatPolynomial::multi_sparse_to_dense_rep(sparse_polys);
499
500 let (comm_comb_ops, _blinds_comb_ops) = dense.comb_ops.commit(&gens.gens_ops, None);
501 let (comm_comb_mem, _blinds_comb_mem) = dense.comb_mem.commit(&gens.gens_mem, None);
502
503 (
504 SparseMatPolyCommitment {
505 batch_size,
506 num_mem_cells: dense.row.audit_ts.len(),
507 num_ops: dense.row.read_ts[0].len(),
508 comm_comb_ops,
509 comm_comb_mem,
510 },
511 dense,
512 )
513 }
514}
515
516impl MultiSparseMatPolynomialAsDense {
517 pub fn deref(&self, row_mem_val: &[Scalar], col_mem_val: &[Scalar]) -> Derefs {
518 let row_ops_val = self.row.deref(row_mem_val);
519 let col_ops_val = self.col.deref(col_mem_val);
520
521 Derefs::new(row_ops_val, col_ops_val)
522 }
523}
524
525#[derive(Debug)]
526struct ProductLayer {
527 init: ProductCircuit,
528 read_vec: Vec<ProductCircuit>,
529 write_vec: Vec<ProductCircuit>,
530 audit: ProductCircuit,
531}
532
533#[derive(Debug)]
534struct Layers {
535 prod_layer: ProductLayer,
536}
537
538impl Layers {
539 fn build_hash_layer(
540 eval_table: &[Scalar],
541 addrs_vec: &[DensePolynomial],
542 derefs_vec: &[DensePolynomial],
543 read_ts_vec: &[DensePolynomial],
544 audit_ts: &DensePolynomial,
545 r_mem_check: &(Scalar, Scalar),
546 ) -> (
547 DensePolynomial,
548 Vec<DensePolynomial>,
549 Vec<DensePolynomial>,
550 DensePolynomial,
551 ) {
552 let (r_hash, r_multiset_check) = r_mem_check;
553
554 //hash(addr, val, ts) = ts * r_hash_sqr + val * r_hash + addr
555 let r_hash_sqr = r_hash * r_hash;
556 let hash_func = |addr: &Scalar, val: &Scalar, ts: &Scalar| -> Scalar {
557 ts * r_hash_sqr + val * r_hash + addr
558 };
559
560 // hash init and audit that does not depend on #instances
561 let num_mem_cells = eval_table.len();
562 let poly_init_hashed = DensePolynomial::new(
563 (0..num_mem_cells)
564 .map(|i| {
565 // at init time, addr is given by i, init value is given by eval_table, and ts = 0
566 hash_func(&Scalar::from(i as u64), &eval_table[i], &Scalar::zero()) - r_multiset_check
567 })
568 .collect::<Vec<Scalar>>(),
569 );
570 let poly_audit_hashed = DensePolynomial::new(
571 (0..num_mem_cells)
572 .map(|i| {
573 // at audit time, addr is given by i, value is given by eval_table, and ts is given by audit_ts
574 hash_func(&Scalar::from(i as u64), &eval_table[i], &audit_ts[i]) - r_multiset_check
575 })
576 .collect::<Vec<Scalar>>(),
577 );
578
579 // hash read and write that depends on #instances
580 let mut poly_read_hashed_vec: Vec<DensePolynomial> = Vec::new();
581 let mut poly_write_hashed_vec: Vec<DensePolynomial> = Vec::new();
582 for i in 0..addrs_vec.len() {
583 let (addrs, derefs, read_ts) = (&addrs_vec[i], &derefs_vec[i], &read_ts_vec[i]);
584 assert_eq!(addrs.len(), derefs.len());
585 assert_eq!(addrs.len(), read_ts.len());
586 let num_ops = addrs.len();
587 let poly_read_hashed = DensePolynomial::new(
588 (0..num_ops)
589 .map(|i| {
590 // at read time, addr is given by addrs, value is given by derefs, and ts is given by read_ts
591 hash_func(&addrs[i], &derefs[i], &read_ts[i]) - r_multiset_check
592 })
593 .collect::<Vec<Scalar>>(),
594 );
595 poly_read_hashed_vec.push(poly_read_hashed);
596
597 let poly_write_hashed = DensePolynomial::new(
598 (0..num_ops)
599 .map(|i| {
600 // at write time, addr is given by addrs, value is given by derefs, and ts is given by write_ts = read_ts + 1
601 hash_func(&addrs[i], &derefs[i], &(read_ts[i] + Scalar::one())) - r_multiset_check
602 })
603 .collect::<Vec<Scalar>>(),
604 );
605 poly_write_hashed_vec.push(poly_write_hashed);
606 }
607
608 (
609 poly_init_hashed,
610 poly_read_hashed_vec,
611 poly_write_hashed_vec,
612 poly_audit_hashed,
613 )
614 }
615
616 pub fn new(
617 eval_table: &[Scalar],
618 addr_timestamps: &AddrTimestamps,
619 poly_ops_val: &[DensePolynomial],
620 r_mem_check: &(Scalar, Scalar),
621 ) -> Self {
622 let (poly_init_hashed, poly_read_hashed_vec, poly_write_hashed_vec, poly_audit_hashed) =
623 Layers::build_hash_layer(
624 eval_table,
625 &addr_timestamps.ops_addr,
626 poly_ops_val,
627 &addr_timestamps.read_ts,
628 &addr_timestamps.audit_ts,
629 r_mem_check,
630 );
631
632 let prod_init = ProductCircuit::new(&poly_init_hashed);
633 let prod_read_vec = (0..poly_read_hashed_vec.len())
634 .map(|i| ProductCircuit::new(&poly_read_hashed_vec[i]))
635 .collect::<Vec<ProductCircuit>>();
636 let prod_write_vec = (0..poly_write_hashed_vec.len())
637 .map(|i| ProductCircuit::new(&poly_write_hashed_vec[i]))
638 .collect::<Vec<ProductCircuit>>();
639 let prod_audit = ProductCircuit::new(&poly_audit_hashed);
640
641 // subset audit check
642 let hashed_writes: Scalar = (0..prod_write_vec.len())
643 .map(|i| prod_write_vec[i].evaluate())
644 .product();
645 let hashed_write_set: Scalar = prod_init.evaluate() * hashed_writes;
646
647 let hashed_reads: Scalar = (0..prod_read_vec.len())
648 .map(|i| prod_read_vec[i].evaluate())
649 .product();
650 let hashed_read_set: Scalar = hashed_reads * prod_audit.evaluate();
651
652 //assert_eq!(hashed_read_set, hashed_write_set);
653 debug_assert_eq!(hashed_read_set, hashed_write_set);
654
655 Layers {
656 prod_layer: ProductLayer {
657 init: prod_init,
658 read_vec: prod_read_vec,
659 write_vec: prod_write_vec,
660 audit: prod_audit,
661 },
662 }
663 }
664}
665
666#[derive(Debug)]
667struct PolyEvalNetwork {
668 row_layers: Layers,
669 col_layers: Layers,
670}
671
672impl PolyEvalNetwork {
673 pub fn new(
674 dense: &MultiSparseMatPolynomialAsDense,
675 derefs: &Derefs,
676 mem_rx: &[Scalar],
677 mem_ry: &[Scalar],
678 r_mem_check: &(Scalar, Scalar),
679 ) -> Self {
680 let row_layers = Layers::new(mem_rx, &dense.row, &derefs.row_ops_val, r_mem_check);
681 let col_layers = Layers::new(mem_ry, &dense.col, &derefs.col_ops_val, r_mem_check);
682
683 PolyEvalNetwork {
684 row_layers,
685 col_layers,
686 }
687 }
688}
689
690#[derive(Debug, Serialize, Deserialize)]
691struct HashLayerProof {
692 eval_row: (Vec<Scalar>, Vec<Scalar>, Scalar),
693 eval_col: (Vec<Scalar>, Vec<Scalar>, Scalar),
694 eval_val: Vec<Scalar>,
695 eval_derefs: (Vec<Scalar>, Vec<Scalar>),
696 proof_ops: PolyEvalProof,
697 proof_mem: PolyEvalProof,
698 proof_derefs: DerefsEvalProof,
699}
700
701impl HashLayerProof {
702 fn protocol_name() -> &'static [u8] {
703 b"Sparse polynomial hash layer proof"
704 }
705
706 fn prove_helper(
707 rand: (&Vec<Scalar>, &Vec<Scalar>),
708 addr_timestamps: &AddrTimestamps,
709 ) -> (Vec<Scalar>, Vec<Scalar>, Scalar) {
710 let (rand_mem, rand_ops) = rand;
711
712 // decommit ops-addr at rand_ops
713 let mut eval_ops_addr_vec: Vec<Scalar> = Vec::new();
714 for i in 0..addr_timestamps.ops_addr.len() {
715 let eval_ops_addr = addr_timestamps.ops_addr[i].evaluate(rand_ops);
716 eval_ops_addr_vec.push(eval_ops_addr);
717 }
718
719 // decommit read_ts at rand_ops
720 let mut eval_read_ts_vec: Vec<Scalar> = Vec::new();
721 for i in 0..addr_timestamps.read_ts.len() {
722 let eval_read_ts = addr_timestamps.read_ts[i].evaluate(rand_ops);
723 eval_read_ts_vec.push(eval_read_ts);
724 }
725
726 // decommit audit-ts at rand_mem
727 let eval_audit_ts = addr_timestamps.audit_ts.evaluate(rand_mem);
728
729 (eval_ops_addr_vec, eval_read_ts_vec, eval_audit_ts)
730 }
731
732 fn prove(
733 rand: (&Vec<Scalar>, &Vec<Scalar>),
734 dense: &MultiSparseMatPolynomialAsDense,
735 derefs: &Derefs,
736 gens: &SparseMatPolyCommitmentGens,
737 transcript: &mut Transcript,
738 random_tape: &mut RandomTape,
739 ) -> Self {
740 transcript.append_protocol_name(HashLayerProof::protocol_name());
741
742 let (rand_mem, rand_ops) = rand;
743
744 // decommit derefs at rand_ops
745 let eval_row_ops_val = (0..derefs.row_ops_val.len())
746 .map(|i| derefs.row_ops_val[i].evaluate(rand_ops))
747 .collect::<Vec<Scalar>>();
748 let eval_col_ops_val = (0..derefs.col_ops_val.len())
749 .map(|i| derefs.col_ops_val[i].evaluate(rand_ops))
750 .collect::<Vec<Scalar>>();
751 let proof_derefs = DerefsEvalProof::prove(
752 derefs,
753 &eval_row_ops_val,
754 &eval_col_ops_val,
755 rand_ops,
756 &gens.gens_derefs,
757 transcript,
758 random_tape,
759 );
760 let eval_derefs = (eval_row_ops_val, eval_col_ops_val);
761
762 // evaluate row_addr, row_read-ts, col_addr, col_read-ts, val at rand_ops
763 // evaluate row_audit_ts and col_audit_ts at rand_mem
764 let (eval_row_addr_vec, eval_row_read_ts_vec, eval_row_audit_ts) =
765 HashLayerProof::prove_helper((rand_mem, rand_ops), &dense.row);
766 let (eval_col_addr_vec, eval_col_read_ts_vec, eval_col_audit_ts) =
767 HashLayerProof::prove_helper((rand_mem, rand_ops), &dense.col);
768 let eval_val_vec = (0..dense.val.len())
769 .map(|i| dense.val[i].evaluate(rand_ops))
770 .collect::<Vec<Scalar>>();
771
772 // form a single decommitment using comm_comb_ops
773 let mut evals_ops: Vec<Scalar> = Vec::new();
774 evals_ops.extend(&eval_row_addr_vec);
775 evals_ops.extend(&eval_row_read_ts_vec);
776 evals_ops.extend(&eval_col_addr_vec);
777 evals_ops.extend(&eval_col_read_ts_vec);
778 evals_ops.extend(&eval_val_vec);
779 evals_ops.resize(evals_ops.len().next_power_of_two(), Scalar::zero());
780 evals_ops.append_to_transcript(b"claim_evals_ops", transcript);
781 let challenges_ops = transcript.challenge_vector(
782 b"challenge_combine_n_to_one",
783 evals_ops.len().log2() as usize,
784 );
785
786 let mut poly_evals_ops = DensePolynomial::new(evals_ops);
787 for i in (0..challenges_ops.len()).rev() {
788 poly_evals_ops.bound_poly_var_bot(&challenges_ops[i]);
789 }
790 assert_eq!(poly_evals_ops.len(), 1);
791 let joint_claim_eval_ops = poly_evals_ops[0];
792 let mut r_joint_ops = challenges_ops;
793 r_joint_ops.extend(rand_ops);
794 debug_assert_eq!(dense.comb_ops.evaluate(&r_joint_ops), joint_claim_eval_ops);
795 joint_claim_eval_ops.append_to_transcript(b"joint_claim_eval_ops", transcript);
796 let (proof_ops, _comm_ops_eval) = PolyEvalProof::prove(
797 &dense.comb_ops,
798 None,
799 &r_joint_ops,
800 &joint_claim_eval_ops,
801 None,
802 &gens.gens_ops,
803 transcript,
804 random_tape,
805 );
806
807 // form a single decommitment using comb_comb_mem at rand_mem
808 let evals_mem: Vec<Scalar> = vec![eval_row_audit_ts, eval_col_audit_ts];
809 evals_mem.append_to_transcript(b"claim_evals_mem", transcript);
810 let challenges_mem = transcript.challenge_vector(
811 b"challenge_combine_two_to_one",
812 evals_mem.len().log2() as usize,
813 );
814
815 let mut poly_evals_mem = DensePolynomial::new(evals_mem);
816 for i in (0..challenges_mem.len()).rev() {
817 poly_evals_mem.bound_poly_var_bot(&challenges_mem[i]);
818 }
819 assert_eq!(poly_evals_mem.len(), 1);
820 let joint_claim_eval_mem = poly_evals_mem[0];
821 let mut r_joint_mem = challenges_mem;
822 r_joint_mem.extend(rand_mem);
823 debug_assert_eq!(dense.comb_mem.evaluate(&r_joint_mem), joint_claim_eval_mem);
824 joint_claim_eval_mem.append_to_transcript(b"joint_claim_eval_mem", transcript);
825 let (proof_mem, _comm_mem_eval) = PolyEvalProof::prove(
826 &dense.comb_mem,
827 None,
828 &r_joint_mem,
829 &joint_claim_eval_mem,
830 None,
831 &gens.gens_mem,
832 transcript,
833 random_tape,
834 );
835
836 HashLayerProof {
837 eval_row: (eval_row_addr_vec, eval_row_read_ts_vec, eval_row_audit_ts),
838 eval_col: (eval_col_addr_vec, eval_col_read_ts_vec, eval_col_audit_ts),
839 eval_val: eval_val_vec,
840 eval_derefs,
841 proof_ops,
842 proof_mem,
843 proof_derefs,
844 }
845 }
846
847 fn verify_helper(
848 rand: &(&Vec<Scalar>, &Vec<Scalar>),
849 claims: &(Scalar, Vec<Scalar>, Vec<Scalar>, Scalar),
850 eval_ops_val: &[Scalar],
851 eval_ops_addr: &[Scalar],
852 eval_read_ts: &[Scalar],
853 eval_audit_ts: &Scalar,
854 r: &[Scalar],
855 r_hash: &Scalar,
856 r_multiset_check: &Scalar,
857 ) -> Result<(), ProofVerifyError> {
858 let r_hash_sqr = r_hash * r_hash;
859 let hash_func = |addr: &Scalar, val: &Scalar, ts: &Scalar| -> Scalar {
860 ts * r_hash_sqr + val * r_hash + addr
861 };
862
863 let (rand_mem, _rand_ops) = rand;
864 let (claim_init, claim_read, claim_write, claim_audit) = claims;
865
866 // init
867 let eval_init_addr = IdentityPolynomial::new(rand_mem.len()).evaluate(rand_mem);
868 let eval_init_val = EqPolynomial::new(r.to_vec()).evaluate(rand_mem);
869 let hash_init_at_rand_mem =
870 hash_func(&eval_init_addr, &eval_init_val, &Scalar::zero()) - r_multiset_check; // verify the claim_last of init chunk
871 assert_eq!(&hash_init_at_rand_mem, claim_init);
872
873 // read
874 for i in 0..eval_ops_addr.len() {
875 let hash_read_at_rand_ops =
876 hash_func(&eval_ops_addr[i], &eval_ops_val[i], &eval_read_ts[i]) - r_multiset_check; // verify the claim_last of init chunk
877 assert_eq!(&hash_read_at_rand_ops, &claim_read[i]);
878 }
879
880 // write: shares addr, val component; only decommit write_ts
881 for i in 0..eval_ops_addr.len() {
882 let eval_write_ts = eval_read_ts[i] + Scalar::one();
883 let hash_write_at_rand_ops =
884 hash_func(&eval_ops_addr[i], &eval_ops_val[i], &eval_write_ts) - r_multiset_check; // verify the claim_last of init chunk
885 assert_eq!(&hash_write_at_rand_ops, &claim_write[i]);
886 }
887
888 // audit: shares addr and val with init
889 let eval_audit_addr = eval_init_addr;
890 let eval_audit_val = eval_init_val;
891 let hash_audit_at_rand_mem =
892 hash_func(&eval_audit_addr, &eval_audit_val, eval_audit_ts) - r_multiset_check;
893 assert_eq!(&hash_audit_at_rand_mem, claim_audit); // verify the last step of the sum-check for audit
894
895 Ok(())
896 }
897
898 fn verify(
899 &self,
900 rand: (&Vec<Scalar>, &Vec<Scalar>),
901 claims_row: &(Scalar, Vec<Scalar>, Vec<Scalar>, Scalar),
902 claims_col: &(Scalar, Vec<Scalar>, Vec<Scalar>, Scalar),
903 claims_dotp: &[Scalar],
904 comm: &SparseMatPolyCommitment,
905 gens: &SparseMatPolyCommitmentGens,
906 comm_derefs: &DerefsCommitment,
907 rx: &[Scalar],
908 ry: &[Scalar],
909 r_hash: &Scalar,
910 r_multiset_check: &Scalar,
911 transcript: &mut Transcript,
912 ) -> Result<(), ProofVerifyError> {
913 let timer = Timer::new("verify_hash_proof");
914 transcript.append_protocol_name(HashLayerProof::protocol_name());
915
916 let (rand_mem, rand_ops) = rand;
917
918 // verify derefs at rand_ops
919 let (eval_row_ops_val, eval_col_ops_val) = &self.eval_derefs;
920 assert_eq!(eval_row_ops_val.len(), eval_col_ops_val.len());
921 self.proof_derefs.verify(
922 rand_ops,
923 eval_row_ops_val,
924 eval_col_ops_val,
925 &gens.gens_derefs,
926 comm_derefs,
927 transcript,
928 )?;
929
930 // verify the decommitments used in evaluation sum-check
931 let eval_val_vec = &self.eval_val;
932 assert_eq!(claims_dotp.len(), 3 * eval_row_ops_val.len());
933 for i in 0..claims_dotp.len() / 3 {
934 let claim_row_ops_val = claims_dotp[3 * i];
935 let claim_col_ops_val = claims_dotp[3 * i + 1];
936 let claim_val = claims_dotp[3 * i + 2];
937
938 assert_eq!(claim_row_ops_val, eval_row_ops_val[i]);
939 assert_eq!(claim_col_ops_val, eval_col_ops_val[i]);
940 assert_eq!(claim_val, eval_val_vec[i]);
941 }
942
943 // verify addr-timestamps using comm_comb_ops at rand_ops
944 let (eval_row_addr_vec, eval_row_read_ts_vec, eval_row_audit_ts) = &self.eval_row;
945 let (eval_col_addr_vec, eval_col_read_ts_vec, eval_col_audit_ts) = &self.eval_col;
946
947 let mut evals_ops: Vec<Scalar> = Vec::new();
948 evals_ops.extend(eval_row_addr_vec);
949 evals_ops.extend(eval_row_read_ts_vec);
950 evals_ops.extend(eval_col_addr_vec);
951 evals_ops.extend(eval_col_read_ts_vec);
952 evals_ops.extend(eval_val_vec);
953 evals_ops.resize(evals_ops.len().next_power_of_two(), Scalar::zero());
954 evals_ops.append_to_transcript(b"claim_evals_ops", transcript);
955 let challenges_ops = transcript.challenge_vector(
956 b"challenge_combine_n_to_one",
957 evals_ops.len().log2() as usize,
958 );
959
960 let mut poly_evals_ops = DensePolynomial::new(evals_ops);
961 for i in (0..challenges_ops.len()).rev() {
962 poly_evals_ops.bound_poly_var_bot(&challenges_ops[i]);
963 }
964 assert_eq!(poly_evals_ops.len(), 1);
965 let joint_claim_eval_ops = poly_evals_ops[0];
966 let mut r_joint_ops = challenges_ops;
967 r_joint_ops.extend(rand_ops);
968 joint_claim_eval_ops.append_to_transcript(b"joint_claim_eval_ops", transcript);
969 assert!(self
970 .proof_ops
971 .verify_plain(
972 &gens.gens_ops,
973 transcript,
974 &r_joint_ops,
975 &joint_claim_eval_ops,
976 &comm.comm_comb_ops
977 )
978 .is_ok());
979
980 // verify proof-mem using comm_comb_mem at rand_mem
981 // form a single decommitment using comb_comb_mem at rand_mem
982 let evals_mem: Vec<Scalar> = vec![*eval_row_audit_ts, *eval_col_audit_ts];
983 evals_mem.append_to_transcript(b"claim_evals_mem", transcript);
984 let challenges_mem = transcript.challenge_vector(
985 b"challenge_combine_two_to_one",
986 evals_mem.len().log2() as usize,
987 );
988
989 let mut poly_evals_mem = DensePolynomial::new(evals_mem);
990 for i in (0..challenges_mem.len()).rev() {
991 poly_evals_mem.bound_poly_var_bot(&challenges_mem[i]);
992 }
993 assert_eq!(poly_evals_mem.len(), 1);
994 let joint_claim_eval_mem = poly_evals_mem[0];
995 let mut r_joint_mem = challenges_mem;
996 r_joint_mem.extend(rand_mem);
997 joint_claim_eval_mem.append_to_transcript(b"joint_claim_eval_mem", transcript);
998 self.proof_mem.verify_plain(
999 &gens.gens_mem,
1000 transcript,
1001 &r_joint_mem,
1002 &joint_claim_eval_mem,
1003 &comm.comm_comb_mem,
1004 )?;
1005
1006 // verify the claims from the product layer
1007 let (eval_ops_addr, eval_read_ts, eval_audit_ts) = &self.eval_row;
1008 HashLayerProof::verify_helper(
1009 &(rand_mem, rand_ops),
1010 claims_row,
1011 eval_row_ops_val,
1012 eval_ops_addr,
1013 eval_read_ts,
1014 eval_audit_ts,
1015 rx,
1016 r_hash,
1017 r_multiset_check,
1018 )?;
1019
1020 let (eval_ops_addr, eval_read_ts, eval_audit_ts) = &self.eval_col;
1021 HashLayerProof::verify_helper(
1022 &(rand_mem, rand_ops),
1023 claims_col,
1024 eval_col_ops_val,
1025 eval_ops_addr,
1026 eval_read_ts,
1027 eval_audit_ts,
1028 ry,
1029 r_hash,
1030 r_multiset_check,
1031 )?;
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 self.poly_eval_network_proof.verify(
1566 comm,
1567 &self.comm_derefs,
1568 evals,
1569 gens,
1570 &rx_ext,
1571 &ry_ext,
1572 &(r_mem_check[0], r_mem_check[1]),
1573 nz,
1574 transcript,
1575 )
1576 }
1577}
1578
1579pub struct SparsePolyEntry {
1580 idx: usize,
1581 val: Scalar,
1582}
1583
1584impl SparsePolyEntry {
1585 pub fn new(idx: usize, val: Scalar) -> Self {
1586 SparsePolyEntry { idx, val }
1587 }
1588}
1589
1590pub struct SparsePolynomial {
1591 num_vars: usize,
1592 Z: Vec<SparsePolyEntry>,
1593}
1594
1595impl SparsePolynomial {
1596 pub fn new(num_vars: usize, Z: Vec<SparsePolyEntry>) -> Self {
1597 SparsePolynomial { num_vars, Z }
1598 }
1599
1600 fn compute_chi(a: &[bool], r: &[Scalar]) -> Scalar {
1601 assert_eq!(a.len(), r.len());
1602 let mut chi_i = Scalar::one();
1603 for j in 0..r.len() {
1604 if a[j] {
1605 chi_i *= r[j];
1606 } else {
1607 chi_i *= Scalar::one() - r[j];
1608 }
1609 }
1610 chi_i
1611 }
1612
1613 // Takes O(n log n). TODO: do this in O(n) where n is the number of entries in Z
1614 pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
1615 assert_eq!(self.num_vars, r.len());
1616
1617 (0..self.Z.len())
1618 .map(|i| {
1619 let bits = self.Z[i].idx.get_bits(r.len());
1620 SparsePolynomial::compute_chi(&bits, r) * self.Z[i].val
1621 })
1622 .sum()
1623 }
1624}
1625
1626#[cfg(test)]
1627mod tests {
1628 use super::*;
1629 use rand::rngs::OsRng;
1630 use rand::RngCore;
1631 #[test]
1632 fn check_sparse_polyeval_proof() {
1633 let mut csprng: OsRng = OsRng;
1634
1635 let num_nz_entries: usize = 256;
1636 let num_rows: usize = 256;
1637 let num_cols: usize = 256;
1638 let num_vars_x: usize = num_rows.log2() as usize;
1639 let num_vars_y: usize = num_cols.log2() as usize;
1640
1641 let mut M: Vec<SparseMatEntry> = Vec::new();
1642
1643 for _i in 0..num_nz_entries {
1644 M.push(SparseMatEntry::new(
1645 (csprng.next_u64() % (num_rows as u64)) as usize,
1646 (csprng.next_u64() % (num_cols as u64)) as usize,
1647 Scalar::random(&mut csprng),
1648 ));
1649 }
1650
1651 let poly_M = SparseMatPolynomial::new(num_vars_x, num_vars_y, M);
1652 let gens = SparseMatPolyCommitmentGens::new(
1653 b"gens_sparse_poly",
1654 num_vars_x,
1655 num_vars_y,
1656 num_nz_entries,
1657 3,
1658 );
1659
1660 // commitment
1661 let (poly_comm, dense) = SparseMatPolynomial::multi_commit(&[&poly_M, &poly_M, &poly_M], &gens);
1662
1663 // evaluation
1664 let rx: Vec<Scalar> = (0..num_vars_x)
1665 .map(|_i| Scalar::random(&mut csprng))
1666 .collect::<Vec<Scalar>>();
1667 let ry: Vec<Scalar> = (0..num_vars_y)
1668 .map(|_i| Scalar::random(&mut csprng))
1669 .collect::<Vec<Scalar>>();
1670 let eval = SparseMatPolynomial::multi_evaluate(&[&poly_M], &rx, &ry);
1671 let evals = vec![eval[0], eval[0], eval[0]];
1672
1673 let mut random_tape = RandomTape::new(b"proof");
1674 let mut prover_transcript = Transcript::new(b"example");
1675 let proof = SparseMatPolyEvalProof::prove(
1676 &dense,
1677 &rx,
1678 &ry,
1679 &evals,
1680 &gens,
1681 &mut prover_transcript,
1682 &mut random_tape,
1683 );
1684
1685 let mut verifier_transcript = Transcript::new(b"example");
1686 assert!(proof
1687 .verify(
1688 &poly_comm,
1689 &rx,
1690 &ry,
1691 &evals,
1692 &gens,
1693 &mut verifier_transcript,
1694 )
1695 .is_ok());
1696 }
1697}