一文了解FPGA 和GPU 加速零知識證明計算的優缺點

本文詳細分析了MSM 算法，橢圓曲線點加算法，蒙哥馬利乘法算法等等，並對比了GPU 和FPGA 在BLS12_381 曲線點加的性能差別。

撰文：Star Li

零知識證明技術應用越來越廣，隱私證明，計算證明，共識證明等等。在尋找更多更好的應用場景的同時，很多人逐步發現零知識證明證明性能是個瓶頸。 Trapdoor Tech 團隊從2019 年開始深入研究零知識證明技術，並一直探索高效的零知識證明加速方案。 GPU 或者FPGA 是目前市面上比較常見的加速平台。本文從MSM 的計算入手，分析FPGA 和GPU 加速零知識證明計算的優缺點。

長話短說；博士

ZKP 是擁有未來廣泛前景的技術。越來越多的應用開始採用零知識證明技術。但ZKP 算法比較多，各種項目使用不同的ZKP 算法。同時，ZKP 證明的計算性能比較差。本文詳細分析了MSM 算法，橢圓曲線點加算法，蒙哥馬利乘法算法等等，並對比了GPU 和FPGA 在BLS12_381 曲線點加的性能差別。總的來說，在ZKP 證明計算方面，短期GPU 優勢比較明顯，Throughput 高，性價比高，具有可編程性等等。 FPGA 相對來說，功耗有一定的優勢。長期看，有可能出現適合ZKP 計算的FPGA 芯片，也可能為ZKP 定制的ASIC 芯片。

ZKP 算法複雜

ZKP 是個零知識證明技術的統稱（Zero Knowledge Proof）。主要由兩種分類：zk-SNARK 以及zk-STARK。 zk-SNARK 目前常見的算法是Groth16，PLONK，PLOOKUP，Marlin 和Halo/Halo2。 zk-SNARK 算法的迭代主要是沿著兩條方向：1/ 是否需要trusted setup 2/ 電路結構的性能。 zk-STARK 算法的優勢是毋需trusted setup，但是驗證計算量是對數線性的。

就zk-SNARK/zk-STARK 算法的應用來看，不同項目使用的零知識證明算法相對分散。 zk-SNARK 算法應用中，因為PLONK/Halo2 算法是universal（無需trusted setup），應用可能越來越多。

PLONK 證明計算量

以PLONK 算法為例，剖析一下PLONK 證明的計算量。

PLONK 證明部分的計算量由四部分組成：

1/ MSM - Multiple Scalar Multiplication。 MSM 經常用來計算多項式承諾。

2/ NTT 計算- 多項式在點值和係數表示之間變換。

3/ Polynomial 計算- 多項式加減乘除。多項式求值（uation）等等。

4/ Circuit Synthesize - 電路綜合。這部分的計算和電路的規模/ 複雜度有關。

Circuit Synthesize 部分的計算量一般來說判斷和循環邏輯比較多，並行度比較低，更適合CPU 計算。通常來講，零知識證明加速一般指的是前三部分的計算加速。其中，MSM 的計算量相對來說最大，NTT 次之。

什麼是 MSM

MSM（Multiple Scalar Multiplication）指的是給定一系列的橢圓曲線上的點和標量，計算出這些點加的結果對應的點。

比如說，給定一個橢圓曲線上的一系列的點：

給定一條指定曲線的一組固定橢圓曲線點：

[G_1, G_2, G_3, …, G_n]

以及隨機的係數：

以及來自指定標量場的隨機採樣的有限域元素：

[s_1, s_2, s_3, …, s_n]

MSM是計算得到橢圓曲線點Q：

Q = \sum_{i=1}^{n}s_i*G_i

行業普遍採用Pippenger 算法對MSM 計算進行優化。深入看看Pippenger 算法的過程的示意圖：

Pippenger 算法的計算過程分成兩步：

1/ Scalar 切分為Windows。如果Scalar 是256bits，並且一個Window 是8bits，則所有的Scalar 切分為256/8=32 個Window。每一層的Window，採用一個「Buckets」臨時存放中間結果。 GW_x 就是一層上的累加結果的點。計算GW_x 也比較簡單，依次遍歷一層中的每個Scalar，根據Scalar 這層的值作為Index，將對應的G_x 加到相應的Buckets 的位上。其實原理也比較簡單，如果兩個點加的係數相同，則先將兩個點相加後再做一次Scalar 加，而不需要兩個點做兩次Scalar 加後再累加。

2/ 每個Window 計算出來的點，再通過double-add 的方式進行累加，從而得到最後的結果。

Pippenger 算法也有很多變形優化算法。不管怎麼說，MSM 算法的底層計算就是橢圓曲線上的點加。不同的優化算法，對應不同的點加個數。

橢圓曲線點加（Point Add）

你可以從這個網站看看具有「short Weierstrass」形式的橢圓曲線上點加的各種算法。

假設兩個點的Projective 坐標分別為（x1, y1, z1) 和（x2, y2, z2) ，則通過如下的計算公式可以計算出點加的結果(x3, y3, z3)。

詳細給出計算過程的原因是想表明整個計算過程絕大部分是整數運算。整數的位寬取決於橢圓曲線的參數。給出一些常見的橢圓曲線的位寬：

• BN256 - 256 位
• BLS12_381 - 381 位
• BLS12_377 - 377 位
• 特別注意的是，這些整數運算是在模域上的運算。模加/ 模減相對來說簡單，重點看看模乘的原理和實現。

模乘（模乘）

給定模域上的兩個值：x 和y。模乘計算指的是x*y mod p。注意這些整數的位寬是橢圓曲線的位寬。模乘的經典算法是蒙哥馬利乘法（MontgomeryMuliplication)。在進行蒙哥馬利乘法之前，被乘數需要轉化為蒙哥馬利表示：

蒙哥馬利乘法計算公式如下：

蒙哥馬利乘法實現算法又有很多：CIOS (Coarsely Integrated Operand Scanning)，FIOS（Finely Integrated Operand Scanning），以及FIPS（Finely Integrated Product Scanning）等等。本文不深入介紹各種算法實現的細節，感興趣的讀者可以自行研究。

為了對比FPGA 以及GPU 的本身的性能差別，選擇最基本的算法實現方法：

簡單的說，模乘算法可以進一步分成兩種計算：大數乘法和大數加法。理解了MSM 的計算邏輯的基礎上，可以選擇模乘的性能（Throughput）來對比FPGA 和GPU 的性能。

觀察和思考

在這樣的FPGA 設計下，可以估算出整個VU9P 能提供的在BLS12_381 橢圓曲線點加Throughput。一個點加（add_mix 方式）大約需要12 個模乘。 FPGA 的系統時鐘為450M。

在同樣的模乘/ 模加算法下，採用同樣的點加算法，Nvidia 3090 的點加Troughput（考慮到數據傳輸因素）超過500M/s。當然，整個計算涉及到多種算法，可能存在某些算法適合FPGA，有些算法適合GPU。採用一樣的算法對比的原因，想對比FPGA 和GPU 的核心計算能力。

基於上述的結果，總結一下GPU 和FPGA 在ZKP 證明性能方面的比較：

總結

越來越多的應用開始採用零知識證明技術。但ZKP 算法比較多，各種項目使用不同的ZKP 算法。從我們的實踐工程經驗來看，FPGA 是個選項，但是目前GPU 是個性價比高選項。 FPGA 偏好確定性計算，有latency 以及功耗的優勢。 GPU 可編程性高，有相對成熟的高性能計算的框架，開發迭代周期短，偏好需要throughput 場景。