w3f / fflonk

Apache License 2.0
25 stars 7 forks source link

Faster multiexps #12

Open swasilyev opened 2 years ago

swasilyev commented 2 years ago
  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:

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