constantine icon indicating copy to clipboard operation
constantine copied to clipboard

Optimize MSM for Bandersnatch/wagon and Verkle Tries

Open mratsim opened this issue 7 months ago • 0 comments

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:
  • https://hackmd.io/@1rDV_-HiSd-uTLJAZgeQTg/Hk0Ec7hO3
  • https://hackmd.io/@jsign/vkt-another-iteration-of-vkt-msms

mratsim avatar Jun 29 '24 22:06 mratsim