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