Vitalik：多項式承諾如何讓 zk-SNARK 的實現更加高效？_VIT

原文標題：An approximate introduction to how zk-SNARKs are possible

原文作者：Vitalik Buterin

原文來源：vitalik.ca

編者注：說到過去十年來誕生的最強密碼學技術，肯定免不了提及零知識證明 (zero knowledge proof)。在區塊鏈領域中，它們有兩大應用場景：可擴展性和隱私。zk-SNARK 作為其中一種 zkp 技術，在近幾年來也得到了較大的突破，以太坊上出現了諸如 zkSync、Scroll、Hermez 等此類使用 zk-SNARK 證明的通用擴容解決方案。

然而，實現 zk-SNARK 并不簡單，因為對某個聲明生成了 zk-SNARK 證明之后，驗證者需要以某種方式檢查計算中的數百萬個步驟。多項式承諾就是在這里發揮其作用，即可以將計算編碼為多項式，然后使用一種特殊類型的多項式“哈希”(多項式承諾)，以允許驗證者在極短的時間內驗證多項式等式，即便這些計算背后的多項式規模無比大。

在本文中，Vitalik 介紹了 zk-SNARK 技術的工作原理和難點，然后解釋了多項式以及多項式承諾如何讓 zk-SNARK 的實現更加高效。

特別感謝 Dankrad Feist、Karl Floersch 以及 Hsiao-wei Wan 的反饋和校對。

過去十年來誕生的最強密碼學技術大概要數通用簡潔零知識證明，通常稱為 zk-SNARK（zero knowledge succinct arguments of knowledge）。zk-SNARK 允許你生成一個證明 (這個證明是針對一些運算得出的特定輸出，可用于對該運算的驗證)，通過這種方式，即使底層計算十分耗時，該證明也可以被快速驗證。“ZK”（零知識）為證明新增了一個額外特性：證明可以隱藏計算的某些輸入。

例如，您可以對以下聲明生成一個證明：“我知道一個秘密值，如果你將數字添加到挑選的單詞 cow 的末尾，然后對其進行 1 億次 SHA256 哈希運算，那么輸出的哈希值以 0x57d00485aa 開頭”。驗證者驗證該證明的耗時可遠小于自行進行 1 億次哈希運算的耗時，而且證明也不會泄漏秘密值。

在區塊鏈領域中，該技術有兩大應用場景：

可擴展性：如果一個區塊的驗證十分耗時，某個人可以驗證區塊并生成一個證明，而其他人只需快速地驗證證明即可

隱私：你可以證明你有權轉移某些資產（你收到了該資產，而且你還沒有轉走），而不透露該資產的來源。這不會對外泄漏交易雙方的信息，確保了交易的安全性。

然而，zk-SNARK 是相當復雜的；實際上，就在 2014-17 年，它們還常被稱為“月亮數學”。好消息是，從那時起，協議愈發簡化，我們對它們的理解也愈發深入。本篇博客將試圖以一種數學水平普通的人能理解的方式來解釋 ZK-SNARKs 的工作原理。

Vitalik：決定向COVID研究項目再投入1億美元贈款:6月9日消息，以太坊聯合創始人 Vitalik Buterin 在社交媒體發文表示，在與 Polygon 聯合創始人 Sandeep Nailwal 討論后得出結論，決定向 COVID 研究項目再投入 1 億美元贈款。其中，CryptoRelief 基金會出資 9000 萬枚 USDC，我本人出資 1000 萬美元。期待我們的團隊持續合作，長期 COVID 研究仍是主要關注點。[2023/6/9 21:24:45]

注意，我們將聚焦于可擴展性；一旦有了可擴展性，這些協議的隱私性就相對容易實現，因此我們將在最后回歸這個主題。

為什么 ZK-SNARK “會”很難

以開頭例子為例：我們有一個數字（我們可以將末尾跟著秘密輸入的 “cow” 整體編碼為一個整數），我們計算該數字的 SHA256 哈希，然后重復做 9999999 次，最后我們檢查輸出的開頭。這里面的計算量特別大。

