PreNTT：面向zk-SNARK的數(shù)論變換計(jì)算并行加速方法

摘 要：簡(jiǎn)潔非交互式零知識(shí)證明（zk-SNARK）由于具備證明驗(yàn)證過(guò)程簡(jiǎn)捷快速的優(yōu)點(diǎn)，已在加密貨幣等眾多領(lǐng)域得到廣泛應(yīng)用。但其證明生成過(guò)程所需計(jì)算仍復(fù)雜耗時(shí)，影響了進(jìn)一步的應(yīng)用拓展。針對(duì)zk-SNARK證明生成過(guò)程中的主要計(jì)算瓶頸——數(shù)論變換（NTT），提出了一種基于GPU的NTT計(jì)算加速方法PreNTT。首先，提出了基于預(yù)計(jì)算的NTT并行計(jì)算方法，利用預(yù)計(jì)算與旋轉(zhuǎn)因子次冪算法優(yōu)化，減少NTT并行計(jì)算開(kāi)銷(xiāo)，并結(jié)合動(dòng)態(tài)預(yù)計(jì)算，進(jìn)一步提高NTT計(jì)算效率。其次，通過(guò)“動(dòng)態(tài)自適應(yīng)計(jì)算核調(diào)度”，可以根據(jù)NTT輸入規(guī)模自適應(yīng)地分配GPU片上資源，提升了大規(guī)模NTT任務(wù)的計(jì)算能效。然后，通過(guò)核外整體數(shù)據(jù)混洗和核內(nèi)局部數(shù)據(jù)混洗相結(jié)合的方式，避免了訪存沖突。最后，使用CUDA多流技術(shù)執(zhí)行數(shù)據(jù)傳輸和計(jì)算過(guò)程，對(duì)預(yù)計(jì)算時(shí)間進(jìn)行了有效隱藏。實(shí)驗(yàn)結(jié)果表明：基于PreNTT實(shí)現(xiàn)的zk-SNARK系統(tǒng)，與目前業(yè)界最先進(jìn)的系統(tǒng)Bellperson相比，NTT模塊運(yùn)行時(shí)間獲得了全規(guī)模最低1.7倍的加速比，最高加速比為9倍。PreNTT能夠有效提高NTT算法并行度，降低zk-SNARK運(yùn)算時(shí)間開(kāi)銷(xiāo)。

關(guān)鍵詞：簡(jiǎn)潔非交互式零知識(shí)證明；數(shù)論變換；GPU；并行計(jì)算；加速

中圖分類(lèi)號(hào)：TP311;TP309.7 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1001-3695（2024）10-025-3059-09

doi：10.19734/j.issn.1001-3695.2024.03.0054

PreNTT：parallel acceleration method for number theory transformation calculations for zk-SNARK

Ding Dong1a，Li Zhengquan1a，2，Chai Zhilei1b

（1.a.School of Internet of Things Engineering，b.School of Artificial Intelligence & Computer Science，Jiangnan University，Wuxi Jiangsu 214122，China;2.State Key Laboratory of Networking & Switching Technology，Beijing University of Posts & Telecommunications，Beijing 100876，China）

Abstract：Zero-knowledge succinct non-interactive proofs（zk-SNARK）have found extensive applications in various fields，including 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 employed precomputation and optimization of twiddle factor powers to reduce the parallel computation overhead in NTT.It also introduced 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 shuffling to avoid memory access conflicts.The use of CUDA multi-stream technology allowed for effective concealment of precomputation 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.

Key words：zero-knowledge succinct non-interactive argument of knowledge;number theoretic transformation;GPU;parallel computing;acceleration

0 引言

簡(jiǎn)潔非交互式零知識(shí)證明（zero-knowledge succinct non-interactive argument of knowledge，zk-SNARK）是由Micali等人提出的加密協(xié)議［1］，它使得一方（證明者）能夠向另一方（驗(yàn)證者）證實(shí)某個(gè)陳述的真實(shí)性，而無(wú)須透露任何額外信息。作為零知識(shí)證明協(xié)議（zero-knowledge proofs，ZKP）的一個(gè)先進(jìn)變體，zk-SNARK生成的證明極其簡(jiǎn)短，通常只有幾百字節(jié)，僅需毫秒級(jí)驗(yàn)證時(shí)間。鑒于其卓越的效率和隱私保護(hù)特性，zk-SNARK已被廣泛應(yīng)用于多種場(chǎng)景，包括加密貨幣［2～4］、電子投票系統(tǒng)［5］、可驗(yàn)證的數(shù)據(jù)庫(kù)外包服務(wù)［6］、可驗(yàn)證的機(jī)器學(xué)習(xí)過(guò)程［7，8］、公鑰加密方案［9］以及匿名認(rèn)證系統(tǒng)［10］等。近些年，基于zk-SNARK的實(shí)現(xiàn)方案不斷涌現(xiàn)［11～14］，其中Groth16方案［14］因其卓越的效率而備受推崇。

盡管zk-SNARK的驗(yàn)證時(shí)間短，但其證明構(gòu)建階段計(jì)算復(fù)雜度極高，且實(shí)際應(yīng)用往往需要頻繁構(gòu)建證明，產(chǎn)生高昂的時(shí)間成本。隨著數(shù)據(jù)規(guī)模和安全性需求的日益增長(zhǎng)，實(shí)際應(yīng)用中越發(fā)難以承受持續(xù)膨脹的計(jì)算開(kāi)銷(xiāo)。因此，計(jì)算效率已經(jīng)成為zk-SNARK實(shí)現(xiàn)中重要的性能指標(biāo)。尤其在證明創(chuàng)建過(guò)程中，橢圓曲線配對(duì)涉及到的數(shù)論變換（number theoretic transformation，NTT）及其逆變換（inverse number theoretic transformation，INTT）在多項(xiàng)式模乘操作中占據(jù)了大量證明時(shí)間［15］。此外，在全同態(tài)加密［16～18］和后量子密碼學(xué)［19］等領(lǐng)域，也存在著諸多對(duì)數(shù)論變換的使用需求。研究者們提出多種硬件架構(gòu)的NTT加速方案，包括CPU、FPGA［20］以及GPU。其中GPU由于其編程靈活度高和高指令吞吐量的特點(diǎn)受到更多關(guān)注及應(yīng)用。

Kim等人［21］對(duì)NTT與離散傅里葉變換（DFT）的算法特點(diǎn)進(jìn)行了對(duì)比分析，提出了一種NTT特有動(dòng)態(tài)根生成方法，利用動(dòng)態(tài)旋轉(zhuǎn)（OT）技術(shù)計(jì)算部分旋轉(zhuǎn)因子，降低模乘成本。但這種優(yōu)化僅限于NTT的后階段，對(duì)全局計(jì)算開(kāi)銷(xiāo)的影響有限。當(dāng)NTT的計(jì)算規(guī)模較小時(shí)，進(jìn)行的模乘運(yùn)算數(shù)量有限，這使得OT技術(shù)在小規(guī)模NTT計(jì)算中的優(yōu)化效果并不顯著。Naina等人［22］提出對(duì)后量子典型算法FrodoKEM、NewHope和Kyber的GPU加速方案，其中對(duì)NTT進(jìn)行了高效實(shí)現(xiàn)。在NTT計(jì)算過(guò)程中，將中間值存儲(chǔ)于GPU片上共享內(nèi)存，減少對(duì)全局存儲(chǔ)器的讀寫(xiě)操作。然而，zk-SNARK的高安全性需求使得蝶形運(yùn)算規(guī)模顯著增加，超出GPU共享內(nèi)存的容量限制。因此，該方法僅在小規(guī)模應(yīng)用中表現(xiàn)優(yōu)異，面對(duì)zk-SNARK中大規(guī)模NTT計(jì)算時(shí)的優(yōu)化效果不佳。文獻(xiàn)［22］提出了進(jìn)一步加速GPU上NTT內(nèi)核的方法，使用CIOS形式的蒙哥馬利乘法，并采用分段乘法和PTX指令集來(lái)提升循環(huán)處理的效率，對(duì)NTT/INTT操作進(jìn)行了數(shù)據(jù)布局和亂序處理的優(yōu)化。然而，該方法主要專(zhuān)注于內(nèi)核級(jí)別的細(xì)粒度優(yōu)化，忽略了內(nèi)核調(diào)度與任務(wù)分配的重要性。這種偏重導(dǎo)致當(dāng)數(shù)據(jù)規(guī)模變化時(shí)，運(yùn)算性能表現(xiàn)出明顯的不穩(wěn)定性。因此，該方法在應(yīng)對(duì)多尺度計(jì)算負(fù)載時(shí)難以實(shí)現(xiàn)穩(wěn)定的加速效果。

鑒于NTT計(jì)算中內(nèi)存訪問(wèn)的高敏感性及其高計(jì)算復(fù)雜度，目前的研究領(lǐng)域還未提供一個(gè)針對(duì)各種規(guī)模計(jì)算負(fù)載的有效的加速策略。因此，本研究借助CPU-GPU異構(gòu)計(jì)算平臺(tái)，針對(duì)zk-SNARK中的NTT，提出一種適應(yīng)各種規(guī)模任務(wù)的高效NTT并行加速方案。本文的主要貢獻(xiàn)包括：

