Fast Computation of Multi-Scalar Multiplication for Pairing-Based zkSNARK Applications

Abstract

The operation of computing$n$scalar multiplications in an elliptic curve group and then adding them together is called n-scalar multiplication.$n$-scalar multiplication is the essential operation for proof generation and verification in pairing-based trusted setup zero-knowledge succinct non-interactive argument of knowledge protocols, which enable the privacy-preserving features in blockchain applications. This paper proposed a method to compute$n$-scalar multiplication taking advantage of$3n$precomputed points. When instantiating over BLS12-381 curve, for$n=2^{c}\ (10\leq c\leq 22)$, which covers the majority of our purported applications, the proposed method showed 2.59% ∼ 12.26% theoretical speed improvement and demonstrated 1.63% ∼ 11.54% experimental improvement against Pippenger's bucket method.