基于GPU的zk-SNARK中多標量乘法的并行計算方法

摘 要：針對zk-SNARK（zero-knowledge succinct non-interactive argument of knowledge）中計算最為耗時的多標量乘法（multi-scalar multiplication，MSM），提出了一種基于GPU的MSM并行計算方案。首先，對MSM進行細粒度任務分解，提升算法本身的計算并行性，以充分利用GPU的大規模并行計算能力。采用共享內存對同一窗口下的子MSM并行規約減少了數據傳輸開銷。其次，提出了一種基于底層計算模塊線程級任務負載搜索最佳標量窗口的窗口劃分方法，以最小化MSM子任務的計算開銷。最后，對標量形式轉換所用數據存儲結構進行優化，并通過數據重疊傳輸和通信時間隱藏，解決了大規模標量形式轉換過程的時延問題。該MSM并行計算方法基于CUDA在NVIDIA GPU上進行了實現，并構建了完整的零知識證明異構計算系統。實驗結果表明：所提出的方法相比目前業界最優的cuZK的MSM計算模塊獲得了1.38倍的加速比。基于所改進MSM的整體系統比業界流行的Bellman提升了186倍，同時比業界最優的異構版本Bellperson提升了1.96倍，驗證了方法的有效性。

關鍵詞：簡潔非交互式零知識證明； 多標量乘法； CUDA； 異構計算系統； 并行計算

中圖分類號：TP311;TP309.7 文獻標志碼：A

文章編號：1001-3695（2024）06-019-1735-08

doi：10.19734/j.issn.1001-3695.2023.11.0498

Parallel computation method for multi-scalar multiplication inzk-SNARK based on GPU

Abstract：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 zero-knowledge 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.

Key words：zk-SNARK; multi-scalar multiplication; CUDA; heterogeneous computing system; parallel computing

0 引言

零知識證明（zero knowledge proof，ZKP）作為一種密碼學協議，可以在不泄露任何隱私信息的情況下證明數據的正確性［1］，具有廣闊的應用前景。但如果要在實際系統中應用ZKP，還需要大幅度提升其“證明生成”和“證明驗證”的效率。在證明驗證效率的提升方面，簡潔非交互式零知識證明（zero-knowledge succinct non-interactive arguments of knowledge， zk-SNARK）在保持高度安全性和可靠性的同時做到了證明驗證的簡潔性，可以在通信成本高或驗證者計算能力較弱的情況下實現高效證明［2，3］，因此已被廣泛應用于數字貨幣［4］、區塊鏈［5，6］、金融［7］、隱私保護［8］等多個領域。然而，盡管zk-SNARK提升了證明驗證的效率，但其證明生成仍十分復雜和耗時。在實際應用場景中，證明生成也會被頻繁調用，過長的證明生成時間嚴重阻礙了zk-SNARK的廣泛應用。

zk-SNARK的證明生成過程主要用到數論變換（number theoretic transformation，NTT）和多標量乘法（multi-scalar multiplication，MSM）。其中MSM是zk-SNARK證明生成過程中最主要的計算瓶頸［9，10］，例如：在著名的zk-SNARK開源庫Bellman中MSM的執行時間占據了整個證明生成總時間的90%以上。

基于上述原因，如何有效縮短以MSM為主的zk-SNARK證明生成過程成為研究熱點。除了算法方面的改進，利用硬件進行加速是其中的重要方法之一。PipeZK［11］提出了一種以ASIC為目標硬件用于加速zk-SNARK的高效流水線結構，將其中最為耗時的兩個子系統NTT和MSM設計為專用硬件加速器，同時與CPU進行異構設計來實現端到端系統。該方案雖然可以顯著提高零知識證明的計算效率，但其通用性相對較差而且不利于更新。Wu等人［12］提出了一種用于加速橢圓曲線上點乘運算的高性能硬件架構，能夠同時適用于Xilinx和Intel FPGA平臺，并基于點乘模塊設計了一個高效的MSM硬件加速器，但相較于Bellperson中基于GPU的異構加速方法，在計算效率上仍有數倍的差距。Yang等人［13］通過在GPU上加速zk-SNARK中耗時的計算內核實現零知識證明，利用GPU全局內存和共享內存中的數據布局和洗牌方法來維護數據空間的一致性，從而加速NTT/INTT計算模塊，其計算效率相較于Bellperson有了明顯的提高，但其并沒有針對計算時延更高的MSM模塊給出更有效的加速方案。在上述的各種硬件加速方法中，最重要的工作是如何充分挖掘算法本身的并行性，這樣才能更好地發揮并行硬件的潛力。此外，在并行計算時，多個計算節點需要進行通信與同步，如何減少節點間通信對整體計算性能的影響也是需要重點解決的問題。而在上述硬件加速相關工作中，針對上述兩點，如何與相應的硬件結構相適配方面的研究尚不夠深入。

