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