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