Is there a use-case for exposing the base field of Jubjub? From the perspective of a user of the elliptic curve library, the base field of the curve is an implementation detail. From looking through the API it seemed like the only place that it's used in the public API is in functions like from_raw_unchecked for unsafely constructing points, but it's not clear why someone would need to do that.

As jubjub::MODULUS:

use jubjub::{Fr, MODULUS};

let modulus: Fr = MODULUS;
// do something with it

IMO the current docs ("Constant representing the modulus r = 0x...") are okay, and it doesn't need a rename or anything.

I found this useful, not sure if others will.

See ZIP 216 for more details.

A new API jubjub::AffinePoint::from_bytes_pre_zip216_compatibility has been added for consensus compatibility. We will use this API in Zcash code until NU5 activates.

This PR is to add an addition chain for performing faster inversion over Fq. According to the benchmark it takes about half the time that the naive way does.

This is using the baseline addition presented by @ValarDragon in https://github.com/zkcrypto/jubjub/issues/1

I wrote a simple program in Java to convert the output in to rust code. I can share that tool if it useful or when we do teh same for Fr.

This changes virtually everything to be constant time, by introducing a new Maybe abstraction that can later be upstream'd to subtle. This borrows from #18's constant time Tonelli-Shanks, adapted to match the current implementation that is more efficient and more closely based on the paper.

TODO: tests for Maybe::and_then and Maybe::map

This is all of the point arithmetic we could possibly need; though we have to consider what is and isn't necessary downstream, and expose a simpler interface. ~This is mostly based on what curve25519-dalek does.~ I've modified my proposed API based on Mike Hamburg's paper.

• [ ] AffinePoint represents a (u, v) coordinate in memory.
  • [ ] ::identity() -> Self (forward from Default::default())
  • [ ] ::compress(&self) -> [u8; 32]
  • [ ] ::decompress_vartime([u8; 32]) -> Self
  • [ ] ::get_u(&self) -> Fq
  • [ ] ::get_v(&self) -> Fq
  • [ ] ::to_affine_niels(&self) -> AffineNielsPoint
  • [ ] ::double(&self) -> ExtendedPoint
  • [ ] (private) ::is_on_curve_var(&self) -> bool
• [ ] ExtendedPoint represents a (U, V, T1, T2, Z) coordinate in memory. (u:Z, v:Z with T1*T2 = uv/Z)
  • [ ] ::to_affine(&self) -> AffinePoint
  • [ ] ::double(&self) -> CompletedPoint
• [ ] AffineNielsPoint represents an affine point in Niels coordinates (v+u, v-u, uv2d)
• [ ] ProjectiveNielsPoint represents a projective point in Niels coordinates (V+U, V-U, Z, 2dUV)

Traits

• [ ] impl Add<&ExtendedNielsPoint> for &ExtendedPoint
• [ ] impl Add<&AffineNielsPoint> for &ExtendedPoint
• [ ] impl Sub<&ExtendedNielsPoint> for &AffinePoint
• [ ] impl Sub<&AffineNielsPoint> for &AffinePoint
• [ ] impl Neg for &AffineNielsPoint
• [ ] impl Neg for &ProjectiveNielsPoint
• [ ] impl Neg for &AffinePoint
• [ ] impl Neg for &ExtendedPoint

This PR is to incorporate the squaring algorithm from https://github.com/zcash/librustzcash/blob/master/pairing/src/bls12_381/fr.rs#L467

I've also added some benchmarks and refactored some of the helper functions to return pairs rather than update one value by reference.

Suggested by @str4d:

The Sarkar algorithm used in the Pasta implementation is applicable to Fq since it is highly 2-adic. (Fr is not, but optimizing Fq square roots is more important for Jubjub curve point decompression, and therefore for Sapling trial decryption; see https://github.com/zcash/librustzcash/pull/423#issuecomment-894377882 ).

In crates.io jubjub version is at 0.7.0 (https://crates.io/crates/jubjub) but here in github is 0.3.0 which is a bit confusing. Will it worth to tag 0.7.0 here now ?

The implementation of WnafGroup::recommended_wnaf_for_num_scalars copies the empirical recommendations from the old pairing::bls12_381 implementation of G1. We should recalculate them for this implementation.

https://github.com/zcash/librustzcash/pull/245#discussion_r471616548

We'd like to have Serde support for use implementing FROST for redjubjub (tracking issue: https://github.com/ZcashFoundation/redjubjub/issues/21). I'd be happy to implement this (probably feature-gated behind a serde feature?) if it would fit with the library.

Jubjub needs you!

... to make efficient addition chains.

• 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfefffffffeffffffff (for inversion in Fq)
• 0x39f6d3a994cebea4199cec0404d0ec02a9ded2017fff2dff7fffffff80000000 (for Legendre symbol in Fq)
• 0x39f6d3a994cebea4199cec0404d0ec02a9ded2017fff2dff80000000 (for sqrt in Fq)
• 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff (also for sqrt in Fq)

• 0x0e7db4ea6533afa906673b0101343b00a6682093ccc81082d0970e5ed6f72cb5 (for inversion in Fr)