一個“簡潔（succinct）”證明指的是證明大小和驗證耗時的增長遠慢于需驗證計算量的增長。如果我們想要一個“簡潔”證明，我們就不能要求驗證者在每輪哈希中做一些運算（因為那樣的話，驗證耗時將與計算量成正比）。相反，驗證者必須以某種方式檢查整個運算過程，而不必窺視運算過程中的每個部分。

有一種自然的技術就是隨機抽樣：讓驗證者只在 500 個不同的地方檢查運算的正確性，如果所有的 500 個檢查都通過了，那么認為運算過程的其余部分也大概率沒問題？

該流程甚至可以通過使用 Fiat-Shamir 啟發式（Fiat-Shamir heuristic）轉化為非交互式證明：證明者計算運算過程的默克爾根，基于默克爾根偽隨機地選取 500 個索引，并提供對應的 500 個默克爾分支。核心思想是證明者并不知道將要揭示哪些分支，直到他們已經對數據生成了“承諾”。如果惡意證明者在了解到需要檢查哪些索引后試圖篡改數據，那么這會改變默克爾根的值，而這將導致一組新隨機索引被選出，這將需要再次去篡改數據…讓惡意證明者陷入無休止的循環中，無法達成目的。

但不幸的是，簡單地隨機抽查運算過程存在一個致命的缺陷：運算過程本身并不健壯。如果惡意證明者在計算過程中的某個位置翻轉一個比特，可以導致一個完全不同的結果，而隨機抽樣驗證者幾乎永遠不會發現。

只需一次故意的插入錯誤，就會導致計算得出完全錯誤的結果，而這幾乎不會被隨機檢查所捕獲。

如果要提出一個 zk-SNARK 協議，那么很多人會走到上面這步，然后陷入困境，最終放棄。不單獨查看每個計算片段的情況下，驗證者究竟如何才能夠校驗每個計算片段？事實證明，有一個絕妙的解決方案。

多項式

多項式是一類特殊的代數表達式，具有以下形式：

Vitalik Buterin：并不認為zkPorter具有比Optimistic Rollup更強的安全保證，且沒有緊密耦合性:以太坊聯合創始人Vitalik Buterin針對Matter Labs披露的zkPorter擴容方案表示：并不認為zkPorter具有比Optimistic Rollup更強的安全保證，寧愿將資產放在Optimistic Rollup中，而不是鏈下數據可用性系統中。zkPorter鏈下數據可用性的安全級別要低于基礎鏈，且沒有緊密耦合性（Tight coupling）。另一方面，分片中的數據可用性層將受到整個以太坊網絡的保護，并兼具緊密耦合性。如果某些應用程序同時使用鏈下數據可用性也是可以的，但前提是鏈下數據在基于分片的數據可用性可用之前明確為臨時措施，但是我認為這沒有必要。[2021/4/14 20:17:45]

x+5

x4

x3

+3x2

+3x+1

628x271

+318x270

+530x269

+…+69x+381

也就是說，它們是有限個形式為 cxk 的項之和。

多項式有許多有趣的特性。但這里，我們將聚焦于多項式的一個特性：多項式是一個可以包含無限信息量（多項式顯然可視為一個整數列表）的單一數學對象上。面的第四個示例包含 tau 的 816 位的信息，而且我們能夠很容易地想象出一個包含更多信息量的多項式。

此外，多項式間的單個等式就能夠表示無限個數間的方程。例如，考慮等式 A(x)+B(x)=C(x)。如果該等式是正確的，那么下面也是正確的：

A(0)+B(0)=C(0)

A(1)+B(1)=C(1)

A(2)+B(2)=C(2)

A(3)+B(3)=C(3)

可以類推到每個可能的下標。甚至，你可以構造特地表示一組數字的多項式，這樣你就可以一次性地檢查眾多等式。例如，假設您想檢查：

12 + 1 = 13

10 + 8 = 18

15 + 8 = 23

15 + 13 = 28

您可以使用一個名為拉格朗日插值的方法來構造多項式：A(x) 在某些特定下標集合（例如 (0，1，2，3) 上的輸出為 (12，10，15，15)），B(x) 在相同下標上的輸出為 (1，8，8，13)，如此類推。準確地說，以下是相應的多項式：

用這些多項式校驗等式 A(x)+B(x)=C(x) 相當于同時校驗上述四個等式。

將多項式與自身進行比較

