zkEVM 的設計存在什麼挑戰?目前有哪些技術解決方案?

原文:zkEVM(HackMD)

作者: Ye Zhang  

編譯: EthereumCN

感謝 Vitalik Buterin、Barry Whitehat、Chih-Cheng Liang、Kobi Gurkan 和 Georgios Konstantopoulos 的審閱和評論

摘要

我們相信 zk-Rollup 遲早成為 L2 賽道的佼佼者— 這是一個非常便宜且安全的一流 L2 擴容解決方案。然而,現存的 zk-Rollup 都是應用專用型的,這讓開發者難以在 zkRollup 中構建通用的可組合的 DApp 並遷移現有的應用程序。我們引入了 zkEVM,它可以為通用的 EVM (以太坊虛擬機,Ethereum Virtual Machine) 驗證零知識證明 (zk proofs)。這允許我們構建一個完全兼容 EVM 的 zk-Rollup,任何現有的以太坊應用程序都可以輕鬆地遷移過去。

在本文中,我們指出了 zkEVM 的設計挑戰何在以及為什麼現在這個方案可行。我們還給出了更加具體和直觀的描述、並概述瞭如何從頭開始構建 zkEVM。

背景

zk-Rollup  被視為以太坊最好的擴容解決方案。它的安全性可以與以太坊一層網絡的安全性媲美,並且與其他 L2 解決方案相比,它最終確定時間最短。具體對比分析請看:https://vitalik.ca/general/2021/01/05/rollup.html

中長期來看,隨著 ZK-SNARK 技術完善,ZK rollups 將在所有用例中脫穎而出。—— Vitalik Buterin

zk-Rollup 的基本概念就是將大量的交易聚合進一個 Rollup 區塊中並為鏈下區塊生成一個簡潔證明。然後 L1 上的智能合約僅需要驗證該證明即可直接應用已更新的狀態,而無需重新執行那些交易。這可以節省一大筆 gas 費,因為驗證證明比重新執行計算要便宜得多了。還省了一筆費用的地方就是將數據壓縮了 (即,只在鏈上保留最少的數據量用於驗證)

雖然 zk-Rollup 安全且高效,它的應用程序仍局限於支付和代幣轉換。由於下列兩個原因,很難去構建通用型的 DApps:

  • 首先,如果你想要在一個 zk-Rollup 中開發 DApps,你需要使用一種特殊的語言 (如 R1CS ) 來編寫你所有的智能合約邏輯。不僅所需要的語言的語法複雜,而且這樣做還需要在零知識證明方面具有極強的專業知識。
  • 第二,目前的 zk-Rollup 不支持可組合性 [1]。這意味著 L2 中的 zk-Rollup 應用程序不能互相交互。這種特性極大地破壞了 DeFi 應用的可組合性。

簡而言之,zk-Rollup 對開發者不友好,目前功能有限。

這是我們想要解決的最大問題。我們希望通過直接支持原生 EVM 驗證,以便在 L2 中提供最好的開發體驗和支持 L2 可組合性。這樣現有的以太坊應用程序就可以簡單地遷移到 zk-Rollup 上了。

在 zk-Rollup 中構建通用型 DApp

在 zk-Rollup 中構建通用 DApp 有兩種方式:

  • 為不同的 DApp 構建專用集成電路 (application-specific circuit, ASIC)。
  • 為智能合約執行構建一個通用的”EVM” 電路

“circuit”  指的是在零知識證明中使用的程序表現形式。比如,如果你想要證明 hash(x) = y,你需要使用電路形式重寫哈希函數。這種電路形式只支持非常有限的表達式 (例如,R1CS 只支持加和乘)。因此,使用電路語言編寫程序是非常困難的—— 你必須使用加法和乘法來構建所有的程序邏輯 (包括 if else、loop 等等)。

第一種方法要求開發者為不同的 DApp 設計專門的”ASIC” 電路。這是使用零知識證明最傳統的方法。通過自定義電路設計,每個 DApp 的開銷將會更小。然而,這種方法帶來了可組合性的問題,因為電路是” 靜態的”,而且由於需要強大的電路設計專業知識,開發體驗會十分不友好 [2]。

第二種方法不需要任何特殊的設計或開發者的專業知識。這種基於機器的證明背後的邏輯為:任何程序最終都會在 CPU 上運行,所以我們只需要構建一個通用 CPU 電路來驗證低級的 CPU 操作。然後我們可以使用這個 CPU 電路來驗證任何程序執行。在我們的場景中,程序是智能合約,而 CPU 是 EVM。然而,由於其巨大開銷,在過去幾年裡這個方法並未被廣泛應用。比如,儘管你只想要在一個步驟中證明 add  的結果是正確的,你仍然需要承擔整個 EVM 電路的開銷。如果在執行追踪中有數千個步驟,那麼證明者的 EVM 電路開銷將提高 1000 倍。[3]

最近,有很多研究按照下面這兩種方法來優化 zk 證明,包括 (i) 提議新的 zk 友好的原語,即 Poseidon hash  可以在電路中實現比 SHA256 高 100 倍的效率,(ii) 目前正提高通用可驗證 VM 的效率,如 TinyRAM,以及 (iii) 越來越多的通用優化技巧,如 Plookup,甚至速度更快的密碼學庫。

在我們的上一篇文章中,我們提議為每個 DApp 設計 “ASIC” 並讓他們通過加密承諾實現通信。然而,根據社區的反饋,我們調了一下我們工作的優先級,即優先選擇第二種方法。我們將專注於構建一個通用的 EVM 電路 (也就是所謂的 “zkEVM”)。在 zkEVM 上開發和在 L1 上開發的體驗將相差無幾。我們不會把設計複雜性留給開發者處理,而是通過自定義的 EVM 電路設計來負責並解決效率問題。

zkEVM 的設計挑戰**

zkEVM 難以構建。儘管多年來我們一直很清楚這個問題,但沒有人成功構建過原生 EVM 電路。與 TinyRAM 不同,由於以下原因,設計和實現 zkEVM 更具挑戰性:

  • 第一,EVM 對橢圓曲線的支持有限。目前,EVM 僅支持 BN254 配對。由於不直接支持循環橢圓曲線,因此很難進行證明遞歸。在此設置下也很難使用其他專用協議。驗證算法必須是 EVM 友好的。
  • 第二,EVM 字長為 256 位。EVM 基於 256 位整數運行 (就像大多數常規 VM 基於 32-64 位整數運行那樣),而 zk 證明” 天然 “地基於素域運作。在電路內進行” 不匹配域運算 “需要範圍證明,這將為每個 EVM 操作增加約 100 個約束條件。這將使 EVM 的電路大小增加兩個數量級。
  • 第三,EVM 有很多特殊操作碼。EVM 與傳統 VM 不同,它有很多像 CALL  這樣的特殊操作碼,並且它也有與執行環境和 gas 相關的錯誤類型。這將給電路設計帶來新的挑戰。
  • 第四,EVM 是一個基於堆棧的虛擬機。SyncVM (zksync) 和 Cario (starkware) 架構在基於寄存器的模型中定義了自己的 IR/AIR。它們構建了一個專門的編譯器來將智能合約代碼編譯成一個新的對 zk 證明友好的 IR。方法是兼容語言,而不是兼容原生 EVM。不管是為基於堆棧的模型證明還是直接支持原生工具鏈,都將變得十分困難。
  • 第五,以太坊存儲佈局帶來了巨大的開銷。以太坊存儲佈局高度依賴於 Keccak  和一個巨大的 MPT  [4],兩者都對 zk 證明不友好,且都產生巨大的證明開銷。例如,在電路中,Keccak 哈希比 Poseidon 哈希大 1000 倍。然而,如果將 Keccak 替換為另一個哈希,則會對現有的以太坊基礎架構造成一些兼容性問題。
  • 第六,基於機器的證明具有巨大的開銷。即使你可以正確地處理上述所有問題,你仍然需要找到一個有效的方法將它們組合在一起以獲得完整的 EVM 電路。即使是像 add  這樣簡單的操作碼也可能導致整個 EVM 電路開銷的產生。

為什麼現在又行得通了?

多虧了研究人員在這一領域取得的巨大進展,近兩年解決了越來越多的效率問題,zkEVM 的證明成本最終是可以解決的!最大的技術改進來自以下幾個方面:

  • 多項式承諾的使用。在過去幾年裡,大多數簡潔的零知識證明協議都堅持在應用專用型的可信設置中使用帶有 PCP 查詢編碼的 R1CS。由於每個約束的程度需要為 2 (雙線性配對 ) 只允許指數相乘一次),所以電路的大小通常會增大,這導致你無法進行許多自定義優化。借助多項式承諾機制,你可以通過通用設置甚至透明設置將約束解除到任何程度。這為後端的選擇提供了極大的靈活性。
  • 查找表參數和自定義小工具的外觀。另一個強大的優化為查找表的使用。這種優化首先在 Arya  中提出,然後在 Plookup  中得到優化。這可以為 zk 不友好的原語 (即 AND、XOR 等按位運算) 節省很多開銷。自定義小工具可以讓你高效地進行高階約束。TurboPlonk  和 UltraPlonk  的程序語法十分優雅,以便更輕鬆地使用查找表和自定義小工具。這對於減少 EVM 電路的開銷非常有幫助。
  • 遞歸證明越來越可行。過去,遞歸證明會帶來巨大開銷,因為它依賴於特殊的配對友好型的循環橢圓曲線 (即基於 MNT 曲線的構造)。這引入了巨大的計算開銷。然而,更多技術的出現正在使這成為可能,並且同時不犧牲效率。例如,Halo  可以避免對於配對友好型曲線的需要,並使用特殊的內積參數分攤遞歸成本。在 Aztec 中,你可以直接對現有協議進行證明聚合 (查找表可以減少非本地域運算的開銷,從而可以使驗證電路變得更小)。它可以大大提高支持的電路大小的規模。
  • 硬件加速使證明更高效。基於最大程度的理解,我們已經為證明者製作了最快的 GPU 和 ASIC/FPGA 加速器。我們的論文描述了 ASIC 證明器已經被今年最大的計算機會議 (ISCA) 接受。GPU 證明者比 Fliecoin 的實現快 5 到 10 倍。這可以大大地提高證明者的計算效率。

那麼,它是如何運作的,以及如何構建它?

除了強大的直覺和技術改善之外,我們還需要更清楚地了解我們需要證明什麼並找出更具體的架構。我們將在後續的文章中介紹更多技術細節和對比。而在下文,我們描述了整個工作流程和一些關鍵想法。

開發者和用戶的工作流

對於開發者,他們可以使用任何與 EVM 兼容的語言實現智能合約,並將編譯後的字節碼部署到 Scroll 上。然後,用戶可以發送交易,與部署的智能合約進行交互。用戶和開發者的體驗將與 Layer1 完全相同。但是,gas 費用顯著降低,並且交易在 Scroll 上即時預先確認 (提款只需花幾分鐘即可完成敲定)。

zkEVM 的工作流

即使外部的工作流保持不變,Layer1 和 Layer2 的底層處理過程也完全不同:

  • Layer1 依賴於智能合約的重新執行。
  • Layer2 依賴於 zkEVM 電路的有效性證明。

下面給出了更加詳細的解釋,說明 L1 和 L2 上的交易有何不同。

在 L1 中,已部署的智能合約的字節碼保存在以太坊的存儲庫中。交易將通過點對點 (P2P) 網絡進行廣播。對於每筆交易,每個全節點都需要加載相應的字節碼並在 EVM 上執行它以使得狀態一致 (交易將用作輸入數據)。

在 L2 中,字節碼也保存在存儲庫中,並且用戶將以同樣的方式進行操作。首先,交易會被發送至鏈下的一個中心化 zkEVM 節點中。然後,zkEVM 將生成一個簡潔的證明 (證明在交易進行後已正確更新狀態),而不是簡單地執行字節碼。最後,L1 上的合約將驗證這些證明並更新狀態,而無需重新執行交易。

接下來讓我們深入了解一下執行過程,看看 zkEVM 最終需要證明什麼。在本地執行中,EVM 會加載字節碼並從頭開始逐個執行字節碼中的操作碼。每個操作碼都可以被認為是在執行以下三個子步驟:(i) 從堆棧、內存或存儲中讀取元素;(ii) 對這些元素執行一些計算;(iii) 將結果寫回到堆棧、內存或存儲庫中。[5] 比如, add  操作碼需要從堆棧中讀取兩個元素,將它們相加並將結果寫回堆棧中。

因此,結論很顯然,zkEVM 的證明需要包含與執行過程相對應的以下方面:

  • 字節碼從永久存儲中正確加載 (你正在運行從某個地址中加載出的正確操作碼)
  • 字節碼中的操作碼是一個接一個執行的 (字節碼按順序執行,不會遺漏或跳過任何操作碼)
  • 每個操作碼都正確執行 (每個操作碼中的三個子步驟都正確執行,R/W + 計算)

zkEVM 的設計亮點

在設計 zkEVM 的架構時,我們需要考慮如何逐一處理/解決上述三個方面的問題。

  1. 我們需要為一些加密累加器設計一個電路。它就像一個 “可驗證的存儲庫”,我們需要一些技術來證明我們正在正確讀取數據。可以使用加密累積器來有效地實現這一目標。[6] 讓我們以默克爾樹為例。已部署的字節碼將作為默克爾樹的一片葉子存儲在上面。然後,驗證者可以通過一個簡潔的證明來驗證該字節碼是從一個給定的地址中正確加載的 (即,驗證電路中的默克爾路徑)。對於以太坊存儲,我們需要電路與 Merkle Patricia Trie 和 Keccak 哈希函數兼容。
  2. 我們需要設計一個電路來將字節碼與實際的執行追踪連接起來。將字節碼移動到一個靜態電路中存在的一個問題就是條件操作碼,如 jump (對應於智能合約中的”loop” 和”if else” 語句)。它可以跳轉 (jump) 到任何地方。在使用特定輸入運行字節碼之前,目標是不確定的。這就是為什麼我們需要驗證實際的執行追踪。執行追踪可以被認為是” 展開的字節碼 “,它將包含實際執行順序中的操作碼序列 (即,如果你跳轉到另一個位置,那麼軌跡將包含目標操作碼和目標位置)。證明者將直接提供執行追踪作為電路的見證。我們需要證明這份提供的執行追踪確實是從具有特定輸入的字節碼中” 展開 “的。其思想是強製程序計數器的值保持一致。為了處理不確定的目的地,則需要讓證明者提供一切。然後你可以使用查找參數有效地檢查一致性 (即,證明具有適當全局計數器的操作碼包含在” 總線 “中)。
  3. 我們需要為每個操作碼設計電路 (證明每個操作碼中的讀、寫和計算都是正確的)。這是最重要的部分— 證明執行追踪中每個操作碼都是正確且一致的。如果你直接把所有東西都放在一起,將會帶來一大筆開銷。這裡最重要的優化思想是:
    • 我們可以將 R/W 和計算分離成兩個證明。一個是將所有操作碼所需的元素提取到” 總線 “ 中。另一個將證明對來自” 總線 “ 的元素執行的計算是正確的。這可以極大地減少每一部分的開銷 (即,你不需要在計算證明中考慮整個 EVM 存儲)。在更加詳細的規範中,第一個稱為” 狀態證明 “,第二個稱為”EVM 證明 “。另一個觀察是,” 總線映射 “ 可以由查找參數有效地處理。
    • 我們可以為每個操作碼設計更高程度的自定義約束 (即,可以通過將 EVM 字分成幾個塊來有效求解)。我們可以根據需要通過選擇多項式來決定是否” 開放 “ 一個約束。這樣可以避免在每個步驟中產生整個 EVM 電路的開銷。

