zkcrypto / group Goto Github PK
View Code? Open in Web Editor NEWElliptic curve group traits and utilities.
License: Other
Elliptic curve group traits and utilities.
License: Other
I'm just annoyed with constantly importing PrimeFieldBits and writing PrimeFieldBits + PrimeGroup. I believe this would be resolvable with a few lines on my end everywhere I use the two, via:
trait PrimeGroupBits {}
impl<G: PrimeGroup> PrimeGroupBits for G where G::Scalar PrimeFieldBits {}
Yet then I need to add those lines to multiple libraries, so I'd appreciate this being introduced upstream. That may actually be the exact patch I'm proposing for here (+pub), as it means downstream libs wouldn't have to apply it themselves (which they may miss via an oversight). While PrimeGroup cannot be automatically applied as such (the Prime
part of PrimeGroup
, no such conveyance is made here.
I fully understand this a minor triviality and you're more than welcome to say it doesn't fit for group/doesn't have enough of a larger use case yet, but I'd appreciate it. Anything performing multiexp requires the former, if using ff properly to do so, and then PrimeGroup offers security (lack of torsion) and GroupEncoding (as frequently required by apps), hence the request for PrimeGroupBits instead of GroupBits.
Alternatively, if #25 has the preference of being over Group instead of over PrimeGroup, I believe a GroupBits for multiexp with PrimeGroupBits impl<G: GroupBits + PrimeGroup> PrimeGroupBits for G {}
would be optimal.
I found myself in a pickle when trying to generalize over both ProjectivePoint
and AffinePoint
.
Currently Group
and PrimeCurveAffine
have identity()
and is_identity()
, but there is no trait that can be implemented on both point types that provides access to this functionality.
So I would like to propose adding a new trait Identity
and refactor identity()
and is_identity()
into it.
Happy to make the PR upon approval.
Similar suggestion to zkcrypto/ff#87
Using associated constants instead of static methods allows using values in const contexts, like defining other constants or const fn
.
I've found the name Curve
a bit confusing as a trait impl'd on ProjectivePoint
s, especially since in @RustCrypto we have an elliptic_curve::Curve
trait which is impl'd on ZSTs representing properties/types for a specific elliptic curve.
I think Curve
is supposed to be a trait for an element of an elliptic curve group (and has Group
as a supertrait already), and as such might be better named CurveGroup
.
Same rationale as for ff::PrimeField::Repr
(zkcrypto/ff#63).
We currently have a group::Wnaf
helper that enables downstream groups to perform optimised scalar multiplications. We should similarly have a helper that enables downstream groups to perform multiscalar multiplication (aka multiexponentiation or sum-of-products).
Code examples we could use as a basis for figuring out a generic, usable, and performant design:
halo2::arithmetic::best_multiexp
bls12_381_plus
fork of bls12_381
).bellperson::groth16::multiscalar
We've been working on refactoring the group
crate traits over in https://github.com/zcash/librustzcash. See here for the current state of the refactor (as of 2020-05-28). The core of the current refactor is the following:
trait Group: GroupOps + GroupOps<<Self as Group>::Subgroup> {
type Subgroup: PrimeGroup
fn identity() -> Self::Subgroup;
}
trait PrimeGroup: Group {}
However, we can't easily convince rustc
that PrimeGroup
is only implemented on types for which Group::Subgroup = Self
, and this then causes issues when using the group operations because Self::Subgroup != Self::Subgroup::Subgroup
.
I'm now considering the following approach, where we define several base traits, and then separate top-level traits for prime-order and cofactor groups:
/// An element of a cryptographic group.
trait Group: GroupOps + ScalarMul<<Self as Group>::Scalar> {
type Scalar: PrimeField;
fn identity() -> Self;
...
}
/// Efficient representation of an elliptic curve point.
trait Curve: Group + GroupOps<<Self as Curve>::AffineRepr> { // Mixed addition
type AffineRepr;
fn to_affine() -> Self::AffineRepr;
...
}
/// A group element with a defined encoding.
trait GroupEncoding {
type Repr: Default + AsRef<[u8]> + AsMut<[u8]>;
fn from_bytes(&Self::Repr) -> CtOption<Self>;
...
}
/// Affine representation of an elliptic curve point that has a defined uncompressed encoding.
trait UncompressedEncoding {
type Uncompressed: Default + AsRef<[u8]> + AsMut<[u8]>;
fn from_uncompressed(&Self::Uncompressed) -> CtOption<Self>;
...
}
/// An element of a prime-order cryptographic group.
trait PrimeGroup: Group + GroupEncoding {}
trait PrimeCurve: Curve<AffineRepr = <Self as PrimeCurve>::Affine> + PrimeGroup {
type Affine: PrimeCurveAffine<Curve = Self, Scalar = Self::Scalar>
// Scalar multiplication with mixed addition
+ Mul<Self::Scalar, Output = Self>;
}
pub trait PrimeCurveAffine:
GroupEncoding
// Scalar multiplication with mixed addition
+ Mul<<Self as PrimeCurveAffine>::Scalar, Output = <Self as PrimeCurveAffine>::Curve>
{
type Scalar: PrimeField;
type Curve: PrimeCurve<Affine = Self, Scalar = Self::Scalar>;
fn identity() -> Self;
fn to_curve(&self) -> Self::Curve;
...
}
trait CofactorGroup:
Group
+ GroupEncoding
// Using the type system to enforce Group + Subgroup -> Group
+ GroupOps<<Self as CofactorGroup>::Subgroup>
{
/// The large prime-order subgroup in which cryptographic operations are performed.
/// If `Self` also implements `PrimeGroup`, then `Self::Subgroup` may be `Self`.
type Subgroup: PrimeGroup<Scalar = Self::Scalar> + Into<Self>;
fn mul_by_cofactor(&self) -> Self::Subgroup;
fn into_subgroup(self) -> CtOption<Self::Subgroup>;
...
}
trait CofactorCurve: Curve<AffineRepr = <Self as CofactorCurve>::Affine> + CofactorGroup {
type Affine: CofactorCurveAffine<Curve = Self, Scalar = Self::Scalar>
// Scalar multiplication with mixed addition
+ Mul<Self::Scalar, Output = Self>;
}
trait CofactorCurveAffine:
GroupEncoding
// Scalar multiplication with mixed addition
+ Mul<<Self as CofactorCurveAffine>::Scalar, Output = <Self as CofactorCurveAffine>::Curve>
{
type Scalar: PrimeField;
type Curve: CofactorCurve<Affine = Self, Scalar = Self::Scalar>;
fn identity() -> Self;
fn to_curve(&self) -> Self::Curve;
...
}
I see several advantages for this kind of API:
PrimeGroup
does not have a Subgroup
associated type, bounding any recursion.PrimeGroup
s, or can explicitly choose to support CofactorGroup
s (and then explicitly handle the subgroup conversion with e.g. CofactorGroup::mul_by_cofactor
, which would be a no-op for PrimeGroup
s).I'd like to hear thoughts on this; in particular, what pain points this might cause for current users of the group
crate vs the current (elliptic-curve-specific) traits.
There is currently no public API in Wnaf
to do the precomputations for the scalar and for the base separately. There should be no obstacle to allowing that because the precomputations are independent. That would be precisely what we need to avoid excess computation and allocation when doing scalar muls for the cross product of a set of scalars and a set of bases. (See zcash/librustzcash#593.)
Originally posted by @daira in #33 (review)
The documentation is lacking whether or not the wNAF exponentiation is safe to use with secret exponents. I'm guessing it is not?
Is everyone only using this for signature verification?
rand_core
v0.6 has been released with first-class WASM support via getrandom
v0.2.
It'd be great to get a version bump of this dependency in the next breaking release.
Curious if there are any plans to get another release out? (No rush!)
We've started a v0.14.x prerelease series of the @RustCrypto elliptic curve crates and it would be nice to maintain lockstep with group
/ff
.
#46 is probably the issue we'd most like to see addressed for those crates since it's blocking our use of wNAF. That said, there are a number of proposed breaking changes in the issue tracker it would be nice to get a yay/nay on.
Some assorted nits about how this crate handles random number generation:
It seems like if tests
were a cargo feature, this crate could depend upon rand_core
instead of rand
(optionally importing the latter when the tests
feature is enabled). One fewer dependency would be nice.
Additionally, I'd suggest changing the Group::random
method in the following way:
- fn random<R: RngCore + ?Sized>(rng: &mut R) -> Self;
+ fn random(rng: impl CryptoRng + RngCore) -> Self;
Concretely this is:
RngCore
is implemented for &mut RngCore
, so you don't need to include &mut
in the signatureCryptoRng
in addition to RngCore
(it seems the reason this isn't already this way is for XorShiftRng
?)impl Trait
as syntactic sugar to remove the type parameter (IMO there's no cases where an explicit type parameter helps here, so removing it makes it easier to read)It would be nice to have a shared trait over projective and affine points that signifies if they belong to a prime group or not.
Currently the prime group traits are split in PrimeCurve
, PrimeCurveAffine
and PrimeGroup
, my understanding is that affine points can only implement PrimeCurveAffine
, therefore having no shared trait between the too.
Therefor I would like to propose a marker trait that can be implemented for both.
Happy to make a PR if somebody can suggest me a name, IANA cryptographer and don't feel 100% comfortable with all the terminology used here.
Per #32, specifically,
I think the generator side of this definitely needs some experimentation, because while there are logical reasons for choosing a particular generator as standard, they aren't as natural as the singular choice of Field::ONE.
yet reminded by #44, now proposing again extending the generator API, I'd like to consolidate discussion and provide a proposal.
The main reasons for the generator function are simply convenience. I'd assume most people using cryptography will always use a single generator. Not only is providing the presumed standard preventing acquiring it, it prevents having to pass it around everywhere. Defining a generator also opens optimizations such as #44. I believe my code lost 15% of its performance when I stopped using dalek's table...
The main issue is almost all points are usable as generators and there's many such reasons to use alternative generators, which I won't bother to iterate here. Removing the generator function to acknowledge this would negatively harm most users AND add frequently unnecessarily API complications as everyone now passes it around at every level.
My suggestion maintains the simple path, while offering further flexibility.
generator()
constIdeally, in my 'I have not yet wrote a line of code to see how well this'd work' opinion, it'd be an RAII-style push to scope a distinct generator. Internally, I presume a static mut HashMap<ThreadId, Vec> could handle pushed generators? So long as the returned lock wasn't usable under async...
The benefit is that then, a theoretically Schnorr PoK crate, could simply call generator()
, not needing to take in a generator in its API, yet still provide PoKs across any generator.
Due to the complexities of the latter, I'm not here to explicitly ask for it in group
. Solely call for GENERATOR
to remain non-constant. This doesn't conflict with #44, adding a non-const function, yet it's my thoughts on the matter. Of course, I'd love to hear @str4d's thoughts since they said experimentation was needed.
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.
batch_normalize
currently documents this caveat:
This function will panic if
p.len() != q.len()
.
However, with const generics you can construct an output array that matches the input size with compile-time assurances:
fn batch_normalize_array<const N: usize>(points: &[Self, N]) -> [Self::AffineRepr; N] { ... }
This issue is to suggest an addition, rather than a replacement, specifically for use cases where the number of points is fixed at compile-time.
Note that this approach is also useful for stack allocating all intermediate values (since you can size the arrays by N
), allowing for efficient implementations on heapless targets.
I want to make that something whose struct is "::Curve" can be transmitted between differernt processes.But now I just be able to transmitted some "double" things.It may be able to transmit some "u64" things.So I want to get all "u64" in "::Curve".And then I can use them to form a "G1Projective" and transform it to get a "::Curve".Why I choose "G1Projective" is that I printf some "::Curve" and get following results:
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.