Pippenger for G1 scalar_mul (single-threaded), add_mixed optimisation

[jon-chuang]

In order to match gnark timings for G1, we should bring mul_assign timings down to 220us from 270us. add_mixed should be brought down from 750us to 705us.

gnark uses the following algorithm credited to Jonathan Bootle: https://jbootle.github.io/Misc/pippenger.pdf.

[burdges]

At some point the Edwards "Jubjub" curves could benefit form Pippenger too, although maybe that code should be modeled on dalek or something, not sure.

[Pratyush]

All elliptic curves in Zexe already work with the pippenger-based MSM!

[Pratyush]

Hmm @jon-chuang do you know what the difference between the two algorithms was? I believe ark-ec is just using the standard EFD algorithms

[jon-chuang]

Well certainly with w-NAF and GLV we've achieved the desired speedup for scalar mul and more. The only remaining question is for the mixed add.

Wrt your question, I don't know.

[ValarDragon]

AFAIU, gnark has a lower finite field multiplication time than arkworks, due to the optimization to montgomery reduction they describe in this article: https://hackmd.io/@zkteam/modular_multiplication#Implementation. Their speedup was 65ns -> 50ns per multiplication, which looks roughly like the speedup for mul_assign.

(Perhaps theres a separate algorithmic speedup there as well)

[jon-chuang]

This is incorrect, the above discrepancies were even after the equivalent alg was implemented. In fact, our assembly montgomery mul is faster.

Anw, I'm closing, as these comments are imo based on old data and not worth digging up. If someone wants to bench carefully and find areas for improvements please do so anew.