眾所周知，欺詐證明是一種在區(qū)塊鏈領域中被廣泛應用的技術(shù)方案，其最早發(fā)源于以太坊社區(qū)，并被 Arbitrum 和 Optimism 等知名以太坊 Layer2 所采用。2023 年比特幣生態(tài)興起后，Robin Linus 提出了名為 BitVM 的方案，以欺詐證明為核心思想，在 Taproot 等比特幣既有技術(shù)的基礎上，為比特幣二層或橋提供了新的安全模型。

BitVM 曾先后推出過多個理論版本，從最早的以邏輯門電路為基元的 BitVM0，到后來以 ZK Fraud Proof 和 Groth16 驗證電路為核心的 BitVM2，與 BitVM 相關的技術(shù)實現(xiàn)路徑在不斷的演化并趨于成熟，吸引了許多從業(yè)人員的關注。大家所聽聞的 Bitlayer、Citrea、BOB、Fiamma 和 Goat Network 等項目均以 BitVM 為技術(shù)根基之一，在此基礎上進行了不同版本的實現(xiàn)。

鑒于市面上系統(tǒng)解釋 BitVM 的資料比較稀少且晦澀難懂，我們推出了以 BitVM 知識科普為目的的系列文章。考慮到 BitVM 與欺詐證明之間根深蒂固的關系，本篇文章將以欺詐證明和 ZK Fraud Proof 為主要話題，以盡可能易懂的語言為大家展開解讀。

我們將以 Optimism 的欺詐證明方案為素材，為大家解析其基于 MIPS 虛擬機和交互式欺詐證明的方案，以及 ZK 化欺詐證明的主要思路。

（Optimism 交互式欺詐證明的機制原理）

OutputRoot 和 StateRoot

Optimism 是知名的 Optimistic Rollup 項目，其基礎架構(gòu)由定序器 ( 主要模塊包含 op-node、op-geth、op-batcher 和 op-proposer) 和以太坊鏈上的智能合約組成。

當定序器處理了一批交易數(shù)據(jù)后，這些 DA 數(shù)據(jù)會被發(fā)送到以太坊上。只要你有能力運行 Optimism 節(jié)點客戶端，就可以把定序器上傳的數(shù)據(jù)下載到本地，之后你可以在本地執(zhí)行這些交易，計算出 Optimism 的當前狀態(tài)集 hash（包括但不限于每個賬戶的當前余額等數(shù)據(jù)）。

如果定序器把錯誤的狀態(tài)集 hash 上傳到了以太坊上，那么你在本地算出的狀態(tài)集 hash 會與之不同，此時你可以通過欺詐證明系統(tǒng)發(fā)起質(zhì)疑，系統(tǒng)會根據(jù)判決結(jié)果對定序器采取限制或懲罰亦或不處罰。

提到「狀態(tài)集」一詞，EVM 系區(qū)塊鏈常用到 Merkle Tree 式的數(shù)據(jù)結(jié)構(gòu)來記錄狀態(tài)集，名為 World State Trie。一筆交易被執(zhí)行后，某些賬戶的狀態(tài)會變化，World State Trie 便會發(fā)生變化，其最終 hash 也會變更。以太坊將 World State Trie 的最終 hash 稱為 StateRoot，用其表現(xiàn)狀態(tài)集的變化。

下圖展示了以太坊 stateRoot 的構(gòu)成，我們可以看到以太坊內(nèi)不同賬戶的余額，智能合約賬戶關聯(lián)的代碼 hash 等數(shù)據(jù)都會被匯總到 World State Trie 中，并依此計算出 stateRoot。

Optimism 的賬戶體系及其數(shù)據(jù)結(jié)構(gòu)大致上與以太坊一致，也采用 StateRoot 字段來體現(xiàn)狀態(tài)集的變化。OP 定序器會定期把名為 OutputRoot 的關鍵字段上傳到以太坊，而 OutputRoot 字段是由 StateRoot 和其他兩個字段共同計算得出的。

繼續(xù)回到最初的問題，當你運行 OP 的節(jié)點客戶端并在本地計算出 StateRoot，以及當前的 OutputRoot 后，假如你發(fā)現(xiàn)自己算出的結(jié)果和 OP 定序器上傳的結(jié)果不一致，便可發(fā)起欺詐證明。那么其具體的機制原理是怎樣的？下面我們將依次介紹 MIPS 虛擬機狀態(tài)驗證與交互式欺詐證明。

