FPG:Figment Capital：深入解讀零知識證明加速

原文標題：AcceleratingZero-KnowledgeProofs

原文作者：FigmentCapital

原文編譯：Lynn，MarsBit

零知識證明允許一個團體在向另一個團體證明一條聲明時不需要透露除去「該聲明為真實的」的信息以外的任何額外信息。盡管這項密碼原語早在上世紀八十年代就已出現，但直到區塊鏈技術的萌發，零知識證明才發現其實際應用，包括區塊鏈擴展、隱私、互操作性，和身份。

盡管聲稱其可以解決區塊鏈技術中的許多最重大的難題，零知識證明仍舊是一項不成熟的技術。在這些問題之中，最主要的其中之一是其證明時間之久。零知識技術應用在不斷改進，其證明的復雜程度也在改進。這些聲明需要更大的算數電路，導致證明時間飆升。生產一個零知識證明可能需要比底層計算增加多達百萬倍。相應地，有大量的團隊正在研究可以改進加速零知識證明所需要的軟件和硬件。

在本文中，我們將提供加速零知識證明的概覽。我們將總結生產零知識證明的主要操作作為討論的起點，并在之后轉向討論這些操作可以如何被加速。

快速上手：什么是零知識證明？

零知識證明允許一方，向另一方證明他們成功地完成了一次計算。一個零知識證明擁有以下三個關鍵特性：

完整性：如果證明者生成了一項有效的證明，一個誠實的驗證者將視該聲明是有效的。

合理性：如果該聲明是虛假的，一個證明者將無法生成一項看起來有效的證明。

零知識：如果該聲明是真實的，一個驗證者不會知道除去「該聲明是真實的」以外的任何信息。

區塊鏈背景下最主要的零知識證明的類型是zk-SNARK。這終證明在上述的傳統的零知識證明的三個特性之上額外有兩條特性：簡潔性和非交互式。具有簡潔性意味著證明的規格小，通常只有幾百字節，并且可以迅速地被驗證者檢驗。非交互式的特性意味著證明者和驗證者之間不需要交互，單單該證明本身已經足夠。較老的零知識證明需要證明者和驗證者之間互發信息以生成一項證明。

簡介性使零知識證明能夠快速地驗證，且從計算角度來看很便宜。這使它們成為了一項很棒的擴展技術。在有效性rollup中，強大的證明者能夠計算數以千計的交易的輸出，針對它們的正確性生產一個簡潔的證明，并將它們發送到底層鏈上。在那里，驗證者能夠檢驗該證明并立刻接受所有已包含的交易的結果，而無需再自行計算。因此，在底層鏈保持去中心化的同時，網絡得以進行擴展。

將上千條交易打包進單一的證明需要巨量的計算工作，從而導致證明時間變長。冗長的證明時間會導致同樣冗長的最終確認時間。因為在交易和證明被發送至底層鏈之前，用戶的交易沒有完全的最終性。而這一過程可能要花一些時間。例如，在Starknet，我們預期證明時間初步上將需要幾個小時。零知識證明在更好的操作、安全、和UX上都需要加速。

一個零知識證明系統包含三個步驟：配置，證明的生成，以及證明的檢驗。

在證明中要用到6個值：

NFT格斗游戲Crypto Fight Club完成277.5萬美元種子輪融資:12月21日消息，NFT格斗游戲Crypto Fight Club (CFC) 完成277.5萬美元種子輪融資，Shima Capital、GenBlock Ventures、D12、AU21、x21、Everse Capital、The Ring等參投。（NewsBTC）[2021/12/21 7:52:39]

R-隨即數字：建立一個零知識證明系統需要一個一次性的秘密隨機數。如果任何群體知道了該隨機數，他們就可以破解代碼并確認秘密輸入值，消除其零知識屬性。這便是「可信設置」的概念從何而來。在可信配置中，不同群體聚到一起，共同生成該隨機數，以保證沒有任何個體能夠知道該秘密。作為一名用戶，你必須信任該設置是被正確完成的，以確保你的信息是私密的。注意，STARK并不要求可信設置。

S?-證明者設置常數：設置完成后將交由證明者的常數，允許其驗證一項有效的證明。

S?-驗證者設置常數：設置完成后將交由驗證者的常數，允許其驗證一項有效的證明。

