Paper 2022/1321

cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs

Tao Lu, Zhejiang University
Chengkun Wei, Zhejiang University
Ruijing Yu, Zhejiang University
Chaochao Chen, Zhejiang University
Wenjing Fang, Ant Group
Lei Wang, Ant Group
Zeke Wang, Zhejiang University
Wenzhi Chen, Zhejiang University

Zero-knowledge proof is a critical cryptographic primitive. Its most practical type, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK), has been deployed in various privacy-preserving applications such as cryptocurrencies and verifiable machine learning. Unfortunately, zkSNARK like Groth16 has a high overhead on its proof generation step, which consists of several time-consuming operations, including large-scale matrix-vector multiplication (MUL), number-theoretic transform (NTT), and multi-scalar multiplication (MSM). Therefore, this paper presents cuZK, an efficient GPU implementation of zkSNARK with the following three techniques to achieve high performance. First, we propose a new parallel MSM algorithm. This MSM algorithm achieves nearly perfect linear speedup over the Pippenger algorithm, a well-known serial MSM algorithm. Second, we parallelize the MUL operation. Along with our self-designed MSM scheme and well-studied NTT scheme, cuZK achieves the parallelization of all operations in the proof generation step. Third, cuZK reduces the latency overhead caused by CPU-GPU data transfer by 1) reducing redundant data transfer and 2) overlapping data transfer and device computation. The evaluation results show that our MSM module provides over 2.08× (up to 2.94×) speedup versus the state-of-the-art GPU implementation. cuZK achieves over 2.65× (up to 4.86×) speedup on standard benchmarks and 2.18× speedup on a GPU-accelerated cryptocurrency application, Filecoin.

Available format(s)
Publication info
Published by the IACR in TCHES 2023
Zero-knowledge proofparallel algorithmmulti-scalar multiplicationzkSNARKGPU
Contact author(s)
lutao2020 @ zju edu cn
weichengkun @ zju edu cn
rjyu @ zju edu cn
zjuccc @ zju edu cn
bean fwj @ antgroup com
shensi wl @ antgroup com
wangzeke @ zju edu cn
chenwz @ zju edu cn
2023-04-15: last of 4 revisions
2022-10-05: received
See all versions
Short URL
Creative Commons Attribution-ShareAlike


      author = {Tao Lu and Chengkun Wei and Ruijing Yu and Chaochao Chen and Wenjing Fang and Lei Wang and Zeke Wang and Wenzhi Chen},
      title = {cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1321},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.