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

mratsim commented 4 years ago

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.

mratsim commented 4 years ago

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 commented 4 years ago

Discussion on Twitter with Consensus ZkSnarks team and the ZkStudyClub:

mratsim / constantine