Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add traits and APIs for dealing with curve coordinates #30

Open
str4d opened this issue Jul 5, 2022 · 8 comments
Open

Add traits and APIs for dealing with curve coordinates #30

str4d opened this issue Jul 5, 2022 · 8 comments
Milestone

Comments

@str4d
Copy link
Member

str4d commented Jul 5, 2022

The original motivation for removing the Base associated type from the old CurveProjective and CurveAffine traits in 15bc628 was that dealing in coordinates directly is almost always incorrect for cryptographic protocols, so we didn't expose them (instead leaving it to the concrete curve impls to handle such needs themselves). And if we don't expose the coordinates anywhere, then there is no reason to expose the base field (the associated type was completely unused at the time).

However, in proving system contexts it is necessary to have access to the coordinates in order to re-implement EC arithmetic inside a circuit. My original plan at the time of the above refactor was to move such curve implementations concretely into the curve crates themselves, but that leads to some awkward dependency tree management (we'd need to split crates like bellman and halo2_proofs up in a way that enabled this). This is why the pasta_curves crate currently exposes the base field and coordinates APIs via a CurveExt trait, but we explicitly want to make that trait obsolete by upstreaming its functionality here (zcash/pasta_curves#41), so we need to develop a solution for it.

@str4d
Copy link
Member Author

str4d commented Jul 5, 2022

We have a few things we need to expose:

  • A Base associated type on curve trait(s).
    • This must only be a property of curves, not groups, so Group and its subtraits must not be affected.
  • API to obtain coordinates from a curve point.
    • This likely should only be added to affine types. If you have a point in its efficient computation form, you need to convert it to affine anyway to access the coordinates, so we may as well make that explicit.
    • The coordinates should likely be returned in a wrapper like we currently do in pasta_curves, to enable us to e.g. operate over them in constant time. This wrapper should guarantee that it repesents a valid curve point.
  • API to obtain a curve point from coordinates.
    • This MUST involve an on-curve check, which we can enforce in the type system. This enables us to construct the coordinates wrapper type from a tuple of coordinates, as we do in pasta_curves currently.

@str4d
Copy link
Member Author

str4d commented Jul 5, 2022

Here's the current trait heirarchy:

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
Loading

If we add the coordinate access APIs to affine representations, then we'd need to add them to both PrimeCurveAffine and CofactorCurveAffine. That's a bit annoying, as these traits are already somewhat duplicative and this would continue to grow them. At the time I implemented the refactor to the above trait graph, I believe I couldn't get the Rust type system to play ball with a CurveAffine trait, but it would be worth attempting this again. It would alter the graph to:

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

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

        Curve -.- CurveAffine
    end

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

        PrimeCurve --> Curve
        PrimeCurve --> PrimeGroup

        PrimeCurveAffine --> CurveAffine

        PrimeCurve -.- PrimeCurveAffine
    end

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

        CofactorCurve --> Curve
        CofactorCurve --> CofactorGroup

        CofactorCurveAffine --> CurveAffine

        CofactorCurve -.- CofactorCurveAffine
    end
Loading

We might be able to avoid the extra bidirectional associated types on CofactorCurve and CofactorCurveAffine by leveraging the ones on Curve and CurveAffine, but I seem to recall trying that in the original refactor and running into issues with viral where bounds. We can give it another go, or we can just come up with more creative associated type names.

Alternatively, we could define a CurveCoordinates trait to encapsulate the new functionality, and express it like so:

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

        CurveCoordinates
    end

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

        PrimeCurve --> Curve
        PrimeCurve --> PrimeGroup

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

        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
        CofactorCurveAffine --> CurveCoordinates

        CofactorCurve -.- CofactorCurveAffine
    end
Loading

@tarcieri
Copy link
Contributor

As a general comment, supporting exotic point encodings and making the existing implementations generic and reusable have been the main reasons for having some form of coordinate access in the https://github.com/RustCrypto/elliptic-curves crates.

So far our solution has been to impl these encodings in the respective crates where they can access private field members and FieldElement types. This has resulted in something of a maintenance burden and makes it look like we offer first-class support for some experimental and not-fully-standardized constructions like https://datatracker.ietf.org/doc/html/draft-jivsov-ecc-compact-05

@str4d str4d added this to the 0.14 milestone Dec 7, 2022
tarcieri added a commit to RustCrypto/traits that referenced this issue Feb 1, 2023
See RustCrypto/elliptic-curves#50 for some historic context.

After being able to get by on `AffineXCoordinate` for generic ECDH and
ECDSA, #1199 added an `AffineYIsOdd` trait which was needed to enable
the generic ECDSA implementation in the `ecdsa` crate to compute the
"recovery ID" for signatures (which is effectively point compression for
the `R` curve point).

This commit consolidates `AffineXCoordinate` and `AffineYIsOdd` into
an `AffineCoordinates` trait.

Some observations since prior discussion in
RustCrypto/elliptic-curves#50:

- Access to coordinates is through bytes, namely `FieldBytes`. This is
  so as to avoid exposing a crate's field element type. This approach
  isn't type safe (base field elements and scalar field elements share
  the same serialization) but does make ECDSA's weird reduction of a
  base field element into the scalar field straightforward in generic
  code.