a）提出并行加速方法PreNTT。NTT計(jì)算中，將需重復(fù)計(jì)算且計(jì)算復(fù)雜度高的旋轉(zhuǎn)因子部分預(yù)先計(jì)算，并使用快速冪算法，有效降低NTT任務(wù)中的計(jì)算開(kāi)銷(xiāo)以及訪存開(kāi)銷(xiāo)，并根據(jù)輸入規(guī)模動(dòng)態(tài)調(diào)整預(yù)計(jì)算內(nèi)容。

b）在GPU中實(shí)現(xiàn)PreNTT，并在其基礎(chǔ)上實(shí)現(xiàn)“動(dòng)態(tài)自適應(yīng)計(jì)算核”?；谳斎胍?guī)模可適應(yīng)性分配GPU每個(gè)線程塊及其內(nèi)部線程的任務(wù)，以此保證GPU計(jì)算時(shí)各線程的負(fù)載平衡性，實(shí)現(xiàn)對(duì)NTT任務(wù)的全規(guī)模加速。

c）提出一種整體+局部的數(shù)據(jù)混洗策略，主計(jì)算核整體與核內(nèi)線程塊分別進(jìn)行數(shù)據(jù)洗牌，減少計(jì)算過(guò)程中的數(shù)據(jù)訪存沖突，保證數(shù)據(jù)正確性。利用CUDA流重疊技術(shù)掩蓋預(yù)計(jì)算核執(zhí)行時(shí)間，提高整體運(yùn)算效率。

此外，在CPU-GPU異構(gòu)系統(tǒng)上實(shí)現(xiàn)了上述并行計(jì)算方案，并構(gòu)建了完整的zk-SNARK系統(tǒng)。與目前業(yè)界最優(yōu)的基于GPU的zk-SNARK實(shí)現(xiàn)Bellperson［23］相比，本文NTT模塊獲得全規(guī)模最低1.7倍的加速比，最高加速比為9倍。

1 預(yù)備知識(shí)

1.1 零知識(shí)證明

相較于其他零知識(shí)證明協(xié)議［24，25］，zk-SNARK擁有簡(jiǎn)潔性和非交互性兩個(gè)優(yōu)勢(shì)。簡(jiǎn)潔性是指zk-SNARK生成的證明非常簡(jiǎn)短，即使面對(duì)復(fù)雜的語(yǔ)句也能夠快速驗(yàn)證。zk-SNARK能夠?yàn)槿魏慰赊D(zhuǎn)換為算術(shù)電路的語(yǔ)句提供證明，算術(shù)電路指一組可以在私密信息上求值的方程。簡(jiǎn)潔性的實(shí)現(xiàn)依賴于使用R1CS（rank-1 constraint system），zk-SNARK通過(guò)將計(jì)算問(wèn)題轉(zhuǎn)換為約束系統(tǒng)，包含輸入變量、中間變量和輸出變量之間的關(guān)系約束，將復(fù)雜問(wèn)題描述為數(shù)學(xué)運(yùn)算電路，生成的證明僅需驗(yàn)證約束關(guān)系的解存在即可，無(wú)須包含解的詳細(xì)值，顯著縮短了證明的尺寸。

傳統(tǒng)零知識(shí)證明協(xié)議要求驗(yàn)證者和證明者同時(shí)在線，多輪交互通信增加了大量通信開(kāi)銷(xiāo)，大大降低了協(xié)議的運(yùn)行效率。zk-SNARK為實(shí)現(xiàn)非交互式證明，由可信三方預(yù)先設(shè)置一系列與特定約束系統(tǒng)緊密相關(guān)的公共參數(shù)及驗(yàn)證密鑰和證明密鑰。證明者根據(jù)公共參數(shù)和私有輸入生成證明，驗(yàn)證者則通過(guò)公共參數(shù)和驗(yàn)證密鑰獨(dú)立驗(yàn)證證明，無(wú)須與證明者交互。

如圖1所示，zk-SNARK協(xié)議主要分為三個(gè)主要步驟：

a）Setup（初始化）：此階段中生成者（prover）會(huì)執(zhí)行一些預(yù)處理操作來(lái)設(shè)置證明系統(tǒng)，包括選定安全參數(shù)、生成公共參數(shù)，并根據(jù)算術(shù)電路構(gòu)建R1CS。

b）Prove（證明）：證明者根據(jù)輸入和電路的描述生成證明，表明輸入滿足電路的規(guī)則，并將證明發(fā)送給驗(yàn)證方。

c）Verify（驗(yàn)證）：驗(yàn)證者（verifier）使用公共參數(shù)、電路描述和證明來(lái)驗(yàn)證生成者的聲明。驗(yàn)證者僅需執(zhí)行少量計(jì)算即可驗(yàn)證證明的真?zhèn)巍?/p>

Setup階段主要進(jìn)行參數(shù)設(shè)置，包括公共參數(shù)和輔助參數(shù)。公共參數(shù)的生成通常在可信任的設(shè)置階段進(jìn)行，涉及生成者的驗(yàn)證密鑰和承諾密鑰等關(guān)鍵參數(shù)。輔助參數(shù)的生成則可在更高層次的設(shè)置過(guò)程中進(jìn)行，包括描述約束系統(tǒng)（R1CS）和約束多項(xiàng)式的系數(shù)等。Setup階段通常具有較高的計(jì)算復(fù)雜度，但在證明系統(tǒng)中僅需執(zhí)行一次即可為多個(gè)證明提供參數(shù)。在prove階段，證明者使用私有輸入和公共參數(shù)來(lái)生成證明。具體步驟包括將輸入映射到約束系統(tǒng)的賦值，使用快速多項(xiàng)式求值方法（如NTT）計(jì)算約束多項(xiàng)式的點(diǎn)值形式，并構(gòu)建證明多項(xiàng)式。證明多項(xiàng)式是一個(gè)用于隱藏生成者的私有輸入的多項(xiàng)式。生成證明過(guò)程需要進(jìn)行大量的多項(xiàng)式求值操作。這些操作涉及將多項(xiàng)式從系數(shù)形式轉(zhuǎn)換為點(diǎn)值形式，并執(zhí)行多項(xiàng)式乘法和加法。Verify階段使用時(shí)間較短，計(jì)算難度較低，本文不再進(jìn)行贅述。

1.2 數(shù)論變換（NTT/INTT）

NTT是一種基于數(shù)論的快速傅里葉變換（fast Fourier transform）算法，用于高效完成有限域上的多項(xiàng)式乘法。NTT是在模數(shù)為素?cái)?shù)p的有限域上進(jìn)行的變換，其中p通常為2的冪加1，即p=2k+1，k為整數(shù)。NTT利用模運(yùn)算的性質(zhì)和數(shù)論中的同余關(guān)系，將多項(xiàng)式乘法轉(zhuǎn)換為在有限域上的點(diǎn)值乘法，從而降低乘法運(yùn)算的復(fù)雜度，式（1）為NTT計(jì)算公式。

A=NTT（a）=∑n-1j=0;i=0ajωij（mod p）（1）

其中：a代表輸入數(shù)據(jù)，一共有n個(gè)輸入，ω代表旋轉(zhuǎn)因子，每個(gè)輸入與不同的旋轉(zhuǎn)因子進(jìn)行乘法運(yùn)算，并且需要對(duì)每個(gè)計(jì)算結(jié)果進(jìn)行累加才可以得到最終結(jié)果。圖2展示了規(guī)模為8的NTT計(jì)算過(guò)程。

如算法1所示為目前最流行的NTT迭代算法，其中Fp指有限域。其中以基2蝶形運(yùn)算為循環(huán)底層，通過(guò)三層循環(huán)實(shí)現(xiàn)迭代算法。

算法1 NTT迭代算法

輸入：A=（a0，a1，…，an-1）∈Fp；ωn∈Fp。

輸出：Y=（y0，y1，…，yn-1）∈Fp。

1Set Y=A

2for i=1 to log2n do //代表蝶形運(yùn)算輪次

3 ωi=ω（p-1）/2in mod p//旋轉(zhuǎn)因子運(yùn)算

4 for k=0 to n-1 by 2i do

5 ω=1 mod p

6 for j=0 to 2i-1 do//結(jié)合步驟4代表輪內(nèi)數(shù)據(jù)運(yùn)算

7 t=ωyk+j+2i-1 mod p

8 u=yk+j

9 yk+j=（u+t）mod p

10 yk+j+2i-1=（u-1+p） mod p

11 ω=ωωi mod p

12 end for

13 end for

14end for

15return Y

NTT的逆運(yùn)算只需要將ω替換為逆元，其他的計(jì)算順序和蝶形運(yùn)算方式不變。完成NTT和INTT后，結(jié)果被放大n倍，故需要對(duì)INTT的輸出序列乘以n的逆元進(jìn)行歸一化處理才能獲取最終結(jié)果。

