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.