MIPS 虛擬機與內(nèi)存 Merkle Tree

前面我們提到，假設我發(fā)現(xiàn) OP 定序器提交的 OutputRoot 有問題，就可以發(fā)起「挑戰(zhàn)」，挑戰(zhàn)流程需要在鏈上完成一系列交互動作，交互完成后，相關智能合約會斷定 OP 定序器是否上傳了錯誤的 OutputRoot。

如果要在鏈上用智能合約驗證 OutputRoot 的正確性，最簡單的方法是在以太坊鏈上實現(xiàn)出 OP 節(jié)點客戶端，采用與 OP 定序器相同的輸入?yún)?shù)，執(zhí)行相同的程序，查驗計算結(jié)果是否一致。這個方案被稱為 Fault Proof Program，其在鏈下很容易實現(xiàn)，但想要在以太坊鏈上運行卻十分困難。因為存在兩個問題：

1. 以太坊上的智能合約無法自動獲得欺詐證明需要的輸入?yún)?shù)；

2. 以太坊每個區(qū)塊的 Gas Limit 有限，不支持復雜度過高的計算任務，我們無法在鏈上完全實現(xiàn) OP 節(jié)點客戶端

第一個問題等價于讓鏈上智能合約讀取鏈下數(shù)據(jù)，可以通過類似預言機的方案來解決。OP 在以太坊鏈上專門部署了PreimageOracle合約，欺詐證明相關合約可以在PreimageOracle 內(nèi)讀取所需的數(shù)據(jù)。

理論上任何人都可以向該合約隨意上傳數(shù)據(jù)，但 OP 的欺詐證明系統(tǒng)有辦法鑒別數(shù)據(jù)是否為其所需，具體過程在此不展開論述，因為對本文的核心話題而言不重要。

對于第二個問題，OP 開發(fā)團隊用 Solidity 編寫了一個 MIPS 虛擬機，實現(xiàn)了 OP 節(jié)點客戶端中的部分功能，足夠欺詐證明系統(tǒng)所用。MIPS 是一種常見的 CPU 指令集架構(gòu)，而 OP 定序器的代碼是用 Golang/Rust 等高級語言編寫的，我們可以將 Golang/Rust 寫的程序編譯為 MIPS 程序，然后通過以太坊鏈上的 MIPS 虛擬機進行處理。

OP 的開發(fā)團隊使用 Golang 編寫了欺詐證明所需的最簡化程序，與 OP 節(jié)點中執(zhí)行交易、生成區(qū)塊及 OutputRoot 的模塊功能基本一致。不過這套精簡化的程序仍無法「完整執(zhí)行」。

也就是說，每個 OP 區(qū)塊中包含很多筆交易，這批交易處理完后，會得到一個 OutputRoot。雖然你知道是哪個區(qū)塊高度下的 OutputRoot 有錯誤，但你如果要把該區(qū)塊中包含的交易全都放到鏈上去跑，證明對應的 OutputRoot 有錯，是不現(xiàn)實的。

此外，每筆交易的執(zhí)行流程中，又涉及到一連串 MIPS 操作碼的有序處理，你不可能把這一串操作碼都放到鏈上合約實現(xiàn)的 MIPS 虛擬機中去跑，因為涉及的計算開銷和 Gas 消耗量太大。

（MIPS 指令集工作原理）

為此，Optimism 團隊設計了交互式欺詐證明系統(tǒng)，其目的是對 OP 的交易處理流程做深度細化。從 OutputRoot 的整個計算流程中，觀測是處理哪個 MIPS 操作碼時，OP 定序器的 MIPS 虛擬機出了錯誤。若確定有錯，則可斷定定序器提供的 OutputRoot 無效。

那么問題就變得明朗了：OP 定序器處理交易打包區(qū)塊的過程，可以被拆解為對巨量 MIPS 操作碼的有序處理，每個 MIPS 操作碼執(zhí)行后，虛擬機的狀態(tài) hash 都會變化，這些記錄可以匯總為一棵 Merkle 樹。

