constantine
constantine copied to clipboard
Optimize MSM for Bandersnatch/wagon and Verkle Tries
Followup to #414
There are 3 ways to optimize MSM for the Bander curves
- 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
- 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
- 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