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