Merge pull request #36 from a16z/refactor/delete-sparse-lookup-matrix

refactor: Delete `SparseLookupMatrix`
a16z · Aug 15, 2023 · 6d79ffa · 6d79ffa
2 parents 8dbcfb0 + d7a6706
commit 6d79ffa
Show file tree

Hide file tree

Showing 6 changed files with 24 additions and 51 deletions.
diff --git a/EngineeringOverview.md b/EngineeringOverview.md
@@ -62,9 +62,7 @@ $v_{E_i}$ is provided by sumcheck in step 2. $E_i(r_z)$ is provided by an oracle
 
 ### 1. Prover commitments
 
-`SparseLookupMatrix` is created from a `C` sized vector of non-zero indices along each dimension.
-
-We convert the `SparseLookupMatrix` to a `DensifiedRepresentation` which handles the construction of:
+We convert a `C` sized vector of lookup indices into a `DensifiedRepresentation` which handles the construction of:
 
 -   $`\text{dim}_i \ \forall i=1,...,C`$
 -   $`E_i \ \forall i=1,...,C`$

diff --git a/README.md b/README.md
@@ -18,8 +18,7 @@ Lookup Arguments via Sum-check and Sparse polynomial commitments, including for
 ## Current usage
 
 ```rust
-  let lookup_matrix = SparseLookupMatrix::new(nz, log_M);
-  let mut dense: DensifiedRepresentation<F, C> = DensifiedRepresentation::from(&lookup_matrix);
+  let mut dense: DensifiedRepresentation<F, C> = DensifiedRepresentation::from(&nz, log_M);
   let commitment = dense.commit::<G>(&gens);
 
   let proof =

diff --git a/src/benches/bench.rs b/src/benches/bench.rs
@@ -1,10 +1,7 @@
 use crate::lasso::surge::SparsePolyCommitmentGens;
 use crate::subtables::and::AndSubtableStrategy;
 use crate::{
-  lasso::{
-    densified::DensifiedRepresentation,
-    surge::{SparseLookupMatrix, SparsePolynomialEvaluationProof},
-  },
+  lasso::{densified::DensifiedRepresentation, surge::SparsePolynomialEvaluationProof},
   utils::random::RandomTape,
 };
 use ark_curve25519::{EdwardsProjective, Fr};
@@ -52,10 +49,10 @@ macro_rules! single_pass_lasso {
       let r: Vec<F> = gen_random_point::<F>(log_s);
 
       let nz = gen_indices::<C>(S, M);
-      let lookup_matrix = SparseLookupMatrix::new(nz.clone(), log_m);
 
       // Prove
-      let mut dense: DensifiedRepresentation<F, C> = DensifiedRepresentation::from(&lookup_matrix);
+      let mut dense: DensifiedRepresentation<F, C> =
+        DensifiedRepresentation::from_lookup_indices(&nz, log_m);
       let gens = SparsePolyCommitmentGens::<G>::new(b"gens_sparse_poly", C, S, C, log_m);
       let _commitment = dense.commit::<$group>(&gens);
       let mut random_tape = RandomTape::new(b"proof");

diff --git a/src/e2e_test.rs b/src/e2e_test.rs
@@ -4,7 +4,7 @@ use merlin::Transcript;
 use crate::{
   lasso::{
     densified::DensifiedRepresentation,
-    surge::{SparseLookupMatrix, SparsePolyCommitmentGens, SparsePolynomialEvaluationProof},
+    surge::{SparsePolyCommitmentGens, SparsePolynomialEvaluationProof},
   },
   subtables::{
     and::AndSubtableStrategy, lt::LTSubtableStrategy, range_check::RangeCheckSubtableStrategy,
@@ -32,9 +32,8 @@ macro_rules! e2e_test {
       // generate sparse polynomial
       let nz: Vec<[usize; C]> = gen_indices($sparsity, M);
 
-      let lookup_matrix = SparseLookupMatrix::new(nz, log_M);
-
-      let mut dense: DensifiedRepresentation<$F, C> = DensifiedRepresentation::from(&lookup_matrix);
+      let mut dense: DensifiedRepresentation<$F, C> =
+        DensifiedRepresentation::from_lookup_indices(&nz, log_M);
       let gens =
         SparsePolyCommitmentGens::<$G>::new(b"gens_sparse_poly", C, $sparsity, NUM_MEMORIES, log_M);
       let commitment = dense.commit::<$G>(&gens);

diff --git a/src/lasso/densified.rs b/src/lasso/densified.rs
@@ -1,8 +1,9 @@
 use ark_ec::CurveGroup;
 use ark_ff::PrimeField;
 
+use super::surge::{SparsePolyCommitmentGens, SparsePolynomialCommitment};
 use crate::poly::dense_mlpoly::DensePolynomial;
-use super::surge::{SparseLookupMatrix, SparsePolyCommitmentGens, SparsePolynomialCommitment};
+use crate::utils::math::Math;
 
 pub struct DensifiedRepresentation<F: PrimeField, const C: usize> {
   pub dim_usize: [Vec<usize>; C],
@@ -16,31 +17,33 @@ pub struct DensifiedRepresentation<F: PrimeField, const C: usize> {
   pub m: usize,
 }
 
-impl<F: PrimeField, const C: usize> From<&SparseLookupMatrix<C>> for DensifiedRepresentation<F, C> {
+impl<F: PrimeField, const C: usize> DensifiedRepresentation<F, C> {
   #[tracing::instrument(skip_all, name = "Densify")]
-  fn from(sparse: &SparseLookupMatrix<C>) -> Self {
+  pub fn from_lookup_indices(indices: &Vec<[usize; C]>, log_m: usize) -> Self {
+    let s = indices.len().next_power_of_two();
+    let m = log_m.pow2();
+
     let mut dim_usize: Vec<Vec<usize>> = Vec::with_capacity(C);
     let mut dim: Vec<DensePolynomial<F>> = Vec::with_capacity(C);
     let mut read: Vec<DensePolynomial<F>> = Vec::with_capacity(C);
     let mut r#final: Vec<DensePolynomial<F>> = Vec::with_capacity(C);
 
     // TODO(#29): Parallelize
     for i in 0..C {
-      let mut access_sequence = sparse
-        .nz
+      let mut access_sequence = indices
         .iter()
         .map(|indices| indices[i])
         .collect::<Vec<usize>>();
-      access_sequence.resize(sparse.s, 0usize);
+      access_sequence.resize(s, 0usize);
 
-      let mut final_timestamps = vec![0usize; sparse.m];
-      let mut read_timestamps = vec![0usize; sparse.s];
+      let mut final_timestamps = vec![0usize; m];
+      let mut read_timestamps = vec![0usize; s];
 
       // since read timestamps are trustworthy, we can simply increment the r-ts to obtain a w-ts
       // this is sufficient to ensure that the write-set, consisting of (addr, val, ts) tuples, is a set
-      for i in 0..sparse.s {
+      for i in 0..s {
         let memory_address = access_sequence[i];
-        debug_assert!(memory_address < sparse.m);
+        debug_assert!(memory_address < m);
         let ts = final_timestamps[memory_address];
         read_timestamps[i] = ts;
         let write_timestamp = ts + 1;
@@ -65,14 +68,12 @@ impl<F: PrimeField, const C: usize> From<&SparseLookupMatrix<C>> for DensifiedRe
       r#final: r#final.try_into().unwrap(),
       combined_l_variate_polys,
       combined_log_m_variate_polys,
-      s: sparse.s,
-      log_m: sparse.log_m,
-      m: sparse.m,
+      s,
+      log_m,
+      m,
     }
   }
-}
 
-impl<F: PrimeField, const C: usize> DensifiedRepresentation<F, C> {
   #[tracing::instrument(skip_all, name = "DensifiedRepresentation.commit")]
   pub fn commit<G: CurveGroup<ScalarField = F>>(
     &self,

diff --git a/src/lasso/surge.rs b/src/lasso/surge.rs
@@ -80,27 +80,6 @@ impl<G: CurveGroup> AppendToTranscript<G> for SparsePolynomialCommitment<G> {
   }
 }
 
-#[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
-pub struct SparseLookupMatrix<const C: usize> {
-  pub nz: Vec<[usize; C]>, // non-zero indices nz_1(i), ..., nz_c(i)
-  pub s: usize,            // sparsity
-  pub log_m: usize,
-  pub m: usize,
-}
-
-impl<const C: usize> SparseLookupMatrix<C> {
-  pub fn new(nonzero_indices: Vec<[usize; C]>, log_m: usize) -> Self {
-    let s = nonzero_indices.len().next_power_of_two();
-
-    SparseLookupMatrix {
-      nz: nonzero_indices,
-      s,
-      log_m,
-      m: log_m.pow2(),
-    }
-  }
-}
-
 #[derive(Debug, CanonicalSerialize, CanonicalDeserialize)]
 struct PrimarySumcheck<G: CurveGroup, const ALPHA: usize> {
   proof: SumcheckInstanceProof<G::ScalarField>,