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