MSM作為一種計算密集型任務具有高度的并行性，需充分考慮硬件的并行計算能力以最大程度發揮MSM的計算特性［14］。FPGA受限于板上資源無法完全發揮其潛在的并行計算能力，ASIC的定制化特點難以應對MSM數據位寬的靈活變換。而CUDA作為一種單指令多線程的編程模型，其高并行性和靈活性的特點為滿足MSM的計算特性提供了理想選擇［15］。

本文針對zk-SNARK中計算最為耗時的多標量乘法，提出一套高效的基于GPU的MSM并行加速方案。主要工作如下：

a）對MSM進行細粒度任務分解，提升算法本身的計算并行性，以充分利用GPU的大規模并行計算能力。采用共享內存對同一窗口下的子MSM并行歸約，減少了數據傳輸開銷。

b）提出了一種基于底層計算模塊線程級任務負載搜索最佳標量窗口的窗口劃分方法，以最小化MSM子任務的計算開銷。

c）對標量形式轉換所用數據存儲結構進行優化，并通過數據重疊傳輸和通信時間隱藏，解決了大規模標量形式轉換過程的時延問題。

此外，基于CUDA在NVIDIA GPU上實現了該MSM并行計算方法，并構建了完整的零知識證明異構計算系統。相比目前業界最優的cuZK的MSM計算模塊，獲得了1.38倍的加速比，基于所改進MSM的整體系統比業界流行的Bellman提升了186倍，同時比業界最優的異構版本Bellperson提升了1.96倍。

1 預備知識

1.1 zk-SNARK協議

零知識證明作為現代密碼學中的基本原語之一，它允許證明者向驗證者證明某個語句的真實性，而無須透露任何關于證明的信息［16］。傳統的交互式零知識證明（interactive zero-knowledge proofs，IZKP）需要證明者和驗證者之間進行多輪交互，證明者需要多次響應驗證者的挑戰才能最終完成證明過程，性能較低，難以應用于大規模網絡中［17］。為了解決該問題，zk-SNARK協議應運而生，zk-SNARK作為一種簡潔非交互式的零知識證明協議，在其證明過程中證明者只需要進行一次計算就可以生成證明，驗證者根據生成的證明自行驗證，避免了雙方的多次通信［18，19］。Groth16作為應用最為廣泛的zk-SNARK協議，在橢圓曲線密碼學的基礎上構建而成，證明過程主要包括設置參數（setup）、生成證明（prove）、驗證（verify）三個階段［20］。

在Groth16協議中對于一個問題多項式F（x），證明者要向驗證者證明其知道一組完整的解向量a，同時不對驗證者泄露任何關于解向量的信息。該協議是基于QAP（quadratic arithmetic program）進行證明的生成和驗證，所以在生成證明之前需要先將原始的問題多項式轉換為QAP形式，轉換過程如圖1上半部分所示，先根據解向量將多項式轉換為一組二元算數電路（circuit），然后根據電路生成R1CS（rank-1 constraint system），最后通過逆傅里葉變換得到QAP的相關多項式系數矩陣，如圖中的U、V、W所示。參數設置階段由可信的第三方隨機生成一些公開參數，同時選取一個私有的隨機變量（挑戰點），將其帶入到QAP多項式中來生成證明密鑰（pk）和驗證密鑰（vk）并公開。任何人都可以使用證明密鑰和驗證密鑰來生成和驗證證明，但只有使用解向量的非公開部分（aw）生成的證明才能通過驗證。生成證明階段是計算最為復雜的階段，其計算步驟主要包括利用QAP和已知多項式t（x）進行三次NTT和一次INTT求得h（x）以及根據證明密鑰和解向量通過MSM生成證明兩個過程，如圖1的下半部分所示。驗證階段則是根據生成的證明（π）和解向量的公開部分（as）以及驗證密鑰（vk），通過雙線性配對來進行驗證。

為了提高安全性，QAP的規模通常會達到數百萬，這也導致了在prove階段要花費大量的時間來生成證明。圖2展示了在AMD Ryzen 9 5900X處理器上，不同規模下證明生成過程總的運算時間和MSM計算時間的對比情況。從圖中可以看出MSM的計算占據了證明生成過程總時間的絕大部分，zk-SNARK證明系統的整體性能在很大程度上取決于MSM的計算效率。因此，通過提高MSM的計算效率可以明顯縮減生成證明的時間，使零知識證明系統在應用中更加高效。