X-公開輸入值：我們用于計算的輸入值。這些將被給到證明者和驗證者，且并不是保密的。

W-私密輸入值：這是秘密的輸入值，被稱作見證，只會被給到證明者。需要注意的是，在上面的圖表中，見證不會被交給驗證者。零知識的關鍵就是它使我們能夠證明有關見證的聲明，且不需要泄露見證。

P-證明：這是由證明者創建、發送給給驗證者的證明。

以上就是深入淺出的「什么是零知識證明？」。就是這么簡潔明了！當你真正過一遍其原理的時候，你會發現它其實挺簡單。但是如果要明白如何加速零知識證明，我們就必須先明白它們在幕后是如何工作的。

MSM與NTT

零知識證明生成有兩大主要瓶頸：多標量乘法和數論變換。這兩項操作自己就能占到證明生成時間的80%到95%?，具體則取決于零知識證明的承諾方案和具體的執行。首先，我們會介紹這些操作，其后，我們將提供各個操作能夠如何加速的概覽。

素數有限場

讓我們從素數有限域開始。MSM和NTT都發生在素數有限域中，因此了解素數有限域是重要的第一步。

想象一下，我們有一組0-10的數字。我們可以給這組數字添加一條規則，即：一旦我們數過數字10?，我們就從數字0重新開始。如果我們減去最低的數字0?，我們就從最后的10開始。

我們稱數字11為模數，因為它是我們開始「循環」的數字。這種類型的數學被稱為模算數。我們與模算數互動的最直觀的經驗是在報時時，我們以12為模數計算小時。

乘法也適用于模算數。如果我們把9?3=27?，我們會得到5作為我們的輸出。這被稱為簡單除法中的「余數」。我們可以把解決方案寫成：

9?3?mod(?11)=27?mod(?11)=5,因為11?2+5=27.2代表我們循環的次數。

請注意，在我們這個0-10的集合中，無論我們選擇什么數字做加法、減法或乘法，我們的結果永遠是這個集合中的另一個數字。換句話說，沒有辦法跳出這個集合。在模算術中，除法要稍微復雜一些，但它的工作原理是相似的。因為我們的集合具有這種封閉性，所以它是一種特殊類型的集合，稱為場。

區塊鏈貸款公司Figure完成2億美元D輪融資，估值達32億美元:區塊鏈貸款公司Figure Technologies在D輪融資中籌集了2億美元，使得該公司的估值達32億美元。此輪投資由10T Holdings和Morgan Creek Digital領投，DCM、DST Global和Digital Currency Group（DCG）等參投。（CoinDesk）[2021/5/21 22:27:12]

從一個場到一個素數有限場是微不足道的。一個有限場是一個具有有限個元素的場。素數有限場是一個以素數為模數的有限場。由于我們的例子中0-10的集合是有限的，并且以質數11作為其模數，所以它是一個質數有限場！

多標量乘法

現在我們已經涵蓋了素數有限場，我們能夠理解MSM了。假設我們有兩行數字。我們可以對這些行進行的一個操作是，將一行中的每個元素，與另一行中的相應元素相乘，然后將乘積相加成為一個單一的數字。這種操作被稱為點積，在數學中常用。下面是它的樣子：

一個向量就是一個數字列表。注意，我們把兩個向量的數字作為輸入，并產生一個單一的數字作為輸出。現在，讓我們修改一下我們的例子。我們可以不計算2個數字向量的點積，而是計算一個點的向量和一個數字向量的點積。

一個標量就是一個普通的數字。在這種情況下，我們的輸出不是一個單獨的數字，而是一個網格上的新點。從圖形上看，上面的計算看起來像下圖這樣：

這個計算包括將網格上的每一個點按一定的系數進行縮放，然后將所有的點相加，得到一個新的點。請注意，無論我們在這個網格上選取什么點，無論我們用什么標量乘以它們，我們的輸出總是網格上的另一個點。

正如我們可以用網格上的點而不是整數來計算點積一樣，我們也可以用橢圓曲線上的點來進行這種計算。橢圓曲線看起來像這樣：

我們在零知識中使用的數學涉及橢圓曲線，它位于素數有限場中。因此，無論我們對橢圓曲線上的任何一點進行何種加法或乘法，其輸出都將是橢圓曲線上的另一個點。標量的點積會輸出另一個標量，坐標的點積會產生另一個坐標，而橢圓曲線點的點積會產生另一個EC點。從視覺上看，橢圓曲線的點積看起來像這樣：

