Accelerating zk-SNARK with Group and Zone Optimization on GPU

Abstract

Zero-knowledge proof (ZKP) is a popular cryptographic strategy for building a trusted environment, which can be applied to blockchain, electronic voting, and other scenarios. However, ZKP involves a number of computationally intensive operations that limit its widespread adoption in time-sensitive practical applications. The multi-scalar multiplication (MSM) dominates the computations and takes over 70% of the total computation time. This paper proposes a GPU-based acceleration method for ZKP by designing several optimization techniques for MSM. First, this paper constructs a formal mathematical formula of the Pippenger algorithm, which provides a theoretical optimization framework for MSM. Second, by parallelizing the prefix sum, the time complexity of the bucket reduction part of MSM is reduced from $\mathcal{O}\left( {3 \times {2^C}} \right)$ to $\mathcal{O}\left( {2 \times {2^C}} \right)$. Finally, this paper also analyzes the influence of group size on the final calculation time under different data scales and gives a suitable range of group sizes. Compared to the state-of-the-art method, our method can achieve 1.01× to 1.12× for throughput.