1.2 多標量乘法（MSM）

多標量乘法是指對于給定的橢圓曲線上的點集合和標量集合，計算這些點與對應標量相乘再相加的運算過程。其數學定義如式（1）所示。

從算法中可以看出，標量的位寬越大，PDBL和PADD總的計算次數越多，PMULT的計算量也越大。以Filecoin為例，MSM的規模為數百萬，標量位寬為256 bit。如果計算出每一個PMULT的結果，然后再通過PADD相加來得到MSM的結果，將會產生巨大的計算時延。

1.3 用于MSM的Pippenger算法

Pippenger算法也叫桶方法，是一種用于計算大規模MSM的高效算法。其核心思想是通過對標量的劃分，將一個高位寬的MSM分解成多個低位寬的MSM，以減少總體的PMUL計算，從而提高計算效率［21］。Pippenger算法的計算細節主要由三個步驟組成：

a）將一個原始的MSM分解成多個較小的子任務。選定一個窗口c（c<λ），將每一個λ bit的標量ki劃分成L=「λ/c個部分，那么一個λ bit的MSM就被分解成了L個c bit的MSM（如果是非等量劃分，最高位的部分進行補零），Yj表示第j個c bit的MSM，ki，j表示第i個標量的第j部分，其中i∈［1，N］，j∈［1，L］。式（1）也就等價于

b）計算出每一個子MSM的結果。初始化2c-1個空桶，然后將Gi累加到與其系數ki，j相對應的桶中。那么Yj的計算公式也就變為

其中：［Bj］u表示第j個c bit的MSM的第u個桶中所有點累加的結果，通過霍納法則可以快速計算出Yj。

2 本文方法ParMSM

Pippenger算法對于子任務的劃分是將一個規模為N的λ bit的MSM劃分為L=「λ/c個規模同樣為N的c bit的MSM，如圖4的第一級子任務劃分所示。以需要計算的橢圓曲線點加（PADD）和點加倍（PDBL）的數量作為計算成本來進行量化分析。每一個子任務的計算成本為

W=（N+2c+1）×PADD（4）

對于一個完整的MSM串行執行的總的計算成本為

Tot_ser=W×L+（（L－1）*2c）×PDBL+L×PADD（5）

該方法最多可以將MSM分解成L個子任務，難以滿足更高水平的并行計算要求。因此，有必要對MSM進行更細粒度的任務分解。這里在原子任務劃分方式的基礎上將每一個規模為N的c bit的MSM繼續拆分成D=「N/M個的規模為M（M<N）的c bit的MSM，相比于原來的L個子任務變成了L*D個子任務，如圖4的第二級子任務劃分所示，這些子MSM之間沒有任何數據依賴，可以并行執行。在應用中可以根據實際的并行處理能力以及MSM的規模來選擇最佳的窗口大小，使子MSM的計算成本最低。

在第二級的子任務劃分中對每一個規模為N的c bit的MSM進行細粒度分解得到的D個規模為M的c bit的MSM，它們位于同一窗口下可以直接進行合并。對此，本文設計了一種用于同一窗口下子MSM結果規約的并行算法。具體的實現方法如圖5所示。首先，將位于同一窗口下的D個子MSM分成「D/2組，其中每一組兩個元素，然后將每一組內的兩個元素相加，由于每組之間的元素沒有任何數據依賴，所以這「D/2組之間的計算可以并行執行。經過第一輪的合并之后由原來的D個元素縮減為「D/2個元素，對這「D/2個元素按照同樣的方法進行并行合并，經過逐級合并后最終只有一個元素，而該元素就是位于同一窗口下的子MSM相加后的結果。該方法將原來的D-1次點加運算縮減為log2（D）次，對于每一個窗口下的子MSM都采用該方法進行并行歸約，可以在很大的程度上節省計算開銷。

假設y為子任務的數量，即y=L*D，那么本文所提出的并行方法中每一個子任務的計算成本為

W=（「N/L+2c）×PADD（6）

同一窗口下子任務歸約的計算成本為

W_red=log2（D）×PADD（7）

一個完整的MSM并行執行的計算成本為

Tot=W+W_red+（（L-1）*2c）×PDBL（8）

相比串行計算的理論加速比約為

從式（9）可以看出，當N為百萬數量級時該并行算法相比于串行計算加速效果非常顯著，并且隨著并行處理能力的增強該并行算法的效率也隨之提高。