橢圓曲線上的一個點與一個標量相乘稱為點乘法。將兩個點相加稱為點加。點乘法和點加法都會在橢圓曲線上輸出一個新的點。

在視覺上，橢圓曲線加法是一個簡單的操作。給定任何兩個EC點，我們可以在它們之間畫一條線。如果我們看一下這條線與曲線第三次相交的地方，我們可以找到它在X軸上的反射，從而找到這兩個點的和。要把一個點G加到自己身上，我們要找到曲線的切線，看看那條線與曲線的交點，然后在X軸上畫一條反射線，直到再次與曲線相交。那個點就是2?G.因此，點乘法也很容易直觀化。它只是涉及到將一個點本身相加。

著名游戲公司 CAPCOM推出Street Fighter II主題NFT:著名游戲公司 CAPCOM（卡普空株式會社）在WAX區塊鏈上推出Street Fighter II主題NFT。用戶可通過信用卡購買包含10張和60張Street Fighter II卡的數字包。（Cointelegraph）[2021/2/18 17:26:32]

關于如何從數學上計算EC加法的詳細解釋超出了本文的范圍。在高層次上，EC加法將兩個非常大的整數相加，并以某個大的素數為模數。

這種將多個橢圓曲線點，與標量相乘，然后相加，得到橢圓曲線上的一個新點的操作稱為多標量乘法。MSM是ZKP生成中最重要的操作之一，然而它只是一個點積。

實際上比這還要簡單：MSM可以被改寫為一堆EC點的加法。

因此，每當你聽到「多標量乘法」時，我們所做的就是把許多EC點加在一起，得到一個新的EC點。

水桶法

「水桶法」是用于加速MSM計算的一個巧妙的技巧。點加法計算在計算上是很便宜的。MSM的問題在于點乘法。在真正的零知識證明中，我們的EC點所乘的標量是非常大的。對于每一個點乘法，計算都需要數百萬次的求和。幸運的是，有一個簡單的方法可以加快MSM的速度：我們可以并行計算所有的點乘法。

水桶法的關鍵思想是，我們可以將這些大點積減少為小點積，并行計算，然后將它們加在一起。

下面是它的工作原理。回顧一下，在計算機中，數字被表示為1和0的二進制數字。

因此，在我們的計算機上，我們的EC乘法實際上可能看起來像這樣：

水桶法的第一步是將這些二進制標量分割成一定位數的窗口。在下面的圖片中，我們將標量分割成4比特的窗口。

請注意，每個桶涵蓋的數值從0000=0到1111=15.在我們將標量分解成4位的窗口后，我們可以將每個EC點分類到涵蓋0-15范圍的桶中。

動態 | 區塊鏈貸款初創公司Figure將完成1.03億美元C輪融資:據TechCrunch消息，總部位于舊金山的區塊鏈金融科技公司Figure Technologies本月遞交給美國證券交易委員會 (SEC) 的文件顯示，該公司已經完成或即將完成1.03億美元的C輪融資。該公司的區塊鏈平臺可用于住房貸款及學生貸款的融資。Figure Technologies是一家總部位于舊金山的金融科技公司，由另一家發展成熟的金融科技公司SoFi的創始人邁克?卡格尼 (Mike Cagney) 聯合創辦。截至今年2月，Figure已經從一群投資者那里籌集了1.2億美元的股權融資，其中包括RPM Ventures、DST Global的合伙人、Ribbit Capital、DCM、DCG、Nimble Ventures以及 Morgan Creek。[2019/12/2]

對于一個給定的窗口，一旦我們把每個點都分類到一個桶里，我們就可以把所有的點加起來，得到每個桶的一個點。

請注意，在這個例子中，我們只顯示了幾個點，但實際上，每個桶都包含很多數字。一旦我們有了每個桶的值，我們就可以把它們都乘以它們的桶號，得到整個窗口的最終值。這個窗口的計算只是另一個點積。

