摘要
针对zk-SNARK(zero-knowledge succinct non-interactive argument of knowledge)中计算最为耗时的多标量乘法(multiscalar multiplication,MSM),提出了一种基于GPU的MSM并行计算方案。首先,对MSM进行细粒度任务分解,提升算法本身的计算并行性,以充分利用GPU的大规模并行计算能力。采用共享内存对同一窗口下的子MSM并行规约减少了数据传输开销。其次,提出了一种基于底层计算模块线程级任务负载搜索最佳标量窗口的窗口划分方法,以最小化MSM子任务的计算开销。最后,对标量形式转换所用数据存储结构进行优化,并通过数据重叠传输和通信时间隐藏,解决了大规模标量形式转换过程的时延问题。该MSM并行计算方法基于CUDA在NVIDIA GPU上进行了实现,并构建了完整的零知识证明异构计算系统。实验结果表明:所提出的方法相比目前业界最优的cuZK的MSM计算模块获得了1.38倍的加速比。基于所改进MSM的整体系统比业界流行的Bellman提升了186倍,同时比业界最优的异构版本Bellperson提升了1.96倍,验证了方法的有效性。
In the context of zk-SNARK,MSM emerges as the predominant computational bottleneck.To address this problem,this paper proposed a GPU-based parallel MSM computation approach.Firstly,the method performed fine-grained task decomposition of MSM to enhance algorithmic computational parallelism,fully leveraging the extensive parallel computing capabilities of GPU.Additionally,it reduced data transfer overhead by employing shared memory for the parallel reduction of sub-MSM tasks within the same window.Secondly,the method introduced a window partitioning strategy based on thread-level task load analysis of the underlying computational modules to search for the optimal scalar window,thereby minimizing the computational cost of MSM subtasks.Lastly,the method optimized the data storage structure used for scalar form transformation and mitigated latency issues in the large-scale scalar form conversion process by employing data overlap transfer and hidden communication time.This paper implemented the MSM parallel computation method based on CUDA on NVIDIA GPU and established a comprehensive zeroknowledge proof heterogeneous computing system.Experimental results show that the proposed method achieves an acceleration ratio of 1.38 times compared to the current state-of-the-art MSM calculation module of cuZK.The overall system based on the improved MSM is 186 times better than the industry-popular Bellman,and 1.96 times better than cutting edge heterogeneous version Bellperson,validating the effectiveness of the approach.
作者
王锋
柴志雷
花鹏程
丁冬
王宁
Wang Feng;Chai Zhilei;Hua Pengcheng;Ding Dong;Wang Ning(School of Artificial Intelligence&Computer Science,Jiangnan University,Wuxi Jiangsu 214122,China;School of Internet of Things Engineering,Jiangnan University,Wuxi Jiangsu 214122,China;Jiangsu Provincial Engineering Laboratory of Pattern Recognition&Computational Intelligence,Wuxi Jiangsu 214122,China)
出处
《计算机应用研究》
CSCD
北大核心
2024年第6期1735-1742,共8页
Application Research of Computers
基金
国家自然科学基金资助项目(61972180)
江苏省模式识别与计算智能工程实验室项目。
