原文標題：《zkEVM：設計挑戰與解決思路》
撰文：Ye Zhang@Scroll
編譯：曾汨
太長不看
我們相信 zk-Rollup 會成為 “香餑餑” —— 其成本優勢和極高的安全性使得一眾 Layer 2 可擴展性方案相形見絀，然而，現有的 zk-Rollup 實現都是針對特定應用的，因此我們很難在某個 zk-Rollup 內構建具有可組合性的通用 dApp，把現有的應用遷移過來也無從談起，我們引入了 zkEVM 用來為通用的 EVM 驗證生成零知識證明。這樣一來，我們就可以構建出完全兼容 EVM 的 zk-Rollup，以便現有以太坊應用輕松遷移到這個 zk-Rollup 上。
在本文中，我們明確指出了 zkEVM 在設計上面臨哪些挑戰以及為何 zkEVM 在當下有可能實現，我們還給出了更加具體、直觀的認知，并概述了如何從頭開始構建 zkEVM，
背景
zk-Rollup 是公認的最佳以太坊可擴展性方案。它不僅在安全性上媲美以太坊 Layer 1，而且在交易敲定速度上是 Layer 2 解決方案的翹楚（點擊此處，查看詳細的對比分析（原文、譯本））。
zk-Rollup 的基礎原理是將大量交易打包到一個 Rollup 區塊內，并在鏈下為該區塊生成一個簡潔證明，隨后，Layer 1 上的智能合約只需驗證該證明即可直接應用新的狀態，無需重新執行這些交易，這樣就可以節約一個數量級的 gas 費，因為證明的驗證成本遠低于重新執行的計算成本。另一個好處是可以通過數據壓縮來節省存儲空間（即，僅在鏈上存儲最少量的數據用于驗證），
雖然 zk-Rollup 安全且高效，但是其應用依然局限于付款和互換（swap）。通用 dApp 構建起來很難，主要有以下兩個原因：
- 第一，如果你想在某個 zk-Rollup 內開發 dApp，你需要使用一種特殊的語言（即，R1CS）來編寫你的所有智能合約的邏輯，這種語言有著復雜的語法，而且要求使用者精通零知識證明。
- 第二，現有的 zk-Rollup 實現不支持可組合性1，因此，在 Layer 2 上，不同的 zk-Rollup 應用之間無法交互，嚴重破壞了 DeFi 應用的可組合性，
簡而言之，zk-Rollup 目前對開發者并不友好，而且功能有限，這是我們想要解決的最大問題，我們想要通過直接支持原生 EVM 驗證來提供最好的開發者體驗，并在 Layer 2 上支持可組合性，讓現有以太坊應用可以原封不動地遷移到 zk-Rollup 上，
在 zk-Rollup 中構建通用 dApp
我們可以通過以下兩種方法在 zk-Rollup 內構建通用 dApp：
- 一種是為不同 dApp 構建專用電路（“ASIC”），
- 另一種是構建通用 “EVM” 電路用于執行智能合約，
第一種方法要求開發者為不同 dApp 設計專用 “ASIC” 電路。這是最傳統的使用零知識證明的方式，自定義的電路設計有助于降低各個 dApp 的成本，但是，這也帶來了可組合性問題，因為電路是 “靜態的”，而且對電路設計知識的高度依賴導致開發者體驗很糟糕2。
第二種方法不需要任何特殊的設計，也不要求開發者具備極強的專業知識，這種基于機器的證明背后的深層概念是，任何程式終將運行在 CPU 上，因此，我們只需要構建一個通用 CPU 電路來驗證低級 CPU 操作，然后，我們可以使用這個 CPU 電路來驗證任何程式執行，就本文的應用場景而言，程式指的就是智能合約，CPU 就是 EVM。然而，由于成本過高，這個方法在過去幾年里沒有得到普遍采用，例如，即使你只想證明某一個操作中 add 的結果是正確的，你依然需要負擔整個 EVM 電路的成本，如果你的執行追蹤中有上千個操作，證明者就要負擔 1000 倍的 EVM 電路成本3。
最近，有很多研究致力于利用這兩種方法來優化零知識證明，包括（i）提議新的零知識證明友好型原語 Poseidon 哈希（Poseidon 哈希在電路中的效率是 SHA256 的 100 倍）；（ii）持續提高通用可驗證虛擬機的效率，就像 TinyRAM 那樣；（iii）越來越多的通用優化技巧，如 Plookup，以及運行速度更快的密碼學庫，在我們之前的文章中，我們提議為每個 dApp 設計 “ASIC” 電路，并讓它們通過密碼學承諾進行通信，然而，根據社區的反饋，我們改變了研究重點，將聚焦于使用第二種方式構建通用 EVM 電路（所謂的 “zkEVM”），zkEVM 將帶來與 Layer 1 完全相同的開發體驗。我們不會把設計復雜性留給開發者，而是利用自定義 EVM 電路設計取而代之，解決效率問題，
zkEVM 的設計挑戰
zkEVM 構建起來很難，盡管多年來這種直覺都很清晰，但是至今還沒有人成功構建出原生 EVM 電路，不同于 TinyRAM，zkEVM 在設計和實現上更具挑戰性，具體原因如下：
- 第一，EVM 對橢圓曲線的支持有限。目前，EVM 只支持 BN254 配對，由于不直接支持循環橢圓曲線，EVM 很難實現證明遞歸。在這種設置下，我們也很難使用其它專用協議。驗證算法必須是 EVM 友好型的，
- 第二，EVM 的 word 大小是 256 位，EVM 基于 256 位整數運行（就像大多數基于 32～64 位整數運行的普通虛擬機那樣），零知識證明則 “天然” 基于素域運行。在電路中進行 “錯配域算術” 需要范圍證明，進而給每個 EVM 操作增加大約 100 個約束，這會將 EVM 電路大小增加兩個數量級，
- 第三，EVM 有許多特殊的操作碼。不同于傳統虛擬機，EVM 有很多特殊的操作碼，如 CALL ，以及與執行環境和 gas 相關的錯誤類型。這會給電路設計帶來新的挑戰，
- 第四，EVM 是基于堆棧的虛擬機，SyncVM（zksync）和 Cario（starkware）架構在基于寄存器的模型中定義自己的 IR/AIR，它們構建了一個專門的編譯器來將智能合約代碼編譯成一個新的零知識證明友好型 IR。該方法是語言兼容的，而非原生 EVM 兼容的。無論是證明基于堆棧的模型，還是直接支持原生工具鏈，都會變得更加困難，
- 第五，以太坊存儲布局帶來了高昂的成本。以太坊存儲布局高度依賴 Keccak 和一個巨型 MPT4。二者都不是零知識證明友好型的，而且會產生高昂的證明成本。例如，Keccak 哈希的電路大小是 Poseidon 哈希的 1000 倍。但是，如果你將 Keccak 哈希替換成另一種哈希，就會給現有的以太坊基礎設施帶來一些兼容問題。
- 第六，基于機器的證明帶來了高昂的成本。即使你可以妥善處理上述所有問題，你依然需要找到一種有效的方法來將它們組合起來得到一個完整的 EVM 電路。正如我在上一節中提到的，即使像 add 這樣簡單的操作碼也有可能需要你負擔整個 EVM 電路的成本。
為何 zkEVM 在當下有可能實現
得益于研究者取得的重大進展，過去兩年里越來越多效率問題得到了解決，zkEVM 的證明成本終于不再是障礙！最主要的技術進展體現在以下幾個方面：
- 多項式承諾（polynomial commitment）的使用，過去幾年來，大多數簡潔零知識證明協議都使用 R1CS，PCP 查詢被編碼到了特定于應用的受信任起步設置（trusted setup）中，這往往會增加電路的大小，導致很多自定義優化都無法實現，因為每個約束的度必須是 2（雙線性配對（bilinear pairing）只允許進行一次指數乘法計算），有了多項式承諾方案，你可以通過通用設置（universal setup）乃至透明設置（transparent setup）將你的約束提高到任何階，大幅提高了后端選擇的靈活性。
- 查找表參數和自定義小工具的出現。另一個重要優化是查找表的使用，這個優化首次提議于 Arya，然后在 Plookup 中得到實現。對于零知識證明不友好型原語（即，AND 和 XOR 等位運算）來說，查找表可以省很多事，自定義小工具可以高效實現高階的約束。TurboPlonk 和 UltraPlonk 定義了優雅的程式語法，降低了使用查找表和定義自定義小工具的難度，這對于降低 EVM 電路的成本幫助很大。
- 遞歸證明的可行性越來越高，過去，遞歸證明會帶來很高的成本，因為它依賴特殊的配對友好型循環橢圓曲線（即，基于 MNT 曲線的結構），這會產生很高的計算成本。然而，越來越多技術能夠在不犧牲效率的情況下使得遞歸證明成為可能。例如，Halo 無需配對友好型曲線，還可以使用特殊的內積參數來攤銷遞歸成本。Aztec 證明了可以直接聚合現有協議的證明（查找表可以減少非原生域運算的成本，從而縮小驗證電路的體積），同樣的電路規模現在能夠實現更多的功能。
- 硬件加速正在提高證明效率。據我們了解，我們已經為證明程式打造了最快的 GPU 和 ASIC/FPGA 加速器。我們關于 ASIC 證明程式的論文已于今年被頂級計算機學術會議 ISCA 接受了，我們的 GPU 證明器比 Filecoin 的實現快了大約 5 至 10 倍，可大幅提高證明器的計算效率，
zkEVM 是如何運作和構建的？
除了強烈的直覺和技術改進，我們還得想明白我們需要證明的是什么，并構思好一個更加具體的架構，更多的技術細節和對比分析會留到之后的文章中進行介紹。在本文中，我們會介紹整個工作流程和一些核心概念，
開發者和用戶的工作流程
開發者可以使用 EVM 兼容語言實現智能合約并在 Scroll 上部署編譯好的字節碼，之后，用戶可以發送交易來與已經部署好的智能合約進行交互，用戶和開發者將獲得與在 Layer 1 上相同的體驗，但是，gas 費會顯著降低，交易將在 Scroll 上即時得到預先確認（提現只需幾分鐘即可敲定），
zkEVM 的工作流程
即使外部工作流程保持不變，Layer 1 和 Layer 2 的底層處理過程是完全不同的：
- Layer 1 靠的是重新執行智能合約，
- Layer 2 靠的是 zkEVM 電路的有效性證明
我們來詳細解釋下 Layer 1 和 Layer 2 上的交易有何不同，在 Layer 1 上，已部署智能合約的字節碼都存儲在以太坊 storage（存儲項）內，交易將在點對點網路中傳播。對于每一筆交易，每個全節點需要加載對應的字節碼并在 EVM 上執行以獲得相同的狀態（交易將作為輸入數據），在 Layer 2 上，字節碼同樣存儲在存儲項內，用戶的操作方式也相同，交易將在鏈下發送至一個中心化的 zkEVM 節點。然后，zkEVM 不單執行字節碼，還將生成一個簡潔證明來表明交易達成后狀態已正確更新。最后，Layer 1 合約將驗證該證明并更新狀態，不再重新執行交易。我們來深入了解一下執行過程，看看 zkEVM 最終需要證明的是什么，在原生執行中，EVM 將加載字節碼并從頭開始逐個執行字節碼中的操作碼。每個操作碼都可以被看作是在執行以下三個步驟：(i) 從堆棧（stack）、memory 或存儲項中讀取元素；(ii) 基于這些元素執行計算；(iii) 將結果寫入堆棧、memory 或存儲項5。例如，add 操作碼需要從堆棧中讀取兩個元素，將它們相加并將結果寫入堆棧，因此，顯而易見的是，zkEVM 的證明需要包含以下幾個方面（與執行流程對應）：
- 字節碼從永久存儲項中正確加載（你正在運行從某個地址加載的正確操作碼）
- 字節碼中的操作碼始終逐一執行（字節碼按順序執行，不會遺漏或跳過任何操作碼）
- 每個操作碼均正確執行（每個操作碼中的三個子操作都正確執行，R/W + 計算）
zkEVM 設計亮點
在為 zkEVM 設計架構時，我們需要分別采取措施滿足上述三個方面的需求。
1. 我們需要為某個密碼學累加器設計一個電路，
這是為了起到 “可驗證存儲器” 的作用，我們需要通過某種技術來證明讀取過程是準確無誤的。密碼學累加器可以更高效地實現這一點 6。我們以默克爾樹為例，已部署的字節碼會被存儲為默克爾樹上的葉節點。然后，驗證者可以使用簡潔證明來驗證該字節碼是否正確加載自某個地址（即，驗證電路中的默克爾路徑），針對以太坊存儲，我們需要這個電路同時兼容默克爾-帕特里夏樹和 Keccak 哈希函數。
2. 我們需要設計一個電路將字節碼與實際的執行追蹤關聯起來，
將字節碼轉移到靜態電路中會帶來一個問題：像 jump 這樣的條件式操作碼（與智能合約中的 loop、if else 語句相對應）可能會跳轉到任何地方。在某個人使用特定輸入運行該字節碼之前，跳轉目的地都是不確定的，這就是為什么我們需要驗證實際的執行蹤跡。執行蹤跡可以被認為是 “展開的字節碼”，包含按實際執行順序排列的操作碼（即，如果你跳轉到另一個位置，蹤跡中將包含該目標操作碼和位置），證明者將直接提供執行蹤跡作為電路的見證數據。我們需要證明該執行追蹤確實是特定的字節碼使用特定的輸入 “展開” 的。我們的想法是強制讓程式計數器的值保持一致，針對目的地不確定的問題，解決思路是讓證明者提供一切數據，然后，你可以使用查找參數高效地檢查一致性（即，證明帶有準確全局計數器的操作碼包含在 “總線” 中）。
3. 我們需要為每個操作碼設計電路（證明每個操作碼中的讀、寫和計算都是正確的），
這是最重要的部分 —— 證明執行追蹤中的每個操作碼都是正確且一致的。如果你直接將所有東西都放在一起，會產生高昂的成本。此處重要的優化思路是：
- 我們可以將 R/W 和計算分成兩個證明。一個證明會將所有操作碼用到的元素都放到 “總線” 中，另一個證明會證明對 “總線” 上元素的計算是正確執行的。這會大幅降低每個部分的成本（即，你在生成計算證明時無需考慮整個 EVM 存儲）。在更詳細的規范中，前者被稱為 “狀態證明”，后者被稱為 “EVM 證明”，另一個發現是，查找聲明可以有效處理 “總線映射” ，
- 我們可以為每個操作碼設計度數更高的定制化約束（即，我們可以將一個 EVM word 切分成多個數據塊，以便更高效地處理），我們可以選擇是否根據需求通過一個選擇符多項式來 “打開” 一個約束，這樣可以避免每個操作都要消耗整個 EVM 電路的成本，
這個架構最初由以太坊基金會提出，依然處于早期階段，正在積極開發中，我們正在與以太坊基金會進行密切合作，旨在找到最佳方式實現該 EVM 電路。迄今為止，我們已經定義了 EVM 電路最重要的特點，并（使用 Halo2 庫中的 UltraPlonk 語法）實現了一些操作碼（點擊此處查看）。更詳細的內容將在后續文章中介紹，我們推薦感興趣的讀者閱讀這篇文檔。開發流程將是透明化的，這將是集整個社區之力的完全開源的設計，希望會有更多人加入進來，貢獻出一份力量，
zkEVM 還能給我們帶來什么？
zkEVM 遠不僅僅是 Layer 2 擴容。我們可以將它理解為通過 Layer 1 有效性證明擴展以太坊 Layer 1 的直接方式。這意味著不需要任何特殊的 Layer 2 就可以擴展現有的 Layer 1，例如，你可以將 zkEVM 當作全節點來使用，該證明可以用來直接證明現有狀態之間的轉換，無需將任何東西遷移到 Layer 2 上，你可以直接證明所有 Layer 1 交易！更寬泛地來說，你可以使用 zkEVM 為整個以太坊生成簡潔證明，就像 Mina 那樣，唯一需要增加的東西是證明遞歸（即，將區塊的驗證電路嵌入 zkEVM）7，
結論
zkEVM 可以為開發者和用戶提供相同的體驗，而且可以在不犧牲安全性的前提下將成本降低幾個數量級。目前已經有人提議了一種架構，可以通過模塊化方式構建 zkEVM。這個架構利用零知識證明的最新突破降低成本（包括自定義約束、查找參數、證明遞歸和硬件加速），我們期待看到更多人為 zkEVM 社區貢獻力量，與我們一起進行頭腦風暴！
注：
- Starkware 于 2021 年 9 月 1 日的公告中聲明已實現可組合性（點擊此處，查看公告），
- 電路是固定且靜態的，例如，在將一個程式實現為電路時，你無法使用可變上限循環，上限必須固定為最大值，電路無法處理動態邏輯，
- 為便于讀者理解，我們在這里詳細說明 EVM 電路的成本。正如前文所言，電路是固定且靜態的，因此，EVM 電路需要包含所有可能的邏輯（這個體量是僅包含 add 的電路的 10000 倍）。這就意味著，即使你只想證明 add，你依然需要負擔該 EVM 電路中可能包含的所有邏輯的成本。也就是說，成本被放大了 10000 倍，在執行追蹤中，你需要證明一連串操作碼，而且每個操作碼都會帶來高昂的成本，
- EVM 本身并沒有與默克爾-帕特里夏樹（MPT）緊密綁定，目前，MPT 僅用于存儲以太坊狀態，要換一個很容易（有人提議使用 Verkle 樹替換掉 MPT）。
- 這是經過高度簡化的抽象概念，從技術上來說，“EVM 狀態” 的名單更長，包括程式計數器、gas 余量、調用棧（以上所有加上堆棧中每次調用的地址和靜態）、一組日志和交易范圍變量（熱存儲槽、退款、自毀）。我們可以另外引入針對不同調用環境的標識符來直接支持可組合性。
- 由于存儲量很大，我們使用累加器進行存儲，內存和堆棧可以使用可編輯的 Plookup（我們可以通過這種方式有效地實現 “RAM”）。
- 將一個完整的遞歸證明添加進 zkEVM 電路并非易事。實現遞歸的最好方式還是使用循環橢圓曲線（即，Pasta 曲線）。我們需要引入某種 “包裝（wrapping）” 過程讓遞歸在以太坊 Layer 1 上可驗證。
