arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations

https://www.arkworks.rs

Apache License 2.0

770 stars 207 forks source link

Optimize MNT4 pairing (2-NAF Miller loop) #307

Closed yelhousni closed 3 years ago

yelhousni commented 3 years ago

305

MNT4

jon-chuang commented 3 years ago

Is there a reason why one does not use a bigger window size for the w-NAf?

yelhousni commented 3 years ago

Is there a reason why one does not use a bigger window size for the w-NAf?

The Miller loop iterates over the binary decomposition of ATE_LOOP_COUNT (double if 0, double-and-add if 1). Noting that point negation is cheap (x,y)->(x,-y), one can leverage a 2-NAF decomposition if it has more 0's than in the binary form.

jon-chuang commented 3 years ago

Wouldn't it make sense to use a table here then?

yelhousni commented 3 years ago

Wouldn't it make sense to use a table here then?

@jon-chuang How would you suggest to do that? I am storing the pre-computed 2-NAF decomposition here https://github.com/scipr-lab/zexe/blob/48ccd3290ddf9502c005a44f0bc6f9e100c9ce8d/algebra/src/mnt4_753/curves/mod.rs#L40 and running a 1/-1 pattern matching in the Miller Loop here https://github.com/scipr-lab/zexe/blob/48ccd3290ddf9502c005a44f0bc6f9e100c9ce8d/algebra-core/src/curves/models/mnt4/mod.rs#L128

yelhousni commented 3 years ago

For CI / Test (nightly) failing, see #303

Pratyush commented 3 years ago

Hey @yelhousni, thanks for the PR! We're transitioning the code in this repo over to https://github.com/arkworks-rs/algebra/; could you make the PR there instead?

Pratyush commented 3 years ago

Hi @yelhousni do you mind re-opening this PR against arkworks-rs/algebra? Sorry for the inconvenience!