Rui Jiang
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Cong Peng
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Min Luo
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Rongmao Chen
National University of Defense Technology, Changsha, China

Debiao He
School of Cyber Science and Engineering, Wuhan University, Wuhan, China

Keywords: Multi-scalar Multiplication, Zero-knowledge Proof, SIMD Parallel Implementation

Abstract

Multi-scalar multiplication (MSM) is the primary building block in many pairing-based zero-knowledge proof (ZKP) systems. MSM at large scales has become the main bottleneck in ZKP implementations. Inspired by existing SIMD-accelerated work, we are focused on accelerating MSM computing efficiency using SIMD instructions in a single CPU environment. First, we propose a SIMD-accelerated MSM computing architecture with no write conflicts and constant memory overheads. This architecture utilizes multithreading to achieve task-level and loop-level parallelism and employs a three-tier buffer mechanism to maximize the utilization of the SIMD engine. Instanced with AVX512-IFMA instructions, we implement six SIMD elliptic curve arithmetic engines for different point addition in three coordinate systems and two groups. Moreover, we integrate our AVX-MSM implementation into the libsnark library, naming it AVX-ZK. In more detail, point deduplication and “Three-Stage” memory optimization are proposed to address problems existing in practical applications. Based on the RELIC library, our performance results on the BLS12-381 curve show that our AVX-MSM achieves up to 27.86x speedup over the most popular Pippenger algorithm. Compared with libsnark, our AVX-ZK implementation achieves over 11.53x (up to 20.26x) speedup under standard benchmarks.