一旦我們計算出每個窗口的窗口值，我們就可以把它們全部加起來，得到我們的最終輸出。但首先，我們需要調整的是，每個窗口代表不同的數值范圍。要做到這一點，我們需要將每個窗口乘以2??**?，其中i是窗口編號，s是窗口長度。我們的窗口是4比特長，所以窗口大小是4?。

然后，我們只需將所有數字相加，就可以得到我們的MSM的最終輸出結果！簡而言之，水桶法包括3個步驟：桶式積累、桶式匯總和窗口匯總。

桶式積累：對于每個窗口，根據其系數，將每個EC點分類到一個桶中。然后將每個桶中的所有點相加，得到每個桶的最終值。

桶式匯總：對于每個窗口，用所有的桶值乘以它們的桶號，然后加在一起，得到一個窗口值。

窗口匯總：把所有的窗口值，乘以它們的位偏移量，然后把它們加在一起，得到你最終的橢圓曲線點。

幾乎所有的零知識證明加速設置都使用了這種水桶法。例如，下面是由JumpCrypto和JumpTrading團隊共同設計的MSM的硬件加速器的圖示。它的大部分內容看起來很熟悉！

水桶法通過并行計算和有效平衡硬件上的工作負荷來加速MSM，從而使證明生成時間得到顯著改善。

數論變換

NTT，也被稱為快速傅里葉變換，是零知識證明生成中的第二個關鍵瓶頸。其操作和基礎數學比MSM更復雜，所以我們不會在此提供技術解釋。相反，我們將觸及一些關于如何和為什么計算它們的直覺。

SoFi CEO啟動區塊鏈初創公司Figure 已獲5000萬美元融資:SoFi首席執行官成立新貸款公司Figure，并獲5000萬美元風險融資。該輪融資由DCM Ventures和Ribbit Capital領投，Mithril Capital Management跟投。SoFi正在探索一種使用區塊鏈來徹底改變產權保險。[2018/5/2]

零知識證明涉及證明關于多項式的聲明。多項式是一個類似f(x)=x2+3?x+1的函數。在零知識證明中，驗證者證明他們擁有一些秘密信息的方式是，證明他們知道一個給定的多項式的輸入，而這個輸入可以求值到一個給定的輸出。例如，驗證者可能被賦予上述多項式，并被要求找到一個使輸出等于11的輸入。雖然這個任務對于小多項式來說是微不足道的，但是當給定的多項式非常大時，它就變得很有挑戰性。事實上，零知識證明的整個基礎是，這項任務對于大多項式來說是如此困難，以至于驗證者將無法重復找到答案，除非他們知道秘密見證。

那么一個必要的步驟就是對多項式進行評估，以證明它等于某個輸出。在零知識中，這些多項式是由算術電路表示的。

算術電路接受一個輸入矢量，并產生一個在這些點上評估的多項式。算術電路的大小因應用而大不相同，從~?10000到超過1000000.

我們可以通過插入一個數字并計算其輸出來直接評估一個多項式。這里有一個例子：

這種方法被稱為直接評估，也是多項式的典型評估方式。問題是，直接求值的計算成本很高——它需要N2次運算，其中N是多項式的度數。因此，雖然這對小的多項式來說不是問題，但在處理大的算術電路時，直接評估會變得非常大。NTT解決了這個問題。通過利用非常大的多項式評估背后的模式，NTT可以評估一項多項式，只需進行N*log(N)計算。

如果我們要評估一個度數為100萬的多項式，直接評估需要1萬億次操作。用NTT計算同樣的多項式，只需要2000萬次操作——速度提高了5萬倍。

總之，評估多項式在零知識證明生成中起著關鍵作用，NTT使我們能夠更有效地評估多項式。然而，即使采用這種技術，大型NTT的處理時間仍然是零知識證明生成的主要瓶頸。

零知識硬件

我們已經對零知識證明加速的最重要的計算做了一個高層次的概述。算法上的改進，如用于MSM的水桶法和用于評估多項式的NTT，導致了零知識證明時間的重大進步。但要進一步提高零知識證明性能，我們必須優化底層硬件。

加速MSM和NTT的發展

正如我們用水桶法所證明的那樣，MSM很容易被并行化。然而，即使在嚴重并行化的情況下，計算時間仍然很長。此外，MSM有大量的內存需求，因為需要存儲所有被操作的EC值。因此，盡管MSM具有在硬件上加速的潛力，但它們需要巨大的內存和并行計算。

