Simplify `Curve` API

[Pratyush]

Currently we have a proliferation of 2-3 different APIs related to groups and curves: Group, ProjectiveCurve and AffineCurve. This causes unnecessary imports for users, and increases the API surface of the library. @ValarDragon and I developed the following simpler interface for group-related operations in ark-ec.

/// Represents (elements of) a group having prime order `r`.
pub trait Group:
	'static
    + Sized
	+ Eq
    + Copy
    + Default
    + Send
    + Sync
    + Hash
    + Debug
    + Display
    + Zero
    + Neg<Output = Self>
    + Add<Self, Output = Self>
    + Sub<Self, Output = Self>
    + AddAssign<Self>
    + SubAssign<Self>
    + MulAssign<<Self as ProjectiveCurve>::ScalarField>
    + for<'a> Add<&'a Self, Output = Self>
    + for<'a> Sub<&'a Self, Output = Self>
    + for<'a> AddAssign<&'a Self>
    + for<'a> SubAssign<&'a Self>
    + core::iter::Sum<Self>
    + for<'a> core::iter::Sum<&'a Self>
    + From<<Self as ProjectiveCurve>::CanonicalRepr>
{
	/// The scalar field `F_r`, where `r` is the order of this group.
    type ScalarField: PrimeField + SquareRootField;

	/// The canonical representation of elements of this group.
	/// For example, in elliptic curve groups, this can be defined to be the affine representation of curve points.
    type CanonicalRepr:
        Copy + Eq + Debug + Display + From<Self> + Into<Self> + UniformRand + Zero + Neg 
        + Mul<<<Self::ScalarField> as PrimeField>::BigInt, Output = Self>;

    /// Returns a fixed generator of this group.
    #[must_use]
    fn generator() -> Self::CanonicalRepr;


    /// Converts `self` into the canonical representation.
    fn to_canonical(&self) -> Self::CanonicalRepr {
        (*self).into()
    }

    /// Normalizes a batch of `self` elements into canonical form.
    fn batch_to_canonical(v: &[Self]) -> Vec<Self::CanonicalRepr>;

    /// Doubles `self`.
    #[must_use]
    fn double(&self) -> Self {
        let mut copy = *self;
        copy.double_in_place();
        copy
    }

    /// Double `self` in place.
    fn double_in_place(&mut self) -> &mut Self;

    /// Compute `self + other`, where `other` has type `Self::CanonicalRepr.
    /// This method is useful for elliptic curve groups, where it can
	/// be implemented via fast(er) mixed addition algorithms.
    fn add_canonical(mut self, other: &Self::CanonicalRepr) -> Self {
        self.add_assign_canonical(other);
        self
    }

    /// Set `self` to be `self + other`, where `other` has type `Self::CanonicalRepr.
    /// This method is useful for elliptic curve groups, where it can
	/// be implemented via fast(er) mixed addition algorithms.
    fn add_assign_canonical(&mut self, other: &Self::CanonicalRepr) {
		*self += &Self::from(other)
	}

    /// Compute `other * self`, where `other` is any type that can be converted
	/// into `<Self::ScalarField>::BigInt`. This includes `Self::ScalarField`.
    fn mul(mut self, other: impl Into<<Self::ScalarField as PrimeField>::BigInt>) -> Self {
        self.mul_bits(ark_ff::BitIteratorBE::without_leading_zeros(other.into()))
    }

    /// Computes `other * self`, where `other` is a *big-endian* 
	/// bit representation of some integer.
    fn mul_bits_be(&self, other: impl Iterator<Item = bool>) -> Self {
        let mut res = Self::zero();
        for b in other {
            res.double_in_place();
            if b {
                res += self;
            }
        }
		res
    }


    /// Returns a group element if the set of bytes forms a valid group element,
    /// otherwise returns None. Intended use cases for this method include constructing
    /// random group elements from a hash-function or RNG output.
	// TODO: decide if this should validate membership within the group?
    fn from_bytes(bytes: &[u8]) -> Option<Self::AffineRepr>;
}

/// The additive `Group` defined by points on an elliptic curve. 
/// Defines additional associated types and constants that are
/// useful when working with curves. 
pub trait CurveGroup: Group {
	/// The cofactor of this elliptic curve.
    const COFACTOR: &'static [u64];

	/// The value `(Self::COFACTOR)^(-1)` in `Self::ScalarField`.
    const COFACTOR_INVERSE: Self::ScalarField;

	/// The base field that this elliptic curve is defined over. 
	/// Unlike `Self::ScalarField`, this does not have to be a prime field.
    type BaseField: Field;
}

This leads to the following simplification for PairingEngine:

Simplified `PairingEngine` trait

pub trait Pairing: Sized + 'static + Copy + Debug + Sync + Send + Eq {
    /// This is the scalar field of the `Self::G1` and `Self::G2`.
    type ScalarField: PrimeField + SquareRootField;

    /// An element of G1.
    type G1: CurveGroup<ScalarField = Self::Fr>: 
