Generic curve arithmetic

[tarcieri]

One of the goals of the elliptic-curve crate is to be able to write code that's generic over (at least Weierstrass) elliptic curve types.

Now that the p256 and k256 crates have arithmetic implementations (thanks @str4d and @tuxxy!), an open question is how to write code that's generic over the underlying AffinePoint and/or ProjectivePoint types.

It seems like AffinePoint and ProjectivePoint could benefit from having traits which at the very least are bounded by the point arithmetic they must support.

It also seems like there needs to be some trait connecting the two of them which can be used to access the From impls and arithmetic (e.g. Add) between the two different point types.

Finally, it seems like there needs to be a trait a weierstrass::Curve type can impl which provides that curve's AffinePoint and ProjectivePoint types as associated types.

Curious if people think this is a good idea and what those traits might look like.

cc @tuxxy

[tarcieri]

@tuxxy brought up scalars on #23

It might make sense to replace the existing Scalar struct in the elliptic-curve crate with a trait as well:

https://docs.rs/elliptic-curve/0.3.0/elliptic_curve/scalar/struct.Scalar.html

The existing Scalar struct is independent of the curve type and sized in terms of bytes, which is a bit suboptimal. Perhaps it would be better to define an Order trait/type it could be generic around (see #13)?

Unfortunately the byte-based sizing is heavily leveraged in typenum arithmetic which computes all sorts of things including rather complex (from a type-level arithmetic perspective) things like the exact size of ASN.1 DER encoded ECDSA signatures, so weierstrass::Curve::ScalarSize will likely have to continue to exist in some form, at least until const generics land and it might be possible to calculate this size in bytes from the curve's order.

[tuxxy]

I have some curve generic traits that I used for a library I am building with @nucypher called Twinkle. I've changed a lot of the backend since, but I have some trait definitions for Scalar and Point.

As an example, here's the definition for Point:

pub trait Point: Sized {
    type Backend: Backend<Point = Self>;
    /// This can be used to swap out the library point type with a custom type.
    /// If no such swapping is done, this should simply be Self.
    type BackendPoint: Sized;

    // Arithmetic functions
    fn point_mul(lhs: <Self::Backend as Backend>::Scalar, rhs: Self) -> Self;
    fn point_add(lhs: Self, rhs: Self) -> Self;
    fn point_sub(lhs: Self, rhs: Self) -> Self;
    fn point_neg(point_val: Self) -> Self;

    fn point_eq(lhs: &Self, rhs: &Self) -> bool;

    // Constants
    fn basepoint() -> Self;
    fn identity() -> Self;

    // Helper functions
    fn new() -> Self {
        Self::identity()
    }
    fn from_backend_point(point: Self::BackendPoint) -> Self;
    fn get_backend_point(self) -> Self::BackendPoint;
}

Obviously, this won't work straight out of the box, but I can imagine a very similar architecture. These traits get implemented on the backend type (e.g. Ristretto's Scalar) and then we have blanket impls for operations on two types called TwinkleScalar and TwinklePoint so that they're generic to 1) a Backend and 2) requires that the Backend type have two associated types that implement Scalar and Point.

What I'm thinking is that the elliptic-curve crate would probably have its own Scalar and Point type that has something like a "backend" for each curve, though this might be able to be simplified a lot more.

[str4d]

See the group crate for another starting point, that we've been using in Zcash. I'm almost done refactoring the ff crate, and group will be next, so this is a good time to be discussing these traits 🙂

[tarcieri]

@str4d awesome! If you have a crate with some existing traits to use for this, all the better

[tuxxy]

I'm finding myself interested in using this crate, but I also need scalar arithmetic. Since we presently lack this, it makes sense for me to potentially scope this out a bit more.

Why would it make sense to refactor Scalar to a trait? It makes more sense to me to implement the curve-specific type Order (perhaps with a trait) and then make Scalar generic over it, as per #13.

Also, I'm not very keen on the idea of a type simply named Order. IMHO, it seems it would be far more usable to name it something specific to the curve. In practice, no one is interested in operating on scalars over an order -- they only care about scalars for a specific curve, which confers the order inherently.

[str4d]

I'm pretty happy with the group and curve trait API I've arrived at in zkcrypto/group#6, so I'll spend some time thinking about refactoring this crate in terms of it. I'm interested to hear feedback in that issue.

[burdges]

I'd vote for either zcash's new traits like @str4d suggests, or zexe's traits, which started as a fork of zcash's traits, and could surely remerge.

I suppose zcash's new traits make it easier to express less structure than the simpler zexe ones, and maybe accommodate Edwards curves better?

[tuxxy]

@str4d These traits look great. 👍

[tarcieri]