在zk-SNARK最先進(jìn)的部署B(yǎng)ellperson［23］中，NTT應(yīng)用主要在兩個(gè)部分，如圖3所示，首先在setup階段使用INTT實(shí)現(xiàn)拉格朗日插值法。特定的約束系統(tǒng)（R1CS）的約束信息一般以一組已知的點(diǎn)的形式給出，使用拉格朗日插值法可將約束信息的點(diǎn)值表示轉(zhuǎn)換為多項(xiàng)式表示。其次在prover階段使用NTT和INTT組合實(shí)現(xiàn)多項(xiàng)式運(yùn)算。將兩個(gè)多項(xiàng)式從系數(shù)表示轉(zhuǎn)換為點(diǎn)表示再進(jìn)行運(yùn)算操作，可以將計(jì)算時(shí)間復(fù)雜度從O（n）降低至O（nlog2n）。圖4為Bellperson中不同規(guī)模NTT的運(yùn)算時(shí)間。

1.3 現(xiàn)有NTT并行算法

在zk-SNARK實(shí)際部署中，NTT的輸入規(guī)模較大（超過(guò)210），根據(jù)式（1），NTT運(yùn)算需要多次蝶形運(yùn)算，如果直接對(duì)NTT任務(wù)進(jìn)行遞歸處理，需要訪問(wèn)和存儲(chǔ)大量數(shù)據(jù)，會(huì)導(dǎo)致訪存沖突和內(nèi)存過(guò)載，造成片上資源損耗以及計(jì)算效率的降低。因此，需要對(duì)NTT算法進(jìn)行改良以適配高效率并行計(jì)算需求。Bellperson是當(dāng)今最流行的zk-SNARK庫(kù)，基于Rust語(yǔ)言實(shí)現(xiàn)，其使用NTT并行算法將NTT任務(wù)分解。

將n個(gè)a分為n2×n1的矩陣形式，由式（1）則可推出如下公式：

A［i1+i2n1］=∑n2-1j2=0［（∑n1-1j1=0a［j1n2+j2］ωj1i1n1）ωj2i1n］ωj2i2n2（2）

其中：i1∈［0，n1）;i2∈［0，n2）。

由式（2）可知，原n規(guī)模的NTT計(jì)算任務(wù)被分解為三個(gè)部分，第一部分為式（3），第二部分為旋轉(zhuǎn)因子運(yùn)算，第三部分為式（4）。

∑n1-1j1=0a［j1n2+j2］ωj1i1n1（3）

∑n2-1j2=0a［j1n2+j2］ωj2i2n2（4）

第一部分，將輸入矩陣按列展開(kāi)，共有n2列規(guī)模為n1的NTT，這n2個(gè)子NTT任務(wù)可并行完成。其中n1是n縮小n2倍，n1的大小可根據(jù)計(jì)算設(shè)備的硬件性能自定義。第二部分，當(dāng)完成n2個(gè)規(guī)模為n1的子NTT后，需要將每個(gè)輸出結(jié)果分別與ωj2i1n相乘，這些旋轉(zhuǎn)因子的計(jì)算開(kāi)銷(xiāo)巨大。最后，根據(jù)式（4），對(duì)處理過(guò)的數(shù)據(jù)進(jìn)行轉(zhuǎn)置操作，仍按列展開(kāi)，每一列為n2規(guī)模的NTT，共有n1列數(shù)據(jù)，對(duì)這n1列并行計(jì)算即可完成完整規(guī)模的NTT計(jì)算任務(wù)。其具體實(shí)現(xiàn)如算法2所示，其中按行按列展開(kāi)的部分，分配至多線程并行執(zhí)行。線程內(nèi)部仍然以基2蝶形運(yùn)算作為底層操作。

算法2 NTT并行算法

輸入：A=a0，a1，…，an2-1an2，an2+1，…，a2n2-1∈Fp，ωn∈Fp。

輸出：Y=（y0，y1，…，yn-1）∈Fp。

1Set Y=A

2compute ω（n2*q）n q∈［0，n1）

3 step 1 for i=0 to （n1-1）/2 do //分塊并行執(zhí)行

4 for k=0 to log2n1 do //區(qū)分不同輪次，塊內(nèi)并行

5 bit=n1/2k

6 for j=0 to （n1-1）/2 do //結(jié)合步驟4進(jìn)行基2蝶形運(yùn)算

7 d=j&（bit-1）

8 u=y2j-d

9 t=yu+bit

10 y2j-d=（u+t） mod p

11 yu+bit=（u-t）×ωn2dkn mod p //10，11為基2蝶形運(yùn)算

12 end for //塊內(nèi)并行結(jié)束，需要塊內(nèi)同步數(shù)據(jù)

13 end for

14end for

15compute ωj2i1n j2∈［0，n2） i1∈［0，n1）

16y=y×ωj2i1n mod p

17transpose Y

18repeat step 1 exchange n2 and n1

19return Y

2 本文方法PreNTT

現(xiàn)有的NTT并行算法通過(guò)將n規(guī)模的任務(wù)分解為多輪較小規(guī)模的NTT。其核心思想是通過(guò)增加計(jì)算任務(wù)的數(shù)量，從而優(yōu)化單一計(jì)算任務(wù)中的計(jì)算負(fù)載和復(fù)雜的內(nèi)存訪問(wèn)模式。這種方式能夠提升每個(gè)計(jì)算任務(wù)的執(zhí)行效率，并加速整體運(yùn)算過(guò)程。

在實(shí)際運(yùn)用中，該算法將n規(guī)模輸入分解為方陣時(shí)（即設(shè)定n2=n1）達(dá)到最佳性能，此時(shí)并行設(shè)備只需實(shí)例化一份計(jì)算核，且無(wú)須進(jìn)行額外的旋轉(zhuǎn)因子計(jì)算。然而，由于現(xiàn)有算法的分解矩陣A的列數(shù)是固定的，恰好分解為方陣的情況較為少見(jiàn)。

當(dāng)算法達(dá)到最佳性能時(shí)，n2=n1=n，以此評(píng)估此算法的最小計(jì)算成本。首先需要明確的是NTT計(jì)算中，計(jì)算成本最高的是蒙哥馬利模乘［26］，它的代價(jià)遠(yuǎn)超其他在NTT中的常規(guī)運(yùn)算。因此，本文將蒙哥馬利模乘的次數(shù)作為衡量NTT計(jì)算成本的指標(biāo)。該算法首先將任務(wù)分為n1個(gè)子任務(wù)并行處理，每個(gè)子任務(wù)進(jìn)一步分為n1/2個(gè)子任務(wù)進(jìn)行蝶形運(yùn)算，第二層子任務(wù)蒙哥馬利乘法的次數(shù)為T(mén)1=log2n1；第二部分計(jì)算旋轉(zhuǎn)因子，以最大值ω（n2-1）（n1-1）n計(jì)算，此次冪運(yùn)算涉及的模乘次數(shù)為T(mén)2=4×log2n1；由于設(shè)定n2=n1，第三部分計(jì)算成本與第一部分相同，即T3=log2n1。因此總的模乘次數(shù)大致為T(mén)=6×log2n1，第二部分旋轉(zhuǎn)因子計(jì)算占據(jù)總計(jì)算成本的2/3。圖5展示了為旋轉(zhuǎn)因子計(jì)算時(shí)間與NTT整體運(yùn)行時(shí)間的對(duì)比，顯而易見(jiàn)，旋轉(zhuǎn)因子計(jì)算的開(kāi)銷(xiāo)在總體成本中占據(jù)了較大比重。業(yè)內(nèi)許多研究［21，22，27］聚焦于訪存優(yōu)化，缺少有效的旋轉(zhuǎn)因子運(yùn)算策略。此外，在zk-SNARK的證明生成過(guò)程中，需要執(zhí)行7次NTT/INTT，相應(yīng)的需要7次旋轉(zhuǎn)因子的計(jì)算。值得注意的是，在生成單次證明的過(guò)程中，NTT的輸入規(guī)模及NTT和INTT的原根均保持不變，這意味著每一次NTT/INTT操作中所需的旋轉(zhuǎn)因子也是相同的。因此，如果能夠在計(jì)算過(guò)程開(kāi)始之前預(yù)先計(jì)算這些旋轉(zhuǎn)因子，并在后續(xù)的每次NTT/INTT操作中重復(fù)利用這些預(yù)計(jì)算結(jié)果，就可以顯著減少不必要的計(jì)算開(kāi)銷(xiāo)。

基于此本文提出了一種基于預(yù)計(jì)算的NTT并行計(jì)算方法，即PreNTT。PreNTT利用二進(jìn)制快速冪算法預(yù)計(jì)算NTT中所需的旋轉(zhuǎn)因子，根據(jù)輸入規(guī)模適配不同的分解策略，以保證最佳計(jì)算性能。PreNTT只需進(jìn)行兩次旋轉(zhuǎn)因子的預(yù)計(jì)算便可得到zk-SNARK的證明生成過(guò)程中全部NTT計(jì)算所需的旋轉(zhuǎn)因子。

在計(jì)算旋轉(zhuǎn)因子ωj2i1n時(shí)，與算法2將ωi1n和ωj2n分開(kāi)計(jì)算后再相乘的計(jì)算方式不同，PreNTT采用二進(jìn)制快速冪算法優(yōu)化旋轉(zhuǎn)因子計(jì)算。如圖6所示，根據(jù)j2×i1的二進(jìn)制值，提取出值為1的位，乘以對(duì)應(yīng)的ω2kn（k為位置坐標(biāo)）。

