BSTMSM: A High-Performance FPGA-based Multi-Scalar Multiplication Hardware Accelerator

Zero-knowledge Proof (ZKP) is widely used in applications like online auctions and electronic voting to ensure privacy. Among ZKP algorithms, Zero-Knowledge Succinct NonInteractive Argument of Knowledge (zk-SNARK) stands out for its efficiency in generating concise proofs and reducing verification costs. However, the generation of zk-SNARK proofs poses challenges due to computation overhead and time requirements, hindering practical applications. Multi-Scalar Multiplication (MSM) is a computationally intensive step in zk-SNARK proof generation and has become a focus for industry acceleration efforts. In this paper, we introduce Barrel State Tracking MSM (BSTMSM), a high-performance FPGA-based MSM hardware accelerator. Unlike traditional approaches, BSTMSM focuses on tracking the state of each barrel rather than the pipeline of point addition (PADD) circuits. This approach eliminates the impact of barrel collisions and improves the utilization rate of PADD circuits by enabling the utilization of the associative law of addition. Furthermore, we have successfully implemented up to double PADD circuits in BSTMSM, leading to remarkable performance enhancements compared to other existing works. For an input size of 220, BSTMSM outperforms the ASIC-based work PipeZK by 1.53x. For an input size of 226, BSTMSM achieves performance improvements of 2.22x compared to the FPGA-based work HARDCAML and 1.24x compared to the GPU-based work GZKP.