0xProject · z2trillion · Mar 27, 2020 · Mar 26, 2020 · Mar 26, 2020 · Mar 26, 2020
diff --git a/algebra/primefield/src/test.rs b/algebra/primefield/src/test.rs
@@ -1,14 1,18 @@
-use crate::{Parameters, PrimeField, UInt};
 use crate::{u256::U256, Parameters, PrimeField};
 use quickcheck::{Arbitrary, Gen};
 
-impl<U, P> Arbitrary for PrimeField<P>
 impl<P> Arbitrary for PrimeField<P>
 where
- U: UInt Arbitrary,
- P: Parameters<UInt = U>,
  P: Parameters<UInt = U256>,
 {
  #[inline(always)]
  fn arbitrary<G: Gen>(g: &mut G) -> Self {
- Self::from_uint_reduce(&U::arbitrary(g))
  Self::from_uint_reduce(&U256::from_limbs([
  u64::arbitrary(g),
  u64::arbitrary(g),
  u64::arbitrary(g),
  u64::arbitrary(g),
  ]))
  }
 }
 

diff --git a/algebra/u256/Cargo.toml b/algebra/u256/Cargo.toml
@@ -22,12 22,14 @@ num-traits = { version = "0.2.10", default_features = false }
 quickcheck = { version = "0.9", optional = true }
 rand = { version = "0.7.2", optional = true }
 serde = { version = "1.0", features = ["derive"], optional = true}
 proptest = { version = "0.9.4", optional = true }
 proptest-derive = { version = "0.1.2", optional = true }
 zkp-macros-decl = { version = "0.1.0", path = "../../utils/macros-decl", default_features = false }
 
 [dev-dependencies]
 criterion = "0.3.0"
-quickcheck = "0.9"
-quickcheck_macros = "0.9.1"
 proptest = "0.9.5"
 proptest-derive = "0.1.2"
 
 [[bench]]
 name = "benchmark"