此方法所需的蒙哥馬利模乘次數(shù)為log2n，假設(shè)輸入規(guī)模為n2=n1=n，與NTT并行加速方法中旋轉(zhuǎn)因子冪運(yùn)算模乘次數(shù)4log2n1相比，PreNTT在旋轉(zhuǎn)因子計(jì)算上的模乘次數(shù)僅為T(mén)2=log2n=2log2n1，而總的模乘次數(shù)為4log2n1，與現(xiàn)有方法相比，PreNTT的模乘次數(shù)加速比為1.5倍。

除了計(jì)算成本的優(yōu)化，PreNTT還在任務(wù)分配和負(fù)載均衡方面進(jìn)行了改進(jìn)。從算法2的分析中，可以明確僅當(dāng)n2=n1=n時(shí)，NTT并行算法中所采納的分解策略達(dá)到最優(yōu)化。然而在實(shí)際應(yīng)用中，滿足此條件顯得較為嚴(yán)苛。為此，PreNTT設(shè)計(jì)了一種動(dòng)態(tài)預(yù)計(jì)算方法，根據(jù)輸入規(guī)模不同動(dòng)態(tài)規(guī)劃預(yù)計(jì)算內(nèi)容，確保NTT的核心計(jì)算部分始終運(yùn)行在最佳狀態(tài)。PreNTT對(duì)NTT任務(wù)進(jìn)行分解時(shí)，分解矩陣A的列數(shù)隨著輸入規(guī)模不同自適應(yīng)變化，即只要輸入規(guī)模n為2的偶次冪，即可將其分解為方陣以達(dá)到并行計(jì)算最佳性能。此時(shí)，PreNTT在預(yù)計(jì)算核中只需利用二進(jìn)制快速冪算法計(jì)算旋轉(zhuǎn)因子，主計(jì)算核中對(duì)其進(jìn)行索引訪問(wèn)即可。而當(dāng)輸入規(guī)模n為2的奇次冪時(shí)，為了將主計(jì)算核任務(wù)分解為方陣，PreNTT提出一種新的預(yù)計(jì)算策略。

如圖7所示，當(dāng)NTT任務(wù)無(wú)法分解為方陣時(shí)，利用GS蝶形運(yùn)算［29］，第一輪進(jìn)行固定步長(zhǎng)的蝶形計(jì)算操作使得NTT任務(wù)得以分解為兩個(gè)相互獨(dú)立且無(wú)數(shù)據(jù)依賴關(guān)系的子計(jì)算任務(wù)。

這些子計(jì)算任務(wù)可視為具有n/2規(guī)模的計(jì)算實(shí)例，按此邏輯繼續(xù)分解，直到子任務(wù)規(guī)模nsub=k（k為NTT主計(jì)算核規(guī)模），將前若干輪蝶形運(yùn)算與旋轉(zhuǎn)因子合并同時(shí)預(yù)計(jì)算。

當(dāng)前預(yù)計(jì)算階段所獲得的旋轉(zhuǎn)因子是不完備的，其原根最高次冪僅至n/2-1。鑒于此，PreNTT提出一種旋轉(zhuǎn)因子補(bǔ)全方法。這種方法利用預(yù)計(jì)算核中存儲(chǔ)的連續(xù)次冪的旋轉(zhuǎn)因子，即ωin，i∈［0，n/2）來(lái)生成主計(jì)算核所需的旋轉(zhuǎn)因子ωin/k，i∈［0，n/k），這里的k代表主計(jì)算核的數(shù)量。

ωin=ωi/kn/k i∈［0，n/2）（5）

根據(jù)式（5），將預(yù)計(jì)算所得的部分旋轉(zhuǎn)因子與ωn/2n相乘，即可生成缺失的旋轉(zhuǎn)因子。值得注意的是，在預(yù)計(jì)算核中得到的旋轉(zhuǎn)因子并非每一項(xiàng)都被主計(jì)算核所使用，而是按固定步長(zhǎng)偏移使用。因此，PreNTT將存儲(chǔ)的旋轉(zhuǎn)因子數(shù)量減少到原本數(shù)量的1/k，從而降低內(nèi)存占用。

實(shí)際部署中，分解策略實(shí)施后，最底層蝶形運(yùn)算的規(guī)模實(shí)際上減少了一半，較小的運(yùn)算規(guī)模意味著更少的訪存次數(shù)和較低的計(jì)算資源消耗，達(dá)到更高的計(jì)算效率。例如，在GPU中，這可以有效地避免Bank沖突；而在FPGA中，則有助于減少資源的占用，并提高其他計(jì)算任務(wù)的并行處理能力。

PreNTT設(shè)計(jì)一種自適應(yīng)的動(dòng)態(tài)預(yù)計(jì)算方法，其將NTT中開(kāi)銷(xiāo)占比較高，且破壞并行計(jì)算負(fù)載均衡的旋轉(zhuǎn)因子計(jì)算提前，使得后續(xù)任務(wù)更易遷移到并行設(shè)備。此外，PreNTT利用更先進(jìn)的旋轉(zhuǎn)因子算法，減少其計(jì)算復(fù)雜度，并根據(jù)輸入規(guī)模不同設(shè)計(jì)不同的任務(wù)分解策略，令主計(jì)算核的數(shù)據(jù)結(jié)構(gòu)始終保持方陣狀態(tài)，達(dá)到最佳計(jì)算性能。

3 基于GPU的PreNTT實(shí)現(xiàn)

3.1 動(dòng)態(tài)自適應(yīng)計(jì)算核的優(yōu)化實(shí)現(xiàn)

在zk-SNARK的計(jì)算中，NTT的輸入規(guī)?？偸?的整數(shù)次冪，記為2n。n的具體數(shù)值對(duì)于底層來(lái)說(shuō)無(wú)法預(yù)測(cè)，盡管先前的研究已經(jīng)取得了一定的進(jìn)展，但這些方法在處理不同規(guī)模輸入時(shí)的效率并不均衡。當(dāng)數(shù)據(jù)規(guī)模較小時(shí)，對(duì)計(jì)算核的細(xì)粒度優(yōu)化無(wú)法有效提高運(yùn)行速度；而面對(duì)大規(guī)模輸入時(shí)，現(xiàn)有算法往往無(wú)法充分利用GPU硬件資源，無(wú)法達(dá)到最佳性能。為了克服這一局限，本研究基于GPU實(shí)現(xiàn)PreNTT，進(jìn)一步提出“動(dòng)態(tài)自適應(yīng)計(jì)算核”。其自適應(yīng)調(diào)整計(jì)算核心，使之可以根據(jù)輸入規(guī)模的不同，靈活選擇最合適的計(jì)算方案。這種動(dòng)態(tài)優(yōu)化不僅能夠克服傳統(tǒng)方法在不同規(guī)模輸入下的性能波動(dòng)，還能夠在全規(guī)模范圍內(nèi)實(shí)現(xiàn)加速。通過(guò)這種方式，PreNTT的NTT優(yōu)化核不受輸入規(guī)模的限制，有效地彌補(bǔ)了現(xiàn)有研究的不足，為zk-SNARK的計(jì)算提供了更為高效和穩(wěn)定的解決方案。

根據(jù)PreNTT的設(shè)計(jì)，其計(jì)算核心會(huì)根據(jù)輸入規(guī)模動(dòng)態(tài)地進(jìn)行自適應(yīng)調(diào)整，采用兩種不同的計(jì)算方案。

當(dāng)n為偶數(shù)時(shí)，由于主計(jì)算核可直接將計(jì)算任務(wù)分解為方陣，PreNTT優(yōu)先處理計(jì)算密集型的旋轉(zhuǎn)因子部分，利用GPU的預(yù)計(jì)算核進(jìn)行計(jì)算并存儲(chǔ)。后續(xù)步驟中，主計(jì)算核僅需執(zhí)行NTT的蝶形運(yùn)算部分，而中間所需的旋轉(zhuǎn)因子可通過(guò)簡(jiǎn)單地訪問(wèn)存儲(chǔ)系統(tǒng)來(lái)獲取。

對(duì)于n為奇數(shù)的情況，問(wèn)題變得相對(duì)復(fù)雜。這意味著NTT任務(wù)無(wú)法將輸入數(shù)據(jù)整理為方陣，直接進(jìn)行分解將導(dǎo)致需要額外的計(jì)算用于蝶形運(yùn)算所需的旋轉(zhuǎn)因子，從而增加不必要的計(jì)算和內(nèi)存開(kāi)銷(xiāo)。因此，PreNTT采用先前描述的GS分解方法，將第一輪蝶形運(yùn)算與旋轉(zhuǎn)因子計(jì)算合并為一個(gè)預(yù)計(jì)算核心。經(jīng)過(guò)預(yù)計(jì)算的分解，主計(jì)算核的任務(wù)被進(jìn)一步細(xì)分為兩個(gè)子任務(wù)，這要求主計(jì)算核被連續(xù)調(diào)用兩次，每次所需處理的計(jì)算規(guī)模為原始任務(wù)的一半，此時(shí)的計(jì)算規(guī)模轉(zhuǎn)變?yōu)?的偶數(shù)次冪，從而可以整理為方陣形式。最后，主計(jì)算核心通過(guò)旋轉(zhuǎn)因子補(bǔ)全方法獲取所需的旋轉(zhuǎn)因子。圖8詳細(xì)展示了PreNTT在GPU上的計(jì)算任務(wù)分解流程。