- Prior to this attempts were made to extract ECDSA-specific bits into a
  trait to handle these conversions, but it complicates both writing
  generic code and optimizing performance. While this still might be
  worth exploring, so far those explorations have largely failed.
- Generally there have been a lot of requests for coordinate access
  specifically for things like point serialization formats. We ended up
  adding "compaction" support upstream but we have had requests for
  several other formats (e.g. Elligator Squared) where direct coordinate
  access would be useful.

This trait can hopefully be replaced by a coordinate access API provided
by the `group` crate in the future. See zkcrypto/group#30
tarcieri added a commit to RustCrypto/traits that referenced this issue Feb 1, 2023
See RustCrypto/elliptic-curves#50 for some historic context.

After being able to get by on `AffineXCoordinate` for generic ECDH and
ECDSA, #1199 added an `AffineYIsOdd` trait which was needed to enable
the generic ECDSA implementation in the `ecdsa` crate to compute the
"recovery ID" for signatures (which is effectively point compression for
the `R` curve point).

This commit consolidates `AffineXCoordinate` and `AffineYIsOdd` into
an `AffineCoordinates` trait.

Some observations since prior discussion in
RustCrypto/elliptic-curves#50:

- Access to coordinates is through bytes, namely `FieldBytes`. This is
  so as to avoid exposing a crate's field element type. This approach
  isn't type safe (base field elements and scalar field elements share
  the same serialization) but does make ECDSA's weird reduction of a
  base field element into the scalar field straightforward in generic
  code.
- Prior to this attempts were made to extract ECDSA-specific bits into a
  trait to handle these conversions, but it complicates both writing
  generic code and optimizing performance. While this still might be
  worth exploring, so far those explorations have largely failed.
- Generally there have been a lot of requests for coordinate access
  specifically for things like point serialization formats. We ended up
  adding "compaction" support upstream but we have had requests for
  several other formats (e.g. Elligator Squared) where direct coordinate
  access would be useful.

This trait can hopefully be replaced by a coordinate access API provided
by the `group` crate in the future. See zkcrypto/group#30
@str4d
Copy link
Member Author

str4d commented Jul 29, 2023

I was able to implement a CurveAffine trait in #48, which means we can look more at the graph above corresponding to that approach. I'm still not sure though if a CurveAffine trait on its own is sufficient here, or if we should still have a standalone CurveCoordinates or similar.

We definitely want to introduce some concept of a curve model into whatever types or traits we build (#29 (comment)). Doing so would help with zcash/pasta_curves#41 as it would be a place we could easily expose the curve constants.

@tarcieri
Copy link
Contributor

In the case of dalek-cryptography/curve25519-dalek#553 we have a request for obtaining extended twisted Edwards coordinates (i.e. X/Y/Z/T). That may be esoteric enough a trait-based abstraction won't help there.

The main other use cases for this we have for @RustCrypto are all accessing affine coordinates, almost all of which are implementations of various wire formats for encoding those coordinates e.g. compact encoding, Elligator (Squared)

@str4d
Copy link
Member Author

str4d commented Jul 30, 2023

I'm not particularly interested in generically exposing the projective coordinates. We do have a use case for it in pasta_curves, but that's to implement hash-to-curve, which would be better suited by a separate trait or helper for implementing that specifically.

str4d added a commit that referenced this issue Jul 30, 2023
We use extension traits to limit how generic the generic code can be,
forcing it to be aware of the specific curve model that the coordinates
are associated with.

Closes #30.
@ycscaly
Copy link

ycscaly commented Oct 9, 2023

I've been asked by @tarcieri to move the discussion from elliptic-curves/#937 to here.

I am writing a Schnorr protocol and need access to the projective coordinates. Well, actually, I don't care about the coordinates per-se but some encoding of the projective point that I can use for commitment/decommitment, and to use on transcript.

Now, my only option is to switch to the affine coordinates. However, this is extremely costly in computation (e.g., in k256 it costs around 10 microseconds.) When writing a proof system that should handle O(1000) provers and O(1000) statements, this becomes a big deal. Actually, my proof system is aggregatable, and the base operations are orders of magnitude cheaper: scalar ops in k256 are in nanoseconds, whereas .to_affine() is in micro, which caused a much surprising bottleneck to the surface during commitment/transcript phases... imagine debugging and reaching that conclusion lol.

So, I need a way to uniquely encode projective points directly; and be able to transition in and out from those values and into a ProjectivePoint structure (I guess here, I need an Into<Vec<u8>> or actually a to_repr() method for Group, and a way to instantiate group elements using that same encoding.

Tony also asked me whether I care about other affine points mapping to the same projective point. I don't. Malicious provers won't be able to use that to their advantage, as they would be committing to the same value that the verifier would be using.

Thoughts on this?

Thanks.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants