Support pairing with negative `u` for BN curves

[weikengchen]

Recently in one of my projects, I need to implement a BN254 curve with very efficient pairing, but two-arity in Fr is not needed. The best known BN254 curve for this situation is:

a BN curve over the 254-bit prime p = 36u^4 + 36u^3 + 24u^2 + 6u + 1 where u = -(2^62 + 2^55 + 1) < 0

with optimal ate pairing, as documented in https://github.com/herumi/ate-pairing, where the u is negative.

This curve differs from the BN254 curve in the arkworks/curves repo mainly because it has a lower NAF weight of |6u+2| and therefore permits a faster pairing. Yet, it does not have a good two-arity in Fr, so not very suitable for FFT.

Problems

Although our BN curve framework leaves space for negative u (here, X), as follows. The support is not full.

pub trait BnParameters: 'static {
    const X: &'static [u64];
    const X_IS_NEGATIVE: bool;
}

Basically, the preparing algorithm for G2 (https://github.com/arkworks-rs/algebra/blob/master/ec/src/models/bn/g2.rs#L68) as well as the Miller loop implementation is a version for u > 0 (https://eprint.iacr.org/2010/186.pdf) rather than a generalized version that works with u < 0 (as in https://eprint.iacr.org/2010/526.pdf). This issue is found by a comparison between the prepared G2 generator between herumi/ate-pairing and arkworks's.

There are two solutions: (1) prepare the G2 elements differently when u < 0 (2) or, do the Miller loop differently when u < 0

A PR may be coming soon to add this support. Though BN254 curves are less likely to be used in cryptocurrency systems since it does not offer 128-bit security, larger BN curves may still be useful---BN curves have G_1 cofactor to be one, a property that many other curves do not have that some applications may want. As time goes, though, we may all go to BLS-24 or BLS-48 curves.

[daira]

Pluto (https://github.com/daira/pluto-eris and https://github.com/arkworks-rs/curves/pull/54) is also a BN curve with negative u. It has high 2-adicity for both base and scalar fields, and low NAF weight.

[weikengchen]

When fixing, I found that all the places to change co-occur what ATE_LOOP_COUNT_IS_NEGATIVE is flagging.

So, turns out that the everything is fixed if one simply sets:

const ATE_LOOP_COUNT_IS_NEGATIVE: bool = true;

I guess this is because it considers ATE_LOOP_COUNT to be 6u+2 rather than |6u+2|. If it is negative, then basically u is also negative.

@daira I will release my code (on a different curve); it may help implement Pluto/Eris.

[weikengchen]

My implementation of that old BN254 curve is here: https://github.com/oblivious-file-sharing/netherite-algebra/tree/main/src/curve_bn254