3 基于GPU的ParMSM實現

3.1 ParMSM的計算架構

在第二級的子任務劃分中位于同一窗口下的D個規模為M的c bit的MSM由一個或多個線程塊處理，線程塊內的每一個線程對應一個子MSM。保證了同一線程塊內的線程所對應的子MSM都位于同一窗口下，而線程塊內具有共享內存可以用于同一個線程塊內的線程之間共享數據。相較于全局內存，共享內存的訪問速度更快，通信延遲更低，在并行計算任務中發揮著重要作用，特別是對于需要線程之間進行數據共享和協作的算法。因此，本文設計了一種利用線程塊內共享內存來實現子MSM的并行歸約的方法。具體的實現細節如圖6所示。

假設一個線程塊內有8個線程，其中每一個線程所計算的子MSM都位于同一窗口。首先，定義一個大小為8的共享內存數組，每一個線程都將其計算的子MSM結果存放在與其塊內線程號對應的共享內存數組中，如圖6中的A0～A7分別表示0～7號線程所計算的結果。隨后，同時啟動0～3號線程進行第一次合并，每一個線程都將其塊內線程號對應的數組下標中的值和距離步長為4的另一個值相加，并將結果更新到0～3號線程對應的共享內存數組中，如圖6中的step1所示，其中B0～B3為更新后的結果。step1結束后將步長減半，啟動0～2號線程進行第二次合并，其中C0和C1為更新后的結果。直到第三次合并步長變為1，啟動0號線程計算出的結果D0就是整個線程塊內歸約后的結果。相比于串行歸約在計算效率上得到了極大的提升，其次在設備端進行塊內歸約后使得需要回傳到主機端的數據量減少，進一步降低通信開銷。在實際應用中可以根據GPU的算力大小以及MSM的規模來選擇最佳的窗口大小，進而完成子任務的合理劃分，具體的窗口查找策略見3.2節。

3.2 最佳窗口查找策略

不同的標量窗口會導致子任務的工作負載不同，從圖7可以看出，當MSM的規模為220、窗口大小為9時計算時間為177 ms，然而當窗口調整為11其計算時間增大到了286 ms，相比于最佳的窗口在計算時間上有了0.62倍的差距。因此，在同一規模下不同的窗口對于計算時間的影響是十分顯著的，那么如何在總的線程數量和MSM計算規模一定的情況下找到最佳的窗口就成為了一個關鍵的問題。

橢圓曲線密碼學中，常用的坐標系有仿射坐標系和投射坐標系。仿射坐標系下每個點只需要存儲兩個數據，內存占用更小，一般用于主機端和設備端之間的數據傳輸，投射坐標在進行點加運算時會避免乘法逆元操作，相比于仿射坐標具有更高的計算效率。在MSM的計算過程中主要涉及了相同坐標系的點加（add）和混合坐標系的點加（add_mix），在以往的窗口劃分中都是以點加的數量來衡量工作負載，進而確定最佳的窗口。點加中最主要的計算是大整數的蒙哥馬利模乘，在具體的計算中add的計算量明顯高于add_mix，以目前最常用的也是計算復雜度相對最低的點加公式add-2007-bl為例，add使用了16蒙哥馬利模乘，add_mix使用了11次蒙哥馬利模乘，所以通過點加的數量來衡量工作負載的大小并不合理。

本文根據更為底層的蒙哥馬利模乘計算模塊進行線程任務負載分析來尋找最佳的標量窗口。假設a、b分別表示add_mix和add中使用蒙哥馬利模乘的次數，t為線程數量，up_window表示窗口大小的上限值，cost表示窗口大小為window_size時每一個線程執行的計算任務需要使用的蒙哥馬利模乘的次數，那么最佳窗口查找算法如算法1所示。該算法的核心思想是：逐一遍歷各個窗口，計算出在該窗口劃分下的每一個線程所需要計算的蒙哥馬利模乘的次數，并與現有的最小值對比，從而確定最優的窗口大小。

算法1 最佳窗口查找算法

3.3 標量形式轉換的并行計算

在Pippenger算法的計算過程中提前將標量重新編碼為有符號的二進制形式，可以將桶的數量減半，降低桶間歸約的時間開銷。對此，本文設計了一種標量的形式轉換算法，可以直接將標量的每一個c bit的窗口值固定在［-2c-1，2c-1-1］，從而使Pippenger算法第二步的計算量減半，算法細節如算法2所示，從最低位的窗口開始遍歷，如果當前窗口的十進制數值大于2c-1就將其減去2c，然后將下一個窗口的值加1，否則不變。

