multi-scalar multiplication / multi-exponentiations (a.k.a. Pippenger algorithm)

[mratsim]

Glossary:

• We talk about scalar multiplication for additive groups G1 (over Fp) and G2 (over Fp2 thanks to a sextic twist)
• We talk about exponentiation for multiplicative group GT (defined over Fp12 for common pairing curve like BN254_Snarks and BLS12_381)

For Zk-SNARKS, we need to compute a linear combination of scalar multiplication/exponentiation:

Q <- [k1] P1 + [k2] P2 + ... + [kn] Pn

As a generalization to the Strauss-Shamir trick for [a]P + [b]Q we can save a significant amount of iterations.

Research

• Vitalik's post on EthResear.ch: https://ethresear.ch/t/simple-guide-to-fast-linear-combinations-aka-multiexponentiations/7238
• Faster batch forgery identification
  Bernstein, Doumen, Lange and Oosterwijk
  https://eprint.iacr.org/2012/549.pdf
• Pippenger’s Multiproduct and Multiexponentiation Algorithms
  Ryan Henry, 2010
  http://cacr.uwaterloo.ca/techreports/2010/cacr2010-26.pdf
• Efficient MultiExponentiation
  Jonathan Bootle
  https://jbootle.github.io/Misc/pippenger.pdf
• Pippenger's Exponentiation Algorithm
  Bernstein, 2002
  https://cr.yp.to/papers/pippenger.pdf
• On the Evaluation of Powers and Monomials
  Nicholas Pippenger, 1980
  https://pdfs.semanticscholar.org/7d65/53e185fd90a855717ee915992e17f38c99ae.pdf

Implementations

• Python by Vitalik: https://github.com/ethereum/research/blob/420a19e4449a2a85cb81a6731d6cf4534c3a366b/fast_linear_combinations/multicombs.py
• Go by Consensys (with multithreading): https://github.com/ConsenSys/gnark/blob/d160f27275a740b879d4132138e642c9c6ea1b0c/ecc/bls381/g1.go#L388
• C++ by the AztecProtocol: https://github.com/AztecProtocol/barretenberg/blob/884c641eb165885f06d7c820dd6cfb4b93851506/barretenberg/src/aztec/ecc/curves/bn254/scalar_multiplication/scalar_multiplication.cpp#L113

Side-note

For batched signature verification (see https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407) we may use this as well. To be studied compared to the PAIR_BLS381_another in Milagro to accumulate line functions for multi-pairing and incur the cost of final exponentiation only once as well.

• https://github.com/status-im/nim-blscurve/blob/1a18d0dbea6f1f00409c660be58eb5206060cb3c/blscurve/bls_signature_scheme.nim#L221-L227
• https://github.com/status-im/nim-blscurve/blob/a4c7050f89a42b997ff7c2b398e6c40120196b15/blscurve/csources/32/pair_BLS381.c#L199-L269

[mratsim]

Other references:

Explanation of Bos-Coster as proposed for batch Schnorr's signature verification in Bitcoin https://bitcoin.stackexchange.com/questions/80698/schnorrs-batch-validation

• Simple Schnorr Multi-Signatureswith Applications to Bitcoin
  Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille, 2018
  https://eprint.iacr.org/2018/068.pdf

• High-speed high security signatures
  Bernstein, Duif, Lange, Schwabe, Yang,
  https://ed25519.cr.yp.to/ed25519-20110926.pdf

[mratsim]

Discussion on Twitter with Consensus ZkSnarks team and the ZkStudyClub:

• https://www.youtube.com/watch?v=Bl5mQA7UL2I
• https://www.slideshare.net/GusGutoski/multiscalar-multiplication-state-of-the-art-and-new-ideas