硬體加速驅動的ZK新紀元

迄今的故事

零知識證明（ZKP）對於去中心化系統的重要性日益增加。 ZK最初是因為在ZCash等專案中大放異彩而走入公眾視野的，但今天ZK是作為乙太坊的一種擴容解決方案而為人們所熟知。

利用ZK，Layer 2（例如Scroll和Polygon）也被稱為Rollups，正在開發zkEVMs（zk乙太坊虛擬機）。 這些zkEVMs處理一批交易，並生成一個小型的證明（以KB為單位的大小）。 此證明可以用來向整個網路驗證該批交易都是有效且正確的。

然而，它們的用途並不止於此。 ZK允許各種有趣的應用。

私有的Layer 1 - 例如Mina，它隱藏了其區塊鏈上的交易和數據的細節，允許使用者僅證明其交易的有效性，而無需透露交易本身的具體資訊。 neptune.cash 和Aleo也是非常有趣的專案。

去中心化的雲平臺 - FedML和 together.xyz 允許以去中心化的方式訓練機器學習（ML）模型，將計算外包給網路，並使用ZKP驗證計算的正確性。 Druglike正在利用類似的技術構建一個更加開放的藥物發現平臺。

去中心化存儲 - Filecoin正在為雲存儲帶來革命性的改變，而ZK正是其核心，允許存儲供應商證明他們在一段時間內存儲了正確的數據。

遊戲 - 更高級的Darkforest版本可能會出現，這需要實時證明。 ZK可能還會擴展遊戲，減少作弊的可能性。 也許還能與去中心化的雲平臺配合，使遊戲能夠支付自己的託管費用！

身份 - 現在也可以通過ZK實現去中心化的身份認證。 圍繞這個想法，正在建立許多有趣的專案。 比如notebook和zkemail（推薦瞭解一下）。

ZK和去中心化系統的影響非常巨大，然而，故事的發展並非盡善盡美，現如今仍然存在許多障礙和挑戰。 包括生成證明的過程非常消耗資源，需要進行多次複雜的數學運算。 隨著開發者們尋求利用ZK技術構建更為雄心勃勃且複雜的協定和系統，無論是對於證明的生成還是驗證過程，開發者們會要求更小的證明大小、更快的性能和更好的優化。

在本文中，我們將探討硬體加速的現狀，以及它將如何在推進ZK應用方面發揮關鍵作用。

斯納克 vs 斯塔克

如今有兩種流行的零知識技術，即zk-STARK和zk-SNARK（在本文中我們忽略了Bulletproofs）。

| | | | |--- |--- |--- | |zk-斯塔克 |zk-SNARK系列 | | |複雜性 - Prover |O（N * poly-log（N）） |O（N * log（N）） | |複雜性 - Verifier |O（poly-log（N）） |O（1） | |證明尺寸 |45KB-200KB |~ 288 位元組 | |抗量子 |是（基於哈希函數）|否 | |受信任的設置 |否 |是 | |零知識 |是 |是 | |互動性 |互動或非互動 |非互動式 | | 開發者文檔 | 有限，但正在擴展 | 良好 |

表1：Snark VS Stark

如上所述，兩者之間存在不同之處和權衡。 最重要的一點是，基於zk-SNARK的系統的可信設置依賴於至少有一個誠實的參與者參與了可信設置過程並在過程結束後銷毀了他們的密鑰。 在鏈上驗證方面，zk-SNARK在gas費方面要便宜得多。 此外zk-SNARK的證明也明顯更小，使其在鏈上存儲更為便宜。

目前，zk-SNARKs比zk-STARKs更受歡迎。 最可能的原因是zk-SNARKs的歷史更為悠久。 另一個可能的原因是Zcash——最早的ZK區塊鏈之一使用了zk-SNARKs，因此目前大多數開發工具和文檔都圍繞zk-SNARK生態系統展開。

如何構建 ZK 應用程式

開發人員可能需要兩個元件來完成ZK應用的開發

一種 ZK-friendly 表達計算的方法（DSL或底層庫）。

一個證明系統，該系統應實現兩個功能：Prove（證明）和Verify（驗證）。

DSLs （domain-specific language） 和 底層庫

在DSL方面，選擇非常多，例如Circom、Halo2、Noir等等。 目前Circom可能是最受歡迎的。
在底層庫方面，一個流行的例子是Arkworks; 還有一些正在開發中的庫，如ICICLE，它是一個CUDA加速庫。

