Iโve added ๐พโ multi-exponentiations to Constantine in ๐พโ multi-exponentiations by mratsim ยท Pull Request #436 ยท mratsim/constantine ยท GitHub, no XTR or Torus-based cryptography just endomorphism acceleration + bucket algorithm/Pippenger on ๐พโ.
For single multi-exponentiation vs single scalar multiplication, the ratio between ๐พโ and ๐พโ is just 3x.
For multiexp and MSM, the ratio becomes 5x because of the affine formula popularized by Aztec and TurboPlonk that divides by 2 the number of base field mul (https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf)
Benchmarks on a Ryzen 7840U (15W~30W laptop 8-core CPU)
Constant-time
Iโve also added constant-time exponentiation so that validators can commit with their private key, using my extremely optimized constant-time routines, the cost of constant-time is only 10% over vartime.
๐พโ
๐พโ
Compared to the next best ๐พโ exponentiation from Gnark, Constantine is 2.28x faster due to a combination of factors:
- 4-GLS endomorphism acceleration instead of 2-GLV
- fully lazy reduced tower for field extension
- Fp2 โ Fp4 โ Fp12 towering instead of the usual Fp2 โ Fp6 โ Fp12 towering (the tradeoff is that inversion is slower, but inversion can be batched)
๐พโ exponentiation, with endomorphism acceleration by mratsim ยท Pull Request #429 ยท mratsim/constantine ยท GitHub for benches vs Gnark
