New core implementation

[ebfull]

I'm designing a new "core" for the cryptography in this library, mostly in the interest of performance and flexibility.

Features include:

• The library will support multiple BN curve implementations all behind this abstract API. In particular, I plan to integrate a stronger curve construction which should be more secure and more useful for zk-SNARKs.
• The user can perform miller loops (with any number of point tuples) manually if they want to avoid unnecessary final exponentiations or redundant ate loops. The Ethereum folks will need to expose all of this functionality in their precompiles if they want to give users maximum performance and flexibility, especially if you need to use newer zk-SNARK schemes or do batch/probablistic verification of proofs.
• The user can perform G2 precomputation for the miller loop manually.
• Support for mixed addition.
• Support for curve point compression (the same way that Zcash compresses proofs).

API preview:

pub trait Field<E: Engine>: Sized +
                            Eq +
                            PartialEq +
                            Copy +
                            Clone +
                            Send +
                            Sync +
                            Debug +
                            'static
{
    fn zero() -> Self;
    fn one(&E) -> Self;
    fn random<R: rand::Rng>(&E, &mut R) -> Self;

    fn is_zero(&self) -> bool;

    fn square(&mut self, &E);
    fn double(&mut self, &E);
    fn negate(&mut self, &E);
    fn add_assign(&mut self, &E, other: &Self);
    fn sub_assign(&mut self, &E, other: &Self);
    fn mul_assign(&mut self, &E, other: &Self);
    fn inverse(&self, &E) -> Option<Self>;
    fn sqrt(&self, &E) -> Option<Self>;
    fn powi<I: IntoIterator<Item=u64>>(&self, engine: &E, exp: I) -> Self;
    fn powb<I: IntoIterator<Item=bool>>(&self, engine: &E, exp: I) -> Self;
}

pub trait PrimeField<E: Engine>: Field<E>
{
    type Repr: AsRef<[u64]>;

    fn from_str(&E, s: &str) -> Result<Self, ()>;
    fn from_repr(&E, Self::Repr) -> Result<Self, ()>;
    fn into_repr(&self, &E) -> Self::Repr;
}

/// A representation of a group element that can be serialized and deserialized,
/// but is not guaranteed to be a point on the curve.
pub trait GroupRepresentation<E: Engine, F: Field<E>, G: Group<E, F>>: Copy +
                                                                       Clone +
                                                                       Sized +
                                                                       Send +
                                                                       Sync +
                                                                       Debug +
                                                                       'static
{
    /// Attempt to parse the representation as an element on
    /// the curve in the affine.
    fn to_affine(&self, &E) -> Option<G::Affine>;

    /// This is like `to_affine` except the caller is
    /// responsible for ensuring the point is on the curve.
    /// If it isn't, this function is allowed to panic,
    /// but not guaranteed to.
    fn to_affine_unchecked(&self, &E) -> G::Affine;
}

pub trait GroupAffine<E: Engine, F: Field<E>, G: Group<E, F>>: Copy +
                                                               Clone +
                                                               Sized +
                                                               Send +
                                                               Sync +
                                                               Debug +
                                                               PartialEq +
                                                               Eq +
                                                               'static
{
    fn to_jacobian(&self, &E) -> G;
    fn to_compressed(&self, &E) -> G::Compressed;
    fn to_uncompressed(&self, &E) -> G::Uncompressed;
}

pub trait Group<E: Engine, F: Field<E>>: Sized +
                                         Eq +
                                         PartialEq +
                                         Copy +
                                         Clone +
                                         Send +
                                         Sync +
                                         Debug +
                                         'static
{
    type Affine: GroupAffine<E, F, Self>;
    type Compressed: GroupRepresentation<E, F, Self>;
    type Uncompressed: GroupRepresentation<E, F, Self>;
    type Prepared: Clone + 'static;

    fn zero(&E) -> Self;
    fn one(&E) -> Self;
    fn random<R: rand::Rng>(&E, &mut R) -> Self;

    fn is_zero(&E) -> Self;

    fn to_affine(&self, &E) -> Self::Affine;
    fn prepare(&self, &E) -> Self::Prepared;

    fn double(&mut self, &E);
    fn negate(&mut self, engine: &E);
    fn add_assign(&mut self, &E, other: &Self);
    fn add_assign_mixed(&mut self, &E, other: &Self::Affine);
    fn mul_assign(&mut self, &E, other: &E::Fr);
}

pub trait Engine: Sized {
    type Fq: PrimeField<Self>;
    type Fr: PrimeField<Self>;
    type Fqe: Field<Self>;
    type Fqk: Field<Self>;
    type G1: Group<Self, Self::Fq>;
    type G2: Group<Self, Self::Fqe>;

    fn new() -> Self;

    fn miller_loop<'a, I>(&self, I) -> Self::Fqk
        where I: IntoIterator<Item=&'a (
                                    &'a <Self::G1 as Group<Self, Self::Fq>>::Prepared,
                                    &'a <Self::G2 as Group<Self, Self::Fqe>>::Prepared
                               )>;

    fn final_exponentiation(&self, &Self::Fqk) -> Self::Fqk;

    fn pairing(&self, p: &Self::G1, q: &Self::G2) -> Self::Fqk
    {
        self.final_exponentiation(&self.miller_loop(
            [(&p.prepare(self), &q.prepare(self))].into_iter()
        ))
    }
}

[zookozcash]

Very cool. :-) Can't wait to see it.