zkcrypto / group Goto Github PK

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.

1. Don't make generator() const
2. Offer a (potentially-std only?) wrapper for Groups allowing overriding their generators

Ideally, 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.

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?

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.

Cc RustCrypto/traits#1170.

These are supposed to be enabling multiplication of scalar references, but clearly they are HRTBing lifetimes that we never use. We should fix this!

Breaking change to traits, so requires a minor release.

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:

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)

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.

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.

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.

I've found the name Curve a bit confusing as a trait impl'd on ProjectivePoints, 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.

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.

Same rationale as for ff::PrimeField::Repr (zkcrypto/ff#63).

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.

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
• zkcrypto/bls12_381#70 (from the 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.
• Protocol implementors can either restrict their implementations to only work with PrimeGroups, or can explicitly choose to support CofactorGroups (and then explicitly handle the subgroup conversion with e.g. CofactorGroup::mul_by_cofactor, which would be a no-op for PrimeGroups).
• Protocol implementors can choose to specialise to elliptic curves if they want to leverage an affine representation and mixed addition in their protocol for efficiency, or they can ignore those traits and stick with the simpler group-focused traits.

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.

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:

1. RngCore is implemented for &mut RngCore, so you don't need to include &mut in the signature
2. Bound on CryptoRng in addition to RngCore (it seems the reason this isn't already this way is for XorShiftRng?)
3. Use 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)