The Luo-Fu-Gong Algorithm for Multi-Scalar Multiplication

Multiscalar multiplication is the most expensive operation in zk-SNARKs using pairings on elliptic curves with applications to blockchains and electronic currency (Zcash). Various methods exist to improve the performance of multiscalar multiplication. These include Pippenger's algorithm from 1976, a long-standing standard, and more recent developments developed by Luo in his PhD thesis. The original publication authored by Luo, Fu and Gong claimed some mathematical statements in Section 5, supported by experimental evidence, to justify their multiscalar multiplication method. This work provides all mathematical proofs of these experimental assertions.