Closed tarcieri closed 4 years ago
@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.
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.
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 🙂
@str4d awesome! If you have a crate with some existing traits to use for this, all the better
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.
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.
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?
@str4d These traits look great. :+1:
@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?
If the new zcash traits by @str4d work for Edwards curves then they should probably work with Schnorr and RSA groups too.
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 useFrom
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, andelliptic_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:
PrimeCurve
and CofactorCurve
traits, which each cover classes of curve models.CofactorCurve
(e.g. Edwards curves that always have a torsion subgroup).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.
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.
I added an elliptic_curve::ops::Invert
trait in https://github.com/RustCrypto/traits/pull/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!
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.
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
andk256
crates have arithmetic implementations (thanks @str4d and @tuxxy!), an open question is how to write code that's generic over the underlyingAffinePoint
and/orProjectivePoint
types.It seems like
AffinePoint
andProjectivePoint
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'sAffinePoint
andProjectivePoint
types as associated types.Curious if people think this is a good idea and what those traits might look like.
cc @tuxxy