Comparison with latest development in zero-knowledge / Snarks protocols

[mratsim]

Hi Thomas,

Your paper was brought to my attention by @yelhousni as I was looking for strategies to improve point decompression in zero-knowledge proofs and blockchain protocols (mratsim/constantine#236)

There has been some recent developments made in parallel by @asanso and @GottfriedHerold and summarized by @jsign:

• https://ihagopian.com/posts/tonelli-shanks-with-precomputed-dlog-tables
• https://hackmd.io/@jsign/bandersnatch-optimized-sqrt-notes

Looking at your table, you do not include the initial exponentiation cost

Re-running your code for the two-adicity of interest, n=32 for all most all "annoying sqrt fields" like Banrdersnatch, the Pasta curves, BLS12-377 except for BLS24-315 for which n=60 (https://eprint.iacr.org/2021/1359.pdf):

Gottfried's optimization with 8-bit windows lead to 34 field operations instead of the 38 you found.

Implementation in:

• bandersnatch/fp: use optimized sqrt crate-crypto/go-ipa#38
• https://github.com/GottfriedHerold/Bandersnatch

cc @kevaundray