值得注意的是，NTT的操作數(shù)都是位寬為256位的標(biāo)量，隨著NTT計(jì)算規(guī)模的擴(kuò)增，GPU的片上可用共享內(nèi)存往往不能滿足經(jīng)過(guò)兩次分解后的子任務(wù)的計(jì)算需求。以RTX3060為例，其片上共享內(nèi)存限制了線程塊內(nèi)NTT規(guī)模的上限，使其最大僅能達(dá)到210，因此，當(dāng)NTT的總計(jì)算規(guī)模增至222時(shí)，無(wú)法將NTT任務(wù)分解為二維矩陣進(jìn)行運(yùn)算。

當(dāng)NTT的總計(jì)算規(guī)模達(dá)到或超過(guò)222時(shí)，簡(jiǎn)單地對(duì)NTT進(jìn)行兩次分解已無(wú)法滿足性能優(yōu)化的預(yù)期。因此，在部署大規(guī)模（超過(guò)221）NTT任務(wù)至GPU時(shí)，本文將計(jì)算任務(wù)進(jìn)行三次分解，并專(zhuān)門(mén)關(guān)注了負(fù)載均衡的問(wèn)題。

設(shè)總NTT規(guī)模為2n（其中n≥21），線程塊內(nèi)計(jì)算規(guī)模nb應(yīng)滿足條件：3nb≥n，并取滿足此條件的最小值。在此基礎(chǔ)上，最后一次計(jì)算核的線程塊內(nèi)計(jì)算規(guī)模定義為n-2nb。這樣的設(shè)計(jì)將NTT計(jì)算任務(wù)分為三維矩陣，盡可能均衡分配每個(gè)維度的數(shù)據(jù)，確保主計(jì)算核中的三個(gè)計(jì)算任務(wù)具有近似的計(jì)算量，從而在預(yù)計(jì)算的旋轉(zhuǎn)因子支持下，實(shí)現(xiàn)最佳的性能表現(xiàn)。而在進(jìn)行三次分解時(shí)，由于此輸入規(guī)模較大，將蝶形運(yùn)算納入預(yù)計(jì)算核會(huì)引入大量的內(nèi)存開(kāi)銷(xiāo)，可能降低CPU與GPU之間的通信效率。因此，在處理大規(guī)模（超過(guò)221）NTT時(shí)統(tǒng)一使用偶數(shù)規(guī)模分解策略。如果采用片上內(nèi)存較大GPU或NTT實(shí)際計(jì)算規(guī)模較小，則無(wú)須考慮此情況。

在處理NTT任務(wù)時(shí)，GPU首先激活預(yù)計(jì)算核心，NTT任務(wù)被逐步分解，主計(jì)算核心隨后被調(diào)用以完成全部計(jì)算任務(wù)。如圖9所示，主計(jì)算核將規(guī)模為n的NTT分為n1×n2矩陣。主計(jì)算過(guò)程分為兩個(gè)獨(dú)立的計(jì)算核心，第一個(gè)計(jì)算核心劃分出n2個(gè)線程塊（block），每個(gè)線程塊被分配n1個(gè)數(shù)據(jù)元素，并為其開(kāi)辟一個(gè)大小為n1的共享內(nèi)存空間。每個(gè)block包含n1/2個(gè)線程，每個(gè)線程負(fù)責(zé)處理兩輸入的蝶形運(yùn)算。在這個(gè)階段，線程塊間不存在數(shù)據(jù)依賴關(guān)系，線程塊內(nèi)的線程采用阻塞同步技術(shù)來(lái)及時(shí)更新存儲(chǔ)在共享內(nèi)存中的數(shù)據(jù)。第二個(gè)計(jì)算核心遵循類(lèi)似的邏輯，首先將輸入矩陣進(jìn)行轉(zhuǎn)置，即線程塊的數(shù)量為n1，每個(gè)線程塊內(nèi)含有n2/2個(gè)線程，同時(shí)，每個(gè)線程塊內(nèi)輸入數(shù)據(jù)和其共享內(nèi)存的大小均設(shè)定為n2。

3.2 NTT訪存與數(shù)據(jù)洗牌策略

在NTT的計(jì)算過(guò)程中，復(fù)雜的訪存操作是一個(gè)不容忽視的挑戰(zhàn)。NTT計(jì)算本身涉及到大量的數(shù)據(jù)交互和存取操作，而在實(shí)施動(dòng)態(tài)任務(wù)分解策略時(shí)，這些訪存操作變得更為復(fù)雜。為了高效處理這些復(fù)雜的訪存需求，并最大化計(jì)算性能，需要對(duì)NTT的核內(nèi)和核外數(shù)據(jù)訪存進(jìn)行深度優(yōu)化。

NTT主計(jì)算核的細(xì)粒度優(yōu)化策略重點(diǎn)研究了數(shù)據(jù)洗牌與訪存優(yōu)化技術(shù)。為了高效計(jì)算，選擇使用共享內(nèi)存和常量?jī)?nèi)存來(lái)存放數(shù)據(jù)，從而降低對(duì)全局內(nèi)存的依賴和訪問(wèn)頻率。盡管全局內(nèi)存在GPU中提供了充足的全局內(nèi)存可供所有線程使用，但其較慢的訪問(wèn)速度和頻繁的讀寫(xiě)操作可能成為性能的制約因子。與此相反，共享內(nèi)存是設(shè)計(jì)用來(lái)在一個(gè)線程塊內(nèi)的各線程間進(jìn)行數(shù)據(jù)交換的，它具有更低的延遲和更高的帶寬。然而，其容量相對(duì)有限，這在大規(guī)模計(jì)算中可能成為一個(gè)限制。考慮到這一點(diǎn)，本文的GPU實(shí)現(xiàn)確保每個(gè)線程塊處理的NTT計(jì)算任務(wù)規(guī)模保持在一定范圍內(nèi)，以確保不超出共享內(nèi)存的容量。

在PreNTT中，主計(jì)算核每個(gè)線程塊會(huì)計(jì)算固定規(guī)模NTT，并且規(guī)模不大，不會(huì)超過(guò)共享內(nèi)存的容量限制，故使用共享內(nèi)存存儲(chǔ)單個(gè)線程塊中蝶形運(yùn)算的中間數(shù)據(jù)避免訪存沖突，加快讀寫(xiě)速度。當(dāng)為每個(gè)線程塊分配256規(guī)模的NTT計(jì)算任務(wù)時(shí)，首先從全局內(nèi)存中提取輸入數(shù)據(jù)，然后將其存儲(chǔ)在共享內(nèi)存中，作為蝶形運(yùn)算的輸入。每個(gè)線程塊將進(jìn)行8輪蝶形運(yùn)算。每輪計(jì)算的輸出結(jié)果作為下一輪計(jì)算的輸入數(shù)據(jù)，數(shù)據(jù)通過(guò)共享內(nèi)存交互，有效降速訪存延遲，進(jìn)而提供整體計(jì)算性能。

在NTT的蝶形運(yùn)算過(guò)程中，頻繁的洗牌操作是一個(gè)核心挑戰(zhàn)。特別是在GPU上，這種數(shù)據(jù)洗牌往往導(dǎo)致內(nèi)存的隨機(jī)訪問(wèn)，進(jìn)而觸發(fā)內(nèi)存訪問(wèn)的沖突，影響計(jì)算性能。核內(nèi)與線程塊內(nèi)數(shù)據(jù)洗牌流程如圖10所示，線程塊內(nèi)部完成計(jì)算后，必須進(jìn)行一次內(nèi)部洗牌操作。在NTT任務(wù)分配上有固定的規(guī)模，位反轉(zhuǎn)操作的輸出也相應(yīng)地固定，PreNTT將位反轉(zhuǎn)操作的數(shù)據(jù)索引存儲(chǔ)在常量?jī)?nèi)存中，減少多余計(jì)算產(chǎn)生的開(kāi)銷(xiāo)。

如圖11所示，在線程塊完成NTT任務(wù)之后，需要進(jìn)行雙重的數(shù)據(jù)洗牌操作。

首先，第一層是核內(nèi)的數(shù)據(jù)轉(zhuǎn)置：該步驟涉及將各個(gè)線程塊的計(jì)算結(jié)果進(jìn)行全局轉(zhuǎn)置，從而糾正分解步驟導(dǎo)致的數(shù)據(jù)錯(cuò)位。接下來(lái)，第二層是核外的數(shù)據(jù)洗牌：在使用GS方法對(duì)NTT任務(wù)進(jìn)行預(yù)計(jì)算分解后，必須將兩次子任務(wù)的結(jié)果進(jìn)行拼接，這涉及對(duì)兩個(gè)主計(jì)算核的數(shù)據(jù)進(jìn)行洗牌操作。