diff --git a/algebra/u256/src/additive.rs b/algebra/u256/src/additive.rs
@@ -107,12 107,10 @@ impl core::iter::Sum for U256 {
 
 // TODO: Replace literals with u256h!
 #[allow(clippy::unreadable_literal)]
-// Quickcheck requires pass by value
-#[allow(clippy::needless_pass_by_value)]
 #[cfg(test)]
 mod tests {
  use super::*;
- use quickcheck_macros::quickcheck;
  use proptest::prelude::*;
  use zkp_macros_decl::u256h;
 
  #[test]
@@ -158,12 156,10 @@ mod tests {
  assert_eq!(a, e);
  }
 
- #[quickcheck]
- fn commutative_add(a: U256, b: U256) -> bool {
- let mut l = a.clone();
- let mut r = b.clone();
- l = &b;
- r = &a;
- l == r
- }
  proptest!(
  #[test]
  fn commutative_add(a: U256, b: U256) {
  prop_assert_eq!(&a &b, b a);
  }
  );
 }
diff --git a/algebra/u256/src/algorithms/knuth_division.rs b/algebra/u256/src/algorithms/knuth_division.rs
@@ -173,7 173,7 @@ pub fn divrem_nbym(numerator: &mut [u64], divisor: &mut [u64]) {
 mod tests {
  use super::*;
  use crate::u256::U256;
- use quickcheck_macros::quickcheck;
  use proptest::prelude::*;
  use zkp_macros_decl::u256h;
 
  const HALF: u64 = 1_u64 << 63;
@@ -253,13 253,15 @@ mod tests {
  assert_eq!(quotient, 1);
  }
 
- #[quickcheck]
- fn div_3by2_correct(q: u64, d0: u64, d1: u64) -> bool {
- // TODO: Add remainder
- let d1 = d1 | (1 << 63);
- let n = U256::from_limbs([d0, d1, 0, 0]) * &U256::from(q);
- debug_assert!(n.limb(3) == 0);
- let qhat = div_3by2(&[n.limb(0), n.limb(1), n.limb(2)], &[d0, d1]);
- qhat == q
- }
  proptest!(
  #[test]
  fn div_3by2_correct(q: u64, d0: u64, d1: u64) {
  // TODO: Add remainder
  let d1 = d1 | (1 << 63);
  let n = U256::from_limbs([d0, d1, 0, 0]) * &U256::from(q);
  debug_assert!(n.limb(3) == 0);
  let qhat = div_3by2(&[n.limb(0), n.limb(1), n.limb(2)], &[d0, d1]);
  prop_assert_eq!(qhat, q);
  }
  );
 }
diff --git a/algebra/u256/src/algorithms/lehmer_gcd.rs b/algebra/u256/src/algorithms/lehmer_gcd.rs
@@ -21,7 21,7 @@ impl Matrix {
 /// Computes a double linear combination efficiently in place.
 ///
 /// Simulataneously computes
-/// 
 ///
 /// ```text
 /// a' = q00 a - q01 b
 /// b' = q11 b - q10 a
@@ -479,7 479,8 @@ pub(crate) fn inv_mod(modulus: &U256, num: &U256) -> Option<U256> {
 #[cfg(test)]
 mod tests {
  use super::*;
- use quickcheck_macros::quickcheck;
  use num_traits::identities::{One, Zero};
  use proptest::prelude::*;
  use zkp_macros_decl::u256h;
 
  #[test]
@@ -530,76 531,73 @@ mod tests {
  );
  }
 
- #[quickcheck]
- // We shadow t for readability.
- #[allow(clippy::shadow_unrelated)]
- fn test_lehmer_loop_match_gcd(mut a: u64, mut b: u64) -> bool {
- const LIMIT: u64 = 1_u64 << 32;
-
- // Prepare valid inputs
- a |= 1_u64 << 63;
- if b > a {
- core::mem::swap(&mut a, &mut b)
- }
-
- // Call the function under test
- let update_matrix = lehmer_loop(a, b);
  proptest!(
  #[test]
  // We shadow t for readability.
  #[allow(clippy::shadow_unrelated)]
  fn test_lehmer_loop_match_gcd(mut a: u64, mut b: u64) {
  const LIMIT: u64 = 1_u64 << 32;
 
  // Prepare valid inputs
  a |= 1_u64 << 63;
  if b > a {
  core::mem::swap(&mut a, &mut b)
  }
 
- // Verify outputs
- assert!(update_matrix.0 < LIMIT);
- assert!(update_matrix.1 < LIMIT);
- assert!(update_matrix.2 < LIMIT);
- assert!(update_matrix.3 < LIMIT);
- if update_matrix == Matrix::IDENTITY {
- return true;
- }
- assert!(update_matrix.0 <= update_matrix.2);
- assert!(update_matrix.2 <= update_matrix.3);
- assert!(update_matrix.1 <= update_matrix.3);
-
- // Compare with simple GCD
- let mut a0 = a;
- let mut a1 = b;
- let mut s0 = 1;
- let mut s1 = 0;
- let mut t0 = 0;
- let mut t1 = 1;
- let mut even = true;
- while a1 > 0 {
- let r = a0 / a1;
- let t = a0 - r * a1;
- a0 = a1;
- a1 = t;
- let t = s0 r * s1;
- s0 = s1;
- s1 = t;
- let t = t0 r * t1;
- t0 = t1;
- t1 = t;
- even = !even;
- if update_matrix == Matrix(s0, t0, s1, t1, even) {
- return true;
  // Call the function under test
  let update_matrix = lehmer_loop(a, b);
 
  // Verify outputs
  assert!(update_matrix.0 < LIMIT);
  assert!(update_matrix.1 < LIMIT);
  assert!(update_matrix.2 < LIMIT);
  assert!(update_matrix.3 < LIMIT);
  prop_assume!(update_matrix != Matrix::IDENTITY);
 
  assert!(update_matrix.0 <= update_matrix.2);
  assert!(update_matrix.2 <= update_matrix.3);
  assert!(update_matrix.1 <= update_matrix.3);
 
  // Compare with simple GCD
  let mut a0 = a;
  let mut a1 = b;
  let mut s0 = 1;
  let mut s1 = 0;
  let mut t0 = 0;
  let mut t1 = 1;
  let mut even = true;
  let mut result = false;
  while a1 > 0 {
  let r = a0 / a1;
  let t = a0 - r * a1;
  a0 = a1;
  a1 = t;
  let t = s0 r * s1;
  s0 = s1;
  s1 = t;
  let t = t0 r * t1;
  t0 = t1;
  t1 = t;
  even = !even;
  if update_matrix == Matrix(s0, t0, s1, t1, even) {
  result = true;
  break;
  }
  }
  prop_assert!(result)
  }
- false
- }
 
- #[quickcheck]
- fn test_mat_mul_match_formula(
- a: U256,
- b: U256,
- q00: u64,
- q01: u64,
- q10: u64,
- q11: u64,
- ) -> bool {
- let a_expected = q00 * a.clone() - q01 * b.clone();
- let b_expected = q11 * b.clone() - q10 * a.clone();
- let mut a_result = a;
- let mut b_result = b;
- mat_mul(&mut a_result, &mut b_result, (q00, q01, q10, q11));
- a_result == a_expected && b_result == b_expected
- }
  #[test]
  fn test_mat_mul_match_formula(a: U256, b: U256, q00: u64, q01: u64, q10: u64, q11: u64) {
  let a_expected = q00 * a.clone() - q01 * b.clone();
  let b_expected = q11 * b.clone() - q10 * a.clone();
  let mut a_result = a;
  let mut b_result = b;
  mat_mul(&mut a_result, &mut b_result, (q00, q01, q10, q11));
  prop_assert_eq!(a_result, a_expected);
  prop_assert_eq!(b_result, b_expected);
  }
  );
 
  #[test]
  fn test_lehmer_double() {
@@ -711,22 709,29 @@ mod tests {
  assert_eq!(gcd, v * b - u * a);
  }
 
- #[quickcheck]
- fn test_gcd_lehmer_extended(a: U256, b: U256) -> bool {
- let (gcd, u, v, even) = gcd_extended(a.clone(), b.clone());
- &a % &gcd == U256::ZERO
- && &b % &gcd == U256::ZERO
- && gcd == if even { u * a - v * b } else { v * b - u * a }
- }
  proptest!(
  #[test]
  fn test_gcd_lehmer_extended(a: U256, b: U256) {
  let (gcd, u, v, even) = gcd_extended(a.clone(), b.clone());
  prop_assert!((&a % &gcd).is_zero());
  prop_assert!((&b % &gcd).is_zero());
 
- #[quickcheck]
- fn test_inv_lehmer(mut a: U256) -> bool {
- const MODULUS: U256 =
- u256h!("0800000000000011000000000000000000000000000000000000000000000001");
- a %= MODULUS;
- match inv_mod(&MODULUS, &a) {
- None => a == U256::ZERO,
- Some(a_inv) => a.mulmod(&a_inv, &MODULUS) == U256::ONE,
  if even {
  prop_assert_eq!(gcd, u * a - v * b);
  } else {
  prop_assert_eq!(gcd, v * b - u * a);
  }
  }
- }
 
  #[test]
  fn test_inv_lehmer(mut a: U256) {
  const MODULUS: U256 =
  u256h!("0800000000000011000000000000000000000000000000000000000000000001");
  a %= MODULUS;
  match inv_mod(&MODULUS, &a) {
  None => prop_assert!(a.is_zero()),
  Some(a_inv) => prop_assert!(a.mulmod(&a_inv, &MODULUS).is_one()),
  }
  }
  );
 }
diff --git a/algebra/u256/src/algorithms/montgomery/generic.rs b/algebra/u256/src/algorithms/montgomery/generic.rs
@@ -173,13 173,11 @@ pub(crate) fn mul_redc_inline<M: MontgomeryParameters<UInt = U256>>(x: &U256, y:
  r
 }
 
-// Quickcheck requires pass-by-value
-#[allow(clippy::needless_pass_by_value)]
 #[cfg(test)]
 mod tests {
  use super::*;
  use crate::MontgomeryParameters;
- use quickcheck_macros::quickcheck;
  use proptest::prelude::*;
  use zkp_macros_decl::u256h;
 
  struct PrimeField();
@@ -198,13 196,15 @@ mod tests {
  const R3: U256 = u256h!("038e5f79873c0a6df47d84f8363000187545706677ffcc06cc7177d1406df18e");
  }
 
- #[quickcheck]
- fn test_to_montgomery_const_consistent(n: U256) {
- let result =
- to_montgomery_const(&n, &PrimeField::MODULUS, PrimeField::M64, &PrimeField::R2);
- let expected = mul_redc_inline::<PrimeField>(&n, &PrimeField::R2);
- assert_eq!(result, expected);
- }
  proptest!(
  #[test]
  fn test_to_montgomery_const_consistent(n: U256) {
  let result =
  to_montgomery_const(&n, &PrimeField::MODULUS, PrimeField::M64, &PrimeField::R2);
  let expected = mul_redc_inline::<PrimeField>(&n, &PrimeField::R2);
  assert_eq!(result, expected);
  }
  );
 
  #[test]
  fn test_redc() {

diff --git a/algebra/u256/src/algorithms/montgomery/mod.rs b/algebra/u256/src/algorithms/montgomery/mod.rs
@@ -37,8 37,6 @@ pub(crate) fn mul_redc_inline<M: MontgomeryParameters<UInt = U256>>(x: &U256, y:
  }
 }
 
-// Quickcheck requires pass-by-value
-#[allow(clippy::needless_pass_by_value)]
 #[cfg(test)]
 mod tests {
  use super::*;
@@ -82,10 80,4 @@ mod tests {
  // from_montgomery::<PrimeField>(&to_montgomery::<PrimeField>(&n)) == n
  // }
  //
- // #[quickcheck]
- // fn test_mulmod(a: U256, b: U256) -> bool {
- // let r = mulmod::<PrimeField>(&a, &b);
- // let e = a.mulmod(&b, &PrimeField::MODULUS);
- // r == e
- // }
 }