Refactors testing around Spartan Polynomials (microsoft#221)

* doc: Improve code comments by adding backticks for formatting - Back-ticks have been added around relevant technical terms, type names, and code references within the comments to better highlight them while reading. * refactor: Refactor Spartan polynomial file organization - Refactor the structure of Spartan SNARK related modules, mainly moving and renaming `polynomial.rs` to `polys/mlpoly.rs` and introducing three new submodules under `polys`: `eq_poly`, `mlpoly`, and `unipoly`. - Implement a new module `polys` that houses refactored and newly introduced polynomial types used in the Spartan SNARK, leading to import refactors across numerous files. - Establish a new file `unipoly.rs` responsible for housing the main structs `UniPoly` and `CompressedUniPoly` * refactor: Fix comment in UniPoly storage and enhance testing - Fix comment about ordering of coefficient storage protocol in `UniPoly` and `CompressedUniPoly` structures for improved processing. - Integrated unit tests for 'from_evals_quad' and 'from_evals_cubic' in context of `pallas::Scalar` and `bn256::Scalar` types, * test: Add multilinear polynomial evaluation test - Introduced new test for multilinear polynomial evaluation in the mlpoly.rs file. * chore: rename to eq / multilinear / univariate * chore: remove unnecessary qualificaitons
dbsrjsgh01 · Aug 22, 2023 · 9659c6e · 9659c6e
1 parent d0a773a
commit 9659c6e
Show file tree

Hide file tree

Showing 24 changed files with 394 additions and 265 deletions.
diff --git a/examples/minroot.rs b/examples/minroot.rs
@@ -1,6  1,6 @@
 //! Demonstrates how to use Nova to produce a recursive proof of the correct execution of
-//! iterations of the MinRoot function, thereby realizing a Nova-based verifiable delay function (VDF).
-//! We execute a configurable number of iterations of the MinRoot function per step of Nova's recursion.
 //! iterations of the `MinRoot` function, thereby realizing a Nova-based verifiable delay function (VDF).
 //! We execute a configurable number of iterations of the `MinRoot` function per step of Nova's recursion.
 type G1 = pasta_curves::pallas::Point;
 type G2 = pasta_curves::vesta::Point;
 use bellpepper_core::{num::AllocatedNum, ConstraintSystem, SynthesisError};

diff --git a/src/circuit.rs b/src/circuit.rs
@@ -182,7  182,7 @@ impl<'a, G: Group, SC: StepCircuit<G::Base>> NovaAugmentedCircuit<'a, G, SC> {
     Ok((params, i, z_0, z_i, U, u, T))
   }
 
-  /// Synthesizes base case and returns the new relaxed R1CSInstance
   /// Synthesizes base case and returns the new relaxed `R1CSInstance`
   fn synthesize_base_case<CS: ConstraintSystem<<G as Group>::Base>>(
     &self,
     mut cs: CS,
@@ -207,7  207,7 @@ impl<'a, G: Group, SC: StepCircuit<G::Base>> NovaAugmentedCircuit<'a, G, SC> {
     Ok(U_default)
   }
 
-  /// Synthesizes non base case and returns the new relaxed R1CSInstance
   /// Synthesizes non base case and returns the new relaxed `R1CSInstance`
   /// And a boolean indicating if all checks pass
   #[allow(clippy::too_many_arguments)]
   fn synthesize_non_base_case<CS: ConstraintSystem<<G as Group>::Base>>(

diff --git a/src/gadgets/ecc.rs b/src/gadgets/ecc.rs
@@ -16,7  16,7 @@ use bellpepper_core::{
 };
 use ff::{Field, PrimeField};
 
-/// AllocatedPoint provides an elliptic curve abstraction inside a circuit.
 /// `AllocatedPoint` provides an elliptic curve abstraction inside a circuit.
 #[derive(Clone)]
 pub struct AllocatedPoint<G>
 where
@@ -156,7  156,7 @@ where
   }
 
   /// Adds other point to this point and returns the result. Assumes that the two points are
-  /// different and that both other.is_infinity and this.is_infinty are bits
   /// different and that both `other.is_infinity` and `this.is_infinty` are bits
   pub fn add_internal<CS: ConstraintSystem<G::Base>>(
     &self,
     mut cs: CS,
@@ -554,7  554,7 @@ where
 }
 
 #[derive(Clone)]
-/// AllocatedPoint but one that is guaranteed to be not infinity
 /// `AllocatedPoint` but one that is guaranteed to be not infinity
 pub struct AllocatedPointNonInfinity<G>
 where
   G: Group,
@@ -567,7  567,7 @@ impl<G> AllocatedPointNonInfinity<G>
 where
   G: Group,
 {
-  /// Creates a new AllocatedPointNonInfinity from the specified coordinates
   /// Creates a new `AllocatedPointNonInfinity` from the specified coordinates
   pub const fn new(x: AllocatedNum<G::Base>, y: AllocatedNum<G::Base>) -> Self {
     Self { x, y }
   }
@@ -587,15  587,15 @@ where
     Ok(Self { x, y })
   }
 
-  /// Turns an AllocatedPoint into an AllocatedPointNonInfinity (assumes it is not infinity)
   /// Turns an `AllocatedPoint` into an `AllocatedPointNonInfinity` (assumes it is not infinity)
   pub fn from_allocated_point(p: &AllocatedPoint<G>) -> Self {
     Self {
       x: p.x.clone(),
       y: p.y.clone(),
     }
   }
 
-  /// Returns an AllocatedPoint from an AllocatedPointNonInfinity
   /// Returns an `AllocatedPoint` from an `AllocatedPointNonInfinity`
   pub fn to_allocated_point(
     &self,
     is_infinity: &AllocatedNum<G::Base>,

diff --git a/src/gadgets/nonnative/bignat.rs b/src/gadgets/nonnative/bignat.rs
@@ -91,12  91,12 @@ pub struct BigNat<Scalar: PrimeField> {
   pub params: BigNatParams,
 }
 
-impl<Scalar: PrimeField> std::cmp::PartialEq for BigNat<Scalar> {
 impl<Scalar: PrimeField> PartialEq for BigNat<Scalar> {
   fn eq(&self, other: &Self) -> bool {
     self.value == other.value && self.params == other.params
   }
 }
-impl<Scalar: PrimeField> std::cmp::Eq for BigNat<Scalar> {}
 impl<Scalar: PrimeField> Eq for BigNat<Scalar> {}
 
 impl<Scalar: PrimeField> From<BigNat<Scalar>> for Polynomial<Scalar> {
   fn from(other: BigNat<Scalar>) -> Polynomial<Scalar> {
@@ -360,7  360,7 @@ impl<Scalar: PrimeField> BigNat<Scalar> {
     let n = min(self.limbs.len(), other.limbs.len());
     let target_base = BigInt::from(1u8) << self.params.limb_width as u32;
     let mut accumulated_extra = BigInt::from(0usize);
-    let max_word = std::cmp::max(&self.params.max_word, &other.params.max_word);
     let max_word = max(&self.params.max_word, &other.params.max_word);
     let carry_bits = (((max_word.to_f64().unwrap() * 2.0).log2() - self.params.limb_width as f64)
       .ceil()
         0.1) as usize;
@@ -439,7  439,7 @@ impl<Scalar: PrimeField> BigNat<Scalar> {
     other: &Self,
   ) -> Result<(), SynthesisError> {
     self.enforce_limb_width_agreement(other, "equal_when_carried_regroup")?;
-    let max_word = std::cmp::max(&self.params.max_word, &other.params.max_word);
     let max_word = max(&self.params.max_word, &other.params.max_word);
     let carry_bits = (((max_word.to_f64().unwrap() * 2.0).log2() - self.params.limb_width as f64)
       .ceil()
         0.1) as usize;
@@ -552,7  552,7 @@ impl<Scalar: PrimeField> BigNat<Scalar> {
       x
     };
     let right_max_word = {
-      let mut x = BigInt::from(std::cmp::min(quotient.limbs.len(), modulus.limbs.len()));
       let mut x = BigInt::from(min(quotient.limbs.len(), modulus.limbs.len()));
       x *= &quotient.params.max_word;
       x *= &modulus.params.max_word;
       x  = &remainder.params.max_word;
@@ -598,7  598,7 @@ impl<Scalar: PrimeField> BigNat<Scalar> {
     let right = right_product.sum(&r_poly);
 
     let right_max_word = {
-      let mut x = BigInt::from(std::cmp::min(quotient.limbs.len(), modulus.limbs.len()));
       let mut x = BigInt::from(min(quotient.limbs.len(), modulus.limbs.len()));
       x *= &quotient.params.max_word;
       x *= &modulus.params.max_word;
       x  = &remainder.params.max_word;
@@ -823,7  823,7 @@ mod tests {
 
   #[test]
   fn test_polynomial_multiplier_circuit() {
-    let mut cs = TestConstraintSystem::<pasta_curves::pallas::Scalar>::new();
     let mut cs = TestConstraintSystem::<Scalar>::new();
 
     let circuit = PolynomialMultiplier {
       a: [1, 1, 1].iter().map(|i| Scalar::from_u128(*i)).collect(),
@@ -890,7  890,7 @@ mod tests {
                 n_limbs,
             },
         };
-        let mut cs = TestConstraintSystem::<pasta_curves::pallas::Scalar>::new();
         let mut cs = TestConstraintSystem::<Scalar>::new();
         circuit.synthesize(&mut cs).expect("synthesis failed");
         prop_assert!(cs.is_satisfied());
     }

diff --git a/src/gadgets/r1cs.rs b/src/gadgets/r1cs.rs
@@ -71,7  71,7 @@ pub struct AllocatedRelaxedR1CSInstance<G: Group> {
 }
 
 impl<G: Group> AllocatedRelaxedR1CSInstance<G> {
-  /// Allocates the given RelaxedR1CSInstance as a witness of the circuit
   /// Allocates the given `RelaxedR1CSInstance` as a witness of the circuit
   pub fn alloc<CS: ConstraintSystem<<G as Group>::Base>>(
     mut cs: CS,
     inst: Option<&RelaxedR1CSInstance<G>>,
@@ -117,7  117,7 @@ impl<G: Group> AllocatedRelaxedR1CSInstance<G> {
     Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
   }
 
-  /// Allocates the hardcoded default RelaxedR1CSInstance in the circuit.
   /// Allocates the hardcoded default `RelaxedR1CSInstance` in the circuit.
   /// W = E = 0, u = 0, X0 = X1 = 0
   pub fn default<CS: ConstraintSystem<<G as Group>::Base>>(
     mut cs: CS,
@@ -146,7  146,7 @@ impl<G: Group> AllocatedRelaxedR1CSInstance<G> {
     Ok(AllocatedRelaxedR1CSInstance { W, E, u, X0, X1 })
   }
 
-  /// Allocates the R1CS Instance as a RelaxedR1CSInstance in the circuit.
   /// Allocates the R1CS Instance as a `RelaxedR1CSInstance` in the circuit.
   /// E = 0, u = 1
   pub fn from_r1cs_instance<CS: ConstraintSystem<<G as Group>::Base>>(
     mut cs: CS,

diff --git a/src/gadgets/utils.rs b/src/gadgets/utils.rs
@@ -225,7  225,7 @@ pub fn conditionally_select_vec<F: PrimeField, CS: ConstraintSystem<F>>(
     .collect::<Result<Vec<AllocatedNum<F>>, SynthesisError>>()
 }
 
-/// If condition return a otherwise b where a and b are BigNats
 /// If condition return a otherwise b where a and b are `BigNats`
 pub fn conditionally_select_bignat<F: PrimeField, CS: ConstraintSystem<F>>(
   mut cs: CS,
   a: &BigNat<F>,
@@ -259,7  259,7 @@ pub fn conditionally_select_bignat<F: PrimeField, CS: ConstraintSystem<F>>(
   Ok(c)
 }
 
-/// Same as the above but Condition is an AllocatedNum that needs to be
 /// Same as the above but Condition is an `AllocatedNum` that needs to be
 /// 0 or 1. 1 => True, 0 => False
 pub fn conditionally_select2<F: PrimeField, CS: ConstraintSystem<F>>(
   mut cs: CS,

diff --git a/src/lib.rs b/src/lib.rs
@@ -783,7  783,7 @@ where
   }
 }
 
-type CommitmentKey<G> = <<G as traits::Group>::CE as CommitmentEngineTrait<G>>::CommitmentKey;
 type CommitmentKey<G> = <<G as Group>::CE as CommitmentEngineTrait<G>>::CommitmentKey;
 type Commitment<G> = <<G as Group>::CE as CommitmentEngineTrait<G>>::Commitment;
 type CompressedCommitment<G> = <<<G as Group>::CE as CommitmentEngineTrait<G>>::Commitment as CommitmentTrait<G>>::CompressedCommitment;
 type CE<G> = <G as Group>::CE;

diff --git a/src/provider/bn256_grumpkin.rs b/src/provider/bn256_grumpkin.rs
@@ -1,4  1,4 @@
-//! This module implements the Nova traits for bn256::Point, bn256::Scalar, grumpkin::Point, grumpkin::Scalar.
 //! This module implements the Nova traits for `bn256::Point`, `bn256::Scalar`, `grumpkin::Point`, `grumpkin::Scalar`.
 use crate::{
   provider::{
     cpu_best_multiexp,

diff --git a/src/provider/ipa_pc.rs b/src/provider/ipa_pc.rs
@@ -3,7  3,7 @@
 use crate::{
   errors::NovaError,
   provider::pedersen::CommitmentKeyExtTrait,
-  spartan::polynomial::EqPolynomial,
   spartan::polys::eq::EqPolynomial,
   traits::{
     commitment::{CommitmentEngineTrait, CommitmentTrait},
     evaluation::EvaluationEngineTrait,

diff --git a/src/provider/keccak.rs b/src/provider/keccak.rs
@@ -1,4  1,4 @@
-//! This module provides an implementation of TranscriptEngineTrait using keccak256
 //! This module provides an implementation of `TranscriptEngineTrait` using keccak256
 use crate::traits::PrimeFieldExt;
 use crate::{
   errors::NovaError,
@@ -13,7  13,7 @@ const KECCAK256_STATE_SIZE: usize = 64;
 const KECCAK256_PREFIX_CHALLENGE_LO: u8 = 0;
 const KECCAK256_PREFIX_CHALLENGE_HI: u8 = 1;
 
-/// Provides an implementation of TranscriptEngine
 /// Provides an implementation of `TranscriptEngine`
 #[derive(Debug, Clone)]
 pub struct Keccak256Transcript<G: Group> {
   round: u16,

diff --git a/src/provider/pasta.rs b/src/provider/pasta.rs
@@ -1,4  1,4 @@
-//! This module implements the Nova traits for pallas::Point, pallas::Scalar, vesta::Point, vesta::Scalar.
 //! This module implements the Nova traits for `pallas::Point`, `pallas::Scalar`, `vesta::Point`, `vesta::Scalar`.
 use crate::{
   provider::{
     cpu_best_multiexp,

diff --git a/src/r1cs.rs b/src/r1cs.rs
@@ -305,7  305,7 @@ impl<G: Group> R1CSShape<G> {
     Ok((T, comm_T))
   }
 
-  /// Pads the R1CSShape so that the number of variables is a power of two
   /// Pads the `R1CSShape` so that the number of variables is a power of two
   /// Renumbers variables to accomodate padded variables
   pub fn pad(&self) -> Self {
     // equalize the number of variables and constraints
@@ -407,15  407,15 @@ impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
 }
 
 impl<G: Group> RelaxedR1CSWitness<G> {
-  /// Produces a default RelaxedR1CSWitness given an R1CSShape
   /// Produces a default `RelaxedR1CSWitness` given an `R1CSShape`
   pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
     RelaxedR1CSWitness {
       W: vec![G::Scalar::ZERO; S.num_vars],
       E: vec![G::Scalar::ZERO; S.num_cons],
     }
   }
 
-  /// Initializes a new RelaxedR1CSWitness from an R1CSWitness
   /// Initializes a new `RelaxedR1CSWitness` from an `R1CSWitness`
   pub fn from_r1cs_witness(S: &R1CSShape<G>, witness: &R1CSWitness<G>) -> RelaxedR1CSWitness<G> {
     RelaxedR1CSWitness {
       W: witness.W.clone(),
@@ -428,7  428,7 @@ impl<G: Group> RelaxedR1CSWitness<G> {
     (CE::<G>::commit(ck, &self.W), CE::<G>::commit(ck, &self.E))
   }
 
-  /// Folds an incoming R1CSWitness into the current one
   /// Folds an incoming `R1CSWitness` into the current one
   pub fn fold(
     &self,
     W2: &R1CSWitness<G>,
@@ -474,7  474,7 @@ impl<G: Group> RelaxedR1CSWitness<G> {
 }
 
 impl<G: Group> RelaxedR1CSInstance<G> {
-  /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
   /// Produces a default `RelaxedR1CSInstance` given `R1CSGens` and `R1CSShape`
   pub fn default(_ck: &CommitmentKey<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
     let (comm_W, comm_E) = (Commitment::<G>::default(), Commitment::<G>::default());
     RelaxedR1CSInstance {
@@ -485,7  485,7 @@ impl<G: Group> RelaxedR1CSInstance<G> {
     }
   }
 
-  /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
   /// Initializes a new `RelaxedR1CSInstance` from an `R1CSInstance`
   pub fn from_r1cs_instance(
     ck: &CommitmentKey<G>,
     S: &R1CSShape<G>,
@@ -498,7  498,7 @@ impl<G: Group> RelaxedR1CSInstance<G> {
     r_instance
   }
 
-  /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
   /// Initializes a new `RelaxedR1CSInstance` from an `R1CSInstance`
   pub fn from_r1cs_instance_unchecked(
     comm_W: &Commitment<G>,
     X: &[G::Scalar],
@@ -511,7  511,7 @@ impl<G: Group> RelaxedR1CSInstance<G> {
     }
   }
 
-  /// Folds an incoming RelaxedR1CSInstance into the current one
   /// Folds an incoming `RelaxedR1CSInstance` into the current one
   pub fn fold(
     &self,
     U2: &R1CSInstance<G>,

diff --git a/src/spartan/direct.rs b/src/spartan/direct.rs
@@ -1,5  1,5 @@
 //! This module provides interfaces to directly prove a step circuit by using Spartan SNARK.
-//! In particular, it supports any SNARK that implements RelaxedR1CSSNARK trait
 //! In particular, it supports any SNARK that implements `RelaxedR1CSSNARK` trait
 //! (e.g., with the SNARKs implemented in ppsnark.rs or snark.rs).
 use crate::{
   bellpepper::{

diff --git a/src/spartan/math.rs b/src/spartan/math.rs
@@ -11,7  11,7 @@ impl Math for usize {
     base.pow(self as u32)
   }
 
-  /// Returns the num_bits from n in a canonical order
   /// Returns the `num_bits` from n in a canonical order
   fn get_bits(self, num_bits: usize) -> Vec<bool> {
     (0..num_bits)
       .map(|shift_amount| ((self & (1 << (num_bits - shift_amount - 1))) > 0))

diff --git a/src/spartan/mod.rs b/src/spartan/mod.rs
@@ -1,4  1,4 @@
-//! This module implements RelaxedR1CSSNARKTrait using Spartan that is generic
 //! This module implements `RelaxedR1CSSNARKTrait` using Spartan that is generic
 //! over the polynomial commitment and evaluation argument (i.e., a PCS)
 //! We provide two implementations, one in snark.rs (which does not use any preprocessing)
 //! and another in ppsnark.rs (which uses preprocessing to keep the verifier's state small if the PCS provides a succinct verifier)
@@ -7,14  7,14 @@
 //! In polynomial.rs we also provide foundational types and functions for manipulating multilinear polynomials.
 pub mod direct;
 pub(crate) mod math;
-pub mod polynomial;
 pub mod polys;
 pub mod ppsnark;
 pub mod snark;
 mod sumcheck;
 
 use crate::{traits::Group, Commitment};
 use ff::Field;
-use polynomial::SparsePolynomial;
 use polys::multilinear::SparsePolynomial;
 
 fn powers<G: Group>(s: &G::Scalar, n: usize) -> Vec<G::Scalar> {
   assert!(n >= 1);