在最后一次調(diào)用GPU計(jì)算核時(shí)，GPU同時(shí)導(dǎo)入兩個(gè)主計(jì)算核的數(shù)據(jù)。這些數(shù)據(jù)隨后經(jīng)過(guò)轉(zhuǎn)置和插入處理，通過(guò)奇偶索引存儲(chǔ)到連續(xù)的全局內(nèi)存區(qū)域，主機(jī)端從全局內(nèi)存獲得最終的計(jì)算輸出。

通過(guò)利用GPU的共享內(nèi)存和常量?jī)?nèi)存資源，結(jié)合雙重?cái)?shù)據(jù)洗牌操作，本文不僅減少了對(duì)較慢的全局內(nèi)存的依賴和訪問(wèn)次數(shù)，優(yōu)化了數(shù)據(jù)在各計(jì)算單元間的流動(dòng)效率，也解決了由PreNTT的任務(wù)分解策略引入的數(shù)據(jù)重組難題，確保了計(jì)算過(guò)程中的結(jié)果正確性。

3.3 CPU-GPU異構(gòu)系統(tǒng)架構(gòu)設(shè)計(jì)

采用上述的PreNTT方法，本文實(shí)現(xiàn)了一種用于NTT計(jì)算的CPU-GPU異構(gòu)加速系統(tǒng)，該系統(tǒng)是基于CUDA異構(gòu)編程框架實(shí)現(xiàn)，內(nèi)存模型如圖12所示。

在GPU計(jì)算核初始化完畢后，主機(jī)端啟動(dòng)預(yù)計(jì)算核，并通過(guò)PCIe將相關(guān)參數(shù)（輸入規(guī)模不同，參數(shù)內(nèi)容也不同）傳送至設(shè)備端的全局內(nèi)存中。預(yù)計(jì)算核從全局內(nèi)存中獲取數(shù)據(jù)，并將每個(gè)線程塊的數(shù)據(jù)暫存于塊內(nèi)共享內(nèi)存，這樣可以優(yōu)化內(nèi)存訪問(wèn)速度。隨后，激活主計(jì)算核并直接從設(shè)備端的全局內(nèi)存中獲取數(shù)據(jù)存儲(chǔ)于塊內(nèi)共享內(nèi)存，用于后續(xù)的計(jì)算任務(wù)。所有計(jì)算核任務(wù)完成后，設(shè)備端將最終的計(jì)算結(jié)果通過(guò)PCIe傳送回主機(jī)端的DDR內(nèi)存。

在啟動(dòng)設(shè)備端的計(jì)算任務(wù)前，主機(jī)端必須完成若干初始化步驟。在預(yù)計(jì)算核運(yùn)行之前，主機(jī)端需為其生成旋轉(zhuǎn)因子向量以供內(nèi)部的快速冪算法使用。當(dāng)預(yù)計(jì)算核的任務(wù)結(jié)束后，主機(jī)端需將主計(jì)算核所需的全部NTT輸入數(shù)據(jù)映射至設(shè)備內(nèi)存中，由于數(shù)據(jù)量巨大，其通信開(kāi)銷(xiāo)大于預(yù)計(jì)算核數(shù)據(jù)傳輸與運(yùn)行時(shí)間。PreNTT采用CUDA多流技術(shù)，它允許內(nèi)存?zhèn)鬏敽陀?jì)算任務(wù)被放置在不同的流中，從而實(shí)現(xiàn)異步執(zhí)行。

如圖13所示，當(dāng)主機(jī)端激活預(yù)計(jì)算核任務(wù)時(shí)，無(wú)須等待預(yù)計(jì)算完成，可同時(shí)進(jìn)行其他操作，如分配內(nèi)存空間或映射輸入數(shù)據(jù)。鑒于預(yù)計(jì)算核的執(zhí)行時(shí)間相對(duì)較短，這種方式確保了主機(jī)端的數(shù)據(jù)處理與預(yù)計(jì)算核的計(jì)算任務(wù)能夠并行執(zhí)行，掩蓋預(yù)計(jì)算核的計(jì)算時(shí)間。

4 系統(tǒng)實(shí)現(xiàn)與結(jié)果評(píng)估

4.1 實(shí)驗(yàn)平臺(tái)和環(huán)境

本文的實(shí)驗(yàn)是在一臺(tái)配備3.7 GHz AMD Ryzen 9 5900X處理器（含12個(gè)物理核心）、12 GB顯存的RTX3060顯卡和128 GB DRAM的服務(wù)器上進(jìn)行。該服務(wù)器運(yùn)行Ubuntu 20.04.5操作系統(tǒng)和CUDA 11.8。硬件平臺(tái)具體數(shù)據(jù)如表1所示。

4.2 系統(tǒng)實(shí)現(xiàn)

主流的異構(gòu)編程框架包含CUDA和OpenCL，兩者各有優(yōu)劣。CUDA針對(duì)NVIDIA生產(chǎn)的GPU，擁有豐富的生態(tài)系統(tǒng)和廣泛的開(kāi)發(fā)資源，其中包括核心庫(kù)、開(kāi)發(fā)工具集以及優(yōu)化庫(kù)。相較之下，OpenCL雖有著較強(qiáng)的跨平臺(tái)能力，能在多種硬件上執(zhí)行，但由于其相對(duì)較小的生態(tài)系統(tǒng)，性能優(yōu)化變得相對(duì)困難?？紤]到這些因素，本文的系統(tǒng)設(shè)計(jì)主要包括主機(jī)端和設(shè)備端兩個(gè)部分，并借助CUDA異構(gòu)編程框架來(lái)處理主機(jī)端與設(shè)備端間的數(shù)據(jù)交互。圖14為NTT異構(gòu)加速框架示意圖。

Bellperson是一個(gè)基于Rust實(shí)現(xiàn)的零知識(shí)證明系統(tǒng)庫(kù)，提供了zk-SNARK證明系統(tǒng)構(gòu)建所需的工具和庫(kù)，如電路特性、約束系統(tǒng)和數(shù)字抽象。本文核心工作在于對(duì)Bellperson的代碼重構(gòu)，考慮到Bellperson使用的CUDA API并不直接支持stream分流，其結(jié)構(gòu)相對(duì)復(fù)雜，本文選擇采用Rust封裝的rustAcuda替代原有庫(kù)，并針對(duì)主機(jī)端的平臺(tái)與設(shè)備查找、內(nèi)核創(chuàng)建等功能進(jìn)行了重新實(shí)現(xiàn)。

4.3 結(jié)果評(píng)估

4.3.1 同類(lèi)工作對(duì)比

在眾多NTT/INTT優(yōu)化方案中，不同方案使用的硬件平臺(tái)不同。例如，文獻(xiàn)［15］基于ASIC進(jìn)行實(shí)現(xiàn)，而B(niǎo)ellperson［23］則提供了GPU和CPU的實(shí)現(xiàn)。此外，不同的應(yīng)用場(chǎng)景也導(dǎo)致了不同的計(jì)算規(guī)模和數(shù)據(jù)位寬，如文獻(xiàn)［27］。為了有效地將這些方案與本文的實(shí)現(xiàn)進(jìn)行比較，對(duì)部分優(yōu)化方案進(jìn)行了計(jì)算效率的抽象分析。

NTT/INTT的計(jì)算復(fù)雜度主要來(lái)源于兩個(gè)方面。首先，蝶形運(yùn)算中基于蒙哥馬利模乘的計(jì)算復(fù)雜度，可表示為O（Nlog2N），其中N為NTT任務(wù)規(guī)模;其次，蒙哥馬利模乘本身的計(jì)算復(fù)雜度，該復(fù)雜度可表示為O（n2），其中n為數(shù)據(jù)位寬，以對(duì)比不同位寬的實(shí)驗(yàn)方案。

總的復(fù)雜度可表示為

O（Nlog2N）×O（n2）=N×log2N×n2

相對(duì)效率可表示為

N×log2N×n2/NTT runtime

表2展示了本研究與相關(guān)工作的計(jì)算效率對(duì)比。值得注意的是，Kyber的實(shí)驗(yàn)是在RTX2060 SUPER平臺(tái)上執(zhí)行的。為了確保實(shí)驗(yàn)的嚴(yán)謹(jǐn)性，本研究對(duì)Kyber的相對(duì)效率進(jìn)行了轉(zhuǎn)換。本文采用TOPS（int32）作為評(píng)估GPU計(jì)算能力的指標(biāo)，其中RTX2060 SUPER的TOPS為7.181，而RTX3060的TOPS達(dá)到12.7。經(jīng)過(guò)轉(zhuǎn)換后，Kyber的相對(duì)效率約為2.86×1011，這是其最佳性能情況。從上述數(shù)據(jù)分析中，可以清晰地看出，相對(duì)于其他相關(guān)工作，本研究的方案具有顯著的加速效果。

4.3.2 基于PreNTT的Bellperson系統(tǒng)的性能評(píng)估

Bellperson主要部署于Zcash和Filecoin等應(yīng)用代表了當(dāng)前技術(shù)的前沿，其不斷根據(jù)最新的研究成果和技術(shù)進(jìn)步進(jìn)行實(shí)時(shí)更新。這保證了所使用的算法始終處于行業(yè)領(lǐng)先水平，使其成為評(píng)估新提出策略有效性和先進(jìn)性的理想對(duì)比對(duì)象。本文對(duì)比的Bellperson版本集成了眾多先進(jìn)NTT加速方案［22，30］，將本文提出的策略與Bellperson對(duì)應(yīng)的NTT算子進(jìn)行比較，可以準(zhǔn)確評(píng)估所提策略在當(dāng)前技術(shù)背景下的性能及可行性。

