作者：Star Li
本文僅做行業學習交流之用，不構成任何投資參考。如需引用，請註明來源，轉載請聯繫IOSG 團隊獲取授權及轉載須知。特別感謝作者Star Li 提供的內容！
零知識證明技術應用越來越廣，隱私證明，計算證明，共識證明等等。在尋找更多更好的應用場景的同時，很多人逐步發現零知識證明證明性能是個瓶頸。 Trapdoor Tech 團隊從2019 年開始深入研究零知識證明技術，並一直探索高效的零知識證明加速方案。 GPU 或者FPGA 是目前市面上比較常見的加速平台。本文從MSM 的計算入手，分析FPGA 和GPU加速零知識證明計算的優缺點。
TL;DR
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計算- 多項式加減乘除。多項式求值（Evaluation）等等。
4/ Circuit Synthesize - 電路綜合。這部分的計算和電路的規模/複雜度有關。
Circuit Synthesize部分的計算量一般來說判斷和循環邏輯比較多，並行度比較低，更適合CPU計算。通常來講，零知識證明加速一般指的是前三部分的計算加速。其中，MSM的計算量相對來說最大，NTT次之。
What's MSM
MSM（Multiple Scalar Multiplication）指的是給定一系列的橢圓曲線上的點和標量，計算出這些點加的結果對應的點。
比如說，給定一個橢圓曲線上的一系列的點：
Given a fixed set of Elliptic curve points from one specified curve:
[G_1, G_2, G_3, ..., G_n]
以及隨機的係數：
and a randomly sampled finite field elements from specified scalar field:
[s_1, s_2, s_3, ..., s_n]
MSM is the calculation to get the Elliptic curve point 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”形式的橢圓曲線上點加的各種算法。
http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
假設兩個點的Projective坐標分別為（x1, y1, z1) 和（x2, y2, z2) ，則通過如下的計算公式可以計算出點加的結果(x3, y3, z3)。
詳細給出計算過程的原因是想表明整個計算過程絕大部分是整數運算。整數的位寬取決於橢圓曲線的參數。給出一些常見的橢圓曲線的位寬：
- BN256 - 256bits
- BLS12_381 - 381bits
- BLS12_377 - 377bits
特別注意的是，這些整數運算是在模域上的運算。模加/模減相對來說簡單，重點看看模乘的原理和實現。
模乘（Modular Muliplication）
給定模域上的兩個值：x和y。模乘計算指的是x*y mod p。注意這些整數的位寬是橢圓曲線的位寬。模乘的經典算法是蒙哥馬利乘法（Montgomery Muliplication)。在進行蒙哥馬利乘法之前，被乘數需要轉化為蒙哥馬利表示：
蒙哥馬利乘法計算公式如下：
蒙哥馬利乘法實現算法又有很多：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場景。
APP 
