search

arkworks-rs / algebra

Libraries for finite field, elliptic curve, and polynomial arithmetic
https://arkworks.rs
Apache License 2.0
633 stars 247 forks source link

Improve Miller loop performance for SW6 #734

Open Pratyush opened 5 years ago

Pratyush commented 5 years ago

Currently the Miller loop for SW6 uses affine coordinates, which makes the loop much slower than necessary. Moving to projective coordinates should speed up the loop significantly.

One can use the MNT6 miller loop code as a reference point to get this working. Indeed, a prior version of the SW6 ML code was basically a port of the MNT6 code, but it had incorrect constants, and so the pairing result was incorrect. This (incorrect) version was ~4x faster than the current (correct) version.

yelhousni commented 5 years ago

Here is a ML in projective coordinates for SW6 curve: https://github.com/EYBlockchain/zk-swap-libff/blob/ey/libff/algebra/curves/sw6/sw6_pairing.cpp and for SW6_BIS (field size of 761 bits): https://github.com/EYBlockchain/zk-swap-libff/blob/ey/libff/algebra/curves/sw6_bis/sw6_bis_pairing.cpp

Pratyush commented 5 years ago

Awesome! Do you mind I port over the implementation to Rust? Is it under the MIT license?

yelhousni commented 5 years ago

Yes, it is MIT you can port it to Rust. I am working btw on porting SW6_BIS to Rust and do a PR here if you want.

Pratyush commented 5 years ago

Yes, that would be great!

yelhousni commented 4 years ago

Normally, affine coordinates should yield a faster pairing over SW6 if the inverse is implemented using the norm map as suggested in [1, 2, 3]. But I think it's not the case here, thus the ~4x factor you remarked.