為滿足用戶對(duì)高效交易處理和快速區(qū)塊確認(rèn)的需求，實(shí)際操作中延遲被視為至關(guān)重要的評(píng)估指標(biāo)。本文提出預(yù)計(jì)算核與主計(jì)算核相結(jié)合的加速方案，對(duì)NTT任務(wù)進(jìn)行分解，實(shí)現(xiàn)全規(guī)模計(jì)算任務(wù)的優(yōu)化。后續(xù)部分本文將從預(yù)計(jì)算核、主計(jì)算核與整體加速效果等角度，分別與Bellperson的GPU實(shí)現(xiàn)進(jìn)行詳細(xì)對(duì)比，以驗(yàn)證PreNTT的有效性。

需要強(qiáng)調(diào)的是，本文為展現(xiàn)PreNTT的先進(jìn)性，將對(duì)比實(shí)驗(yàn)中Bellperson的NTT并行方案進(jìn)行了改進(jìn)。Bellperson中對(duì)NTT任務(wù)分解并不是動(dòng)態(tài)變化的，每次執(zhí)行運(yùn)算時(shí)，分解矩陣的列數(shù)（即線程塊的運(yùn)算量）是固定的，當(dāng)輸入規(guī)模增加時(shí)，分解之后的任務(wù)會(huì)存在負(fù)載不均衡的問(wèn)題。在實(shí)驗(yàn)中，手動(dòng)將Bellperson每次的分解矩陣調(diào)整到最佳負(fù)載情況，即接近方陣的形式。本節(jié)展示的Bellperson相關(guān)數(shù)據(jù)為其算法所能展現(xiàn)的最佳性能。

首先，在預(yù)計(jì)算核部分，通過(guò)采用旋轉(zhuǎn)因子的快速冪算法進(jìn)行了優(yōu)化。為了明確對(duì)比，本文從Bellperson中單獨(dú)提取了旋轉(zhuǎn)因子的計(jì)算開(kāi)銷(xiāo)，與PreNTT預(yù)計(jì)算中旋轉(zhuǎn)因子的計(jì)算時(shí)間進(jìn)行對(duì)比。如圖15所示，采用快速冪算法來(lái)計(jì)算旋轉(zhuǎn)因子具有顯著的效果。當(dāng)計(jì)算規(guī)模為216時(shí)已經(jīng)達(dá)到了1.6倍的加速比，隨著計(jì)算規(guī)模的增加，加速效果逐漸顯現(xiàn)。在計(jì)算規(guī)模為221時(shí)，加速比進(jìn)一步提升至2.5倍，這超出了預(yù)期的2倍加速比。

GPU中共享內(nèi)存的可用空間是有限的，當(dāng)NTT的計(jì)算規(guī)模擴(kuò)大到221時(shí)，需要進(jìn)行三次分解以完成全部的計(jì)算任務(wù)，增加了額外的旋轉(zhuǎn)因子計(jì)算開(kāi)銷(xiāo)。這種情況下，使用預(yù)計(jì)算核來(lái)單獨(dú)處理旋轉(zhuǎn)因子的方法不受NTT任務(wù)分解次數(shù)的限制，展現(xiàn)出獨(dú)特的優(yōu)勢(shì)?？梢灶A(yù)料的是，隨著計(jì)算規(guī)模繼續(xù)擴(kuò)大，加速效果將越來(lái)越突出。

通過(guò)結(jié)合核內(nèi)外雙重?cái)?shù)據(jù)混洗策略，本文提出并實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)自適應(yīng)的計(jì)算框架，無(wú)須擔(dān)心額外的訪存沖突和內(nèi)核調(diào)用問(wèn)題。當(dāng)規(guī)模為2n時(shí)，將n的奇偶性作為分類(lèi)依據(jù)，設(shè)計(jì)了兩種預(yù)計(jì)算策略。系統(tǒng)在執(zhí)行過(guò)程中會(huì)依據(jù)輸入的規(guī)模動(dòng)態(tài)選擇合適的計(jì)算分解方案。當(dāng)n為奇數(shù)時(shí)，預(yù)計(jì)算核執(zhí)行一輪蝶形運(yùn)算和部分旋轉(zhuǎn)因子計(jì)算。相對(duì)應(yīng)的主計(jì)算核會(huì)執(zhí)行對(duì)旋轉(zhuǎn)因子的補(bǔ)充計(jì)算。圖16為n是奇數(shù)情況下，預(yù)計(jì)算模塊與主計(jì)算模塊的運(yùn)行時(shí)間與同規(guī)模下Bellperson的對(duì)比。

為確保在全規(guī)模下提高計(jì)算效率，以RTX3060的片上內(nèi)存作為參考標(biāo)準(zhǔn)，在221或更高的規(guī)模下，主計(jì)算核采用三維分解策略，預(yù)計(jì)算核只進(jìn)行旋轉(zhuǎn)因子計(jì)算。值得一提的是，奇數(shù)時(shí)的分解策略可以將NTT分解為無(wú)數(shù)據(jù)依賴的獨(dú)立任務(wù)，這一特性在多GPU的使用場(chǎng)景中具有重要意義，其應(yīng)用前景廣闊。表3列出了單輪NTT／INTT計(jì)算任務(wù)中，PreNTT相對(duì)于Bellperson的加速比。

由表3可知，當(dāng)采用奇偶分解策略時(shí)，加速比表現(xiàn)較為顯著。但隨著任務(wù)規(guī)模的逐漸擴(kuò)大，加速比的增幅呈現(xiàn)緩慢的下降趨勢(shì)。主要原因是在NTT的GPU部署中，性能瓶頸主要集中旋轉(zhuǎn)因子的計(jì)算以及全局內(nèi)存訪問(wèn)和塊間通信。本文提出的優(yōu)化方案效果體現(xiàn)在旋轉(zhuǎn)因子計(jì)算和線程內(nèi)的高效運(yùn)算上，隨著NTT規(guī)模的擴(kuò)大，數(shù)據(jù)訪問(wèn)和通信的開(kāi)銷(xiāo)逐漸成為影響計(jì)算核心整體運(yùn)行時(shí)間的主導(dǎo)因素，導(dǎo)致PreNTT的加速比出現(xiàn)下降趨勢(shì)。如果能采用具有更大片上內(nèi)存和帶寬的GPU設(shè)備，PreNTT有潛力對(duì)更大規(guī)模的任務(wù)實(shí)現(xiàn)更高的加速優(yōu)化。此外，本文采用CUDA多流技術(shù)，使得預(yù)計(jì)算核與主計(jì)算核的數(shù)據(jù)傳輸與運(yùn)算能夠在兩個(gè)異步流中并發(fā)執(zhí)行。主機(jī)端負(fù)責(zé)將大量的輸入數(shù)據(jù)映射到GPU內(nèi)存中，將創(chuàng)建內(nèi)存空間以及數(shù)據(jù)傳輸消耗的時(shí)間開(kāi)銷(xiāo)統(tǒng)稱為計(jì)算核準(zhǔn)備時(shí)間。如圖17所示，主計(jì)算核所需的準(zhǔn)備時(shí)間往往超過(guò)預(yù)計(jì)算核的整體時(shí)間。因此，通過(guò)CUDA多流重疊的策略，預(yù)計(jì)算核的執(zhí)行時(shí)間得以與主機(jī)端的數(shù)據(jù)映射時(shí)間并行，從而進(jìn)一步提高了整體的計(jì)算效率。

圖18展示了采用多流技術(shù)掩蓋預(yù)計(jì)算核運(yùn)行時(shí)間之后，NTT整體加速比變化趨勢(shì)。結(jié)果表明，本文NTT并行方案在與Bellperson并行方案的對(duì)比下，獲得了全模塊最低1.7倍的加速比。

5 結(jié)束語(yǔ)

本文提出了一種NTT并行加速方法PreNTT，并基于GPU對(duì)其進(jìn)行實(shí)現(xiàn)。首先，使用高效的旋轉(zhuǎn)因子預(yù)計(jì)算方法，結(jié)合主計(jì)算中自適應(yīng)的動(dòng)態(tài)分解策略，提出一種高效的NTT并行計(jì)算方法PreNTT。其次，在GPU部署PreNTT，采用雙層動(dòng)態(tài)任務(wù)分解策略，確保各子任務(wù)的計(jì)算負(fù)載平衡，提升計(jì)算效率，確保在全數(shù)據(jù)規(guī)模變化下的持續(xù)加速能力。在核內(nèi)實(shí)施了雙級(jí)數(shù)據(jù)混洗操作，降低了訪存沖突的可能性，保證任務(wù)分解過(guò)程的準(zhǔn)確性。最后，利用CUDA流技術(shù)，覆蓋了預(yù)計(jì)算核心的時(shí)間消耗，進(jìn)一步提升了加速效果。實(shí)驗(yàn)結(jié)果顯示，與當(dāng)前最先進(jìn)的NTT加速方法Bellperson相比，本文方法在計(jì)算速度、加速穩(wěn)定性和拓展性上均有顯著提升。在未來(lái)的研究中，將繼續(xù)探索超大規(guī)模NTT的優(yōu)化方法，研究如何利用多設(shè)備集群來(lái)提高NTT的計(jì)算速度，降低其通信復(fù)雜性，從而提升zk-SNARK的計(jì)算性能。