Vitalik：以太坊2.0或需多年才能解決擴容問題:以太坊聯合創始人Vitalik Buterin表示，以太坊基礎層可擴展性還有很長路要走，很可能在很多年之后都無法實現區塊鏈基礎層擴容。按照Vitalik說法，基于應用程序基礎層擴容或許會在以太坊2.0最后一個主要階段完成之后才會出現，所以可能需要等待幾年。Vitalik表示，他鑒于當前情況建議將以太坊擴容工作全部放在二層Layer 2解決方案上，同時他建議一旦「以太坊1.5階段」完全通過權益證明，那么基本上就不會關注擴容問題了。如果用戶不確信「以太坊1.5階段」能夠解決容量問題，那么還可以采取折衷方法，即：擁有少量執行分片（比如4-8個）和更多數據分片。Vitalik建議在錢包中直接構建二層協議，比如MetaMask或Status，他也強調在「跨二層協議傳輸」方面需要做更多工作，二層解決方案可以某種方式成為協議本身一部分，而以太坊1.0則可以用作為Optimistic Rollup客戶端。[2020/10/3]

甚至，你可以用一個簡單的多項式等式來校驗相同多項式的大量相鄰取值的關系。這稍微更進一步。假設您想校驗，對于給定的多項式 F，在整數范圍 {0,1…98} 內滿足 F(x+2)=F(x)+F(x+1)（因此，如果您還校驗F(0)=F(1)=1，那么 F(100) 將是第 100 個斐波拉契數）。

作為多項式，F(x+2)?F(x+1)?F(x) 不會正好為零，因為它在 x={0,1…98} 范圍外的取值是不受限的。但我們可以做一些巧妙的處理。一般而言，有這樣一條定則：如果多項式 P 在某些集合 S={x1，x2…xn} 上的取值為零，那么可以表示為 P(x)=Z(x)?H(x) 的形式，其中 Z(x)=(x?x1)?（x?x2)?…?(x?xn)，而且 H(x) 也是一個多項式。換句話說，在某個集合上值為零的任一多項式可以表示為在相同集合上值為零的最簡（最低階）多項式的（多項式）倍數。

為什么會這樣？這其實是多項式長除法的一個巧妙的推論：因式定理（the factor theorem）。我們知道，當用 Z(x) 除 P(x) 時，我們將得到商 Q(x) 和余數 R(x)，滿足 P(x)=Z(x)?Q(x)+R(x)，其中余數 R(x) 的階嚴格小于 Z(x)。因為我們知道多項式 P 在集合 S 上的取值為零，這意味著多項式 R 在集合 S 上的取值也必須為零。因此，我們可以通過多項式插值簡單地計算 R(x)，因為它是一個階至多為 n?1 的多項式，而我們知道其中的 n 個取值（集合 S 上的取值為零）。使用上述所有零值進行插值得到零多項式，因此，R(x)=0，H(x)=Q(x)。（譯者注，一個有 n 個解的 n?1 次多項式必為零多項式）

回到我們的例子上，如果我們有一個編碼了斐波那契數的多項式 F（因此，在 x={0,1…98} 上滿足 F(x+2)=F(x)+F(x+1)，那么我可以通過證明多項式 P(x)= F(x+2)?F(x+1)?F(x) 在該范圍的取值為零來向你證明 F 確實滿足該條件： H(x)=(F(x+2)?F(x+1)?F(x))/Z(x)，其中 Z(x)=(x?0)?(x?1)?…?(x?98).

聲音 | Kavita Gupta：風投在加密貨幣領域的投資方式發生了變化:ConsenSys Ventures創始執行合伙人Kavita Gupta在最近接受采訪時表示，風投在加密貨幣領域的投資方式發生了變化。風投開始適應新的模式，加密貨幣投資比較獨特，其流動性、持續性、風險特征、波動性等因素都與傳統的長線投資基金有很大不同。區塊鏈投資者的構成在不斷變化，企業家畫像也在變化。在這一領域擔任CEO的人士從大部分是年期的技術專家變成了很多是經驗豐富的工程師和連續創業者。產品的愿景、路線圖，尤其是接納的理由和友好的用戶界面已成為了討論主題之一。一些大型風投公司正在成立加密貨幣領域專用基金，使世界更加接近Web 2.0和Web 3.0，并驗證這一領域的許多早期技術，而這些技術在一年前還看起來可能是不現實的。”[2019/1/30]