算法2 標量形式轉換

對于數百萬規模的MSM，如果在主機端進行數據的處理然后再傳輸到設備端將會產生巨大的計算時延。GPU作為一種支持多線程并發執行的計算平臺，相比于CPU具有支持大規模并行的特征［23］。利用GPU的這種特性來對大規模的標量進行并行計算可以極大地節省計算時間。具體的處理方法如圖8所示。

首先，將N個標量平均分配給所有的線程，假設一共有t個線程，那么每一個線程處理規模為Z=N/t標量形式轉換的計算，經過轉換后原本λ bit的標量變成了L=「λ/c個int類型的數據表示。其次，由于每一個線程對于數據的訪問都是按列進行的，如果按行去存儲會降低緩存的命中率，從而增加數據訪問的延遲。因此，在數據存儲方面，為了能夠實現連續性訪問，選擇將每個標量同一窗口下的數據依次存放在一起，然后放在設備端全局內存中作為MSM計算核心的輸入，無須拷貝到主機端，避免了數據傳輸的時間開銷。雖然，存儲上相比于按行存儲會增加一部分的時間開銷，但可以使在橢圓曲線上的點集從主機端傳輸到設備端的同時，無縫地進行標量形式轉換的并行計算，有效解決了存儲過程中尋址所占用的時間開銷問題。

3.4 基于CPU-GPU異構的MSM整體設計

3.4.1 CPU-GPU異構架構

CPU-GPU異構架構是一種使用CPU和GPU協同工作的計算架構，CPU和GPU具有各自的存儲空間，通過PCI-e總線進行數據傳輸。該架構允許CPU和GPU在處理不同類型的任務時發揮各自的優勢，從而提高整體的性能［24，25］。CUDA作為一種在異構計算環境中實現并行計算的編程框架，它基于NVIDIA的GPU架構提供了專門針對GPU進行并行計算的編程接口和工具集［26］。其異構架構如圖9所示。

3.4.2 整體優化設計

在整體的異構設計中，GPU上的計算模塊主要有標量的形式轉換內核和MSM計算內核，其中標量形式轉換數據依賴于標量集，MSM計算數據依賴于點集和經過形式轉換后的標量。CUDA流作為一種并行計算模型，它是在CUDA編程模型中實現主機端和設備端異步操作的機制。利用CUDA流的異步機制，可以在GPU執行標量形式轉換內核的同時，將點集從主機端傳到設備端。圖10展示了ParMSM與Bellperson的MSM計算方案對比。相比于Bellperson的單個CUDA 流模式，本文將標量集的傳輸和標量形式轉換內核的啟動依次添加到stream1，點集的傳輸和MSM計算內核的啟動以及結果的回傳依次添加到stream2，通過重疊主機端到設備端的數據傳輸和GPU計算提高了系統工作效率。

對于從設備端回傳到主機端的結果，需要進一步計算才能得到最終的結果，由于這部分的數據規模和計算量比較小，同時計算過程中數據的依賴性比較強，所以將該部分的計算放到CPU上。計算細節如算法3所示，從最高位的窗口開始，先將其對應的線程塊結果累加到初始零點，隨后將結果乘以2c繼續累加下一個窗口下的線程塊返回值，直到最低位。其中T是回傳到主機端的所有線程塊進行歸約后的結果，num_window表示一個λ bit的標量被c bit的窗口切分的數量。

算法3 主機端歸約算法

4 系統實現與結果評估

4.1 實驗平臺和環境

本文的實驗是在一臺帶有3.7 GHz的AMD Ryzen 9 5900X處理器（每個處理器有12個核心），12 GB顯存的RTX3060顯卡與128 GB DRAM的服務器上進行的，運行Ubuntu 20.04.5和 CUDA 11.8。

4.2 系統實現

Bellperson 是一個使用Rust編程語言實現的高效的零知識證明庫，可用于構建和驗證零知識證明，已經應用在一個著名的去中心化加密貨幣網絡Filecoin中。本文基于CUDA C平臺實現了更加高效的MSM計算模塊ParMSM，并將其集成在Bellperson中，從而構建一個完整的零知識證明系統，代碼開源在https：//github.com/20171759/msm-stream.git。具體的實現過程如圖11所示。

