elliptic-curve: Move away from the `Curve` and `CurveArithmetic` traits

[carloskiki]

I have been thinking of ways to improve the elliptic-curve crate so that it can be properly implemented for all types of curves, and I think the best way we could do this is by deprecating the family of Curve traits. I know this would be a big change, and I am not sure I am right, but here's how I see it:

I like to use zero sized types as proofs. Proof that you have acquired lock, proof that a method was called, proof that something was instantiated, etc. (See this amazing blog, that's where I get my opinion from.) Zero sized types that can simply be constructed do not do much except serve as labels (which is what Curve instances do). I claim that we don't need these "labels", because we already have crates. For example, instead of elliptic_curve::AffinePoint<P256>, I would rather see p256::AffinePoint.

I went through elliptic-curve to see how this would transform the crate. Here is an example with the ecdh module. Currently the diffie_hellman function is defined as such:

pub fn diffie_hellman<C>(
    secret_key: impl Borrow<NonZeroScalar<C>>,
    public_key: impl Borrow<AffinePoint<C>>,
) -> SharedSecret<C>
where
    C: CurveArithmetic,
{
    let public_point = ProjectivePoint::<C>::from(*public_key.borrow());
    let secret_point = (public_point * secret_key.borrow().as_ref()).to_affine();
    SharedSecret::new(secret_point)
}

If we remove the CurveArithmetic trait, and instead consider what we want secret_key and public_key to implement, it could look something like this:

pub fn diffie_hellman<P>(
    secret_scalar: impl Borrow<NonZeroScalar<P::Scalar>>,
    public_point: impl Borrow<P>,
) -> SharedSecret<P>
where
    P: group::Group + AffineCoordinates,
{
    let secret_point = *public_point.borrow() * secret_scalar.borrow().as_ref();
    SharedSecret::new(secret_point)
}

Instead of requiring that some Curve trait is implemented, we require that a point implements group::Group and AffineCoordinates. We are removing a layer of indirection by directly specifying our requirements on the data we are using.

Removing this indirection would work for most other types in the library, for example it would be NonZeroScalar<S> instead of NonZeroScalar<C: CurveArithmetic> which would match NonIdentity<P>.

I think this is similar to what #1177 is proposing. I appreciate any feedback :)

[tarcieri]

The reason everything is generic around Curve/CurveArithmetic is so as an end user you don't need to tediously notate the litany of traits which are needed to generically implement any complex protocol. Everything is generic around the curve to make it possible to easily write curve-agnostic code. Edit: I also think this is one of the reasons why people want elliptic-curve support for curve25519-dalek in the first place despite the fact it already impls the group traits.

There are other ways that sort of goal could be accomplished, like a bounded marker trait that receives an automatic blanket impl (this approach is used in group for example, e.g. GroupOps), but as things are currently implemented CurveArithmetic provides a protocol implementor with quite a bit out-of-the-box: https://docs.rs/elliptic-curve/latest/elliptic_curve/trait.CurveArithmetic.html

You've translated one trivial example, but something like ecdsa is a better example of a non-trivial protocol: https://github.com/RustCrypto/signatures/blob/master/ecdsa/src/hazmat.rs

(NOTE: I also think this is a pretty major redesign proposal right as we're close to trying to ship, so I'd advise saving anything like this for the next round of breaking changes)

[carloskiki]

The reason everything is generic around Curve/CurveArithmetic is so as an end user you don't need to tediously notate the litany of traits which are needed to generically implement any complex protocol.

I understand the appeal of the Curve traits for the end users. I see two category of users. Those that need to use a specific elliptic curve, and those that want to generically use any elliptic curve. For the former category, I don't think removing the Curve trait is an issue. They barely need to know that the crate exists. The elliptic curve implementations already re-export the necessary modules like ecdh and ecdsa. I think the second group of users is quite small, and they should know what they are doing. I'm not proposing to split the arithmetic of a curve into individual traits (which would be tedious). Simply, if one needs arithmetic they should use Group (instead of Curve), and if one needs access the point coordinates they use AffineCoordinates. The big problem that I see currently with Curve and CurveArithmetic is that they are too restrictive for implementers and simply don't fit for some curves.

I also think this is one of the reasons why people want elliptic-curve support for curve25519-dalek in the first place despite the fact it already impls the group traits.

The personal reason I want curve25519-dalek to implement the Curve traits is for hash2curve. If hash2curve was not bound by the Curve traits, then I would not need them for curve25519-dalek. I think this is a common theme, if the traits were designed around the data they use rather than the Curve ZST, things might be more composable.

There are other ways that sort of goal could be accomplished, like a bounded marker trait that receives an automatic blanket impl (this approach is used in group for example, e.g. GroupOps), but as things are currently implemented CurveArithmetic provides a protocol implementor with quite a bit out-of-the-box: https://docs.rs/elliptic-curve/latest/elliptic_curve/trait.CurveArithmetic.html

You've translated one trivial example, but something like ecdsa is a better example of a non-trivial protocol: https://github.com/RustCrypto/signatures/blob/master/ecdsa/src/hazmat.rs

I will open a draft PR on ecdsa, so that we can see what it could look like if we stopped relying on the Curve/CurveArithmetic traits. I feel like that would be a good experiment as to whether we are on the right track.

(NOTE: I also think this is a pretty major redesign proposal right as we're close to trying to ship, so I'd advise saving anything like this for the next round of breaking changes)

I agree and I am in no rush.

[tarcieri]

Those that need to use a specific elliptic curve, and those that want to generically use any elliptic curve. [...] I think the second group of users is quite small

It is exceedingly common to support usage of ECDSA with multiple NIST curves like P-256, P-384, and P-521.

If you only care about a single elliptic curve, you don't need to constrain yourself to a trait-based API at all.

Simply, if one needs arithmetic they should use Group (instead of Curve)

Group has quite a few gaps. I would again invite you to look at the CurveArithmetic trait: https://docs.rs/elliptic-curve/latest/elliptic_curve/trait.CurveArithmetic.html

Some of these have open issues in the group crate. Some have gotten upstreamed (e.g. MulByGenerator), but at the very least Group would need an extension trait to bound on to provide an equivalent level of functionality, as I was suggesting earlier.

if one needs access the point coordinates they use AffineCoordinates

This is one example of a trait that's missing from group with an open issue (https://github.com/zkcrypto/group/issues/30). However many protocols need to know the size of AffineCoodinates::FieldRepr, and potentially compute additional sizes from that (e.g. SEC1 coordinate serialization, hash2curve). That's something any non-trivial use of AffineCoordinates will need to appropriately notate in the bounds.

Reductions and linear combinations are some examples of other missing pieces.

The big problem that I see currently with Curve and CurveArithmetic is that they are too restrictive for implementers and simply don't fit for some curves.

One thing that's definitely true is the use of homogeneous coordinates is an implementation detail which is leaking out. That doesn't need any massive redesign to solve though, just a simplification, as proposed in #1900.

It's also true CurveArithmetic assumes something of a "batteries included" curve implementation and can't work with deficient curve implementations. However, it also implements little more than the minimum for what is truly required for cross-curve protocols.

I think this is all beating around the bush regarding the Montgomery form of Curve25519, right? It exists to allow for compact implementations of Diffie-Hellman on embedded platforms by using the Montgomery ladder. If you are doing anything more sophisticated than that, it's not a great choice, and is generally a bad target for cross-curve protocol implementations.

The personal reason I want curve25519-dalek to implement the Curve traits is for hash2curve.

hash2curve could potentially be extracted into its own crate that only depends on ff/group, though I think there are still too many gaps to make that work and hash2curve would need to define some traits which are redundant with Curve/CurveArithmetic to actually make that work. I agree it's a little weird having it in the elliptic-curve crate as that's a "traits" crate, and perhaps if @mikelodder7 gave us the hash2curve crate name we could find a way to extract it. I'll leave it to @daxpedda for a concrete opinion on whether this is a good idea, I would imagine migrating from elliptic-curve to raw group would be annoying due to the need to manually notate the trait bounds required and define traits redundant with elliptic-curve to fill in the gaps.

Do you actually care about using hash2curve with the Montgomery form? (offhand I'm not even sure if it's defined for the Montgomery form, and too lazy to look it up ATM).

If hash2curve was not bound by the Curve traits, then I would not need them for curve25519-dalek. I think this is a common theme, if the traits were designed around the data they use rather than the Curve ZST, things might be more composable. [...] I will open a draft PR on ecdsa, so that we can see what it could look like if we stopped relying on the Curve/CurveArithmetic traits

As a start you might go through elliptic-curve and ecdsa and look at all of the types which are currently generic around a Curve/CurveArithmetic and propose a replacement, ideally giving concrete examples of "composability" you have in mind which isn't possible now. We can then discuss if the replacement is actually an improvement.

For example, are you proposing a wholesale swap of Curve for a particular crate's ProjectivePoint everywhere? If so, does ecdsa::Signature<p256::ProjectivePoint> actually make more sense than ecdsa::Signature<p256::NistP256>? Or how about SecretKey<p256::ProjectivePoint> versus SecretKey<p256::NistP256>. Neither of those types have anything to do with projective points. You can paper over all of this with type aliases, but that's not an excuse for using a generic parameter that's semantically unclear.

You could instead make these generic around the scalar types that are actually relevant to them, e.g. SecretKey<p256::Scalar> and ecdsa::Signature<p256::Scalar>. This has the problem that there are now many different types to be generic around and the user has to pick the correct one for the given use case. I would also argue it's still semantically less clear than the curve name.

(I'll also note that elliptic_curve::SecretKey and ecdsa::Signature both currently work without a curve arithmetic implementation, making them useful for e.g. PKCS#8 key storage and as a signature type for hardware-backed signers respectively. The latter is used with the yubihsm and yubikey crates, for example)

To respond to one more thing you said earlier:

Removing this indirection would work for most other types in the library, for example it would be NonZeroScalar<S> instead of NonZeroScalar<C: CurveArithmetic>

So it would be NonZeroScalar<p256::Scalar> instead of NonZeroScalar<p256::Nist256>, which feels a little redundant name-wise. It would probably be better as NonZero<p256::Scalar> in that case, and could potentially reuse crypto_bigint::NonZero if it could be made to work with the orphan rules.

If the use of homogenous coordinates were abstracted over, then NonIdentity<p256::AffinePoint> and NonIdentity<p256::ProjectivePoint> could simply be NonIdentityPoint<p256::NistP256> which would give you the consistency you seem to be after there.

I think this is a common theme, if the traits were designed around the data they use rather than the Curve ZST, things might be more composable.

The design of Curve/CurveArithmetic is in part a reaction to my experience using group. The design of group is quite complex with a number of associated types which are sometimes redundant, and figuring out the exact path from the type you have to the type you want to get to can be quite difficult, as can notating the bounds:

graph RL
    subgraph external
        standard[Clone, Copy, Debug, Eq, Sized, Send, Sync]
        additive[Add, Sub, AddAssign, SubAssign]
        multiplicative[Mul, MulAssign]
        Neg
        Sum
    end

    subgraph ops
        GroupOps --> additive
        GroupOpsOwned -->|ref| GroupOps
        ScalarMul --> multiplicative
        ScalarMulOwned -->|ref| ScalarMul
    end

    subgraph group
        Group --> standard
        Group --> Sum
        Group --> Neg
        Group --> GroupOps
        Group --> GroupOpsOwned
        Group --> ScalarMul
        Group --> ScalarMulOwned

        GroupEncoding

        WnafGroup --> Group
    end

    subgraph curve
        Curve --> Group
        Curve -->|affine| GroupOps
        Curve -->|affine| GroupOpsOwned
    end

    subgraph prime
        PrimeGroup --> Group
        PrimeGroup --> GroupEncoding

        PrimeCurve --> Curve
        PrimeCurve --> PrimeGroup

        PrimeCurveAffine --> standard
        PrimeCurveAffine --> GroupEncoding
        PrimeCurveAffine --> Neg
        PrimeCurveAffine -->|scalar| multiplicative

        PrimeCurve -.- PrimeCurveAffine
    end

    subgraph cofactor
        CofactorGroup --> Group
        CofactorGroup --> GroupEncoding
        CofactorGroup -->|subgroup| GroupOps
        CofactorGroup -->|subgroup| GroupOpsOwned

        CofactorCurve --> Curve
        CofactorCurve --> CofactorGroup

        CofactorCurveAffine --> standard
        CofactorCurveAffine --> GroupEncoding
        CofactorCurveAffine --> Neg
        CofactorCurveAffine -->|scalar| multiplicative

        CofactorCurve -.- CofactorCurveAffine
    end

Using a type family with a flat hierarchy rooted in a curve ZST makes it semantically clear that code is generic over curves, gives you a single type to be generic over which semantically makes sense in that role, makes it significantly easier to locate any given type, eliminates redundancies by having one place you can go for any associated type, and defining the type relationships in bounds on the associated types dramatically reduces the where bounds that have to be manually notated.

Having simple where bounds for algorithms implemented generically over curves is one of the core design goals of the existing CurveArithmetic trait. In most places where C: CurveArithmetic suffices, and brings in the full functionality of group in addition to all of the additional traits elliptic-curve defines. It was designed this way because those manually written where bounds are viral and have to be repeated all over the place as Rust currently lacks abstractions for reducing the boilerplate, other than designing your type family in a way the bounds are on the associated types or supertraits instead and don't need to be manually notated.

This makes what you're proposing a problematic change for a couple reasons. Anyone who has ever implemented or used an algorithm generically over multiple elliptic curves will now need to update all of their where bounds as it's a breaking change. Simply dropping in Group or Group + AffineCoordinates is unlikely to work in most cases. Implementers of algorithms will need to figure out the precise bounds they need based on the arithmetic ops they're using. Downstream users will need to change the bounds in their generic code in kind. And if someone decides to use some operation that isn't in Group like LinearCombination in the future, their bounds change, and anywhere they've virally spread needs to be updated.

I am generally opposed to making those bounds more complicated and worried what you're proposing would make them significantly more complicated. We have tried very hard to make them as simple as possible.

[tarcieri]

I think the solution to the main complaints in this PR is #1900. Though that may not make it into elliptic-curve v0.14.

We are not going to get rid of traits defined by elliptic-curve for curve arithmetic entirely, or ask everyone to tediously notate every generic algorithm implementation with the specific traits they used for a specific function. Being able to bound on C: CurveArithmetic alone is by design to keep the bounds manageable and enable generic implementations where you spend your time working on the algorithm, rather than notating bounds.

The "suite of types" approach to identifying curve-specific types prevents duplication as has been seen in group, and enables "generic over curves" algorithms without asking the API designers to choose between curve points or scalars as the generic type, especially because cases arise where the type needed for a generic parameter wouldn't make sense in context, as has been noted above.