Generic curve arithmetic about elliptic-curves HOT 14 CLOSED

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 🙂

from elliptic-curves.

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.

from elliptic-curves.

@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.

from elliptic-curves.

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.

from elliptic-curves.

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

from elliptic-curves.

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.

from elliptic-curves.

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?

from elliptic-curves.

@str4d These traits look great. 👍

from elliptic-curves.

@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?

from elliptic-curves.

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

from elliptic-curves.

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.

from elliptic-curves.

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.

from elliptic-curves.

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!

from elliptic-curves.

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.

from elliptic-curves.