你可以自行計算 Z(x)（理想情況下會被提前計算出來），檢查該等式，如果檢查通過，那么 F(x) 的確滿足條件！

現在，退一步，留意一下我們做了什么。我們將一個步長 100 的計算（計算第 100 個斐波那契數）轉換為單個多項式等式。當然，證明第 N 個斐波那契數的取值意義不大，尤其是因為斐波那契數具有閉合形式。但你可以使用完全相同的底層技術，只需一些額外的多項式和更復雜的等式，就可以對任意步長的任意計算進行編碼。

現在，如果存在一種使用多項式校驗等式的方法，而且這種方法比檢查每個系數快得多…

多項式承諾

再一次，事實證明，這樣的方法是存在的：多項式承諾。最好把多項式承諾看作一種對多項式進行“哈希”的特殊方法，該哈希擁有額外特性，即你可以通過校驗多項式哈希間的等式來校驗多項式間的等式。不同多項式承諾方案在適用等式類型上有著不同的特點。

下面是一些常見的例子，您可以使用各種多項式承諾方案（我們使用com(P)來表示“對多項式 P 的承諾”）：

相加：給定 com(P)、com(Q) 和 com(R)，檢查是否滿足 P+Q=R

相乘：給定 com(P)、com(Q) 和 com(R)，檢查是否滿足 P?Q=R

在某個點上求值：給定 com(P)、w、z 和一個補充證明（或“見證”）Q，驗證 P(w)=z

值得注意的是，這些原語可以相互組合。如果支持加法和乘法，那么你可以這樣計算：為了證明 P(w)=z，你可以構造出 Q(x)=

（P(x)?z）/（x?w）， 然后驗證者可以驗證:

這行得通是因為如果存在這樣一個多項式 Q(x)，那么 P(x)?z=Q(x)?(x?w)，這意味著P(x)?z 在 w 處等于零（因為 x?w 在 w 處等于零），因此 P(x) 在 w 處等于 z。

如果你能計算出某點的取值，那么你可以進行各種校驗。這是因為有一個數字定理表明：大體上，如果一些包含了一些多項式的等式在一個隨機選擇的下標下成立，那么對多項式整體而言等式基本為真。因此，如果我們只有一個證明某點取值的機制，那么我們就可以通過一個交互式游戲進行驗證，如我們的方程 P(x+2)?P(x+1)?P(x)=Z(x)?H(x)：

Vitalik Buterin提出加密經濟學提案對抗虛假信息:2月25日，在泰國曼谷舉辦的亞太以太坊社區大會上，以太坊創始人Vitalik Buterin進行了題為Cryptoeconomics to Save the Internet的演講。在演講中，他將目光放在了最近推特冒充本人賬號詐騙以太幣的虛假消息事件，提出賦予用戶代幣的提案來審查辨別虛假信息并加以懲罰的加密經濟學提案。Buterin指出，這群狡詐的騙子通過在推特上冒充他本人及其他區塊鏈業內人士，并用虛假的點贊、轉發和評論來偽裝這些虛假賬戶的有效性，以此來騙取個人用戶的虛擬貨幣。他認為，這些虛假新聞引起的詐騙行為能夠以自區塊鏈行業發展起來的加密經濟學來進行對抗。[2018/2/27]

正如前面提到的，我們可以使用 Fiat-Shamir 啟發式使其轉化為非交互式：證明者可以令 r=hash(com(P), com(H))（其中 hash 是任一加密哈希函數；它不需要擁有任何特殊屬性）并計算 r。證明者不能通過挑選只“符合”特定 r 的 P 和 H 來進行“欺詐行為”，因為他們在選取 P 和 H 時不知道 r！

快速回顧

ZK-SNARK很難，因為驗證者需要以某種方式檢查計算中的數百萬個步驟，而無需直接地檢查每個單獨的步驟（因為這會十分耗時）。

我們通過將計算編碼為多項式來解決這個問題。

單個多項式可以包含無限大的信息量，而且單個多項式表達式（例如，P(x+2)?P(x+1)?P(x)=Z(x)?H(x)）可以代表無限個數間的方程。

如果你可以驗證多項式等式，那么你同時在隱式地驗證所有的數值等式（用任何實際 x 下標替換多項式中的 x）。

我們使用一種特殊類型的多項式“哈希”，稱為多項式承諾，以允許我們在極短時間內驗證多項式等式，即使背后的多項式規模非常大。

那么，這些神奇的多項式哈希是如何工作的？

目前有三種被廣泛使用的主流方案：bulletproofs, Kate and FRI。

這里是Dankrad Feist對Kate承諾的描述：https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html

這里是curve25519-dalek團隊對bulletproofs的描述：https://doc-internal.dalek.rs/bulletproofs/notes/inner_product_proof/index.html，而這里是我的圖解：https://twitter.com/VitalikButerin/status/1371844878968176647

這里是對FRI的描述，我寫的…：https://vitalik.ca/general/2017/11/22/starks_part_2.html

哇，哇，別緊張。試著簡單地講解其中一個，不要把我帶到更可怕的鏈接上

老實說，它們沒有那么簡單。這就是為什么所有的這些數學理論直到 2015 年左右才真正崛起的緣故。

請？

在我看來，FRI 是最容易理解透的（如果你愿意把橢圓曲線配對 elliptic curve pairings 看作黑盒，Kate 會更容易理解，但配對確實很復雜，所以總體來說我覺得 FRI 更簡單）。

以下是 FRI 工作原理的簡化版（簡單起見，免去真正協議中的許多技巧和優化）。假設你有一個階小于n的多項式 P。對 P 的承諾是某組預選下標取值的默克爾根（例如，{0,1…8n?1} ，盡管這并不是最高效的選取方式）。現在我們需要額外添加一些東西來證明這組取值來自一個階小于 n 的多項式。（譯者注，需要驗證多項式階小于 n 的原因是保證作惡者通過隨機抽樣概率盡可能低，給定多項式 P，一個基本擬合 P 的另一個多項式 Q，也是能通過隨機抽樣的，但 Q 的特點是其階要足夠大才能成功）

我們要求證明者提供 Q(x) 和 R(x) 的 Merkle 根。然后，我們生成一個隨機數 r，并要求證明者提供一個“隨機線性組合”S(x)=Q(x)+r?R(x)。

我們偽隨機抽樣了一大組下標（像之前一樣，使用提供的Merkle根作為隨機種子），并要求證明者在這些下標處提供 P、Q、R 和 S 的 Merkle 分支。在每個提供的下標處，我們校驗：

如果我們做了足夠校驗，那么我們可以確信 S(x) 的“預期”值與“提供”值最多（例如，1%）是不同的。

從這里開始，我們簡單地用 S 重復上面的游戲，逐步“降低”我們關心的多項式的階，直到多項式的階低到我們可以直接校驗的程度。

和前面的示例一樣，這里的“Bob”是一個抽象概念，對密碼學家在思維上論證協議非常有用。事實上，Alice 自己生成了完整證明，為了防止她作弊，我們使用 Fiat-Shamir：我們根據此前證明中生成的數據的哈希隨機選取每個樣本的下標或 r 值。

（在該簡化協議中）一個對 P 完整的“FRI承諾”包括：

流程中的每步都可能會引入一些“誤差”，但如果您進行了足夠多的檢查，那么總誤差將低到你可以證明 P(x) 在至少 80% 的下標處等于一個階小于 n 的多項式。這足以滿足我們用例的需求：如果你想在 zk-SNARK 中作弊，你需要對少數值進行多項式承諾，其多項式的取值會在多處不同于真正階小于 n 的多項式，因此任何對其進行 FRI 承諾的嘗試都會失敗。

此外，您仔細檢查一下，FRI 承諾中對象的總數和大小是 O(log階)，因此，對于大型多項式，承諾實際上比多項式本身小得多。

為了檢查這類不同多項式承諾間的等式（例如，給定對 A、B 和 C 的 FRI 承諾，檢查 A(x)+B(x)=C(x)），只需簡單地隨機選擇很多下標，要求驗證者提供在每個多項式的這些下標處的 Merkle 分支，并驗證等式在每個下標處成立即可。

上面描述的是一種效率極低的協議；有很多代數技巧可以將協議效率提高約 100 倍，如果你想要一個切實可行的協議，比如在區塊鏈交易中使用，你需要使用這些技巧。特別是，例如，Q 和 R 實際上不是必要的，因為如果你非常聰明地選擇取值點，你可以直接從 P 的取值重構出所需 Q 和 R 的取值。但是上面的描述應該足以讓你確信多項式承諾從原理上是可行的。

有限域

因為數字的“回環”方式，模運算有時被稱為“時鐘數學”

通過模運算，我們創造了一個全新的算術系統，它和傳統算術一樣是自洽的。因此，我們可以討論該域中的所有同類結構，包括我們在“常規數學”中討論的多項式。密碼學家喜歡使用模數學（或者，更一般的，“有限域”），因為任何模運算結果的大小都會有界-無論你做什么，值都不會“超出”集合 {0,1,2…p?1}。即使計算有限域中一個一百萬次多項式，也不會得出一個集合以外的值。

將計算轉化為一組多項式等式更具意義的例子？

隱私

但這里有一個問題：我們怎么知道對 P(x) 和 R(x) 的承諾不會“泄漏”信息（使得能夠揭示我們試圖隱藏的 P(64) 的確切值）？

這里有些好消息：這些證明是對大量的數據和計算生成的小證明。因此，一般來說，證明往往不夠大，只能暴露一點點信息。但我們能從“只有一點點”推進到“零”嗎？幸運的是，我們可以。

在這里，一個相當通用的技巧是往多項式添加一些“模糊因子”。當我們選定P時，將 Z(x) 的小倍數加到多項式中（即，取隨機 E(X)，令 P′(x)=P(x)+Z(x)?E(x)）。這并不會影響命題的正確性（事實上，P′ 在“在計算發生”的下標處的值與 P 相同，因此它仍是有效的轉義版本），但它可以在承諾中添加足夠多的額外“噪聲”，使得任何余下信息不可恢復。此外，對于 FRI，重要的是不要對計算發生范圍的隨機點進行采樣（在本例中為 {0…64} ）。（譯者注，這樣即使是同樣的多項式也會讓人猜不到）

我們能再回顧一下嗎？？

最優秀的三類多項式承諾是 FRI、Kate 和 bulletProof。

Kate在概念上是最簡單的，但它依賴于非常復雜的橢圓曲線配對“黑盒”。

FRI很酷，因為它只依賴哈希；它的工作原理是將多項式逐漸歸約為階越來越低的多項式，并在每步進行隨機抽樣檢查，使用 Merkle 分支來證明等價性。

為了防止單個值大小的膨脹，我們不在整數上做算術運算和多項式運算，而是在有限域上做所有事情（通常是對一些素數 p 進行模運算）

多項式承諾天然支持隱私保護，因為生成的證明已經比多項式小得多了，因此多項式承諾只能暴露多項式中一點點信息。但我們可以往多項式添加一些隨機性，將暴露的信息從“一點點”減少到“零”。

哪些問題仍在研究當中？

優化 FRI：已經有很多涉及精心挑選的取值域的優化，“DEEP-FRI”，以及一系列其他讓 FRI更高效的技巧。Starkware 及其他人正在研究這塊。

將計算編碼為多項式的更佳方法：找出將涉及哈希函數、內存訪問和其他特征的復雜計算編碼為多項式等式的最高效方法仍是一個挑戰。在這方面已經取得了很大的進展（例如，見 PLOOKUP)，但我們仍需更多的進展，特別是如果我們想將通用虛擬機執行編碼為多項式的話。

增量可驗證計算：如果隨著計算繼續能夠高效地“擴展”證明，那就太好了。這在“單證明者”情況下很有價值，而且在“多證明者”的情況下也很有價值，特別對于不同參與者創建區塊的區塊鏈而言。最近一些在這方面的工作，請參見 Halo。

比推 Bitpush News

媒體專欄

閱讀更多

金色早8點

Bress

財經法學

PANews

成都鏈安

鏈捕手

Odaily星球日報

Tags：ITAVITVITATERTITANS價格VitteeyVita Inuinterstellarchain

瑞波幣