IACR News item: 15 January 2024
Xudong Zhu, Haoqi He, Zhengbang Yang, Yi Deng, Lutan Zhao, Rui Hou
ePrint Report
Zero-knowledge proof (ZKP) is a cryptographic primitive that enable a prover to convince a verifier that a statement is true without revealing any other information beyond the correctness of the statement itself. Due to its powerful capabilities, its most practical type, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK), has been widely deployed in various privacy-preserving applications such as cryptocurrencies and verifiable computation. Although state-of-the-art zkSNARKs are highly efficient for the verifier, the computational overhead for the prover is still orders of magnitude too high to warrant use in many applications. This overhead is due to several time-consuming operations, including large-scale matrix-vector multiplication (MUL), number-theoretic transform (NTT), and especially the multi-scalar multiplication (MSM) with the highest proportion. Thus, further efficiency improvements are needed.
In this paper we focus on comprehensive optimization of running time and storage space needed by the MSM algorithm on GPUs. Specifically, we propose a new modular and adaptive parameter configuration technique—elastic MSM to enable us to change the scale of MSM according to our own wishes by performing a corresponding amount of preprocessing. This technique enable us to fully unleash the potential of various efficient parallel MSM algorithms. From another perspective, our technique could also be regarded as a preprocessing technique over the well-known Pippenger algorithm, which is modular and could be used to accelerate almost all the most advanced parallel Pippenger algorithms on GPUs. Meanwhile, our technique provides an adaptive trade-off between the running time and the extra storage space needed by parallel Pippenger algorithms on GPUs. We implemented and tested elastic MSM over two prevailing parallel Pippenger algorithms on GPUs. Given a range of practical parameters, across various preprocessing space limitations (across various MSM scales), our construction achieves up to about 28× and 45× (25× and 40×) speedup versus two state-of-the-art preprocessing parallel Pippenger algorithms on GPUs, respectively.
In this paper we focus on comprehensive optimization of running time and storage space needed by the MSM algorithm on GPUs. Specifically, we propose a new modular and adaptive parameter configuration technique—elastic MSM to enable us to change the scale of MSM according to our own wishes by performing a corresponding amount of preprocessing. This technique enable us to fully unleash the potential of various efficient parallel MSM algorithms. From another perspective, our technique could also be regarded as a preprocessing technique over the well-known Pippenger algorithm, which is modular and could be used to accelerate almost all the most advanced parallel Pippenger algorithms on GPUs. Meanwhile, our technique provides an adaptive trade-off between the running time and the extra storage space needed by parallel Pippenger algorithms on GPUs. We implemented and tested elastic MSM over two prevailing parallel Pippenger algorithms on GPUs. Given a range of practical parameters, across various preprocessing space limitations (across various MSM scales), our construction achieves up to about 28× and 45× (25× and 40×) speedup versus two state-of-the-art preprocessing parallel Pippenger algorithms on GPUs, respectively.
Additional news items may be found on the IACR news page.