在交互式欺詐證明流程中，要確定 OP 定序器在執(zhí)行哪個 MIPS 操作碼后，虛擬機的狀態(tài) hash 出了問題，然后在鏈上重現(xiàn)出當時 MIPS 虛擬機的狀態(tài)，執(zhí)行操作碼，觀測之后的狀態(tài) hash 是否與定序器提交的結(jié)果一致。由于只在鏈上執(zhí)行一條 MIPS 操作碼，復雜度不高，可以在以太坊鏈上完成計算流程。但要做到這些，我們需要把 MIPS 虛擬機的狀態(tài)信息如部分內(nèi)存數(shù)據(jù)上傳到鏈上。

在代碼實現(xiàn)層面，以太坊鏈上與欺詐證明相關的智能合約，會通過以下名為 Step 的函數(shù)完成最后的 MIPS 操作碼執(zhí)行流程：

上述函數(shù)參數(shù)中的 _stateData 和 _proof 代表單條 MIPS 操作碼執(zhí)行的依賴數(shù)據(jù)項，比如 MIPS 虛擬機的寄存器狀態(tài)、內(nèi)存狀態(tài) hash 等。其示意圖如下：

我們可以通過 _stateData 和 _proof 輸入這些 MIPS 虛擬機的環(huán)境參數(shù)，在鏈上運行單條 MIPS 指令，獲得權(quán)威結(jié)果。如果鏈上得出的權(quán)威結(jié)果與定序器提交的結(jié)果不一致，則說明定序器做惡。

我們一般稱 _stateData 的哈希為 statehash，可以粗略理解為整個 MIPS 虛擬機狀態(tài)的 hash。在_stateData 的幾個字段內(nèi)， memRoot 是最為精妙的設計。眾所周知，一段程序在執(zhí)行過程中會占用大量內(nèi)存，CPU 會與部分內(nèi)存地址中的數(shù)據(jù)產(chǎn)生讀寫交互。所以當我們在鏈上通過 VM.Step 函數(shù)執(zhí)行某條 MIPS 操作碼時，需要提供 MIPS 虛擬機部分內(nèi)存地址中的數(shù)據(jù)。

OP 采用了 32 位架構(gòu)的 MIPS 虛擬機，其內(nèi)存共包含 2 的 27 次方個地址，可以組織成一棵 28 層的二叉 Merkle Tree，底層葉子有 2 的 27 次方個，每個葉子記錄虛擬機的一個內(nèi)存地址中的數(shù)據(jù)。所有葉子中的數(shù)據(jù)匯總后，算出的 hash 便是 memRoot。下圖顯示了記錄 MIPS 虛擬機內(nèi)存數(shù)據(jù)的 Merkle 樹的結(jié)構(gòu)：

我們需要提供一部分內(nèi)存地址中的內(nèi)容，這部分內(nèi)容通過step 函數(shù)中的_proof 字段來上傳到以太坊鏈上。這里還要上傳基于內(nèi)存 Merkle 樹的默克爾證明，證明你 / 定序器提供的數(shù)據(jù)的確存在于內(nèi)存 Merkle 樹中，而非憑空編造的。

交互式欺詐證明

在上文中，我們已經(jīng)解決了第二個問題，完成了 MIPS 操作碼的鏈上執(zhí)行與虛擬機狀態(tài)驗證，但挑戰(zhàn)者與定序器該如何定位到那條有爭議的 MIPS 操作碼指令？

相信很多人在網(wǎng)上多多少少閱讀過交互式欺詐證明的簡單解釋，對于其二分法的思路有所聽聞。OP 團隊開發(fā)了一套被稱為 Fault Dispute Game(FDG) 的協(xié)議，在 FDG 中，包含兩個角色：挑戰(zhàn)者和防御者。

假如我們發(fā)現(xiàn)定序器提交到鏈上的 OutputRoot 有問題，那么我們就可以作為 FDG 中的挑戰(zhàn)者，而定序器會作為防御者。為了便于定位到前文提及的需要鏈上處理的 MIPS 操作碼，FDG 協(xié)議要求參與者都要在本地構(gòu)建一顆 Merkle 樹，稱為 GameTree，其具體結(jié)構(gòu)如下:

我們可以看到 GameTree 其實比較復雜，有層級嵌套的關系，由第一層級的樹及第二層級的子樹構(gòu)成，也就是說，第一層級的樹的底層葉子本身包含了一棵樹。

前面我們介紹過，定序器生成的每個區(qū)塊都包含一個 OutputRoot，而 GameTree 第一層級樹的葉子節(jié)點，就是不同區(qū)塊的 OutputRoot。挑戰(zhàn)者和防御者需要在 OutputRoot 構(gòu)成的 Merkle 樹中交互，確定哪個區(qū)塊的 OutputRoot 有爭議。

在確定爭議區(qū)塊后，我們就會下潛到 GameTree 的第二層級。第二層級的樹也是一顆 Merkle 樹，底層葉子就是上文介紹的 MIPS 虛擬機的狀態(tài) hash。在欺詐證明場景下，爭議雙方在本地構(gòu)造的 GameTree 的部分葉子節(jié)點會不一致，處理了某個操作碼之后的虛擬機狀態(tài) hash 會表現(xiàn)出不同。

之后雙方在鏈上進行多次交互，最終定位到有爭議的地方，確定需要在鏈上跑的單條 MIPS 操作碼。

至此，我們就完成了交互式欺詐證明的全部流程。總結(jié)來說，交互式欺詐證明包含兩個核心機制:

1.FDG 先定位到需要上鏈執(zhí)行的 MIPS 操作碼及此時的 VM 狀態(tài)信息；

2.在以太坊鏈上實現(xiàn)的 MIPS 虛擬機里執(zhí)行該操作碼，獲得最終結(jié)果。

ZK 化欺詐證明

我們可以看到上述傳統(tǒng)欺詐證明的交互極為復雜，需要在 FDG 流程里進行多輪交互，然后將單條指令在鏈上重放。但這種方案存在幾個難點：

1. 多輪交互需要在以太坊鏈上觸發(fā)，差不多需要幾十次交互，會產(chǎn)生大量 gas 成本；

2. 交互式欺詐證明的過程較長，一旦交互啟動，Rollup 就無法正常執(zhí)行交易；

3. 鏈上實現(xiàn)特定 VM 來重放指令是較為復雜的，開發(fā)難度極高

為了解決這些問題，Optimism 官方提出了 ZK Fraud Proof 的概念。核心在于當挑戰(zhàn)者進行挑戰(zhàn)時，指定其認為需要在鏈上重放的一筆交易，Rollup 定序器給出被挑戰(zhàn)交易的 ZK 證明，由以太坊上的智能合約進行驗證，如驗證通過，則可認為該交易的處理流程沒錯誤，Rollup 節(jié)點沒做惡。

上圖中的 Challenger 為挑戰(zhàn)者，而 Defender 是 OP 定序器。在正常情況下，OP 定序器根據(jù)接收到的交易生成區(qū)塊，并將不同區(qū)塊的狀態(tài)承諾提交到以太坊上，可以將其簡單視為區(qū)塊的哈希值。Challenger 可以根據(jù)區(qū)塊哈希進行挑戰(zhàn)。Defender 接受挑戰(zhàn)后，會生成一個 ZK 證明以證明區(qū)塊的生成結(jié)果沒有錯誤。上圖中的 Bonsai 實際上是一種 ZK Proof 生成工具。

相比于交互式欺詐證明，ZK Fraud Proof 的最大優(yōu)點是將多輪交互修改為了一輪的 ZK 證明生成和鏈上驗證，節(jié)省了大量時間和 gas 成本。而相比于 ZK Rollup，基于 ZK Fraud Proof 的 OP Rollup 不需要每次出塊都生成證明，只在被挑戰(zhàn)時臨時生成一個 ZK 證明，這也降低了 Rollup 節(jié)點的計算成本。

ZK 化欺詐證明的思路也被 BitVM2 所采用。采用 BitVM2 的項目方如 Bitlayer 和 Goat Network 及 ZKM、Fiama 等，通過比特幣腳本來實現(xiàn) ZK Proof 驗證程序，并對需要上鏈的程序尺寸進行了極大程度的精簡化。限于篇幅，本文不展開贅述，大家可等待我們之后關于 BitVM2 的文章來深入理解其實現(xiàn)路徑，敬請期待！