迄今的故事
零知識證明（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應用方面發揮關鍵作用。
Snark vs Stark
如今有兩種流行的零知識技術，即zk-STARK和zk-SNARK（在本文中我們忽略了Bulletproofs）。
zk-STARKzk-SNARKComplexity – ProverO(N * poly-log(N))O(N * log(N))Complexity – VerifierO(poly-log(N))O(1)Proof size45KB-200KB~ 288 Bytes抗量子Yes (hash function based)NoTrusted setupNoYesZero KnowledgeYesYesInteractivity
Interactive or
non-interactive
Non interactive開發者文件有限，但正在擴展良好
表1：Snark VS Stark
如上所述，兩者之間存在不同之處和權衡。最重要的一點是，基於zk-SNARK的系統的可信任設定依賴於至少有一個誠實的參與者參與了可信任設定過程並在過程結束後銷毀了他們的金鑰。在鏈上驗證方面，zk-SNARK在gas費方面便宜得多。此外zk-SNARK的證明也明顯更小，使其在鏈上儲存更為便宜。
目前，zk-SNARKs比zk-STARKs更受歡迎。最可能的原因是zk-SNARKs的歷史更為悠久。另一個可能的原因是Zcash——最早的ZK區塊鏈之一使用了zk-SNARKs，因此目前大多數開發工具和文件都圍繞著zk-SNARK生態系統。
How to build a ZK Application
開發人員可能需要兩個元件來完成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友善的，就會變得複雜。
Proving System
可以將證明系統類比為一種軟體，主要完成兩項任務：產生證明和驗證證明。證明系統通常接受電路、證據和公共/私有參數作為輸入。
兩個最受歡迎的證明系統是Groth16和PLONK系列（Plonk,HyperPlonk, UltraPlonk）
Trusted SetupProof size
Prover
複雜度
Verifier 複雜度彈性Groth16Circuit specificsmallLowLowLowPlonkUniversalLargeHigh常數High
表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 VS 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
多標量乘法（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也可能發展，為大規模證明生成器和低功耗設備提供極為高效的解決方案（詳情請參閱先前的文章）。
