They sometimes switch from $y^2 = x^3 + 7$ to $y^2 = x^3 + 7 t^6$ in order to use Jacobian coordinates. I haven't looked at why this is useful or whether a similar optimization applies to Pallas and Vesta. (The same structure of isomorphisms between curves is present; the question is whether it is useful for us.)

https://github.com/bitcoin-core/secp256k1/blob/60556c9f49a9384efd7f16b734820ae19108f053/src/ecmult_impl.h#L83-L93

This (along with its other related traits) was a helper trait that we created to provide additional methods needed for halo2_proofs that the ff crate traits didn't have, while we figured out what those needed additional methods were. Now that we've cut halo2_proofs 0.1.0, we need to finish the job:

• Figure out how to better abstract these additional methods if necessary.
• Add these abstractions to ff.
• Delete the FieldExt trait.

The jubjub README has some good warnings around security audit status and side-channels. This repo's README could include similar information.

In particular it should be noted in the README that these implementations (e.g. point addition) are not constant-time.

This information can also go in the rust documentation.

These were helper traits that we created to provide additional methods needed for halo2_proofs that the group crate traits didn't have, while we figured out what those needed additional methods were. Now that we've cut halo2_proofs 0.1.0, we need to finish the job:

• Figure out how to better abstract these additional methods.
• Add these abstractions to group.
• Delete the CurveExt and CurveAffine traits.

We want to be able to leverage GPUs in halo2, via the ec-gpu crate. This requires two changes:

• The curve implementation needs to support producing the GPU kernel for finite field arithmetic.
• halo2 needs to use GPU-aware MSM and FFT algorithms.

This issue covers the second change. We should implement the GpuEngine trait from the ec-gpu crate (behind a gpu feature flag), and then the ec-gpu-gen crate should be able to generate the necessary CUDA/OpenCL source code for MSMs and FFTs.

As pointed out by NCC, it should be the length of an input block for the hash, which is 128 bytes for BLAKE2b-512.

