search

mratsim / constantine

Constantine: modular, high-performance, zero-dependency cryptography stack for verifiable computation, proof systems and blockchain protocols.
Other
413 stars 44 forks source link

Optimize MSM for Bandersnatch/wagon and Verkle Tries #415

Open mratsim opened 5 months ago

mratsim commented 5 months ago

Followup to #414

There are 3 ways to optimize MSM for the Bander curves

  1. MSM for Bandersnatch and Banderwagon does not use endomorphism acceleration. This is because their endomorphism requires to switch to projective coordinates. https://github.com/mratsim/constantine/blob/90f5e4d3093883a5b7f0b7192f2cfbb29ad93682/constantine/named/zoo_endomorphisms.nim#L53-L77
  2. We use Projective coordinates but Twisted Extended (X, Y, Z, T) might be noticeably faster (22% according to paper): https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf
  3. Implement precomputed tables for fixed CRS for Verkle Tries / IPA: