介紹一個前沿主題：「證明遞歸及其在 ZKML 中的應用。 “ 如今，證明遞歸幾乎是零知識證明證明龐大複雜程式的唯一方法。 此外，ZKML 將可驗證的 AI 引入區塊鏈。
作者：Maggie，Foresight Research
PPT 連結： https://img.foresightnews.pro/file/ProofRecursion.pdf
大家下午好， 歡迎來到 zkDay Tech Talk。
我叫 Maggie，我是 Foresight Ventures 的技術總監。
我很高興 Dr. Cathie 作為我們這個話題的共同演講者。 Dr. Cathie 是以太坊基金會 Privacy & Scaling Explorations 團隊的 ZKML 研究員。
我們很高興向您介紹一個前沿主題：「證明遞歸及其在 ZKML 中的應用。 ”
如今，證明遞歸幾乎是零知識證明證明龐大複雜程式的唯一方法。 此外，ZKML 將可驗證的 AI 引入區塊鏈。
現在，我想先簡要介紹一下我們公司。
- Foresight Ventures 是一家以研究驅動的專注於區塊鏈技術與加密行業的投資機構。 我們的產品矩陣包括幾個關鍵組成部分。
- 首先，Foresight News 是亞太地區最大的多語種 web3 媒體平臺。
- 其次，我們運營著 Foresight X，Foresight X 是我們的加速器，目前同步在巴黎舉辦 hacker house 活動。
- 最後，我們擁有蓬勃發展的全球開發者社區 OpenBuild。
如果您想瞭解更多關於我們的資訊，請隨時訪問我們的官方網站或在社交媒體管道上與我們建立聯繫。
現在，讓我們開始今天的議程。
我們的討論將分為兩個部分：證明遞歸部分和 ZKML 部分。
我將用前半個小時來解釋為什麼證明遞歸很重要，理論的演變以及基於摺疊的證明遞歸。
然後，Cathie 博士將接過話題，介紹證明遞歸在實際 ZKML 中的應用。
為什麼我們要關注證明遞歸呢？
這是因為我們在使用零知識證明（ZKP）來證明程序正確執行時面臨了兩個挑戰：
首先，將非常龐大且複雜的程式在單個整體 ZKP 中進行證明是低效且不切實際的。 從幻燈片上的圖表可以看出，我們首先需要將目標程式轉換為 ZKP 能理解的算術電路（arithmetic circuits）或約束（constraints）。 然後，我們將這些電路和見證（Witness）輸入到 ZKP 證明系統中生成證明。 之後再進行驗證。 包含大量計算和複雜演算法的程式可能會生成龐大的電路和大量的約束。 這增加了生成證明所需的計算資源。 有的時候，由於證明者的記憶體限制，證明生成可能都無法成功執行。
此外，一些證明不適合在區塊鏈上驗證，因為區塊鏈上有 Gas 限制。 因此，控制證明的大小和證明驗證過程的複雜性也是至關重要的。
為了解決這些挑戰，我們通常採用三種方法：證明組合（proof composition）、證明聚合（proof aggregation）和證明遞歸（proof recursion）。
- 證明組合使用不同的證明系統依次生成最終證明。 第一個證明系統是一個快的證明系統，但可能會生成一個較大的證明。 為了減小證明的大小，我們可以運行第二個系統，該系統可能是一個較慢的證明系統，但會生成一個較短的證明。 第二個證明系統將證明第一個系統的驗證者會接受見證。 因此，通過證明組合，我們可以構建一個快的證明系統，並且證明也較小。
- 第二種方法是證明聚合。 證明聚合是將多個證明聚合成一個單一的證明。 例如，zkEVM 包含了許多不同的電路，如 EVM 電路、RAM 電路、存儲電路等。 在實踐中，驗證所有這些證明在區塊鏈上是非常昂貴的。 因此，我們使用證明聚合，即使用一個證明來證明這些多個子電路證明是有效的。 這個單一的證明在區塊鏈上更容易被驗證。
- 第三種強大的方法是證明遞歸。 證明遞歸的概念是構建一連串的驗證者電路，在每一步中，我們可以生成一個比前一個證明更容易驗證的證明。 最終，我們只需要用最低的複雜度來驗證最終的證明。
證明遞歸可以用於實現增量可驗證計算 Incrementally Verifiable Computation（IVC）。
當我們有一個很長的計算，這個計算是迴圈執行函數 F。 比如，我們有一個初始狀態 S0，在執行 F 后，我們得到 S1，然後重複此過程直到得到最終輸出 Sn。 我們希望證明輸出 Sn 是正確的結果。
證明遞歸在這裡的作用是可以逐步更新一個證明 i 到一個證明 i +1。 證明可以逐步更新，最終，我們只需驗證一個證明，以確保整個執行鏈是有效的。
因此，它最適用於長計算和不斷演化的計算。
- 對於長時間計算，我們可以將其分解為多步，並使用 IVC 來證明這些步驟，從而降低了證明者所需的記憶體大小。
- 當將這種方法應用於區塊鏈時，它也是非常有價值的。 由於區塊鏈的狀態不斷增長，通過 IVC 證明，我們可以通過檢查最新的遞歸證明來驗證當前狀態。 如果該證明有效，我們可以相信整個執行歷史是正確的。
總之，由於證明者的記憶體和時間限制，證明遞歸幾乎是我們能夠證明非常複雜的陳述的唯一方法。 而且，IVC 已經在簡潔區塊鏈 Mina、VDF 函數、ZKML 等中得到了應用。
IVC 技術的演變
在過去的幾年中，IVC 經歷了三個階段的演變。
- 第一個階段是基於 SNARKS 的 IVC。
- 第二個階段基於帶累加的 SNARKS 或 NARKS 的 IVC。
- 最新階段是基於摺疊的 IVC。 這引起了當今的廣泛關注。
今天，我們將簡要回顧前兩種類型，然後將重點放在最後一種基於摺疊 IVC 方案上。
- 基於 SNARK 的 IVC 原理簡單。 在每一步中，IVC 證明者需要證明兩件事情：因此，IVC 遞迴電路中嵌入了一個 SNARK 驗證電路，並需要完全驗證前一步生成的證明。 這個電路龐大且昂貴。
- 函數 F 正確執行了，生成了狀態 S。
- 前一步生成的 ZKP 證明π是有效的。
- 第二類 IVC 是基於帶累加的 SNARKs，例如 halo 和 halo2。 它們不需要在 IVC 遞迴電路中嵌入 SNARK 驗證電路。 而是，它們引入了累加方案，將驗證的昂貴部分延遲到一個累加器中，只在遞歸電路中保留一個小的累加驗證者。 累加驗證者的成本遠低於完整的 SNARK 驗證者。
- IVC 的最新阶段是基于折叠（folding schemes）的。 折叠方案最初由 Nova 引入。 它是一种将两个待证明的实例压缩为一个实例的方法。 假设我们有一个电路 C 和两个实例 (x1,w1) (x2,w2)。 我们想将它们折叠在一起并输出一个新的折叠实例 (x, w)。 如果两个原始实例是有效的，我们将得到一个有效的折叠实例。如果折叠实例是有效的，证明者必须知道原始实例 x1 和 x2 的有效见证 w1 和 w2。
基于折叠的 IVC 技术原理
现在，让我们尝试将两个 R1CS 实例折叠在一起，看看是否能满足上一张幻灯片中提到的条件。
我们有两个原始见证，z1 和 z2（实际上是 w1 和 w2）。z1 满足方程 Az1 * Bz1 = Dz1，表示它是一个有效的见证。同样，z2 也是一个满足条件的见证。
然后，我们使用一个随机线性组合将它们折叠在一起，设定 z = z1 + 随机数 r * z2。我们希望折叠后的见证 z 也是一个有效的实例。也就是说，我们希望 Az * Bz = Dz。
但是，當我們展開 Az * Bz 時，會生成許多交叉項，且結果並不等於 Dz。 因此，z 不是有效的。 我們未能成功將兩個 R1CS 實例摺疊在一起。
然而，如果我們允許方程中存在一些雜訊，它可能是相等的。 Nova 引入了一個誤差向量（error vector）E，它吸收了摺疊時生成的交叉項。 還有一個標量 c，用於吸收 Dz 的額外因數。
這個 R1CS 變體被稱為 relaxed R1CS。 relaxed R1CS 的實例包括 x，標量 c，和誤差向量 E。 一個有效的見證 z 滿足 Az * Bz = C * Dz + E（實際上是說如果等式滿足則 w 是有效的見證）。
我們有兩個實例：*（x1， c1， E1），其見證為 w1*，和（x2， c2， E2），其見證為 w2。 兩個見證都是有效的。 現在，讓我們看看是否可以將它們一起摺疊。
我們展開方程 Az * Bz。 最後，我們得到 c * Dz + E。 所以 z 滿足了這個方程，是一個有效的見證。
現在，我們可以將 z1 和 z2 摺疊在一起，得到一個新的摺疊見證 z，該見證對於 ABD 是有效的。
然而，值得注意的是，E 是由 E1, E2 和 T 计算得到的，其中 T 包含了那些交叉项，是从见证算出来的。因此，折叠的证明者（folding prover）必须向验证者（folding verifier）提供见证以计算 E。这使得折叠方案不是 non-trivial 的，也不是零知识的。
Not non-trivial 意味着验证折叠实例可能不比验证原始的两个实例更高效，或者通信成本太大。不是零知识的，是因为在这种情况下，验证者得知了 witnesses。
为了解决这个问题，我们可以用 E 和 T 的承诺 (commitment) 來替换 E 和 T。证明者不再向验证者发送见证，而是发送承诺以帮助验证者计算折叠的实例。
因此，我们将实例中的 E 替换为 E 的承诺，并将 E 移动到见证中。这被称为 commited relaxed R1CS。请注意，为了更容易理解，这里展示的方法是从 Nova 的论文简化而来的。
现在，让我们来看一下折叠方法。我们有一个折叠证明者和一个验证者。证明者有两个 commited relaxed R1CS 实例 I1 和 I2，以及这两个实例的见证 z1 和 z2。验证者只有实例 I1 和 I2。
- 首先，证明者将计算交叉项 T，并将 T 的承诺发送给验证者，以帮助其计算折叠实例。
- 然后，验证者选择一个随机数 r 并将其发送给证明者，我们可以使用 Fiat-Shamir 变换使其成为非交互式的。
- 折叠证明者计算折叠实例 I 和见证 Z。
- 验证者使用承诺 T 和原始实例 I1 和 I2，轻松计算出折叠实例 I。
如果两个原始见证 z1 和 z2 是满足条件的见证，那么折叠见证 z 将是折叠实例 I 的满足条件的见证。我们需要注意的是，承诺方案必须是加同态的。
在 IVC 中，我们可以使用折叠方案来折叠在每一步中生成的 committed relaxed R1CS 实例。
我们可以将实例 I0 和 I1 折叠在一起，生成一个折叠实例 I 0 到 1，我们也称之为运行实例。然后，将新实例 I2 与该运行实例折叠在一起，得到 I 0 到 2。我们重复这些步骤，得到最终实例 I 0 到 n-1。
最后，使用折叠后的见证，我们可以为最终的折叠实例生成 ZKP 证明，然后进行验证。
然而，这个证明是不完美的，因为在这里的 SNARK 验证者只知道折叠见证是有效的，但无法保证折叠过程是正确完成的。
因此，我们必须在每一步中验证折叠过程。
我们描述一个方法 F’，即 IVC 递归方法。它既包括迭代方法 F，也包括能够验证折叠过程的方法。
为了验证折叠过程，我们首先验证 hi，它是上一步折叠结果的哈希。然后我们验证折叠过程，即将实例 i 与运行实例 0 到 i-1 折 叠，生成一个新实例 0 到 i，验证着是否正确。然后输出 hi+1，即折叠结果的哈希。因此，我们通过执行一些哈希和乘法运算，以非常低的成本在每一步中验证了折叠过程。
总结一下，正如我们之前提到的，基于 SNARK 的 IVC 成本高昂，因为我们需要读取整个证明并在 IVC 递归方法中完整的验证方法。
当涉及到基于 SNARK with accumulation 类型的 IVC 时，我们仍然需要每一步都读取整个证明。但有所改进的是，我们可以将验证分为一个复杂的部分和一个简单的部分，将简单的部分在 IVC 链上运行，延迟复杂部分的验证。
而对于基于折叠的 IVC，我们所需做的就是读取未证明的实例，并将它们折叠到一个运行实例中。折叠过程的验证很简单，就是进行一些基本的哈希和乘法运算。我们甚至可以将证明部分推迟到最后一步。与前两种方法相比，基于折叠的 IVC 产生的递归开销最低。因此，它们是目前最优的方法。
更多的基於摺疊的 IVC
在 Nova 的摺疊方案引入后，自去年以來，我們看到了許多不同基於摺疊的 IVC 方法。
其中之一是 SuperNova，它支援 IVC 鏈中存在多種方法。
給定若干非確定性方法，例如 F1 到 F3，以及一個φ函數在每一步中選擇其中一個 F。 因此，這個例子中，在 IVC 鏈中我們有 3 種類型的方法，而每種方法可能會出現多次。
為了摺疊這些 non-uniform 的 IVC 電路實例，SuperNova 將 Nova 應用於每組 F。 使用 φ 函數來選出運行實例，並將當前實例摺疊到運行實例中。 通過這種方式，我們單獨摺疊每組 F。
Sangria 是 Plonk 的摺疊方案，或者更準確地說，是 PLONKish 的摺疊方案。
PLONKish 在定義約束和門行為方面提供了很大的靈活性。 它不僅支援加法和乘法約束（addition and multiplication constraints），還支持複製約束（copy constraints）和自定義門約束，例如查找約束（lookup constraints）。 查找約束使得 zk 不友好的方法能夠被預先計算以獲得更好的性能。
PLONKish 功能強大，加速了各種程序的 zk 算數化。 Sangria 發現摺疊方案可以輕鬆擴展到 PLONKish 約束系統。 支援加法和乘法約束、複製約束和 2 階自定義約束。
總之，證明遞歸是一種非常聰明的技術，它使我們能夠證明大而複雜的陳述。
基於摺疊的 IVC 方案如今引起了極大的關注，並且比基於 SNARK 的 IVC 更高效。 我們相信它們將在業界得到廣泛採用。
這裡的圖表列出了基於摺疊的 IVC 的重要創新，讓我們快速回顧一下。
- Nova，R1CS 的摺疊方案，允許我們對於同一個方法的循環執行用到 IVC。
- 如果我們可以在每一步執行不同的功能，那就更好了。 所以 SuperNova 將 Nova 推廣到 non-uniform IVC 上，我們在 IVC 鏈上能運行多個方法，並且每個方法都可能在 IVC 上出現多次。
- Sangria 發現到 Nova 的摺疊方案可以應用於 PLONKish 約束系統。 它支援複製約束（copy constraints）和 2 階的自定義約束（degree-2 custom constraints），但不支援高階自定義約束（high degree custom constraints）和查找約束（lookup constraints）。
- HyperNova 引入了 Customizable Constraint Systems（CCS）的摺疊方案。 HyperNova 支援高階自定義約束和查找約束，並使用 sum-check protocol 來避免執行大量的 FFT（快速傅里葉變換）。
- ProtoStar 進一步增強了摺疊方案，支援高階自定義約束、查找約束和 non-uniform IVC。
在結束演講之前，我想強調，如果在座的任何人都有出色的想法，並需要資源將其付諸實踐，請務必不要猶豫，隨時聯繫我們 Foresight Ventures。
此外，我們邀請您加入我們的 Foresight X 第二屆的孵化計劃。 我們在這裡支持並培養您的創業之路。 借助我們深厚的行業知識和豐富的資源，我們將確保您的專案蓬勃發展。
此外，如果您從事學術或研究領域，Foresight X 提供競爭力的 Grants 來支援您的研究之路。
我們在這裡提供一個 QR 碼，其中包含您可能感興趣的所有連結，包括研究報告。 請隨時拍照或掃描該二維碼，瞭解更多資訊。 如果演講結束后您有任何問題，您可以在 Twitter 上找到我。
再次感謝您參與我們的 Tech Talk。 現在，我將把舞臺交給 Cathie 博士進行下一部分的演講。
感謝 Mr. Keep 對內容進行校對。
免責聲明：作為區塊鏈資訊平臺，本站所發佈文章僅代表作者及嘉賓個人觀點，與 Web3Caff 立場無關。 本文內容僅用於資訊分享，均不構成任何投資建議及要約，並請您遵守所在國家或地區的相關法律法規。