MulAssign<Self::Fr>; // needed due to https://github.com/rust-lang/rust/issues/69640

    /// An element of G1 that has been preprocessed for use in a pairing.
    type G1Prepared: Default + Clone + Send + Sync + Debug + From<Self::G1>;

/// An element of G2.
    type G2: CurveGroup<ScalarField = Self::Fr>: 
MulAssign<Self::Fr>; // needed due to https://github.com/rust-lang/rust/issues/69640

    /// An element of G2 that has been preprocessed for use in a pairing.
    type G2Prepared: Default + Clone + Send + Sync + Debug + From<Self::G1>;


    /// The extension field that hosts the target group of the pairing.
    type TargetField: Field;

    /// Perform a miller loop with some number of (G1, G2) pairs.
    #[must_use]
    fn miller_loop<'a>(i: impl IntoIterator<Item = &'a (Self::G1Prepared, Self::G2Prepared)>) -> MillerLoopOutput<Self>;

    /// Perform final exponentiation of the result of a miller loop.
    #[must_use]
    fn final_exponentiation(_: MillerLoopOutput<Self>) -> PairingOutput<Self::TargetField>;

    /// Computes a product of pairings.
    #[must_use]
    fn product_of_pairings<'a>(i: impl IntoIterator<Item = &'a (Self::G1Prepared, Self::G2Prepared)>) -> PairingOutput<Self::TargetField>
    {
        Self::final_exponentiation(&Self::miller_loop(i))
    }

    /// Performs a pairing between `p` and and `q
    #[must_use]
    fn pairing(p: Self::G1, q: Self::G2) -> PairingOutput<Self::TargetGroup> {
        let g1_prep = Self::G1Prepared::from(p);
        let g2_prep = Self::G2Prepared::from(q);
        Self::product_of_pairings(core::iter::once(&(g1_prep, g2_prep)))
    }
}


/// Represents the target group of a pairing. This struct is a 
/// wrapper around the field that the target group is embedded in.
pub struct PairingOutput<P>(P::TargetField);

impl<P: Pairing> PairingOutput<P> {
/// Converts `self` into an element of the underlying field.
fn to_field_element(&self) -> P::TargetField {
self.0
}
}

impl<P: Pairing> Group for PairingOutput<P: Pairing> {
type ScalarField = P::ScalarField;
}

/// Represents the output of the Miller loop of the pairing.
pub struct MillerLoopOutput<P: Pairing>(P::TargetField);

impl<P: Pairing> Mul<P::ScalarField> for MillerLoopOutput<P> {
// elided
}

A lot of this API has been inspired by the clean APIs in the group and pairing crates.

[Pratyush]

cc @kobigurk @jon-chuang would this potential design cause any problems with your downstream use case in Celo? I don't have cycles to implement this change for a while, so there's ample time for feedback!

[burdges]

We noticed some methods could be const fn too, definitely the new methods, but probably many others.

[daira]

Have you considered depending on the group and pairing crates? That would really help with interoperability (e.g. I believe it would mean that bellman could use curves defined by Arkworks). These crates are pretty lightweight.

[swasilyev]

Re: decide if this should validate membership within the group?

Could you please leave some backdoor to create an out-of-the-subgroup point. We use such point in a protocol to initialize an additive affine accumulator. Also testing subgroup checks is another case.

[burdges]

We do this too for the same use cases. It's likely overkill for affine addition, but harmless. We're delaying batching subgroup checks, but doing so appears important eventually.

[vlopes11]

Broke down https://github.com/arkworks-rs/algebra/pull/294 into smaller steps

• [x] Add SWAffine and SWProjective
• [x] Add TEAffine and TEProjective
• [ ] Add Pairing and PairingOutput
• [ ] Add CyclotomicField, replacing ad-hoc cyclotomic functions
• [ ] Replace conjugate by cyclotomic_inverse when applicable
• [ ] Add From<G1Projective> to G1Prepared
• [ ] Add From<G2Projective> to G2Prepared
• [ ] Replace PairingEngine to Pairing
• [ ] Replace AffineCurve and ProjectiveCurve by Group and CurveGroup
• [ ] Add alias G2Affine to SWAffine
• [ ] Add alias G2Projective to SWProjective
• [ ] Implement CyclotomicField for Fp2, Fp3, Fp4, Fp6
• [x] Rename GroupAffine to Affine when applicable
• [x] Rename GroupProjective to Projective when applicable
• [ ] Encapsulate (x, y) of G2HomProjective
• [ ] Add ed bls12-381 to test-curves

[nickray]

add_canonical and add_assign_canonical could be additional Add and AddAssign trait bounds, which would compose well (for instance when defining the VariableBaseMSM trait), downside you can't give an overridable default impl in terms of the From bound.

[nickray]

Another thing are the doubling methods. These could be modeled as traits by bounding on Shl and ShlAssign, and for ergonomics defining an internal trait with double as << 1 and double_in_place as <<= 1.