這些DSL被設計用來輸出約束系統。 與通常的程式不同（通常以x ：= y * z的形式進行求值），在約束形式中的相同程式看起來更像x - y * z = 0。 通過將程式表示為約束系統，我們發現諸如加法或乘法之類的操作可以用單個約束來表示。 然而，更複雜的操作，如位操作，可能需要數百個約束！

因此，將某些哈希函數實現為ZK友好程式變得複雜。 在零知識證明中，哈希函數通常用於確保數據的完整性和/或驗證數據的特定屬性，但由於位操作的約束數量較多，使得某些哈希函數難以適應零知識證明的環境。 這種複雜性可能會影響到證明生成和驗證的效率，從而成為開發者在構建基於ZK的應用時需要考慮和解決的問題

因此，將某些哈希函數實現為ZK友好的，就會變得複雜。

證明

可以將證明系統類比為一種軟體，主要完成兩項任務：生成證明和驗證證明。 證明系統通常接受電路、證據和公共/私有參數作為輸入。

兩個最流行的證明系統是Groth16和PLONK系列（Plonk，HyperPlonk， UltraPlonk）

| | | | | | | |--- |--- |--- |--- |--- |--- | | | Trusted Setup | Proof size | Prover複雜度 | Verifier 複雜度 | 靈活性 | |格羅斯16 |特定電路 |小 |低 |低 |低 | |普隆克 |通用 |大 |高 |常數 |高 |

表2：Groth16 vs Plonk

如表2所示Groth16需要一個可信設置過程，但Groth16為我們提供了更快的證明和驗證時間，以及恆定的證明大小。

Plonk提供了一個通用的設置，每次生成證明時，都會為你運行的電路執行一個預處理階段。 儘管支援許多電路，Plonk的驗證時間是恆定的。

在約束方面，兩者也存在差異。 Groth16的約束大小呈線性增長，缺乏靈活性，而Plonk則更加靈活。

總的來說，要明白性能直接與你的ZK應用程式的約束數量相關。 約束越多，證明者必須計算的操作就越多。

瓶頸

證明系統包含兩個主要的數學運算：多標量乘法（MSM）和快速傅里葉變換（FFT）。 今天我們將探討兩者都存在的系統，在這樣的系統中，MSM可能佔用約60%的運行時間，而FFT佔用約30%。

MSM需要大量的記憶體訪問，這在大多數情況下會消耗機器的大量記憶體，同時還要執行許多標量乘法運算。

FFT演算法通常需要將輸入數據重新排列成特定順序以執行變換。 這可能需要大量的數據移動，並可能成為瓶頸，特別是對於大的輸入大小。 如果記憶體訪問模式不適合緩存層次結構，緩存利用率也可能成為問題。

**在這種情況下，硬體加速是全面優化ZKP性能的必由之路。 **

硬體加速

談起硬體加速，這讓人回想起ASICs和GPUs是如何主宰比特幣和乙太坊的挖礦。

雖然軟體優化同樣非常重要且有價值，但它們有其局限性。 而硬體優化可以通過設計帶有多個處理單元的FPGAs來提高並行性，例如減少線程同步或向量化。 通過改進記憶體層次結構和訪問模式，記憶體訪問也能更有效地得到優化。

如今在ZKP領域，主要趨勢似乎轉向了：GPU和FPGA。

短期內，GPU在價格上具有優勢，特別是在ETH轉向權益證明（POS）后，使得大量的GPU礦機閑置，處於待命狀態。 此外GPU還具有開發週期短的優點，併為開發者提供大量“即插即用”的並行性。

然而，FPGA應在迎頭追趕，特別是在比較外形尺寸和功耗時。 FPGA也為高速數據流提供了更低的延遲。 當多個FPGAs聚集在一起時，它們與GPU集群相比提供了更好的性能。

GPU 與 FPGA

GPU：

**開發時間：**GPU提供了快速的開發時間。 像CUDA和OpenCL這樣的框架開發者文檔完善且受歡迎。

**功耗：**GPU非常“耗電”。 即使開發者在利用數據級並行性和線程級並行性時，GPU仍然消耗大量的電力。

可用性：目前消費級的GPU價格便宜且容易獲得。

FPGA：

**開發週期：**FPGA有一個更複雜的開發週期，並需要更專業的工程師。 FPGAs允許工程師實現許多GPU無法實現的「底層」優化。

**延遲：**FPGAs特別是在處理大數據流時提供了較低的延遲。

成本與可用性：FPGA比GPU更昂貴，並且不如GPU那樣容易獲得。

ZPRIZE獎

如今提到硬體優化與ZKP的瓶頸，那就繞不開一個比賽-ZPRIZE

