Faster multiexps

[swasilyev]

1. Generating KZG setup is a very special example of fixed-base multiexp: the single fixed base is multiplied by a series of scalars. Currently ark_ec::msm::FixedBase is used. How optimal is that?
   • Yao's algorithm is designed to compute powers of a single base.
   • Bernstein claims, section 7, that single-base Pippenger is optimal
   • Gnark has a special routine exactly for this single-base multiexp
     Actually this case is of lesser importance because parameters used in practice are created in this form once. After they are updated that is another problem.
2. URS updates (those performed by a single party, not SRS updates during the 2nd phase of the MPC) seem no different from the next case. Proving validity of an update efficiently might be more challenging.
3. Currently ark_ec::msm::VariableBase is used for computing KZG commitments. In most cases prover works with the same URS, so can afford some precomputations. How advantageous can it be. Interesting multiexp implementations i'm aware of:
   • arkworks
   • gnark
     - kzg
   • celo + bw6-761 asm
   • barretenberg:
     - https://github.com/AztecProtocol/barretenberg/blob/master/barretenberg/src/aztec/ecc/pippenger.md
     - code

https://eprint.iacr.org/2012/549.pdf is another popular paper on the topic