Skip to content

Commit

Permalink
Arecibo backports (microsoft#223)
Browse files Browse the repository at this point in the history 
* refactor: Simplify NIFS struct and remove PhantomData usage

- Simplified the NIFS struct in `nifs.rs` file by removing extraneous elements.

* refactor: Refactor ipa_pc.rs to use InnerProductArgument directly

- Removed `EvaluationArgument` struct from `ipa_pc.rs` file, replacing it with direct usage of `InnerProductArgument`.
- Updated `EvaluationEngineTrait` type declarations to accommodate the change.
- Reworked `prove` and `verify` methods to work directly with `InnerProductArgument`.
- Made `InnerProductArgument` visibility public.

* refactor: Refactor PoseidonROCircuit struct trait bound

- Trait bound changed from `PrimeField   PrimeFieldBits` to `PrimeField` in `poseidon.rs`.

* refactor: mutualize macro for secp/bn256 cycles

* Optimize generator creation in provider module

- Refactored the `from_label` function in pasta.rs removing redundant collect, flatten operations and Vec<usize> creation,

* refactor: Optimize circuit methods and enhance trait compatibility

- Optimized performance by refactoring the use of iterator `into_iter()` to the iterator itself in `gadgets/r1cs.rs`.
- removed a clone in ppsnark.
  • Loading branch information
@huitseeker
huitseeker authored Aug 29, 2023
1 parent 6a6308e commit bd56514
Show file tree
Hide file tree
Showing 9 changed files with 148 additions and 301 deletions.
4 changes: 2 additions & 2 deletions src/gadgets/r1cs.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -207,7 207,7 @@ impl<G: Group> AllocatedRelaxedR1CSInstance<G> {
.collect::<Result<Vec<AllocatedNum<G::Base>>, _>>()?;

// absorb each of the limbs of X[0]
for limb in X0_bn.into_iter() {
for limb in X0_bn {
ro.absorb(&limb);
}

Expand All @@ -223,7 223,7 @@ impl<G: Group> AllocatedRelaxedR1CSInstance<G> {
.collect::<Result<Vec<AllocatedNum<G::Base>>, _>>()?;

// absorb each of the limbs of X[1]
for limb in X1_bn.into_iter() {
for limb in X1_bn {
ro.absorb(&limb);
}

Expand Down
3 changes: 0 additions & 3 deletions src/nifs.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -10,7 10,6 @@ use crate::{
traits::{commitment::CommitmentTrait, AbsorbInROTrait, Group, ROTrait},
Commitment, CommitmentKey, CompressedCommitment,
};
use core::marker::PhantomData;
use serde::{Deserialize, Serialize};

/// A SNARK that holds the proof of a step of an incremental computation
Expand All @@ -19,7 18,6 @@ use serde::{Deserialize, Serialize};
#[serde(bound = "")]
pub struct NIFS<G: Group> {
pub(crate) comm_T: CompressedCommitment<G>,
_p: PhantomData<G>,
}

type ROConstants<G> =
Expand Down Expand Up @@ -72,7 70,6 @@ impl<G: Group> NIFS<G> {
Ok((
Self {
comm_T: comm_T.compress(),
_p: PhantomData,
},
(U, W),
))
Expand Down
140 changes: 1 addition & 139 deletions src/provider/bn256_grumpkin.rs
View file
Original file line number Diff line number Diff line change
@@ -1,5 1,6 @@
//! This module implements the Nova traits for `bn256::Point`, `bn256::Scalar`, `grumpkin::Point`, `grumpkin::Scalar`.
use crate::{
impl_traits,
provider::{
cpu_best_multiexp,
keccak::Keccak256Transcript,
Expand Down Expand Up @@ -40,145 41,6 @@ pub mod grumpkin {
};
}

// This implementation behaves in ways specific to the bn256/grumpkin curves in:
// - to_coordinates,
// - vartime_multiscalar_mul, where it does not call into accelerated implementations.
macro_rules! impl_traits {
(
$name:ident,
$name_compressed:ident,
$name_curve:ident,
$name_curve_affine:ident,
$order_str:literal
) => {
impl Group for $name::Point {
type Base = $name::Base;
type Scalar = $name::Scalar;
type CompressedGroupElement = $name_compressed;
type PreprocessedGroupElement = $name::Affine;
type RO = PoseidonRO<Self::Base, Self::Scalar>;
type ROCircuit = PoseidonROCircuit<Self::Base>;
type TE = Keccak256Transcript<Self>;
type CE = CommitmentEngine<Self>;

fn vartime_multiscalar_mul(
scalars: &[Self::Scalar],
bases: &[Self::PreprocessedGroupElement],
) -> Self {
cpu_best_multiexp(scalars, bases)
}

fn preprocessed(&self) -> Self::PreprocessedGroupElement {
self.to_affine()
}

fn compress(&self) -> Self::CompressedGroupElement {
self.to_bytes()
}

fn from_label(label: &'static [u8], n: usize) -> Vec<Self::PreprocessedGroupElement> {
let mut shake = Shake256::default();
shake.update(label);
let mut reader = shake.finalize_xof();
let mut uniform_bytes_vec = Vec::new();
for _ in 0..n {
let mut uniform_bytes = [0u8; 32];
reader.read_exact(&mut uniform_bytes).unwrap();
uniform_bytes_vec.push(uniform_bytes);
}
let gens_proj: Vec<$name_curve> = (0..n)
.collect::<Vec<usize>>()
.into_par_iter()
.map(|i| {
let hash = $name_curve::hash_to_curve("from_uniform_bytes");
hash(&uniform_bytes_vec[i])
})
.collect();

let num_threads = rayon::current_num_threads();
if gens_proj.len() > num_threads {
let chunk = (gens_proj.len() as f64 / num_threads as f64).ceil() as usize;
(0..num_threads)
.collect::<Vec<usize>>()
.into_par_iter()
.map(|i| {
let start = i * chunk;
let end = if i == num_threads - 1 {
gens_proj.len()
} else {
core::cmp::min((i 1) * chunk, gens_proj.len())
};
if end > start {
let mut gens = vec![$name_curve_affine::identity(); end - start];
<Self as Curve>::batch_normalize(&gens_proj[start..end], &mut gens);
gens
} else {
vec![]
}
})
.collect::<Vec<Vec<$name_curve_affine>>>()
.into_par_iter()
.flatten()
.collect()
} else {
let mut gens = vec![$name_curve_affine::identity(); n];
<Self as Curve>::batch_normalize(&gens_proj, &mut gens);
gens
}
}

fn to_coordinates(&self) -> (Self::Base, Self::Base, bool) {
let coordinates = self.to_affine().coordinates();
if coordinates.is_some().unwrap_u8() == 1
// The bn256/grumpkin convention is to define and return the identity point's affine encoding (not None)
&& (Self::PreprocessedGroupElement::identity() != self.to_affine())
{
(*coordinates.unwrap().x(), *coordinates.unwrap().y(), false)
} else {
(Self::Base::zero(), Self::Base::zero(), true)
}
}

fn get_curve_params() -> (Self::Base, Self::Base, BigInt) {
let A = $name::Point::a();
let B = $name::Point::b();
let order = BigInt::from_str_radix($order_str, 16).unwrap();

(A, B, order)
}

fn zero() -> Self {
$name::Point::identity()
}

fn get_generator() -> Self {
$name::Point::generator()
}
}

impl PrimeFieldExt for $name::Scalar {
fn from_uniform(bytes: &[u8]) -> Self {
let bytes_arr: [u8; 64] = bytes.try_into().unwrap();
$name::Scalar::from_uniform_bytes(&bytes_arr)
}
}

impl<G: Group> TranscriptReprTrait<G> for $name_compressed {
fn to_transcript_bytes(&self) -> Vec<u8> {
self.as_ref().to_vec()
}
}

impl CompressedGroup for $name_compressed {
type GroupElement = $name::Point;

fn decompress(&self) -> Option<$name::Point> {
Some($name_curve::from_bytes(&self).unwrap())
}
}
};
}

impl<G: Group> TranscriptReprTrait<G> for grumpkin::Base {
fn to_transcript_bytes(&self) -> Vec<u8> {
self.to_repr().to_vec()
Expand Down
17 changes: 4 additions & 13 deletions src/provider/ipa_pc.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -32,13 32,6 @@ pub struct VerifierKey<G: Group> {
ck_s: CommitmentKey<G>,
}

/// Provides an implementation of a polynomial evaluation argument
#[derive(Clone, Debug, Serialize, Deserialize)]
#[serde(bound = "")]
pub struct EvaluationArgument<G: Group> {
ipa: InnerProductArgument<G>,
}

/// Provides an implementation of a polynomial evaluation engine using IPA
#[derive(Clone, Debug, Serialize, Deserialize)]
pub struct EvaluationEngine<G: Group> {
Expand All @@ -52,7 45,7 @@ where
{
type ProverKey = ProverKey<G>;
type VerifierKey = VerifierKey<G>;
type EvaluationArgument = EvaluationArgument<G>;
type EvaluationArgument = InnerProductArgument<G>;

fn setup(
ck: &<<G as Group>::CE as CommitmentEngineTrait<G>>::CommitmentKey,
Expand Down Expand Up @@ -81,9 74,7 @@ where
let u = InnerProductInstance::new(comm, &EqPolynomial::new(point.to_vec()).evals(), eval);
let w = InnerProductWitness::new(poly);

Ok(EvaluationArgument {
ipa: InnerProductArgument::prove(ck, &pk.ck_s, &u, &w, transcript)?,
})
InnerProductArgument::prove(ck, &pk.ck_s, &u, &w, transcript)
}

/// A method to verify purported evaluations of a batch of polynomials
Expand All @@ -97,7 88,7 @@ where
) -> Result<(), NovaError> {
let u = InnerProductInstance::new(comm, &EqPolynomial::new(point.to_vec()).evals(), eval);

arg.ipa.verify(
arg.verify(
&vk.ck_v,
&vk.ck_s,
(2_usize).pow(point.len() as u32),
Expand Down Expand Up @@ -164,7 155,7 @@ impl<G: Group> InnerProductWitness<G> {
/// An inner product argument
#[derive(Clone, Debug, Serialize, Deserialize)]
#[serde(bound = "")]
struct InnerProductArgument<G: Group> {
pub struct InnerProductArgument<G: Group> {
L_vec: Vec<CompressedCommitment<G>>,
R_vec: Vec<CompressedCommitment<G>>,
a_hat: G::Scalar,
Expand Down
137 changes: 137 additions & 0 deletions src/provider/mod.rs
View file
Original file line number Diff line number Diff line change
Expand Up @@ -139,3 139,140 @@ pub(crate) fn cpu_best_multiexp<C: CurveAffine>(coeffs: &[C::Scalar], bases: &[C
acc
}
}

/// Curve ops
/// This implementation behaves in ways specific to the halo2curves suite of curves in:
// - to_coordinates,
// - vartime_multiscalar_mul, where it does not call into accelerated implementations.
// A specific reimplementation exists for the pasta curves in their own module.
#[macro_export]
macro_rules! impl_traits {
(
$name:ident,
$name_compressed:ident,
$name_curve:ident,
$name_curve_affine:ident,
$order_str:literal
) => {
impl Group for $name::Point {
type Base = $name::Base;
type Scalar = $name::Scalar;
type CompressedGroupElement = $name_compressed;
type PreprocessedGroupElement = $name::Affine;
type RO = PoseidonRO<Self::Base, Self::Scalar>;
type ROCircuit = PoseidonROCircuit<Self::Base>;
type TE = Keccak256Transcript<Self>;
type CE = CommitmentEngine<Self>;

fn vartime_multiscalar_mul(
scalars: &[Self::Scalar],
bases: &[Self::PreprocessedGroupElement],
) -> Self {
cpu_best_multiexp(scalars, bases)
}

fn preprocessed(&self) -> Self::PreprocessedGroupElement {
self.to_affine()
}

fn compress(&self) -> Self::CompressedGroupElement {
self.to_bytes()
}

fn from_label(label: &'static [u8], n: usize) -> Vec<Self::PreprocessedGroupElement> {
let mut shake = Shake256::default();
shake.update(label);
let mut reader = shake.finalize_xof();
let mut uniform_bytes_vec = Vec::new();
for _ in 0..n {
let mut uniform_bytes = [0u8; 32];
reader.read_exact(&mut uniform_bytes).unwrap();
uniform_bytes_vec.push(uniform_bytes);
}
let gens_proj: Vec<$name_curve> = (0..n)
.into_par_iter()
.map(|i| {
let hash = $name_curve::hash_to_curve("from_uniform_bytes");
hash(&uniform_bytes_vec[i])
})
.collect();

let num_threads = rayon::current_num_threads();
if gens_proj.len() > num_threads {
let chunk = (gens_proj.len() as f64 / num_threads as f64).ceil() as usize;
(0..num_threads)
.into_par_iter()
.flat_map(|i| {
let start = i * chunk;
let end = if i == num_threads - 1 {
gens_proj.len()
} else {
core::cmp::min((i 1) * chunk, gens_proj.len())
};
if end > start {
let mut gens = vec![$name_curve_affine::identity(); end - start];
<Self as Curve>::batch_normalize(&gens_proj[start..end], &mut gens);
gens
} else {
vec![]
}
})
.collect()
} else {
let mut gens = vec![$name_curve_affine::identity(); n];
<Self as Curve>::batch_normalize(&gens_proj, &mut gens);
gens
}
}

fn to_coordinates(&self) -> (Self::Base, Self::Base, bool) {
// see: grumpkin implementation at src/provider/bn256_grumpkin.rs
let coordinates = self.to_affine().coordinates();
if coordinates.is_some().unwrap_u8() == 1
&& (Self::PreprocessedGroupElement::identity() != self.to_affine())
{
(*coordinates.unwrap().x(), *coordinates.unwrap().y(), false)
} else {
(Self::Base::zero(), Self::Base::zero(), true)
}
}

fn get_curve_params() -> (Self::Base, Self::Base, BigInt) {
let A = $name::Point::a();
let B = $name::Point::b();
let order = BigInt::from_str_radix($order_str, 16).unwrap();

(A, B, order)
}

fn zero() -> Self {
$name::Point::identity()
}

fn get_generator() -> Self {
$name::Point::generator()
}
}

impl PrimeFieldExt for $name::Scalar {
fn from_uniform(bytes: &[u8]) -> Self {
let bytes_arr: [u8; 64] = bytes.try_into().unwrap();
$name::Scalar::from_uniform_bytes(&bytes_arr)
}
}

impl<G: Group> TranscriptReprTrait<G> for $name_compressed {
fn to_transcript_bytes(&self) -> Vec<u8> {
self.as_ref().to_vec()
}
}

impl CompressedGroup for $name_compressed {
type GroupElement = $name::Point;

fn decompress(&self) -> Option<$name::Point> {
Some($name_curve::from_bytes(&self).unwrap())
}
}
};
}
Loading

0 comments on commit bd56514

Please sign in to comment.