這種架構首先由以太坊基金會提出,並且仍處於早期研發階段中。我們正與基金會密切合作,以找到實現 EVM 電路的最佳解決方案。到目前為止,我們已經定義了其最重要的特徵,一些操作碼已經實現 (使用 Halo2 存儲庫中的 UltraPlonk 語法)。更多細節將在後續文章中介紹。我們建議有興趣的讀者閱讀此文檔。開發過程將是透明的。這將是社區共同努力以及完全開源的設計成果。希望更多的人能夠加入並為此做出貢獻。

zkEVM 還能帶來些什麼?

zkEVM 不僅僅是 L2 擴容那麼簡單。我們可以這樣理解它,這是一個通過 L1 有效性證明來擴容以太坊 L1 的直接方式。這意味著,你可以不需要任何特殊 L2 的情況下擴容現存的 L1。

比如,你可以將 zkEVM 用作一個全節點。這個證明可以用來直接證明現有狀態之間的轉換—— 不需要將任何東西移植到 L2 中,你可以直接證明所有的 L1 交易!更廣泛地說,你可以使用 zkEVM 為整個以太坊生成一個簡潔的證明,比如 Mina。唯一需要添加的是證明遞歸 (即,將區塊的驗證電路嵌入到 zkEVM 中)[7]。

結論

對於開發者和用戶來說,在 zkEVM 上的開發和使用體驗與在一層上的沒什麼區別。並且在不犧牲安全性的前提下,zkEVM 的交易費便宜了一個數量級。已經有人提出了一種架構,即以模塊化的方式來構建 zkEVM。而且,zkEVM 利用了最近在零知識證明方面的突破來減少開銷 (包括自定義約束、查找參數、證明遞歸和硬件加速)。我們期待看到更多的人加入 zkEVM 社區,為其開發做出努力!


腳註

[1] Starkware 在幾天前宣稱其實現了可組合性 (參考文章)

[2] 電路是固定和靜態的。例如,在將程序實現為電路時,你無法使用可變上限循環。上限必須固定為其最大值。並且,它無法處理動態邏輯。

[3] 為了更清楚地說明這一點,我們在這裡詳細闡述了 EVM 電路的成本。正如我們前面所描述的,電路是固定的和靜態的。因此,EVM 電路需要包含所有可能的邏輯 (比單純的 add  操作碼要大 10,000 倍)。這意味著即便你只是想證明 add,你仍然需要承擔 EVM 電路中所有可能邏輯的開銷。這將使成本增加 10,000 倍。在執行追踪中,你需要驗證一系列操作碼,而每個操作碼都產生很大的開銷。

[4] EVM 本身沒有與 Merkle Patricia tree 緊密綁定。MPT 就是目前以太坊狀態的存儲方式。要換成另一個並不難 (如,目前有人提議使用 Verkle trees  替換 MPT)。

[5] 這是一個高度簡化的抽象概念。從技術上講,”EVM 狀態 “ 的列表更長,包括 PC、剩餘 gas、調用堆棧 (以上所有加上堆棧中每次調用的地址和靜態)、一組日誌和交易範圍的變量 (熱存儲槽、退款、自毀)。我們可以針對不同的調用環境添加標識符來直接支持可組合性。

[6] 由於存儲量很大,我們使用累加器進行存儲。對於內存和堆棧,可以使用可編輯的 Plookup (“RAM” 可以通過這種方式有效實現)。

[7] 向 zkEVM 電路添加一個完整的遞歸證明是很重要的。進行遞歸的最佳方法仍然是使用循環橢圓曲線 (即 Pasta 曲線)。需要一些” 封裝“ 過程以使其在以太坊 L1 上可驗證。

ECN 的翻譯工作旨在為中國以太坊社區傳遞優質資訊和學習資源,文章版權歸原作者所有,轉載須註明原文出處。

免責聲明:作為區塊鏈信息平台,本站所發布文章僅代表作者及嘉賓個人觀點,與 Web3Caff 立場無關。本文內容僅用於信息分享,均不構成任何投資建議及要約,並請您遵守所在國家或地區的相關法律法規。