• Update specification (2021.1.20)
• Update Sage code (zcash/pasta#2)
• Update Rust code (#8)
• Update test vectors

I would really appreciate, if some alloc independent version of hash_to_curve got into upstream.

By modifying the current API? Or adding an alternative API? @str4d

In #4 we introduced a std feature flag, to enable downstream users to disable anything relying on std. This happened to gate all of the traits, because both FieldExt and CurveAffine depended on std::io.

We removed std::io usage from FieldExt in #20, so it could now be removed from any feature flag. CurveAffine still relies on std::io, but I want to remove that as well. Then we're just left with the fact that CurveExt requires FieldExt, FieldExt is bound on SqrtRatio, and the only way we can implement SqrtRatio right now depends on SqrtTables, which requires alloc.

So, we should add an alloc feature flag, and move everything behind it. We might also be able to remove the std feature flag as a result (which has not been in a release yet). There's no point in having the traits themselves be no-std accessible if we can't implement them without alloc. Once we have a fallback for SqrtRatio we can consider making the other traits no-std usable.

We want to be able to leverage GPUs in halo2, via the ec-gpu crate. This requires two changes:

• The curve implementation needs to support producing the GPU kernel for finite field arithmetic.
• halo2 needs to use GPU-aware MSM and FFT algorithms.

This issue covers the first change. We should implement the GpuField trait from the ec-gpu crate (behind a gpu feature flag), and then the ec-gpu-gen crate should be able to generate the necessary CUDA/OpenCL source code.

The lack of these operators results in awkward constructions, especially when constructing constants larger than 128 bits.

a << k would be equivalent to a * TWO.pow(k).
a >> k would drop the low-order k bits.

These definitions satisfy

• (a >> k) << k == a when a is a multiple of 2^k;
• (a << k) >> k == a when a << k does not overflow.

In order to implement the trait CurveExt for a curve it is necessary to implement the method:
fn coordinates(&self) -> CtOption<Coordinates<Self>>
This requires to create the struct Coordinates which cannot be done directly from outside the crate since its attributes x, y are pub(crate). There is also no method to create the struct.

If the visibility was changed to pub other curves could be implemented reusing this trait.

This will include the API refactor and no-std / alloc support.

It is quite typical, at least in my experience, for code using pasta_curves crate to have the necessity to persist or transfer structs with fields of types Fp and Fq, which requires (de)serialization.

As Rust doesn't allow implementing traits for imported structs, we have to manually write (de)serializers for every struct that contains Fp or Fq fields instead of being able to just do a simple #[derive].

Would you consider adding serialization impl's to these types? At least for some popular serialization libraries such as serde and borsh. The implementations could be behind a feature flag. The change, I believe, would be as much as adding a #[derive(Serialize,Deserialize,BorshSerialize,BorshDeserialize)] to the struct declaration.

I can do a PR, if you prefer.

Once #25 has been closed by #26, we should refactor CurveAffine to remove its std::io APIs. Then we can place those traits behind the alloc feature flag, and remove the std feature flag (which has not been in a release yet).

Currently this library has two field implementations, the Pallas field and the Vesta field. They only differ in their prime modulus, and are otherwise almost identically implemented. This makes the library harder to maintain, as every change needs to be duplicated.

There are several possible approaches we could take to improve the situation:

• Use a declarative macro.
  • We already use a declarative macro for implementing the curves, so it would be in keeping with the rest of the library.
  • This has been proposed and implemented here: e150cc5
• Use a procedural macro, i.e. ff_derive
  • This is how we originally implemented BLS12-381 in the pairing crate, but we replaced that with a direct implementation of the field in the bls12_381 crate, and ff_derive hasn't been as effectively maintained since. If we switched to it, the majority of our field maintenance effort could go into ff_derive instead of here.
• Use crypto-bigint to implement the internal field details.
  • This would reduce the amount of code we need to maintain, which would just be the mapping from a big integer element to a prime field element.
  • This would be quite a divergence from previous approaches. I also don't know how feature-complete crypto-bigint is, though progress is being made.
  • If this is a practical and performant approach, we could also combine it with either the declarative macro or ff_derive approach to make it easier to maintain as well.

In the Orchard spec we use incomplete addition inside the circuit, in places where we want efficiency, and where finding an edge case in incomplete addition is isomorphic to breaking discrete log (which the rest of the protocol already relies on for balance integrity). For some of these, like Sinsemilla in the commitment tree, we will want to add consensus rules that the ⊥ case never occurs (e.g. so transactions are only ever mined with anchors that exist in the chain). This will require implementing incomplete addition outside the circuit, but we default to impl std::ops::* using complete addition (for safety).

We should add Point::add_incomplete APIs that implement incomplete addition, are only usable with concrete knowledge of the point type (i.e. not generically), and document why you should not reach for them unless you have analysed the necessary edge cases.

Addition (incomplete, any a): http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
Doubling for a = 0: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l

These are used in Arkworks for short Weierstrass curves. I also implemented a variant of them in the ChudnovskyPoint class in the Sage implementation of Pasta used to generate the hash-to-curve test vectors. (The latter actually modifies the addition formulae to be complete, at some extra cost.)

A possible alternative is https://eprint.iacr.org/2015/1060 (see also privacy-scaling-explorations/halo2curves#15).

I came across https://github.com/iden3/ffiasm and wondered if this asm code has ever been benched against the actual implementation. And if so, whether it is faster.

I did some initial exploration and saw that most of the asm backend we have at PSE (see here) is as optimized as what rust here compiles too. (At least for fns like double as seen in: #44 (comment)

From a quick look, to functions like double or square looks like the exact same thing or even slightly worse:

Square

Double

From a superficial view is already obvious that PSE-ASM is has less ops.

So I just wonder if anyone has done a deep analysis on that. As from a short check, looks like is not worth even considering it.