primeorder: supports only curves with a = -3

[survived]

primeorder docs say that crate provides generic implementation of elliptic curve arithmetic for curves defined as

y² = x³ + ax + b

However, I can see that ProjectivePoint::double is implementation of Renes-Costello-Batina 2015 (Algorithm 6). Paper says that Algorithm 6 is exception-free point doubling for prime order short Weierstrass curves $E/\mathbb{F}_q : y^2 = x^3 + a x + b$ with $a = −3$.

Do you consider eventually switching to more generic algorithms, like algorithm 3 from the same paper which doesn't require $a$ to be $-3$? In any case, worth mentioning in the docs that atm only $a=-3$ curves are supported to avoid confusion.

[tarcieri]

The primeorder crate could probably benefit from a larger warning that its current use cases are as a support library for the curve implementations in https://github.com/RustCrypto/elliptic-curves and that it might be problematic for 3rd parties to use to instantiate other prime order elliptic curves.

You're correct that it uses an algorithm specialized to $a = −3$. We certainly want to retain the current implementation as that's the coefficient used for all of the crates in this repo which use primeorder as a dependency.

Other values of $a$ could potentially be supported in the future, but that shouldn't come at a performance cost to the crates in this repo.

[survived]

It's actually can be adopted without sacrificing performance. Here I drafted a PoC that makes ProjectivePoint::add work for curves with any $a$. As you can see, I added EQUATION_A_EQUALS_MINUS_3 const to PrimeCurveParams. It allowed me to check if we need to do optimisations in ProjectivePoint::add function and call either add_optimised if $a=-3$ or add_unoptimised otherwise. Those if branches in add function (which check whether we need to enforce optimisations or not) should be optimised out by compiler since condition is a constant.

Let me know if you're interested in contribution, I can cover other functions as well and send a PR.

[tarcieri]

That seems like a reasonable enough workaround for now. Anything else I can think of would require unstable Rust features like impl const Trait.

It's a breaking change, although I think we're about ready to start making breaking changes again. ff/group have been updated to v0.13 and the elliptic-curve crate (and ecdsa crate) have been updated to use them.

[newpavlov]

My PR draft had support for -3, 0, and general formulas (see the CurveKind enum). It relied on associated constant and removal of unreachable branches by compiler. But I am not familiar with the current design of primeorder to say whether the used approach would work for it.

[tarcieri]

Yeah, we can experiment with various APIs prior to the next release.

An enum is an option, but also (marker) traits and free functions (used to impl a trait method) are some others.

[survived]

Another design option is to have a dedicated Optimizations<C> structure that would define whether $a=-3$ on curve C and other optimizations-related stuff. The PrimeCurveParams would look like:

pub trait PrimeCurveParams {
    // ...
    
    const OPTIMIZATIONS: Optimizations<Self>;
}

And optimizations struct itself:

pub struct Optimizations<C: PrimeCurveParams> { /* ... */ }

impl<C: PrimeCurveParams> Optimizations<C> {
    /// No optimizations are enforsed
    pub const fn none() -> Self { /* ... */ }
    /// Specifies that coeficient `a` of curve equation equals to `-3`
    pub const fn coef_a_equals_3(mut self, v: bool) -> Self {
        self.a_eq_minus_3 = v;
        self
    }
    /// Indicates whether coeficient `a` of curve equation equals to `-3`
    pub const fn is_coef_a_equals_minus_3(&self) -> bool {
        self.a_eq_minus_3
    }
}

And when implementing PrimeCurveParams trait, you just construct this struct:

impl PrimeCurveParams for MyCurve {
    // ...

    const OPTIMIZATIONS: Optimizations<MyCurve> = Optimizations::none()
        .coef_a_equals_3(true);
}

I like this approach because introducing new optimization options is not a breaking change. E.g. at some point you may define optimized arithmetic for $a=0$, and it's as easy as adding new private field to a struct and exposing new method, no need for major version bump. On other hand, if adding new optimizations is not in the scope, it may be not worth it.

[survived]

Generic point addition could benefit from having precomputed $b_3 = 3 * b$, it can be also placed in Optimizations struct:

Optimizations struct code

pub struct Optimizations<C: PrimeCurveParams> {
    a_eq_minus_3: bool,
    b3: Option<C::FieldElement>,
}

impl<C: PrimeCurveParams> Optimizations<C> {
    /// No optimizations are enforsed
    pub const fn none() -> Self {
        Self{ a_eq_minus_3: false, b3: None }
    }
    
    /// Specifies that coeficient `a` of curve equation equals to `-3`
    pub const fn coef_a_equals_3(mut self, v: bool) -> Self {
        self.a_eq_minus_3 = v;
        self
    }
    
    /// Indicates whether coeficient `a` of curve equation equals to `-3`
    pub const fn is_coef_a_equals_minus_3(&self) -> bool {
        self.a_eq_minus_3
    }
    
    /// Specifies `b3 = 3 * b`
    pub const fn set_b3(mut self, b3: C::FieldElement) -> Self {
        self.b3 = Some(b3);
        self
    }
    
    /// Returns `3*b`
    pub fn get_b3(&self) -> C::FieldElement {
        self.b3.unwrap_or_else(|| C::EQUATION_B * C::FieldElement::from(3))
    }
}

I'm not saying it's necessary optimization, just giving an example how the struct could evolve

[tarcieri]

I took a shot at implementing the trait-based approach I had in mind: #728

It adds a set of marker traits for properties of EQUATION_A: https://github.com/RustCrypto/elliptic-curves/pull/728/files#diff-8d033e08c09fc858735f2278e89b9794e1f0b3ac14cca03669326bbcdb77964c

Those marker traits can be used as bounds for trait impls on ProjectivePoint<C>: https://github.com/RustCrypto/elliptic-curves/pull/728/files#diff-db3482bdae95a49c5c5ed884efbe3027b314441d4fb5676c884b99923ce13e35R197-R246

I only did (a newly extracted) Double trait for now, but it could be used for other trait impls like Add

Edit: never mind, the impls conflict Refactored to use ZSTs as markers for the special properties of EQUATION_A, and that works.

[tarcieri]

@survived having a type or trait which holds a set of precomputed constants for optimizations is an interesting idea.

I think it's already possible to do those precomputations at compile time, albeit with a macro that calls a predefined set of const fns (in the absence of stable impl const Trait) invoked from the respective curve implementation crate.

As it were, p256 and p384 both use impl_field_element! macro which writes a common set of const fns.

[survived]

I like marker approach! It doesn't require to write those if-statements on constant expression to switch between algorithm implementation.

I don't have strong preferences, I can go with any of options. I'd let you, as a code owner, decide which one I should implement in my PR. I'll start by implementing algorithms using EQUATION_A_EQUALS_MINUS_3 constant for simplicity, and then can switch to whatever option you prefer.

[survived]

I think it's already possible to do those precomputations at compile time

It is definitely possible, it's just matter of how you retrieve this precomputed data for generic C: PrimeCurveParams. E.g. if we store all the constants as trait associated constants, then we have many lengthy-named constants, and adding new constants is a breaking change. Having a dedicated struct for those parameters as I suggested above hides complexity, though it requires more code to write and maintain.

[tarcieri]

Went ahead and landed #728.

I also added the Double trait upstream to the elliptic-curve crate and will circle back on getting it upgraded and the crate version numbers bumped.