ZPrize是當前ZK領域中最重要的舉措之一。 ZPrize是一個競賽，鼓勵團隊為ZKP的關鍵瓶頸（如MSM、NTT、Poseidon等）在多種平臺（如FPGA、GPU、行動裝置和瀏覽器）上開發硬體加速，評判標準為延遲、輸送量和效率。

結果非常有趣。 例如，GPU的改進非常巨大：

degree為2^26下的MSM從5.86秒提高到2.52秒，提高了131%。 另一方面，與GPU的結果相比，FPGA解決方案往往沒有任何基準測試，GPU結果有先前的基準測試可供比較，而大多數FPGA解決方案都是首次開源這樣的演算法，預計未來會有所改進。

這些結果表明瞭大多數開發者在開發他們的硬體加速解決方案時所感到舒適的方向。 許多團隊為GPU類別競爭，但只有很少一部分團隊為FPGA類別競爭。 我不確定這是因為在為FPGA開發時缺乏經驗，還是大部分FPGA公司/團隊選擇秘密開發以商業化出售他們的解決方案。

ZPrize向社區提供了一些非常有趣的研究成果。 隨著ZPrize更多輪次的開始，我們將看到越來越多有趣的解決方案和問題的出現。

硬體加速的實際例子

以Groth16為例，如果我們檢查rapidsnark對Groth16的實現，可以觀察到主要執行了兩個操作：FFT（快速傅立葉變換）和MSM（多標量乘法）; 這兩種基本運算在許多證明系統中都是常見的。 它們的執行時間直接與電路的約束數量相關。 自然地，隨著編寫更複雜的電路，約束的數量會增加。

為了直觀地理解與感受FFT與MSM操作到底佔據了多大的計算量，我們可以查看Ingonyama對Groth16電路（在32GB扇區上執行的Filecoin的Vanilla C2過程）進行的基準測試，結果如下

如上圖所示，對於許多證明者來說，MSM（多標量乘法）可能會佔用大量的運行時間，並成為一個嚴重的性能瓶頸，這就使得MSM成為需要加速的重要密碼學算子之一。

那麼MSM在其他ZK證明系統中又會佔據證明者多少的計算量呢？ 如下圖所示

在Plonk中，MSM的開銷佔比來到了85%以上，圖片來自**Ingonyama最新論文Pipe MSM。 **

**所以硬體加速應當如何加速MSM？ **

男男性行為者

在談如何加速MSM之前，我們需要理解什麼是MSM

**多標量乘法（MSM， Multi-Scalar Multiplication）**是一種用於計算多個標量乘法之和的演算法，形式如下

其中G是橢圓曲線群中一點，a是標量，MSM的結果也會是一個橢圓曲線點

我們可以將MSM分解為兩個主要的子元件：

模乘法（Modular Multiplication）

橢圓曲線點加法（Elliptic Curve Point Addition）

我們以Affine（x，y）類型的點為例，進行樸素的P+Q運算。

當我們想要計算P + Q=R時，我們需要計算一個值k，通過k與P，Q的橫座標從而

獲得R的座標. 計算過程如上，在這個過程裡面我們進行了2次乘法，1次平方，1次求逆運算，以及若干次加法 減法運算。 值得注意的是，**上述運算都是在有限域當中進行的，也就是mod P下的運算。 實際當中，P會非常的大。 **

上述運算的開銷為 求逆>>乘法 **>****平方，**加減法的開銷可忽略。

所以我們希望盡量避免求逆運算，因為一次求逆的開銷至少是乘法的百倍。 通過拓展座標系我們就可以做到這一點，但是代價是過程的乘法數量會相應增加一些，如 **Jacobian座標： XYZ += XYZ，乘法會增加到10次以上，****具體取決於加法演算法。 **

GPU VS FPGA 加速MSM

本節將比較兩個領先的MSM實現，PipeMSM和Sppark，其中PipeMSM在FPGA上實現，而Sppark在GPU上實現。

Sppark和PipeMSM使用最先進的Pippenger演算法 實現MSM，也被稱為**bucket演算法; **

Sppark使用CUDA實現; 它們的版本具有高度的並行性，並在最新的GPU上運行時取得了令人印象深刻的結果。

然而，PipeMSM不僅優化了演算法，還為模數乘法（Modular Multiplication）和橢圓曲線點加法（EC Addition）的數學基元提供了優化。 PipeMSM處理了整個「MSM堆疊」，實現了一系列的數學技巧和優化，旨在使MSM更適合硬體，並設計了一種旨在降低延遲以及重點關注並行化的硬體設計。

