Paper 2022/1321
cuZK: Accelerating Zero-Knowledge Proof with A Faster Parallel Multi-Scalar Multiplication Algorithm on GPUs
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published by the IACR in TCHES 2023
- Keywords
- 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 - History
- 2023-04-15: last of 4 revisions
- 2022-10-05: received
- See all versions
- Short URL
- https://ia.cr/2022/1321
- License
-
CC BY-SA
BibTeX
@misc{cryptoeprint:2022/1321,
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},
url = {https://eprint.iacr.org/2022/1321}
}