PreNTT:面向zk-SNARK的数论变换计算并行加速方法OA北大核心CSTPCD

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.