下面讓我們快速回顧一下PipeMSM的實現。

低延遲
PipeMSM旨在在對大量輸入執行多個MSM時提供低延遲。 由於動態頻率縮放的原因，GPU不能提供確定性的低延遲，GPU會根據工作負載調整其時鐘速度。

但是由於優化的硬體設計，FPGA實現可以為特定工作負載提供確定的性能和延遲。

EC加法實現

橢圓曲線點加法（EC Addition）被實現為低延遲、高度並行且完整的公式（完整意味著它正確計算了橢圓曲線群中任何兩點的和）. 橢圓曲線點加法在EC加法模組中以流水線方式使用，以減少延遲。

我們選擇將座標表示為射影座標，在加法演算法上我們使用一個Complete橢圓曲線點加法公式。 主要優點是我們不必處理邊緣情況。 完整的公式;

我們以流水線和並行的方式實現了這個加法公式，我們的FPGA橢圓曲線加法器電路只需12次乘法、17次加法和就能執行這個公式。 而原始公式需要15次模乘法、13次加法。 FPGA設計如下

模乘實現（multi mod）

我們利用了Barrett Reduction和 Karatsuba 演算法。

Barrett Reduction是一種有效計算 r≡ab mod p （其中 p 是固定的）的演算法。 Barrett Reduction試圖通過近似除法來替換除法（一種昂貴的操作）。 可以選擇一個誤差容限來描述我們尋找正確結果的範圍。 我們發現，較大的誤差容限允許使用較小的約化常數; 這減小了模約化操作中使用的中間值的大小，從而減少了計算最終結果所需的乘法次數。

在下面的藍色方框中，我們可以看到，由於我們的高誤差容限，我們必須進行多次檢查以找到準確的結果。

簡而言之，Karatsuba演算法用於優化我們在Barrett Reduction中執行的乘法。 Karatsuba演算法將兩個n位數的乘法簡化為三個n/2位數的乘法; 這些乘法可以將位數簡化到足夠窄，直到可以直接由硬體計算。 細節可以閱讀Ingo的paper：Pipe MSM

利用上述算子，我們開發了一個低延遲、高度並行的MSM實現。

核心思想是：不是一次計算整個MSM，而是並行地將每個chunk傳遞到EC加法器中。 EC加法器的結果累積到最終的MSM中。

最終結果****

上圖展示了Sppark和PipeMSM之間的比較。

最突出的是FPGA提供的顯著節能效果，對於未來大規模證明生成操作來說，這可能極為重要。 值得注意的是，我們的實現是在@125MHz下進行原型設計和基準測試的，將時鐘速度提高到@500MHz可能會將計算時間提高4倍或更多。

使用我們的FPGA的另一個優勢是，由於它們消耗的能量較少，產生的熱量也較少，因此可以將它們安裝在小型機箱伺服器中。

我們正處於用於ZKP的FPGA工程的初期階段，應該期待演算法的進一步改進。 此外，FPGA在計算MSM的時候，CPU正處於空閒狀態，通過將FPGA與系統資源（CPU/GPU）結合使用，可能可以實現更快的時間。

總結

ZKP已成為分散式系統的關鍵技術。

ZKP的應用將遠遠超越僅僅擴展乙太坊這個層面，而是允許將計算外包給不受信任的第三方，允許開發以前不可能的系統，例如分散式雲計算、身份系統等等。

傳統上，ZKP的優化主要集中在軟體級別的改進上，但隨著對更卓越性能的需求增加，我們將看到更多涉及硬體和軟體的先進加速解決方案。

目前我們主要看到的加速方案使用的是GPU，這是因為使用CUDA的開發時間短，而且目前消費級GPU非常便宜且豐富。 GPU還提供了令人難以置信的性能。 所以GPU不太可能在短期內從這個領域消失。

隨著更多複雜的開發團隊進入該領域，我們很可能會看到FPGA在功耗效率和性能方面處於領先地位。 與GPU相比，FPGA提供了更多底層定製以及更多配置選項。 與ASIC相比，FPGA具有更快的開發速度和靈活性。 隨著ZKP世界的快速發展，FPGA可以使用不同的程式重新刷寫以適應不同的系統和更新解決方案。

然而，要生成接近即時的證明，可能需要根據我們為其生成證明的系統，將GPU/FPGA/ASIC配置組合在一起。

ZPU也可能會發展，為大規模證明生成器和低功耗設備提供極為高效的解決方案（詳情見之前的文章）。