NTT對硬件不太友好。最重要的是，它們需要頻繁地將數據洗進洗出外部存儲器。數據是以隨機訪問模式從內存中檢索的，這就增加了數據傳輸時間的延遲。隨機內存訪問和數據洗牌成為一個主要瓶頸，限制了NTT的并行化能力。大多數關于加速NTT的工作都集中在管理計算與內存的互動方式上。例如，這篇來自Jump的論文描述了一種方法，通過減少需要訪問內存的次數和將數據流向計算機芯片，從而加速NTT，將內存訪問延遲降到最低。

解決MSM和NTT瓶頸的最簡單方法是完全消除該操作。事實上，最近的一些工作，如Hyperplonk引入了對Plonk的修改，取消了執行NTT的需要。這使得Hyperplonk的加速更簡單，但是引入了新的瓶頸，比如昂貴的sumcheck協議。在光譜的另一端，STARK不需要MSM，也提供了一個更簡單的優化問題。

然而，加速MSM和NTT僅僅是零知識加速的第一步。即使我們可以假設將MSM和NTT的計算時間降至0?，我們也只能實現證明生成時間的5-20倍加速。這是由于阿姆達爾定律，該定律指出，加速度受我們實際進行計算的時間部分的限制。如果MSM和NTT占了90%的證明時間，消除它們仍會留下10%的證明時間。

雖然加快MSM和NTT的速度很重要，但它們只是一個開始。為了取得進一步的進展，我們還必須加快「其他」操作，包括見證生成和散列。

硬件概述

有四種主要的計算機芯片類型：CPU、GPU、FPGA和ASIC.每種芯片在其結構、性能和通用性方面都有不同的權衡。

中央處理單元是大多數消費類電子產品如筆記本電腦中的芯片。它們的通用性使它們很適合用于各種設備和日常任務。高通用性是以犧牲性能為代價的。CPU只能按順序處理操作，使其在許多應用中表現不佳。

圖形處理單元是一種更專業的芯片。它們有大量的內核用于并行處理，使它們特別適合于圖形渲染和機器學習等應用。盡管沒有CPU那么普遍，也沒有FPGA或ASIC那么專業，但GPU是一種普遍的、可獲得的硬件。它們的流行導致了像CUDA和OpenCL這樣的低級庫的發展，幫助開發者利用GPU的可并行性，而不需要了解底層硬件。

現場可編程門陣列是可定制的芯片，可以以可重復使用的方式為特定的應用進行優化。開發人員可以使用硬件描述語言直接對其硬件進行編程，從而實現更高的性能。硬件可以被反復修改，而不需要新的芯片。FPGA的缺點是其更大的技術復雜性——很少有開發者有編程經驗。即使擁有必要的專業知識，定制FPGA的研究和開發成本也很高。盡管如此，FPGA在從國防科技到電信等行業都有應用。

特定應用集成電路是為某一特定任務過度優化的定制設計芯片。與允許硬件重新編程的FPGA不同，ASIC的規格是根植于芯片中的，防止它們被重新利用。對于任何特定的任務，ASIC都是最強大和最節能的芯片。例如，比特幣挖礦是由ASIC主導的，它計算的哈希值遠遠多于其他類型的芯片。

鑒于這些選擇，哪一個是最好的零知識證明成？這取決于應用程序。像Penumbra和Aztec這樣的隱私應用程序允許用戶在提交給網絡之前，通過創建其交易的SNARK來進行私人交易。由于所需的證明相對較小，只需使用他們的CPU就可以在他們的本地瀏覽器中生成。但對于真正需要硬件加速的較大的零知識證明，CPU是不夠的。

硬件加速

我們可以通過多種方式在硬件上加速零知識證明：

并行處理：同時進行獨立計算。

管線：確保我們的計算機的所有資源在任何時候都被使用，以最大限度地提高我們在一個時鐘周期內的計算量。

超頻：將硬件的時鐘速度提高到超過默認速度，以加速計算。如果不小心這樣做，可能會損壞硬件。

增加內存帶寬：使用更高帶寬的內存來提高我們讀寫數據的速度。在零知識中，證明生成的瓶頸往往不是計算，而是數據的傳遞。

