There's a lot more that could be done here, but this is a good start. Benchcmp results:

 name                         pre.bench ns/iter  post.bench ns/iter  diff ns/iter   diff %  speedup 
 fq12_exponentiation          11,716,547         10,224,742            -1,491,805  -12.73%   x 1.15 
 fq12_scalar_multiplication   37,328             32,967                    -4,361  -11.68%   x 1.13 
 fr_addition                  78                 78                             0    0.00%   x 1.00 
 fr_inverses                  39,070             38,530                      -540   -1.38%   x 1.01 
 fr_multiplication            168                139                          -29  -17.26%   x 1.21 
 fr_subtraction               94                 88                            -6   -6.38%   x 1.07 
 g1_addition                  3,793              3,273                       -520  -13.71%   x 1.16 
 g1_deserialization           1,543              1,324                       -219  -14.19%   x 1.17 
 g1_scalar_multiplication     1,061,075          923,539                 -137,536  -12.96%   x 1.15 
 g1_serialization             41,245             41,461                       216    0.52%   x 0.99 
 g1_serialization_normalized  1,557              1,550                         -7   -0.45%   x 1.00 
 g1_subtraction               3,863              3,181                       -682  -17.65%   x 1.21 
 g2_addition                  20,402             16,647                    -3,755  -18.41%   x 1.23 
 g2_deserialization           4,425,378          3,751,399               -673,979  -15.23%   x 1.18 
 g2_scalar_multiplication     5,002,151          4,310,324               -691,827  -13.83%   x 1.16 
 g2_serialization             47,679             44,978                    -2,701   -5.66%   x 1.06 
 g2_serialization_normalized  2,968              2,681                       -287   -9.67%   x 1.11 
 g2_subtraction               20,110             16,400                    -3,710  -18.45%   x 1.23 
 perform_pairing              13,292,641         11,376,729            -1,915,912  -14.41%   x 1.17 

Hello!

This is a small modification to the miller_loop and precompute methods. Both methods iterate over the bits of parameter ate_loop_count. If the bit is set to true, a line function for the G2 group element is precomputed in precompute. Then later in miller_loop, the line function is scaled by the paired G1 group element, with the result being multiplied into the accumulated Fp12 element f.

We can take advantage of the fact that negations on an elliptic curve are essentially free, and use a Non-Adjacent-Form representation of ate_loop_count. Instead of a binary representation, each 'bit' can be either 0, 1 or -1. The hamming weight of the NAF is ~50% less than the binary form.

The precompute algorithm is modified to iterate over NAF entries of ate_loop_count_naf. If an entry is -1, a line function relative to -G2 is computed. This reduces the number of precomputed G2 entries, from 102 to 87.

This provides a corresponding ~15% reduction in the run-time of the miller loop, as each precompute entry requires a line doubling computation in Fp2 and a scalar multiplication in Fp12, both of which are expensive.

Hello there!

We've been discussing the parity bn library in the EIP-1829 telegram channel, and noticed that pairing algorithm has some noticeable areas that could be sped up.

Specifically, the 'final exponentiation' step in a bilinear pairing only needs to be computed once for a batch of pairings. In addition, a significant portion of the 'miller loop' algorithm only needs to be performed once for a batch of pairings.

As currently implemented, these computationally intensive steps were being performed for every pair of points passed to the library.

I have put together a small algorithm that computes a bilinear pairing for a batch of points that takes advantage of these speedups. The resulting algorithm is at least 2x faster when computing a pairing of 10 points, which is fairly significant.

I'm quite unfamiliar with Rust, so if there are any changes that need to be made to the PR I would be happy to make them. @shamatar from matter labs has also been hacking away at this with me, and also has a solution at https://github.com/shamatar/bn

Cheers, Zac.

(From upstream.) The y coordinate shouldn't be negated if it's zero.

This doesn't break any API invariants, but it does look like you're changing the library to expose more things.

See also https://github.com/scipr-lab/libsnark/issues/60.

Supersedes #1

(From upstream.) The y coordinate shouldn't be negated if it's zero.

This doesn't break any API invariants, but it does look like you're changing the library to expose more things.

See also https://github.com/scipr-lab/libsnark/issues/60.

This PR updates the bigints (U512 and U256) to use u128 for limbs. The fields' inverses were defined over 2^64 so I had to extend them to 2^128.

benchcmp

name                         control ns/iter  variable ns/iter  diff ns/iter   diff %  speedup
 fq12_exponentiation          4,544,644        2,338,371           -2,206,273  -48.55%   x 1.94
 fq12_scalar_multiplication   14,569           7,125                   -7,444  -51.09%   x 2.04
 fr_addition                  17               13                          -4  -23.53%   x 1.31
 fr_inverses                  8,711            5,531                   -3,180  -36.51%   x 1.57
 fr_multiplication            104              41                         -63  -60.58%   x 2.54
 fr_subtraction               20               14                          -6  -30.00%   x 1.43
 g1_addition                  1,805            756                     -1,049  -58.12%   x 2.39
 g1_deserialization           768              482                       -286  -37.24%   x 1.59
 g1_scalar_multiplication     481,975          212,330               -269,645  -55.95%   x 2.27
 g1_serialization             9,898            6,428                   -3,470  -35.06%   x 1.54
 g1_serialization_normalized  549              431                       -118  -21.49%   x 1.27
 g1_subtraction               1,872            771                     -1,101  -58.81%   x 2.43
 g2_addition                  8,440            3,768                   -4,672  -55.36%   x 2.24
 g2_deserialization           1,776,474        864,284               -912,190  -51.35%   x 2.06
 g2_scalar_multiplication     2,056,874        983,488             -1,073,386  -52.19%   x 2.09
 g2_serialization             12,477           7,628                   -4,849  -38.86%   x 1.64
 g2_serialization_normalized  1,039            752                       -287  -27.62%   x 1.38
 g2_subtraction               8,388            3,820                   -4,568  -54.46%   x 2.20
 perform_pairing              5,315,023        2,644,591           -2,670,432  -50.24%   x 2.01

@Vurich pointed out that activating rustc-serialize made the Group trait more restrictive, which could cause compilation errors. Turns out that this trait requirement isn't even required.

I'm proposing to use Cryptographically Secure RNGs. I also changed the deprecated notation of try!() to ?, and put the tests in groups/mod.rs within a test module to only have rand and rand_chacha as dev-dependencies.