在目前最新版本的Bellperson中，其最主要的計算被封裝在了EC-GPU庫中。在EC-GPU中使用的是Rust封裝的CUDA API——Rust-GPU-tool，由于其對CUDA的支持比較有限，并不支持CUDA流的操作，這里引入了另一個對CUDA支持更友好的庫RustaCUDA。在數據傳輸過程中，由于Rust封裝的CUDA API只支持最基本的數據類型，并不支持Affine、Projective，Scalar等類型的數據，在EC-GPU中是將所有的數據全部切分成u8的類型，用數組的形式進行存儲，然后再通過PCI-e進行數據傳輸。實際應用中數據位寬高達384 bit，同時數據規模比較大且數據結構比較復雜，導致傳輸效率并不理想。因此，為了提高數據的傳輸效率，在RustaCUDA庫中引入blstrs庫，在底層添加了所需要的數據結構，避免了因數據切分而造成的時間浪費。

對于設備端源碼的調用，本文選擇在主機端使用NVCC編譯器將CUDA源代碼編譯成.fatbin文件，通過調用RustaCUDA庫進行設備查找，創建上下文，加載二進制文件。然后，創建所需要的CUDA流，將需要啟動的任務放到與之對應的流中，最后為了保證CUDA流中操作的正確執行順序和結果，使用RustaCUDA庫中的synchronize（）函數來同步流。

4.3 實驗評估

為了驗證本文方案的有效性，選擇了目前最為主流的Groth16協議的CPU實現版本Bellman和當前應用最為廣泛、性能最優的CPU-GPU異構實現版本Bellperson作為主要的對照實驗。在同類工作對比中選擇了目前最新的cuZK［27］作為對照來評估ParMSM的性能。同時為了驗證ParMSM的通用性，選擇與不同ZKP系統中的MSM進行實驗對比分析。

在實驗數據規模的選擇上，以Filecion應用為例，其在實際應用中數據規模大多數集中在220～221，同時隨著安全性能的提升，數據規模也將變得更高。因此，本文的實驗數據規模選擇到223以上。這樣可以確保本文的方案能夠與業界最為先進的解決方案進行比較，并且充分驗證其有效性。

4.3.1 同類工作對比

文獻［27］提出了一種新的MSM并行計算方法，基于CSR稀疏矩陣來存儲每一個子MSM，利用并行稀疏矩陣轉置算法對其進行并行轉置來保證數據的連續，之后將其系數相同的點都累加到對應的桶中，利用霍納法則將所有桶中的點進行加權求和。最后，基于C語言實現了一個完整的零知識證明庫cuZK。

與cuZK將MSM的計算全部遷移到GPU上不同，本文重點在于研究如何充分利用CPU和GPU的協同計算，根據任務的不同計算特性，靈活地將任務分配給最適配的處理器，以獲得最佳性能。此外，一方面鑒于Rust語言具有出色的內存安全性和并發安全性，能夠防范多種安全漏洞和內存錯誤，從而提高系統的穩定性，本文基于Rust語言實現該CPU-GPU異構加速模塊。另一方面，本文是將異構加速模塊集成到了當前應用最為廣泛的零知識證明庫Bellperson中，以適應更高的應用前景。

cuZK對線程進行組織時使用了太多的線程塊，而每一個線程塊內的線程數量過少，導致了線程塊在流式多處理器之間的頻繁切換；另一方面，為了避免數據傳輸而使用GPU來做串行計算，影響了計算效率。圖12展示了在GPU為RTX 3060，CPU為AMD Ryzen 9 5900X設備上，本文提出的ParMSM與cuZK在219～223規模下完整的MSM計算時間對比。結果表明，ParMSM相比cuZK實現了1.38倍的加速。

4.3.2 ParMSM通用性分析

為了評估本文所提出的ParMSM加速方案的通用性，選擇兩種應用比較廣泛的ZKP系統，針對不同位寬的MSM進行對比分析。halo2和Bulletproofs分別為基于CPU實現的halo協議和Bulletproofs協議的零知識證明開源庫，數據位寬分別位256 bit和320 bit，表1展示了本文提出的ParMSM對比halo2和Bulletproofs的加速效果。結果表明，相比于halo2本文的ParMSM在數據規模為220～224時最高可以獲得289倍的加速比，相比于Bulletproofs最高可以獲得225倍的加速比。因此，ParMSM針對于不同位寬的MSM仍然有穩定的加速效果。

4.3.3 基于ParMSM的Bellperson系統的性能評估

Bellperson是在Bellman系統的基礎上對其中的主要計算模塊基于GPU進行了并行加速，其對MSM任務的劃分相當于圖4的逆過程。首先將MSM的規模均等劃分，然后利用選定的窗口分別對每一個小規模的MSM進行進一步子任務分解。經過分解后每一個小規模的MSM都被劃分成多個同等規模的低位寬的MSM，每一個低位寬的MSM由一個CUDA線程利用桶方法進行計算。等到所有線程都計算完成后將結果傳輸到主機端內存中，在主機端進行加權求和，最終計算出一個完整的MSM。