在內存中實現對大整數的更好表示：GPU被設計為在浮點數上進行計算。零知識運算是在有限域的大整數上進行的。在內存中實現對這些大整數的更好表示，可以減少內存需求和數據洗牌。

使內存訪問模式可預測：像PipeZK這樣的論文探討了在計算NTT的同時使內存訪問模式可預測的方法，使其更容易并行化。

任何類型的芯片都可以被流水線化和超頻。GPU非常適合并行化，但它們的架構是固定的；開發者被限制在所提供的內核和內存上。GPU不能為大整數創造更好的表示方法，也不能使內存訪問模式更可預測。雖然CUDA和OpenCL等GPU庫提供了一定程度的靈活性，但硬件有局限性；更高的性能最終需要更靈活的硬件。盡管如此，GPU仍然可以加速零知識證明。零知識硬件加速公司Ingonyama正在建立ICICLE，這是一個用CUDA為NvidiaGPU建立的零知識加速庫。該庫包含加速常見零知識操作的工具，如MSM和NTT.

FPGA的時鐘速度比GPU低，但可以通過編程來解決上述所有的加速策略。他們最大的問題只是對其進行編程。對于零知識來說，組織一個既有密碼學專業知識又有FPGA工程專業知識的團隊是非常困難的。早期為零知識加速生產FPGA的團隊是像JumpCrypto和JaneStreet這樣已經擁有FPGA和密碼學人才的復雜交易公司。FPGA也仍然有瓶頸——單個FPGA往往沒有足夠的片上存儲器來執行NTT，需要額外的外部存儲器。

將硬件驅動的零知識速商業化的最嚴格的嘗試，甚至比單片FPGA更進一步。為了獲得進一步的收益，像Cysic和Ulvetanna這樣的公司正在建立FPGA服務器和FPGA集群，結合多個FPGA提供額外的存儲器和可并行計算，以進一步加速證明生成。這些團隊的早期結果是有希望的：Cysic聲稱他們的FPGA服務器在MSM比Jump的FPGA架構快100倍，在NTT比最知名的GPU實現快13倍。標準化的基準還沒有建立起來，但結果指向了重大改進。

ASIC能夠為零知識證明生成提供絕對最高的性能。今天的ZKASIC的問題是，他們正在為一個移動的目標進行優化——零知識正在迅速發展。由于ASIC需要1-2年和1000-2000萬美元來生產，他們必須等到零知識已經足夠穩固，所生產的芯片不會很快被淘汰。另外，零知識證明的市場規模在未來幾年才變得足夠大，足以證明ASIC所需的資本投資是合理的。

FPGA和ASIC之間有一個微妙的梯度。雖然FPGA是可編程的，但它們的芯片有不可編程的硬化部分。固化部件的性能比可編程的要高得多。隨著零知識市場的發展，像Xilinx和Altera這樣的FPGA公司可以生產新的FPGA，嵌入專門為零知識證明中的常見操作設計的硬化組件。同樣，ASIC也可以被設計成包括一些靈活性。例如，Cysic未來計劃生產專門針對MSM、NTT和其他一般操作的ASIC，同時保持靈活性以適應許多證明系統。

從長遠來看，ASIC將提供最強大的零知識證明加速功能。在此之前，我們預計FPGA將服務于計算最密集的零知識用例，因為其可編程性使其能夠比GPU更快地執行NTT、MSM和其他加密操作。對于某些應用，GPU將提供性能和可及性之間最具吸引力的平衡。

結論

區塊鏈行業多年來一直在等待零知識證明為生產做好準備。這項技術已經吸引了我們的想象力，承諾增強去中心化應用的可擴展性、隱私和互操作性。直到最近，該技術還不現實，主要是由于硬件限制和漫長的證明時間。這種情況正在迅速改變：零知識證明方案和硬件的進步正在解決MSM和NTT等計算瓶頸問題。有了更好的算法和更強大的硬件，我們可以將零知識證明加速到足以釋放其潛力，從而徹底改變Web3。

鳴謝：特別感謝BrianRetford、LeoFan、EmanueleCesena、MikhailKomarov、AnthonyRose、WillWolf和LukePearson，以及PenumbraLabs團隊的精彩討論和反饋，為本文做出了貢獻。

Tags：FPGFIGASI區塊鏈FPG幣YFIGDXIASI價格區塊鏈是窮人的最后一次機會

波場