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!(
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, z[col] * val)
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.square();
557 let hash_func = |addr: &Scalar, val: &Scalar, ts: &Scalar| -> Scalar {
558 r_hash_sqr * ts + (*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.square();
860 let hash_func = |addr: &Scalar, val: &Scalar, ts: &Scalar| -> Scalar {
861 r_hash_sqr * ts + (*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 self.proof_ops.verify_plain(
971 &gens.gens_ops,
972 transcript,
973 &r_joint_ops,
974 &joint_claim_eval_ops,
975 &comm.comm_comb_ops,
976 )?;
977
978 // verify proof-mem using comm_comb_mem at rand_mem
979 // form a single decommitment using comb_comb_mem at rand_mem
980 let evals_mem: Vec<Scalar> = vec![*eval_row_audit_ts, *eval_col_audit_ts];
981 evals_mem.append_to_transcript(b"claim_evals_mem", transcript);
982 let challenges_mem = transcript.challenge_vector(
983 b"challenge_combine_two_to_one",
984 evals_mem.len().log2() as usize,
985 );
986
987 let mut poly_evals_mem = DensePolynomial::new(evals_mem);
988 for i in (0..challenges_mem.len()).rev() {
989 poly_evals_mem.bound_poly_var_bot(&challenges_mem[i]);
990 }
991 assert_eq!(poly_evals_mem.len(), 1);
992 let joint_claim_eval_mem = poly_evals_mem[0];
993 let mut r_joint_mem = challenges_mem;
994 r_joint_mem.extend(rand_mem);
995 joint_claim_eval_mem.append_to_transcript(b"joint_claim_eval_mem", transcript);
996 self.proof_mem.verify_plain(
997 &gens.gens_mem,
998 transcript,
999 &r_joint_mem,
1000 &joint_claim_eval_mem,
1001 &comm.comm_comb_mem,
1002 )?;
1003
1004 // verify the claims from the product layer
1005 let (eval_ops_addr, eval_read_ts, eval_audit_ts) = &self.eval_row;
1006 HashLayerProof::verify_helper(
1007 &(rand_mem, rand_ops),
1008 claims_row,
1009 eval_row_ops_val,
1010 eval_ops_addr,
1011 eval_read_ts,
1012 eval_audit_ts,
1013 rx,
1014 r_hash,
1015 r_multiset_check,
1016 )?;
1017
1018 let (eval_ops_addr, eval_read_ts, eval_audit_ts) = &self.eval_col;
1019 HashLayerProof::verify_helper(
1020 &(rand_mem, rand_ops),
1021 claims_col,
1022 eval_col_ops_val,
1023 eval_ops_addr,
1024 eval_read_ts,
1025 eval_audit_ts,
1026 ry,
1027 r_hash,
1028 r_multiset_check,
1029 )?;
1030
1031 timer.stop();
1032 Ok(())
1033 }
1034}
1035
1036#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
1037struct ProductLayerProof {
1038 eval_row: (Scalar, Vec<Scalar>, Vec<Scalar>, Scalar),
1039 eval_col: (Scalar, Vec<Scalar>, Vec<Scalar>, Scalar),
1040 eval_val: (Vec<Scalar>, Vec<Scalar>),
1041 proof_mem: ProductCircuitEvalProofBatched,
1042 proof_ops: ProductCircuitEvalProofBatched,
1043}
1044
1045impl ProductLayerProof {
1046 fn protocol_name() -> &'static [u8] {
1047 b"Sparse polynomial product layer proof"
1048 }
1049
1050 pub fn prove(
1051 row_prod_layer: &mut ProductLayer,
1052 col_prod_layer: &mut ProductLayer,
1053 dense: &MultiSparseMatPolynomialAsDense,
1054 derefs: &Derefs,
1055 eval: &[Scalar],
1056 transcript: &mut Transcript,
1057 ) -> (Self, Vec<Scalar>, Vec<Scalar>) {
1058 transcript.append_protocol_name(ProductLayerProof::protocol_name());
1059
1060 let row_eval_init = row_prod_layer.init.evaluate();
1061 let row_eval_audit = row_prod_layer.audit.evaluate();
1062 let row_eval_read = (0..row_prod_layer.read_vec.len())
1063 .map(|i| row_prod_layer.read_vec[i].evaluate())
1064 .collect::<Vec<Scalar>>();
1065 let row_eval_write = (0..row_prod_layer.write_vec.len())
1066 .map(|i| row_prod_layer.write_vec[i].evaluate())
1067 .collect::<Vec<Scalar>>();
1068
1069 // subset check
1070 let ws: Scalar = (0..row_eval_write.len())
1071 .map(|i| row_eval_write[i])
1072 .product();
1073 let rs: Scalar = (0..row_eval_read.len()).map(|i| row_eval_read[i]).product();
1074 assert_eq!(row_eval_init * ws, rs * row_eval_audit);
1075
1076 row_eval_init.append_to_transcript(b"claim_row_eval_init", transcript);
1077 row_eval_read.append_to_transcript(b"claim_row_eval_read", transcript);
1078 row_eval_write.append_to_transcript(b"claim_row_eval_write", transcript);
1079 row_eval_audit.append_to_transcript(b"claim_row_eval_audit", transcript);
1080
1081 let col_eval_init = col_prod_layer.init.evaluate();
1082 let col_eval_audit = col_prod_layer.audit.evaluate();
1083 let col_eval_read: Vec<Scalar> = (0..col_prod_layer.read_vec.len())
1084 .map(|i| col_prod_layer.read_vec[i].evaluate())
1085 .collect();
1086 let col_eval_write: Vec<Scalar> = (0..col_prod_layer.write_vec.len())
1087 .map(|i| col_prod_layer.write_vec[i].evaluate())
1088 .collect();
1089
1090 // subset check
1091 let ws: Scalar = (0..col_eval_write.len())
1092 .map(|i| col_eval_write[i])
1093 .product();
1094 let rs: Scalar = (0..col_eval_read.len()).map(|i| col_eval_read[i]).product();
1095 assert_eq!(col_eval_init * ws, rs * col_eval_audit);
1096
1097 col_eval_init.append_to_transcript(b"claim_col_eval_init", transcript);
1098 col_eval_read.append_to_transcript(b"claim_col_eval_read", transcript);
1099 col_eval_write.append_to_transcript(b"claim_col_eval_write", transcript);
1100 col_eval_audit.append_to_transcript(b"claim_col_eval_audit", transcript);
1101
1102 // prepare dotproduct circuit for batching then with ops-related product circuits
1103 assert_eq!(eval.len(), derefs.row_ops_val.len());
1104 assert_eq!(eval.len(), derefs.col_ops_val.len());
1105 assert_eq!(eval.len(), dense.val.len());
1106 let mut dotp_circuit_left_vec: Vec<DotProductCircuit> = Vec::new();
1107 let mut dotp_circuit_right_vec: Vec<DotProductCircuit> = Vec::new();
1108 let mut eval_dotp_left_vec: Vec<Scalar> = Vec::new();
1109 let mut eval_dotp_right_vec: Vec<Scalar> = Vec::new();
1110 for i in 0..derefs.row_ops_val.len() {
1111 // evaluate sparse polynomial evaluation using two dotp checks
1112 let left = derefs.row_ops_val[i].clone();
1113 let right = derefs.col_ops_val[i].clone();
1114 let weights = dense.val[i].clone();
1115
1116 // build two dot product circuits to prove evaluation of sparse polynomial
1117 let mut dotp_circuit = DotProductCircuit::new(left, right, weights);
1118 let (dotp_circuit_left, dotp_circuit_right) = dotp_circuit.split();
1119
1120 let (eval_dotp_left, eval_dotp_right) =
1121 (dotp_circuit_left.evaluate(), dotp_circuit_right.evaluate());
1122
1123 eval_dotp_left.append_to_transcript(b"claim_eval_dotp_left", transcript);
1124 eval_dotp_right.append_to_transcript(b"claim_eval_dotp_right", transcript);
1125 assert_eq!(eval_dotp_left + eval_dotp_right, eval[i]);
1126 eval_dotp_left_vec.push(eval_dotp_left);
1127 eval_dotp_right_vec.push(eval_dotp_right);
1128
1129 dotp_circuit_left_vec.push(dotp_circuit_left);
1130 dotp_circuit_right_vec.push(dotp_circuit_right);
1131 }
1132
1133 // The number of operations into the memory encoded by rx and ry are always the same (by design)
1134 // So we can produce a batched product proof for all of them at the same time.
1135 // prove the correctness of claim_row_eval_read, claim_row_eval_write, claim_col_eval_read, and claim_col_eval_write
1136 // TODO: we currently only produce proofs for 3 batched sparse polynomial evaluations
1137 assert_eq!(row_prod_layer.read_vec.len(), 3);
1138 let (row_read_A, row_read_B, row_read_C) = {
1139 let (vec_A, vec_BC) = row_prod_layer.read_vec.split_at_mut(1);
1140 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1141 (vec_A, vec_B, vec_C)
1142 };
1143
1144 let (row_write_A, row_write_B, row_write_C) = {
1145 let (vec_A, vec_BC) = row_prod_layer.write_vec.split_at_mut(1);
1146 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1147 (vec_A, vec_B, vec_C)
1148 };
1149
1150 let (col_read_A, col_read_B, col_read_C) = {
1151 let (vec_A, vec_BC) = col_prod_layer.read_vec.split_at_mut(1);
1152 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1153 (vec_A, vec_B, vec_C)
1154 };
1155
1156 let (col_write_A, col_write_B, col_write_C) = {
1157 let (vec_A, vec_BC) = col_prod_layer.write_vec.split_at_mut(1);
1158 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1159 (vec_A, vec_B, vec_C)
1160 };
1161
1162 let (dotp_left_A, dotp_left_B, dotp_left_C) = {
1163 let (vec_A, vec_BC) = dotp_circuit_left_vec.split_at_mut(1);
1164 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1165 (vec_A, vec_B, vec_C)
1166 };
1167
1168 let (dotp_right_A, dotp_right_B, dotp_right_C) = {
1169 let (vec_A, vec_BC) = dotp_circuit_right_vec.split_at_mut(1);
1170 let (vec_B, vec_C) = vec_BC.split_at_mut(1);
1171 (vec_A, vec_B, vec_C)
1172 };
1173
1174 let (proof_ops, rand_ops) = ProductCircuitEvalProofBatched::prove(
1175 &mut vec![
1176 &mut row_read_A[0],
1177 &mut row_read_B[0],
1178 &mut row_read_C[0],
1179 &mut row_write_A[0],
1180 &mut row_write_B[0],
1181 &mut row_write_C[0],
1182 &mut col_read_A[0],
1183 &mut col_read_B[0],
1184 &mut col_read_C[0],
1185 &mut col_write_A[0],
1186 &mut col_write_B[0],
1187 &mut col_write_C[0],
1188 ],
1189 &mut vec![
1190 &mut dotp_left_A[0],
1191 &mut dotp_right_A[0],
1192 &mut dotp_left_B[0],
1193 &mut dotp_right_B[0],
1194 &mut dotp_left_C[0],
1195 &mut dotp_right_C[0],
1196 ],
1197 transcript,
1198 );
1199
1200 // produce a batched proof of memory-related product circuits
1201 let (proof_mem, rand_mem) = ProductCircuitEvalProofBatched::prove(
1202 &mut vec![
1203 &mut row_prod_layer.init,
1204 &mut row_prod_layer.audit,
1205 &mut col_prod_layer.init,
1206 &mut col_prod_layer.audit,
1207 ],
1208 &mut Vec::new(),
1209 transcript,
1210 );
1211
1212 let product_layer_proof = ProductLayerProof {
1213 eval_row: (row_eval_init, row_eval_read, row_eval_write, row_eval_audit),
1214 eval_col: (col_eval_init, col_eval_read, col_eval_write, col_eval_audit),
1215 eval_val: (eval_dotp_left_vec, eval_dotp_right_vec),
1216 proof_mem,
1217 proof_ops,
1218 };
1219
1220 let mut product_layer_proof_encoded: Vec<u8> = Vec::new();
1221 product_layer_proof.serialize(&mut product_layer_proof_encoded).unwrap();
1222 let msg = format!(
1223 "len_product_layer_proof {:?}",
1224 product_layer_proof_encoded.len()
1225 );
1226 Timer::print(&msg);
1227
1228 (product_layer_proof, rand_mem, rand_ops)
1229 }
1230
1231 pub fn verify(
1232 &self,
1233 num_ops: usize,
1234 num_cells: usize,
1235 eval: &[Scalar],
1236 transcript: &mut Transcript,
1237 ) -> Result<
1238 (
1239 Vec<Scalar>,
1240 Vec<Scalar>,
1241 Vec<Scalar>,
1242 Vec<Scalar>,
1243 Vec<Scalar>,
1244 ),
1245 ProofVerifyError,
1246 > {
1247 transcript.append_protocol_name(ProductLayerProof::protocol_name());
1248
1249 let timer = Timer::new("verify_prod_proof");
1250 let num_instances = eval.len();
1251
1252 // subset check
1253 let (row_eval_init, row_eval_read, row_eval_write, row_eval_audit) = &self.eval_row;
1254 assert_eq!(row_eval_write.len(), num_instances);
1255 assert_eq!(row_eval_read.len(), num_instances);
1256 let ws: Scalar = (0..row_eval_write.len())
1257 .map(|i| row_eval_write[i])
1258 .product();
1259 let rs: Scalar = (0..row_eval_read.len()).map(|i| row_eval_read[i]).product();
1260 assert_eq!( ws * row_eval_init , rs * row_eval_audit);
1261
1262 row_eval_init.append_to_transcript(b"claim_row_eval_init", transcript);
1263 row_eval_read.append_to_transcript(b"claim_row_eval_read", transcript);
1264 row_eval_write.append_to_transcript(b"claim_row_eval_write", transcript);
1265 row_eval_audit.append_to_transcript(b"claim_row_eval_audit", transcript);
1266
1267 // subset check
1268 let (col_eval_init, col_eval_read, col_eval_write, col_eval_audit) = &self.eval_col;
1269 assert_eq!(col_eval_write.len(), num_instances);
1270 assert_eq!(col_eval_read.len(), num_instances);
1271 let ws: Scalar = (0..col_eval_write.len())
1272 .map(|i| col_eval_write[i])
1273 .product();
1274 let rs: Scalar = (0..col_eval_read.len()).map(|i| col_eval_read[i]).product();
1275 assert_eq!(ws * col_eval_init, rs * col_eval_audit);
1276
1277 col_eval_init.append_to_transcript(b"claim_col_eval_init", transcript);
1278 col_eval_read.append_to_transcript(b"claim_col_eval_read", transcript);
1279 col_eval_write.append_to_transcript(b"claim_col_eval_write", transcript);
1280 col_eval_audit.append_to_transcript(b"claim_col_eval_audit", transcript);
1281
1282 // verify the evaluation of the sparse polynomial
1283 let (eval_dotp_left, eval_dotp_right) = &self.eval_val;
1284 assert_eq!(eval_dotp_left.len(), eval_dotp_left.len());
1285 assert_eq!(eval_dotp_left.len(), num_instances);
1286 let mut claims_dotp_circuit: Vec<Scalar> = Vec::new();
1287 for i in 0..num_instances {
1288 assert_eq!(eval_dotp_left[i] + eval_dotp_right[i], eval[i]);
1289 eval_dotp_left[i].append_to_transcript(b"claim_eval_dotp_left", transcript);
1290 eval_dotp_right[i].append_to_transcript(b"claim_eval_dotp_right", transcript);
1291
1292 claims_dotp_circuit.push(eval_dotp_left[i]);
1293 claims_dotp_circuit.push(eval_dotp_right[i]);
1294 }
1295
1296 // verify the correctness of claim_row_eval_read, claim_row_eval_write, claim_col_eval_read, and claim_col_eval_write
1297 let mut claims_prod_circuit: Vec<Scalar> = Vec::new();
1298 claims_prod_circuit.extend(row_eval_read);
1299 claims_prod_circuit.extend(row_eval_write);
1300 claims_prod_circuit.extend(col_eval_read);
1301 claims_prod_circuit.extend(col_eval_write);
1302
1303 let (claims_ops, claims_dotp, rand_ops) = self.proof_ops.verify(
1304 &claims_prod_circuit,
1305 &claims_dotp_circuit,
1306 num_ops,
1307 transcript,
1308 );
1309 // verify the correctness of claim_row_eval_init and claim_row_eval_audit
1310 let (claims_mem, _claims_mem_dotp, rand_mem) = self.proof_mem.verify(
1311 &[
1312 *row_eval_init,
1313 *row_eval_audit,
1314 *col_eval_init,
1315 *col_eval_audit,
1316 ],
1317 &Vec::new(),
1318 num_cells,
1319 transcript,
1320 );
1321 timer.stop();
1322
1323 Ok((claims_mem, rand_mem, claims_ops, claims_dotp, rand_ops))
1324 }
1325}
1326
1327#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
1328struct PolyEvalNetworkProof {
1329 proof_prod_layer: ProductLayerProof,
1330 proof_hash_layer: HashLayerProof,
1331}
1332
1333impl PolyEvalNetworkProof {
1334 fn protocol_name() -> &'static [u8] {
1335 b"Sparse polynomial evaluation proof"
1336 }
1337
1338 pub fn prove(
1339 network: &mut PolyEvalNetwork,
1340 dense: &MultiSparseMatPolynomialAsDense,
1341 derefs: &Derefs,
1342 evals: &[Scalar],
1343 gens: &SparseMatPolyCommitmentGens,
1344 transcript: &mut Transcript,
1345 random_tape: &mut RandomTape,
1346 ) -> Self {
1347 transcript.append_protocol_name(PolyEvalNetworkProof::protocol_name());
1348
1349 let (proof_prod_layer, rand_mem, rand_ops) = ProductLayerProof::prove(
1350 &mut network.row_layers.prod_layer,
1351 &mut network.col_layers.prod_layer,
1352 dense,
1353 derefs,
1354 evals,
1355 transcript,
1356 );
1357
1358 // proof of hash layer for row and col
1359 let proof_hash_layer = HashLayerProof::prove(
1360 (&rand_mem, &rand_ops),
1361 dense,
1362 derefs,
1363 gens,
1364 transcript,
1365 random_tape,
1366 );
1367
1368 PolyEvalNetworkProof {
1369 proof_prod_layer,
1370 proof_hash_layer,
1371 }
1372 }
1373
1374 pub fn verify(
1375 &self,
1376 comm: &SparseMatPolyCommitment,
1377 comm_derefs: &DerefsCommitment,
1378 evals: &[Scalar],
1379 gens: &SparseMatPolyCommitmentGens,
1380 rx: &[Scalar],
1381 ry: &[Scalar],
1382 r_mem_check: &(Scalar, Scalar),
1383 nz: usize,
1384 transcript: &mut Transcript,
1385 ) -> Result<(), ProofVerifyError> {
1386 let timer = Timer::new("verify_polyeval_proof");
1387 transcript.append_protocol_name(PolyEvalNetworkProof::protocol_name());
1388
1389 let num_instances = evals.len();
1390 let (r_hash, r_multiset_check) = r_mem_check;
1391
1392 let num_ops = nz.next_power_of_two();
1393 let num_cells = rx.len().pow2();
1394 assert_eq!(rx.len(), ry.len());
1395
1396 let (claims_mem, rand_mem, mut claims_ops, claims_dotp, rand_ops) = self
1397 .proof_prod_layer
1398 .verify(num_ops, num_cells, evals, transcript)?;
1399 assert_eq!(claims_mem.len(), 4);
1400 assert_eq!(claims_ops.len(), 4 * num_instances);
1401 assert_eq!(claims_dotp.len(), 3 * num_instances);
1402
1403 let (claims_ops_row, claims_ops_col) = claims_ops.split_at_mut(2 * num_instances);
1404 let (claims_ops_row_read, claims_ops_row_write) = claims_ops_row.split_at_mut(num_instances);
1405 let (claims_ops_col_read, claims_ops_col_write) = claims_ops_col.split_at_mut(num_instances);
1406
1407 // verify the proof of hash layer
1408 self.proof_hash_layer.verify(
1409 (&rand_mem, &rand_ops),
1410 &(
1411 claims_mem[0],
1412 claims_ops_row_read.to_vec(),
1413 claims_ops_row_write.to_vec(),
1414 claims_mem[1],
1415 ),
1416 &(
1417 claims_mem[2],
1418 claims_ops_col_read.to_vec(),
1419 claims_ops_col_write.to_vec(),
1420 claims_mem[3],
1421 ),
1422 &claims_dotp,
1423 comm,
1424 gens,
1425 comm_derefs,
1426 rx,
1427 ry,
1428 r_hash,
1429 r_multiset_check,
1430 transcript,
1431 )?;
1432 timer.stop();
1433
1434 Ok(())
1435 }
1436}
1437
1438#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
1439pub struct SparseMatPolyEvalProof {
1440 comm_derefs: DerefsCommitment,
1441 poly_eval_network_proof: PolyEvalNetworkProof,
1442}
1443
1444impl SparseMatPolyEvalProof {
1445 fn protocol_name() -> &'static [u8] {
1446 b"Sparse polynomial evaluation proof"
1447 }
1448
1449 fn equalize(rx: &[Scalar], ry: &[Scalar]) -> (Vec<Scalar>, Vec<Scalar>) {
1450 match rx.len().cmp(&ry.len()) {
1451 Ordering::Less => {
1452 let diff = ry.len() - rx.len();
1453 let mut rx_ext = vec![Scalar::zero(); diff];
1454 rx_ext.extend(rx);
1455 (rx_ext, ry.to_vec())
1456 }
1457 Ordering::Greater => {
1458 let diff = rx.len() - ry.len();
1459 let mut ry_ext = vec![Scalar::zero(); diff];
1460 ry_ext.extend(ry);
1461 (rx.to_vec(), ry_ext)
1462 }
1463 Ordering::Equal => (rx.to_vec(), ry.to_vec()),
1464 }
1465 }
1466
1467 pub fn prove(
1468 dense: &MultiSparseMatPolynomialAsDense,
1469 rx: &[Scalar], // point at which the polynomial is evaluated
1470 ry: &[Scalar],
1471 evals: &[Scalar], // a vector evaluation of \widetilde{M}(r = (rx,ry)) for each M
1472 gens: &SparseMatPolyCommitmentGens,
1473 transcript: &mut Transcript,
1474 random_tape: &mut RandomTape,
1475 ) -> SparseMatPolyEvalProof {
1476 transcript.append_protocol_name(SparseMatPolyEvalProof::protocol_name());
1477
1478 // ensure there is one eval for each polynomial in dense
1479 assert_eq!(evals.len(), dense.batch_size);
1480
1481 let (mem_rx, mem_ry) = {
1482 // equalize the lengths of rx and ry
1483 let (rx_ext, ry_ext) = SparseMatPolyEvalProof::equalize(rx, ry);
1484 let poly_rx = EqPolynomial::new(rx_ext).evals();
1485 let poly_ry = EqPolynomial::new(ry_ext).evals();
1486 (poly_rx, poly_ry)
1487 };
1488
1489 let derefs = dense.deref(&mem_rx, &mem_ry);
1490
1491 // commit to non-deterministic choices of the prover
1492 let timer_commit = Timer::new("commit_nondet_witness");
1493 let comm_derefs = {
1494 let comm = derefs.commit(&gens.gens_derefs);
1495 comm.append_to_transcript(b"comm_poly_row_col_ops_val", transcript);
1496 comm
1497 };
1498 timer_commit.stop();
1499
1500 let poly_eval_network_proof = {
1501 // produce a random element from the transcript for hash function
1502 let r_mem_check = transcript.challenge_vector(b"challenge_r_hash", 2);
1503
1504 // build a network to evaluate the sparse polynomial
1505 let timer_build_network = Timer::new("build_layered_network");
1506 let mut net = PolyEvalNetwork::new(
1507 dense,
1508 &derefs,
1509 &mem_rx,
1510 &mem_ry,
1511 &(r_mem_check[0], r_mem_check[1]),
1512 );
1513 timer_build_network.stop();
1514
1515 let timer_eval_network = Timer::new("evalproof_layered_network");
1516 let poly_eval_network_proof = PolyEvalNetworkProof::prove(
1517 &mut net,
1518 dense,
1519 &derefs,
1520 evals,
1521 gens,
1522 transcript,
1523 random_tape,
1524 );
1525 timer_eval_network.stop();
1526
1527 poly_eval_network_proof
1528 };
1529
1530 SparseMatPolyEvalProof {
1531 comm_derefs,
1532 poly_eval_network_proof,
1533 }
1534 }
1535
1536 pub fn verify(
1537 &self,
1538 comm: &SparseMatPolyCommitment,
1539 rx: &[Scalar], // point at which the polynomial is evaluated
1540 ry: &[Scalar],
1541 evals: &[Scalar], // evaluation of \widetilde{M}(r = (rx,ry))
1542 gens: &SparseMatPolyCommitmentGens,
1543 transcript: &mut Transcript,
1544 ) -> Result<(), ProofVerifyError> {
1545 transcript.append_protocol_name(SparseMatPolyEvalProof::protocol_name());
1546
1547 // equalize the lengths of rx and ry
1548 let (rx_ext, ry_ext) = SparseMatPolyEvalProof::equalize(rx, ry);
1549
1550 let (nz, num_mem_cells) = (comm.num_ops, comm.num_mem_cells);
1551 assert_eq!(rx_ext.len().pow2(), num_mem_cells);
1552
1553 // add claims to transcript and obtain challenges for randomized mem-check circuit
1554 self
1555 .comm_derefs
1556 .append_to_transcript(b"comm_poly_row_col_ops_val", transcript);
1557
1558 // produce a random element from the transcript for hash function
1559 let r_mem_check = transcript.challenge_vector(b"challenge_r_hash", 2);
1560
1561 self.poly_eval_network_proof.verify(
1562 comm,
1563 &self.comm_derefs,
1564 evals,
1565 gens,
1566 &rx_ext,
1567 &ry_ext,
1568 &(r_mem_check[0], r_mem_check[1]),
1569 nz,
1570 transcript,
1571 )
1572 }
1573}
1574
1575pub struct SparsePolyEntry {
1576 idx: usize,
1577 val: Scalar,
1578}
1579
1580impl SparsePolyEntry {
1581 pub fn new(idx: usize, val: Scalar) -> Self {
1582 SparsePolyEntry { idx, val }
1583 }
1584}
1585
1586pub struct SparsePolynomial {
1587 num_vars: usize,
1588 Z: Vec<SparsePolyEntry>,
1589}
1590
1591impl SparsePolynomial {
1592 pub fn new(num_vars: usize, Z: Vec<SparsePolyEntry>) -> Self {
1593 SparsePolynomial { num_vars, Z }
1594 }
1595
1596 fn compute_chi(a: &[bool], r: &[Scalar]) -> Scalar {
1597 assert_eq!(a.len(), r.len());
1598 let mut chi_i = Scalar::one();
1599 for j in 0..r.len() {
1600 if a[j] {
1601 chi_i *= r[j];
1602 } else {
1603 chi_i *= Scalar::one() - r[j];
1604 }
1605 }
1606 chi_i
1607 }
1608
1609 // Takes O(n log n). TODO: do this in O(n) where n is the number of entries in Z
1610 pub fn evaluate(&self, r: &[Scalar]) -> Scalar {
1611 assert_eq!(self.num_vars, r.len());
1612
1613 (0..self.Z.len())
1614 .map(|i| {
1615 let bits = self.Z[i].idx.get_bits(r.len());
1616 SparsePolynomial::compute_chi(&bits, r) * self.Z[i].val
1617 })
1618 .sum()
1619 }
1620}
1621
1622#[cfg(test)]
1623mod tests {
1624 use super::*;
1625use ark_std::{UniformRand};
1626use rand::RngCore;
1627
1628 #[test]
1629 fn check_sparse_polyeval_proof() {
1630 let mut rng = ark_std::rand::thread_rng();
1631
1632 let num_nz_entries: usize = 256;
1633 let num_rows: usize = 256;
1634 let num_cols: usize = 256;
1635 let num_vars_x: usize = num_rows.log2() as usize;
1636 let num_vars_y: usize = num_cols.log2() as usize;
1637
1638 let mut M: Vec<SparseMatEntry> = Vec::new();
1639
1640 for _i in 0..num_nz_entries {
1641 M.push(SparseMatEntry::new(
1642 (rng.next_u64()% (num_rows as u64)) as usize,
1643 (rng.next_u64() % (num_cols as u64)) as usize,
1644 Scalar::rand(&mut rng),
1645 ));
1646 }
1647
1648 let poly_M = SparseMatPolynomial::new(num_vars_x, num_vars_y, M);
1649 let gens = SparseMatPolyCommitmentGens::new(
1650 b"gens_sparse_poly",
1651 num_vars_x,
1652 num_vars_y,
1653 num_nz_entries,
1654 3,
1655 );
1656
1657 // commitment
1658 let (poly_comm, dense) = SparseMatPolynomial::multi_commit(&[&poly_M, &poly_M, &poly_M], &gens);
1659
1660 // evaluation
1661 let rx: Vec<Scalar> = (0..num_vars_x)
1662 .map(|_i| Scalar::rand(&mut rng))
1663 .collect::<Vec<Scalar>>();
1664 let ry: Vec<Scalar> = (0..num_vars_y)
1665 .map(|_i| Scalar::rand(&mut rng))
1666 .collect::<Vec<Scalar>>();
1667 let eval = SparseMatPolynomial::multi_evaluate(&[&poly_M], &rx, &ry);
1668 let evals = vec![eval[0], eval[0], eval[0]];
1669
1670 let mut random_tape = RandomTape::new(b"proof");
1671 let mut prover_transcript = Transcript::new(b"example");
1672 let proof = SparseMatPolyEvalProof::prove(
1673 &dense,
1674 &rx,
1675 &ry,
1676 &evals,
1677 &gens,
1678 &mut prover_transcript,
1679 &mut random_tape,
1680 );
1681
1682 let mut verifier_transcript = Transcript::new(b"example");
1683 assert!(proof
1684 .verify(
1685 &poly_comm,
1686 &rx,
1687 &ry,
1688 &evals,
1689 &gens,
1690 &mut verifier_transcript,
1691 )
1692 .is_ok());
1693 }
1694}