圖13展示了不同規模下標量形式轉換串行和并行計算時間，可以看出本文提出的對大規模標量形式轉換的并行計算方法比串行計算獲得了97.9倍的加速比。圖14展示了本文提出的集成了ParMSM的Bellperson系統與原Bellperson在不同規模下點集從主機端到設備端數據傳輸時間對比。由于本文在RustaCUDA庫的底層添加了Affine類型的數據結構，減少了數據切分所占用的時間，其傳輸效率相比于Bellperson有了明顯的提升。圖15則展示了本文設計方案中點集的傳輸和標量形式轉換計算時間對比，可以看出GPU進行標量處理所用的時間高于去掉數據切片操作后點集的傳輸時間，低于Bellperson方案中的點集傳輸時間。綜上所述，通過CUDA流技術可以完美地掩蓋通信所占用的時間。

異構設計中，CPU主要負責將回傳的結果進一步處理以得到最終的MSM結果，這部分計算的數據量比較小，經過測試在5900X上的執行時間為4～5 ms。表2展示了本文構建的零知識證明系統與Bellman和Bellperson在不同規模下完整的MSM的計算時間對比，圖16則更直觀地展示了在不同規模下本文與Bellperson的性能對比。實驗結果表明，本文方案相比于Bellman獲得了高達186倍的加速，相比于Bellperosn在220規模時有2.12倍的加速比，在221～224時有1.96倍以上的加速比。在220規模時由于Bellperson中選擇的窗口并不是最佳，所以在220時獲得了更高的加速比，而在221～224規模時其窗口大小為最佳，因此在221～224時獲得穩定的加速比。

5 結束語

本文提出了一種基于GPU的MSM并行加速方案。首先，對MSM進行更細粒度的任務分解，以適應GPU高并行性能。利用共享內存對同一窗口下的子MSM并行歸約，提高計算效率的同時減少數據傳輸。其次，基于底層計算模塊的線程級任務負載分析尋找最佳標量窗口，解決了MSM子任務劃分不合理的問題。最后，對標量形式轉換的數據存儲結構進行優化，并基于GPU對其進行并行計算，通過重疊數據傳輸和計算掩蓋了通信時間。實驗結果表明，與目前應用最為廣泛、性能最優的Bellperson實現以及目前最優的GPU實現cuZK相比，在1b5242c37e72cb68b6091a761f0d9ed0計算效率上有顯著的提高。

在對零知識證明中主要的計算模塊進行加速后其主性能瓶頸已由原來的多標量乘法和多項式運算轉變為R1CS的生成過程。在未來的工作中，計劃為zk-SNARK協議中R1CS的生成過程設計有效的加速方案。

參考文獻：

［1］Goldwasser S， Micali S， Rackoff C. The knowledge complexity of interactive proof-systems［M］. New York： ACM Press， 2019.

［2］Ben-Sasson E， Chiesa A， Tromer E， et al. Succinct{non-interactive}zero knowledge for a von Neumann architecture［C］//Proc of the 23rd USENIX Security Symposium. Berkeley， CA： USENIX Association， 2014： 329-349.

［3］Banerjee A， Clear M， Tewari H. Demystifying the role of zk-SNARKs in Zcash［C］//Proc of IEEE Conference on Application， Information and Network Security. Piscataway， NJ： IEEE Press， 2020： 12-19.

［4］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： 394-411.

［5］Kosba A， Miller A， Shi A， et al. Hawk： the blockchain model of cryptography and privacy-preserving smart contracts［C］//Proc of IEEE Symposium on Security and Privacy. Piscataway， NJ： IEEE Press， 2016： 839-858.

［6］Liu Jingwei， Jiang Weiyang， Sun Rong， et al. Conditional anonymous remote healthcare data sharing over blockchain［J］. IEEE Journal of Biomedical and Health Informatics， 2023，27（5）： 2231-2242.

［7］Patel R， Migliavacca M， Oriani M E. Blockchain in banking and finance： a bibliometric review［J］. Research in International Business and Finance， 2022，62： 101718.

［8］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.

［9］趙海旭， 柴志雷， 花鵬程， 等. zk-SNARK中數論變換的硬件加速方法研究［J］. 計算機科學與探索， 2024，18（2）：538-552. （Zhao Haixu， Chai Zhilei， Hua Pengcheng， et al. Hardware accele-ration of number theoretic transform for zk-SNARK［J］. Journal of Frontiers of Computer Science and Technology， 2024，18（2）：538-552.）

