计算机应用研究2024，Vol.41Issue(10)：3059-3067,9.DOI:10.19734/j.issn.1001-3695.2024.03.0054
PreNTT:面向zk-SNARK的数论变换计算并行加速方法
PreNTT:parallel acceleration method for number theory transformation calculations for zk-SNARK
摘要
Abstract
Zero-knowledge succinct non-interactive proofs(zk-SNARK)have found extensive applications in various fields,in-cluding cryptocurrencies,due to their swift and efficient proof verification process.However,the computational intensity of the proof generation process poses a significant challenge,particularly at the number theoretic transform(NTT)stage.This paper proposed a GPU-based acceleration method for NTT computations,named PreNTT,to address this bottleneck.The method em-ployed precomputation and optimization of twiddle factor powers to reduce the parallel computation overhead in NTT.It also in-troduced dynamic precomputation to enhance the efficiency of these computations.The algorithm made use of dynamic adaptive kernel scheduling,which allocated GPU resources on-chip according to the NTT input size,thereby boosting the computational efficiency for large-scale tasks.Additionally,the approach combined external global data shuffling with internal local data shuff-ling to avoid memory access conflicts.The use of CUDA multi-stream technology allowed for effective concealment of precompu-tation times during data transfer and computation processes.Experimental results indicate that the zk-SNARK system utilizing PreNTT achieves a speed-up ratio ranging from 1.7x to 9x in NTT module running times compared to Bellperson,the industry-leading system.PreNTT effectively increases the parallelism of the NTT algorithm and reduces the computational overhead in zk-SNARK operations.关键词
简洁非交互式零知识证明/数论变换/GPU/并行计算/加速Key words
zero-knowledge succinct non-interactive argument of knowledge/number theoretic transformation/GPU/paral-lel computing/acceleration分类
信息技术与安全科学引用本文复制引用
丁冬,李正权,柴志雷..PreNTT:面向zk-SNARK的数论变换计算并行加速方法[J].计算机应用研究,2024,41(10):3059-3067,9.基金项目
国家自然科学基金资助项目(61972180) （61972180）
北京邮电大学网络与交换技术全国重点实验室开放课题资助项目(SKLNST-2023-1-13) （SKLNST-2023-1-13）