參考文獻(xiàn)：

［1］Benet J，Greco N.Filecoin：a decentralized storage network［R］.［S.l.］：Protocol Labs，2017：1-36.

［2］Miers I，Garman C，Green M，et al.Zerocoin：anonymous distributed e-cash from bitcoin［C］//Proc of IEEE Symposium on Security and Privacy.Piscataway，NJ：IEEE Press，2013：397-411.

［3］柳欣，徐秋亮.改進(jìn)的支持暫停匿名用戶服務(wù)的電子現(xiàn)金系統(tǒng)［J］.計(jì)算機(jī)應(yīng)用研究，2016，33（10）：3099-3104.（Liu Xin，Xu Qiuliang.Improved support for the suspension of the electronic cash system for anonymous user services［J］.Application Research of Computers，2016，33（10）：3099-3104.）

［4］Sasson E B，Chiesa A，Garman C，et al.Zerocash：decentralized anonymous payments from bitcoin［C］//Proc of IEEE Symposium on Security and Privacy.Piscataway，NJ：IEEE Press，2014：459-474.

［5］劉紅，張靖宇，雷夢(mèng)婷，等.基于區(qū)塊鏈的公平和可驗(yàn)證電子投票智能合約［J］.應(yīng)用科學(xué)學(xué)報(bào)，2023，41（4）：541-562.（Liu Hong，Zhang Jingyu，Lei Mengting，et al.Blockchain-based fair and verifiable electronic voting smart contract［J］.Journal of Applied Sciences，2023，41（4）：541-562.）

［6］Zhang Yupeng，Genkin D，Katz J，et al.vSQL：verifying arbitrary SQL queries over dynamic outsourced databases［C］//Proc of IEEE Symposium on Security and Privacy.Piscataway，NJ：IEEE Press，2017：863-880.

［7］Zhao Lingchen，Wang Qian，Wang Cong，et al.VeriML：enabling inte-grity assurances and fair payments for machine learning as a service［J］.IEEE Trans on Parallel and Distributed Systems，2021，32（10）：2524-2540.

［8］吳昊天，李一凡，崔鴻雁，等.基于零知識(shí)證明和區(qū)塊鏈的聯(lián)邦學(xué)習(xí)激勵(lì)方案［J］.信息網(wǎng)絡(luò)安全，2024，24（1）：1-13.（Wu Haotian，Li Yifan，Cui Hongyan，et al.Federated learning incentive scheme based on zero-knowledge proof and blockchain［J］.Netinfo Security，2024，24（1）：1-13.）

［9］景旭，楊少坤.面向聯(lián)盟鏈轉(zhuǎn)賬隱私保護(hù)的+HomElG零知識(shí)證明協(xié)議［J］.工程科學(xué)與技術(shù)，2023，55（5）：272-282.（Jing Xu，Yang Shaokun.+HomElG zero-knowledge proof protocol for privacy protection of consortium chain transfers［J］.Advanced Engineering Sciences，2023，55（5）：272-282.）

［10］王后珍，郭巖，張煥國(guó).基于矩陣填充問(wèn)題的高效零知識(shí)身份認(rèn)證方案［J］.武漢大學(xué)學(xué)報(bào)：理學(xué)版，2021，67（2）：111-117.（Wang Houzhen，Guo Yan，Zhang Huanguo.Efficient zero-knowledge identity authentication scheme based on matrix stuffing problem［J］.Journal of Wuhan University：Natural Science，2021，67（2）：111-117.）

［11］Maller M，Bowe S，Kohlweiss M，et al.Sonic：zero-knowledge SNARKs from linear-size universal and updatable structured reference strings［C］//Proc of ACM SIGSAC Conference on Computer and Communications Security.New York：ACM Press，2019：2111-2128.

［12］Byunz B，F(xiàn)isch B，Szepieniec A.Transparent SNARKs from DARK compilers［C］//Advances in Cryptology-EUROCRYPT 2020：the 39th Annual International Conference on Theory and Applications of Cryptographic Techniques.Berlin：Springer，2020：677-706.

［13］Chiesa A，Hu Y，Maller M，et al.Marlin：preprocessing zkSNARKs with universal and updatable SRS［C］//Advances in Cryptology-EUROCRYPT：the 39th Annual International Conference on Theory and Applications of Cryptographic Techniques.Berlin：Springer International Publishing，2020：738-768.

［14］Groth J.On the size of pairing-based noninteractive arguments［C］//Advances in Cryptology-EUROCRYPT：the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin：Springer，2016：305-326.

［15］Zhang Ye，Wang Shuo，Zhang Xian，et al.Pipezk：accelerating zero-knowledge proof with a pipelined architecture［C］//Proc of ACM/IEEE 48th Annual International Symposium on Computer Architecture.Piscataway，NJ：IEEE Press，2021：416-428.

［16］Haleplidis E，Tsakoulis T，EL-KADY A，et al.Studying OpenCL-based number theoretic transform for heterogeneous platforms［C］//Proc of the 24th Euromicro Conference on Digital System Design.Piscataway，NJ：IEEE Press，2021：339-346.

［17］Kim S，Lee K，Cho W，et al.Hardware architecture of a number theoretic transform for a bootstrappable RNS-based homomorphic encryption scheme［C］//Proc of the 28th IEEE Annual International Symposium on Field-Programmable Custom Computing Machines.Pisca-taway，NJ：IEEE Press，2020：56-64.

［18］周慧凱.同態(tài)加密的硬件卸載及其在隱私保護(hù)計(jì)算中的應(yīng)用［J］.小型微型計(jì)算機(jī)系統(tǒng)，2021，42（3）：595-600.（Zhou Huikai.Hardware offloading of homomorphic encryption and its application in privacy-preserving computing［J］.Journal of Chinese Computer Systems，2021，42（3）：595-600.）

［19］Kales D，Ramacher S，Rechberger C，et al.Efficient FPGA implementations of LowMC and picnic［C］//Proc of Cryptographers’Track at RSA Conference.Berlin：Springer，2020：417-441.

［20］Agrawal R，Bu L，Ehret A，et al.Open-source FPGA implementation of post-quantum cryptographic hardware primitives［C］//Proc of the 29th International Conference on Field Programmable Logic and App-lications. Piscataway，NJ：IEEE Press，2019：211-217.

［21］Kim S，Jung W，Park J，et al.Accelerating number theoretic transformations for bootstrappable homomorphic encryption on GPU［C］//Proc of IEEE International Symposium on Work-load Characterization.Piscataway，NJ：IEEE Press，2020：264-275.

［22］Naina G，Arpan J，Kumar C A，et al.PQC acceleration using GPUs：Frodokem，NewHope，and Kyber［J］.IEEE Trans on Parallel and Distributed Systems，2020，32（3）：575-586.

［23］FILECOIN.Bellperson：GPU parallel acceleration for zk-SNARK［EB/OL］.［2020］.https：//github.com/filecoin-project/bellperson.

［24］李龔亮，賀東博，郭兵，等.基于零知識(shí)證明的區(qū)塊鏈隱私保護(hù)算法［J］.華中科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2020，48（7）：112-116.（Li Gongliang，He Dongbo，Guo Bin，et al.Blockchain privacy protection algorithm based on zero-knowledge proof［J］.Journal of Huazhong University of Science and Technology：Nature Science，2020，48（7）：112-116.）

［25］Byunz B，Bootle J，Boneh D，et al.Bulletproofs：short proofs for confidential transactions and more［C］//Proc of IEEE Symposium on Security and Privacy.Piscataway，NJ：IEEE Press，2018：315-334.

［26］Montgomery P L.Modular multiplication without trial division［J］.Mathematics of Computation，1985，44（170）：519-521.

［27］Lee W K，Hwang S O.High throughput implementation of post-quantum key encapsulation and decapsulation on GPU for Internet of Things applications［J］.IEEE Trans on Services Computing，2021，15（6）：3275-3288.

［28］Gentleman W M，Sande G.Fast Fourier transforms：for fun and profit［C］//Proc of Fall Joint Computer Conference.New York：ACM Press，1966：563-578.

［29］趙海旭，柴志雷，花鵬程，等.zk-SNARK中數(shù)論變換的硬件加速方法研究［J］.計(jì)算機(jī)科學(xué)與探索，2024，18（2）：538-552.（Zhao Haixu，Chai Zhilei，Hua Pengcheng，et al.Research on hardware acceleration method of number theory transformation in zk-SNARK［J］.Journal of Frontiers of Computer Science & Technology，2024，18（2）：538-552.）

［30］Ni Ning，Zhu Yongxin.Enabling zero knowledge proof by accelerating zk-SNARK kernels on GPU［J］.Journal of Parallel and Distributed Computing，2023，173：20-31.