［10］Cilliers S， Mishra A K. Exploration of algorithms for the hardware acceleration of multi-scalar multiplication on FPGA［C］//Proc of International Conference on Emerging Trends in Networks and Computer Communications. Piscataway， NJ： IEEE Press， 2023： 264-274.

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

［12］Wu Guiming， He Qianwen， Jiang Jiali， et al. A high-performance hardware architecture for ECC point multiplication over Curve25519［C］//Proc of the 30th Annual International Symposium on Field-Programmable Custom Computing Machines. Piscataway， NJ： IEEE Press， 2022： 1-9.

［13］Yang Kang， Wang Xiao. Non-interactive zero-knowledge proofs to multiple verifiers［C］//Proc of International Conference on Theory and Application of Cryptology and Information Security. Cham： Springer， 2022： 517-546.

［14］Botrel G， El Housni Y. Faster Montgomery multiplication and multi-scalar-multiplication for SNARKs［J］. IACR Trans on Cryptographic Hardware and Embedded Systems， 2023（3）：504-521.

［15］Hijma P， Heldens S， Sclocco A， et al. Optimization techniques for GPU programming［J］. ACM Computing Surveys， 2023，55（11）： 1-81.

［16］Qi Huayi， Cheng Ye， Xu MingHui， et al. Split： a hash-based me-mory optimization method for zero-knowledge succinct non-interactive argument of knowledge（zk-SNARK）［J］. IEEE Trans on Compu-ters， 2023，72（7）： 1857-1870.

［17］Ishai Y， Kushilevitz E， Ostrovsky R， et al. Zero-knowledge proofs from secure multiparty computation［J］. SIAM Journal on Computing， 2009，39（3）： 1121-1152.

［18］Guan Zhangshuang， Wan Zhiguo， Yang Yang， et al. BlockMaze： an efficient privacy-preserving account-model blockchain based on zk-SNARKs［J］. IEEE Trans on Dependable and Secure Computing， 2022， 19（3）： 1446-1463.

［19］Reddy S B. A zk-SNARK based proof of assets protocol for bitcoin exchanges［C］//Proc of the 15th International Conference on Communication Systems & Networks. Piscataway， NJ： IEEE Press， 2023： 135-140.

［20］Groth J. On the size of pairing-based non-interactive arguments［C］//Proc of the Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2016： 305-326.

［21］Pippenger N. On the evaluation of powers and related problems［C］//Proc of the 17th Annual Symposium on Foundations of Computer Science. Piscataway， NJ： IEEE Press， 1976： 258-263.

［22］Phalakarn K， Suppakitpaisarn V. Optimal representation for right-to-left parallel scalar and multi-scalar point multiplication［J］. International Journal of Networking and Computing， 2018，8（2）： 166-185.

［23］Liu Chenran， Feng Jian， Fang Ming. Heterogeneous CPU-GPU acce-lerated parallel subgridding FDTD algorithm［C］//Proc of Internatio-nal Applied Computational Electromagnetics Society Symposium. Piscataway， NJ： IEEE Press， 2023： 1-3.

［24］張峰， 翟季冬， 陳政， 等. 面向異構融合處理器的性能分析， 優化及應用綜述［J］. 軟件學報， 2020， 31（8）： 2603-2624. （Zhang Feng， Zhai Jidong， Chen Zheng， et al. Survey on performance analysis， optimization， and applications of heterogeneous fusion processors［J］. Journal of Software， 2020，31（8）： 2603-2624.）

［25］Fang Juan， Zhou Kuan， Tan Chen， et al. Dynamic block size adjustment and workload balancing strategy based on CPU-GPU heterogeneous platform［C］//Proc of IEEE International Conference on Parallel & Distributed Processing with Applications， Big Data & Cloud Computing， Sustainable Computing & Communications， Social Computing & Networking. Piscataway， NJ： IEEE Press， 2019： 16-18.

［26］Zhou Tao， Cai Qiangming， Cao Xin， et al. GPU-accelerated HO-SIE-DDM using NVIDIA CUDA for analysis of multiscale problems［C］//Proc of Asia-Pacific International Symposium on Electromagnetic Compatibility. Piscataway， NJ： IEEE Press， 2022： 1-4.

［27］Lyu Tao， Wei Chenkun， Yu Ruijing， et al. cuZK： accelerating zero-knowledge proof with a faster parallel multi-scalar multiplication algorithm on GPUs［J］. IACR Trans on Cryptographic Hardware and Embedded Systems， 2023（3）： 194-220.