首頁

Partnered With:

以代碼角度解讀zkEVM

閱讀本文需 13 分鐘

zkEVM是用zk-SNARK技術將EVM的執行進行證明

原文標題：《零知識證明—zkEVM解讀》

原文作者：Star Li, 星想法

衆所周知，zkRollup 是 L2 中安全等級最高的 Rollup 方案，但是 zkRollup 目前沒有可編程性，更無從談起可組合性。zkEVM 是用 zk-SNARK 技術將 EVM 的執行進行證明。zkRollup 支持了 zkEVM，在 L2 就能支持兼容 EVM 的智能合約。目前有幾個團隊都在研究 zkEVM 的實現。除了 AppliedZKP 公開了一些電路設計的思路和細節外，其他團隊都沒有詳細的資料。AppliedZKP 有關 zkEVM 的設計資料如下：

https://github.com/appliedzkp/zkevm-specs

https://hackmd.io/Hy_nqH4yTOmjjS9nbOArgw

本文詳細分析 AppliedZKP 構想的 zkEVM 設計。本文中提到的 zkEVM 專指 AppliedZKP 提出的 zkEVM 方案。

01 背景

以太坊的每一個節點爲了確保交易的正確性，需要針對每一個區塊中的每一筆交易執行。也就是說，每一個節點需要驗證以太坊的整個交易歷史，並且要一筆筆的進行執行驗證。zkEVM 利用零知識證明技術（zk-SNARK）證明：

· 針對智能合約的交易執行，生成交易證明。在 L2 實現 zkRollup 支持可編程性。

· 針對以太坊的每一個區塊，生成區塊證明。

這些證明都由兩部分組成：State proof（狀態證明）和 EVM proof（EVM 執行證明）。在一條交易執行過程中，State 包括 Storage，Memory 以及 Stack 的狀態。

Bus-mapping 是設計的基礎思想。一般的 PC 體系結構中，CPU 通過總線訪問存儲（內存/硬盤），也就是計算和存儲分開。zkEVM 採用的同樣的架構思想，狀態的變化和指令的執行分開，並且分別由 State proof 和 EVM proof 進行證明。

State proof 負責 Bus Mapping 信息的一致性和正確性。一致性指的 Bus Mapping 和 State 之間的讀寫一致。正確性指的是 Bus Mapping 中的讀寫狀態正確。EVM proof 負責 EVM 的 op code 的執行正確（如果涉及到 State 的 op code，保證存儲相關的操作正確）。

EVM Execution 和存儲之間好像有一條存儲訪問的總線一樣：EVM Execution 通過 Bus Mapping 獲取或者存儲執行需要的相關狀態。採用 Bus Mapping 的方式，需要證明 Bus Mapping 和 State 以及 EVM Execution 之間的「總線」操作的正確性。邏輯上分成如下的幾步：讀取狀態，EVM 執行（修改狀態），寫回狀態。Bus Mapping 包括了讀取以及寫回狀態。

02 Bus Mapping

Bus Mapping 包括了兩種狀態，一種是讀取老的狀態，一種是寫回生成新的狀態。無論是老的狀態和新的狀態，Bus Mapping 都是「包含」關係。這種「包含」的 mapping 關係可以通過 Plookup 算法證明。

存儲狀態（Storage/Memory/Stack），採用 key-value 的格式進行表示。key-value 對的綁定關係可以實現爲一個序列：

想證明某個 key-value 對在一些 key-value 中，可以通過三個 Plookup 證明實現：

keys 和 values 是 State 相關的 key-value 對。mappings 是所有 key-value 對行程的 mapping 數組。通過三個 Plookup 證明：

1/ 某個 mapping 的 key 在 keys 中

2/ 某個 mapping 的 value 在 values 中

3/ 某個 mapping 在 mappings 中

並且 mapping 和 key-value 滿足 build_mapping 建立的關係。如上的這些證明，能夠證明某個 key-value 對是 keys 和 values 的 mapping 中的部分。

