FlexMSM: A Flexible FPGA Accelerator for Multi-Scalar Multiplication with Reconfigurable Arithmetic and Dual-Decoupled Aggregation

Abstract

Zero-Knowledge Proofs (ZKPs), particularly zk- SNARKs, are extensively employed in privacy-sensitive applications, but proof generation in such protocols imposes significant computational overhead. A major performance bottleneck is Multi-Scalar Multiplication (MSM), a highly compute-intensive operation on elliptic curves. While existing work focuses on specialized curves such as BLS12-377, which support more efficient elliptic curve arithmetic, there is limited exploration of MSM on general-purpose curves such as BLS12-381, which lack such optimizations and make parallelization more difficult. It faces the following challenges: imbalanced resource usage in modular multipliers, performance disparity between elliptic curve operations, and under-utilization of point addition unit in scheduling. To tackle these challenges, we propose FlexMSM, a flexible and scalable FPGA-based accelerator to accelerate MSM. FlexMSM innovates three techniques. First, we present a reconfigurable modular multiplier based on our proposed Hybrid-Weight Modular Multiplication algorithm, which strikes a balance between hardware cost and the number of MSM cores deployed on a single FPGA. Second, we propose a unified point addition scheme and design a fully pipelined point addition (PADD) unit. This design eliminates timing mismatch between pipeline stages and shortens the critical path. Third, we introduce dual-decoupled scheduling strategy for the bucket aggregation phase in Pippenger algorithm, which reduces pipeline stalls and improves the utilization of the PADD unit in MSM. To the best of our knowledge, FlexMSM is the first work to support up to double MSM cores for BLS12-381 curve on a single Xilinx UltraScale+ VU13P FPGA, leading to remarkable performance enhancements compared to existing works for input sizes from 218to 226. For the degree of 220, FlexMSM with two cores on a single FPGA achieves speedups of 19.29× over Hardcaml, 8.57× over if-ZKP, 2.14× over OPTIMSM on FPGA, 6.57× over ASIC-based work PipeZK, and 9.29× over GPU-based work GZKP.