I realized that the scalar base multiplication on twisted edwards curves, might be optimized by implementing a windowed fixed algorithm with precomputed values.
Reference design (circomlib) from https://github.com/iden3/circomlib/blob/master/circuits/escalarmul.circom
- 4-bit windows
- Precompute
[j * 2^(4*i)]·G for each window i
- Use mux over 16 entries per window (4-bit select) and accumulate.
We have implemented it for our elgamal babyjubjub schema, and saved around 17% constraints (on a circuit with 2 scalar base multiplications and 1 scalar multiplication). Feel free to reuse the code if useful.
https://github.com/vocdoni/gnark-crypto-primitives/blob/optimizations/elgamal/mul.go