在如上的基礎上，可以定義出 bus_mapping 的數據結構：

其中，global_counter 是 slot 的編號。slot 是一個證明邏輯的最小單元。一個交易的證明由多條指令組成，每個指令可能由多個 slot 組成。op 是操作類型，邏輯上由讀和寫組成。prog_counter 是 pc。所有的 bus_mapping 中的讀取操作可以通過 plookup 確定是不是「屬於」當前的 State。讀取狀態需要和老的存儲狀態一致，寫入狀態需要和更新後的存儲狀態一致。

在 Bus mapping 的基礎上，採用 State Proof 和 EVM Proof 證明數據的讀寫正確以及和 opcode 的語義一致。

03 State Proof

State Proof 證明了和「存儲」相關的讀寫和 Bus Mapping 的數據一致。也就是在「總線」上的讀寫數據的一致性。State Proof 根據存儲類型分成三種證明。

Storage

和 Storage 相關的 op code 羅列如下：

相關的 op code 分爲兩種，一種是 Storage 讀，一種是 Storage 寫。比如 SLOAD 就是從 Storage 讀取數據到 Stack 中。Storage 相關的 op code 對應的讀寫數據在 Bus mapping 中。注意，State Proof 中的 Storage 證明只單純證明 Storage 相關的讀寫操作是否在 bus mapping 中。至於讀寫數據的語義信息是通過 EVM proof 進行證明的。

Memory

從 State Proof 證明的角度看，所有的內存操作按照 index 進行排序。index 是內存地址。舉個例子：

地址 0 和地址 1 的相關內存操作羅列在一起。每個內存地址在程序開始執行時會初始化爲 0。也就是 global_counter 爲零時，index 0/1 初始爲 0。從 Bus Mapping 的角度看，這些內存操作如下：

對於每個地址上的讀寫數據都需要保持一致性。這些一致性由如下的約束檢查：

藍色部分限制內存只有讀寫操作，褐色部分限制每個地址內存初始爲零，並且讀寫數據一致，橘黃色部分限制相關的內存操作在 bus mapping 中。

Stack

Stack 的操作主要分爲三類：Push/Pop，Dup 和 Swap。用 1024 大小的數組模擬 Stack 實現。Stack 的位置信息的檢查由 EVM proof 完成。Stack 的數據和 bus mapping 的關係由 Stack proof 完成。基本思路和 Memory 一致。

04 EVM Proof

EVM Proof 是 EVM 執行相關約束的核心。EVM proof 需要證明如下的一些邏輯：

1/ EVM 執行的代碼是指定的 transaction 的代碼邏輯

2/ 和存儲相關的語義是否正確，比如 Stack 的位置管理，SLoad 數據和 Stack 的數據是否一致等等

3/ 和計算相關的語義是否正確，比如算術計算等等

4/ 跳轉邏輯是否正確，比如 Call 指令

5/ Gas 消耗計算正確

6/ 程序終止是否正確

Slot 是電路的基本單元。多個 Slot 可以組合在一起實現一個 op code 的語義。

算術計算

以加法爲例，通過 Plookup 可以證明 8bit 整數的計算。通過多個 8bit 的加法以及進位，可以實現任意長度的加法。

兩個數的比較的實現原理和加法類似。

跳轉邏輯

call_id 記錄一個執行環境。爲了綁定和跳轉邏輯的關係，call_id 採用如下的計算邏輯：

call_id -> rlc(calldata_callid, call_data_start_addr, call_data_size, return_data_callid,return_data_start_addr, return_data_size, origin, caller, call_value, call_stack_depth)

rlc 是 random linear combination。

EVM proof 的邏輯相對來說比較複雜。當前公佈的文檔沒有展開描述設計的細節。zkEVM 給出了大致的設計思路，細節的部分還需要進一步細化。