@tuxxy I'm definitely a fan of keeping the existing concrete Scalar type which is heavily wired into mundane things like supporting private key storage formats (e.g. PKCS#8). I guess the question is how do you reconcile that with the individual Scalar types exposed for each curve. Should we just use From impls, or can the existing scalar arithmetic be hoisted out of the way generically?

I'd be happy with any solution for Order, but the current problem is when scalars are loaded from some external source, nothing checks they're reduced modulo the order.

The tricky part in all of this is the type-level arithmetic which makes it possible to compute exact-sized (or in the case of ASN.1 DER signatures, near exact) types and therefore have no_std compatibility. This is presently handled by a ScalarSize associated type on the Curve.

In practice, no one is interested in operating on scalars over an order -- they only care about scalars for a specific curve, which confers the order inherently.

The reason why I was interested in making scalars generic over an Order as opposed to a Curve is the curve types are presently elliptic_curve::weierstrass::Curve and I thought it would be interesting to be able to support other curve forms without requiring a Scalar type per curve form, so Order seemed like a nice middle ground.

I suppose alternatively we could have a fully generic elliptic_curve::Curve trait capable of expressing any curve form, and elliptic_curve::weierstrass::Curve as a sort of sub-trait?

[burdges]

If the new zcash traits by @str4d work for Edwards curves then they should probably work with Schnorr and RSA groups too.

[str4d]

I'm definitely a fan of keeping the existing concrete Scalar type which is heavily wired into mundane things like supporting private key storage formats (e.g. PKCS#8). I guess the question is how do you reconcile that with the individual Scalar types exposed for each curve. Should we just use From impls, or can the existing scalar arithmetic be hoisted out of the way generically?

In the ff crate, PrimeField (which I think is equivalent to what you are imagining for Order) has a Repr associated type; this could probably just be the existing concrete scalar type for each curve impl. Would that be sufficient, or do we need to experiment more with how this affects private key storage?

I suppose alternatively we could have a fully generic elliptic_curve::Curve trait capable of expressing any curve form, and elliptic_curve::weierstrass::Curve as a sort of sub-trait?

This is roughly the direction that the group::Curve: group:Group trait is pointing in. Group handles generic group arithmetic and has a Scalar associated type. Curve specialises group arithmetic to "general elliptic curves", where you know there will be some set of efficient representations congruent an EC point with affine representation. Specialising beyond that implies further knowledge of the curve's structure, which I could see covering three areas:

• The PrimeCurve and CofactorCurve traits, which each cover classes of curve models.
• Traits for specific curve models (Weierstrass, Edwards, ...), some of which could potentially be sub-traits of e.g. CofactorCurve (e.g. Edwards curves that always have a torsion subgroup).
• Traits for protocols that rely on specifics of a curve's structure (e.g. ECDSA), which we may or may not want to constrain to specific curve models or classes of curves depending on the protocol.

If the new zcash traits by @str4d work for Edwards curves then they should probably work with Schnorr and RSA groups too.

They are intended to work for Edwards curves (Jubjub is a twisted Edwards curve). The base unit that the group crate assumes is a cyclic group of prime order, and everything else builds from there.

[tarcieri]

Would that be sufficient, or do we need to experiment more with how this affects private key storage?

The really tricky thing right now is weierstrass::Curve::ScalarSize is the base typenum constant value from which all the GenericArray sizes are computed. It needs to stick around in some form.

For an example, an ECDSA signature is represented as two scalar values r and s. An ASN.1 encoded signature adds up to an additional 9-bytes of framing. Right now the ecdsa crate is able to use typenum arithmetic to compute the sizes of signature types from the curve's ScalarSize, e.g. for P-256 ASN.1-encoded signature it's (32 * 2) + 9 = 73 bytes, for P-384 it's (48 * 2) + 9 = 105 bytes.

[tarcieri]

I added an elliptic_curve::ops::Invert trait in RustCrypto/traits#228 which looks like the following:

/// Perform an inversion on a field element (i.e. base field element or scalar)
pub trait Invert {
    /// Field element type
    type Output;

    /// Invert a field element.
    fn invert(&self) -> CtOption<Self::Output>;
}

This made it possible to eliminate the specifics of blinding scalar inversions from the ECDSA signing API, which was helpful:

https://github.com/RustCrypto/elliptic-curves/pull/99/files#diff-995156456abcc4ccf4d937223154cb43

But I also didn't really put any thought into this trait design, and I'm curious if there are other places we could source a similar trait from, or alternative designs to consider /cc @nickray @str4d

Also note that I'd like to cut another release of elliptic-curve fairly soon, like in the next week or so!

[tarcieri]

I implemented the ff::{Field, PrimeField} and group::{Group, Curve} traits on k256 in #164 and p256 in #169. With that, I'd say we now support generic curve arithmetic, at least as well as the ff and group crates do.