Paper 2024/1246
MSMAC: Accelerating Multi-Scalar Multiplication for Zero-Knowledge Proof
Abstract
Multi-scalar multiplication (MSM) is the most computation-intensive part in proof generation of Zero-knowledge proof (ZKP). In this paper, we propose MSMAC, an FPGA accelerator for large-scale MSM. MSMAC adopts a specially designed Instruction Set Architecture (ISA) for MSM and optimizes pipelined Point Addition Unit (PAU) with hybrid Karatsuba multiplier. Moreover, a runtime system is proposed to split MSM tasks with the optimal sub-task size and orchestrate execution of Processing Elements (PEs). Experimental results show that MSMAC achieves up to 328× and 1.96× speedups compared to the state-of-the-art implementation on CPU (one core) and GPU, respectively, outperforming the state-of-the-art ASIC accelerator by 1.79×. On 4 FPGAs, MSMAC performs 1,261× faster than a single CPU core.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. DAC2024
- Keywords
- Zero-Knowledge ProofMulti-Scalar Multiplication (MSM)FPGA
- Contact author(s)
- guiming wgm @ antgroup com
- History
- 2024-08-07: approved
- 2024-08-06: received
- See all versions
- Short URL
- https://ia.cr/2024/1246
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1246,
author = {Pengcheng Qiu and Guiming Wu and Tingqiang Chu and Changzheng Wei and Runzhou Luo and Ying Yan and Wei Wang and Hui Zhang},
title = {{MSMAC}: Accelerating Multi-Scalar Multiplication for Zero-Knowledge Proof},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1246},
year = {2024},
url = {https://eprint.iacr.org/2024/1246}
}
