BitVM背景知識：欺詐證明與ZK Fraud Proof的實現思路

考慮到BitVM與欺詐證明之間根深蒂固的關係，本篇文章將以欺詐證明和ZK Fraud Proof為主要話題，以盡可能易懂的語言為大家展開解讀。

作者： Shew & Noah， 仙壤GodRealmX

眾所周知，欺詐證明是一種在區塊鏈領域中被廣泛應用的科技方案，其最早發源於乙太坊社區，並被Arbitrum和Optimism等知名乙太坊Layer2所採用。 2023年比特幣生態興起後，Robin Linus提出了名為BitVM的方案，以欺詐證明為覈心思想，在Taproot等比特幣既有科技的基礎上，為比特幣二層或橋提供了新的安全模型。

BitVM曾先後推出過多個理論版本，從最早的以邏輯門電路為基元的BitVM0，到後來以ZK Fraud Proof和Groth16驗證電路為覈心的BitVM2，與BitVM相關的科技實現路徑在不斷的演化並趨於成熟，吸引了許多從業人員的關注。 大家所聽聞的Bitlayer、Citrea、BOB、Fiamma和GoatNetwork等項目均以BitVM為科技根基之一，在此基礎上進行了不同版本的實現。

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

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

OutputRoot和StateRoot

Optimism是知名的Optimistic Rollup項目，其基礎架構由定序器（主要模塊包含op-node、op-geth、op-batcher和op-proposer）和乙太坊鏈上的智慧合約組成。

當定序器處理了一批交易數據後，這些DA數據會被發送到乙太坊上。 只要你有能力運行Optimism節點用戶端，就可以把定序器上傳的數據下載到本地，之後你可以在本地執行這些交易，計算出Optimism的當前狀態集hash（包括但不限於每個帳戶的當前餘額等數據）。

如果定序器把錯誤的狀態集hash上傳到了乙太坊上，那麼你在本地算出的狀態集hash會與之不同，此時你可以通過欺詐證明系統發起質疑，系統會根據判决結果對定序器採取限制或懲罰亦或不處罰。

提到“狀態集”一詞，EVM系區塊鏈常用到Merkle Tree式的資料結構來記錄狀態集，名為World State Trie。 一筆交易被執行後，某些帳戶的狀態會變化，World State Trie便會發生變化，其最終hash也會變更。 乙太坊將World State Trie的最終hash稱為StateRoot，用其表現狀態集的變化。

下圖展示了乙太坊stateRoot的構成，我們可以看到乙太坊內不同帳戶的餘額，智慧合約帳戶關聯的程式碼hash等數據都會被匯總到World State Trie中，並依此計算出stateRoot。

Optimism的帳戶體系及其資料結構大致上與乙太坊一致，也採用StateRoot欄位來體現狀態集的變化。 OP定序器會定期把名為OutputRoot的關鍵欄位上傳到乙太坊，而OutputRoot欄位是由StateRoot和其他兩個欄位共同計算得出的。

繼續回到最初的問題，當你運行OP的節點用戶端並在本地計算出StateRoot，以及當前的OutputRoot後，假如你發現自己算出的結果和OP定序器上傳的結果不一致，便可發起欺詐證明。 那麼其具體的機制原理是怎樣的？ 下麵我們將依次介紹MIPS虛擬機器狀態驗證與互動式欺詐證明。

MIPS虛擬機器與記憶體Merkle Tree

前面我們提到，假設我發現OP定序器提交的OutputRoot有問題，就可以發起“挑戰”，挑戰流程需要在鏈上完成一系列互動動作，互動完成後，相關智慧合約會斷定OP定序器是否上傳了錯誤的OutputRoot。

如果要在鏈上用智慧合約驗證OutputRoot的正確性，最簡單的方法是在乙太坊鏈上實現出OP節點用戶端，採用與OP定序器相同的輸入參數，執行相同的程式，查驗計算結果是否一致。 這個方案被稱為Fault Proof Program，其在鏈下很容易實現，但想要在乙太坊鏈上運行卻十分困難。 因為存在兩個問題：

1.乙太坊上的智慧合約無法自動獲得欺詐證明需要的輸入參數；

2.乙太坊每個區塊的Gas Limit有限，不支持複雜度過高的計算任務，我們無法在鏈上完全實現OP節點用戶端

第一個問題等價於讓鏈上智慧合約讀取鏈下數據，可以通過類似預言機的方案來解决。 OP在乙太坊鏈上專門部署了PreimageOracle合約，欺詐證明相關合約可以在PreimageOracle內讀取所需的數據。

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

對於第二個問題，OP開發團隊用Solidity編寫了一個MIPS虛擬機器，實現了OP節點用戶端中的部分功能，足够欺詐證明系統所用。 MIPS是一種常見的CPU指令集架構，而OP定序器的程式碼是用Golang/Rust等高階語言編寫的，我們可以將Golang/Rust寫的程式編譯為MIPS程式，然後通過乙太坊鏈上的MIPS虛擬機器進行處理。

OP的開發團隊使用Golang編寫了欺詐證明所需的最簡化程式，與OP節點中執行交易、生成區塊及OutputRoot的模塊功能基本一致。 不過這套精簡化的程式仍無法“完整執行”。

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

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

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

那麼問題就變得明朗了：OP定序器處理交易打包區塊的過程，可以被折開為對巨量MIPS操作碼的有序處理，每個MIPS操作碼執行後，虛擬機器的狀態hash都會變化，這些記錄可以匯總為一棵Merkle樹。

在互動式欺詐證明流程中，要確定OP定序器在執行哪個MIPS操作碼後，虛擬機器的狀態hash出了問題，然後在鏈上重現出當時MIPS虛擬機器的狀態，執行操作碼，觀測之後的狀態hash是否與定序器提交的結果一致。 由於只在鏈上執行一條MIPS操作碼，複雜度不高，可以在乙太坊鏈上完成計算流程。 但要做到這些，我們需要把MIPS虛擬機器的狀態資訊如部分記憶體數據上傳到鏈上。

在程式碼實現層面，乙太坊鏈上與欺詐證明相關的智慧合約，會通過以下名為Step的函數完成最後的MIPS操作碼執行流程：

上述函數參數中的_stateData和_proof代表單條MIPS操作碼執行的依賴資料項目，比如MIPS虛擬機器的寄存器狀態、記憶體狀態hash等。 其示意圖如下：

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

我們一般稱_stateData的雜湊為statehash，可以粗略理解為整個MIPS虛擬機器狀態的hash。 在_stateData的幾個欄位內， memRoot是最為精妙的設計。 眾所周知，一段程式在執行過程中會佔用大量記憶體，CPU會與部分記憶體位址中的數據產生讀寫互動。 所以當我們在鏈上通過VM. Step函數執行某條MIPS操作碼時，需要提供MIPS虛擬機器部分記憶體位址中的數據。

OP採用了32比特架構的MIPS虛擬機器，其記憶體共包含2的27次方個地址，可以組織成一棵28層的二叉Merkle Tree，底層葉子有2的27次方個，每個葉子記錄虛擬機器的一個記憶體位址中的數據。 所有葉子中的數據匯總後，算出的hash便是memRoot。 下圖顯示了記錄MIPS虛擬機器記憶體數據的Merkle樹的結構：

我們需要提供一部分記憶體位址中的內容，這部分內容通過step函數中的_proof欄位來上傳到乙太坊鏈上。 這裡還要上傳基於記憶體Merkle樹的默克爾證明，證明你/定序器提供的數據的確存在於記憶體Merkle樹中，而非憑空編造的。

互動式欺詐證明

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

相信很多人在網上多多少少閱讀過互動式欺詐證明的簡單解釋，對於其二分法的思路有所聽聞。 OP團隊開發了一套被稱為Fault Dispute Game（FDG）的協定，在FDG中，包含兩個角色：挑戰者和防禦者。

假如我們發現定序器提交到鏈上的OutputRoot有問題，那麼我們就可以作為FDG中的挑戰者，而定序器會作為防禦者。 為了便於定位到前文提及的需要鏈上處理的MIPS操作碼，FDG協定要求參與者都要在本地構建一顆Merkle樹，稱為GameTree，其具體結構如下：

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

前面我們介紹過，定序器生成的每個區塊都包含一個OutputRoot，而GameTree第一層級樹的葉子節點，就是不同區塊的OutputRoot。 挑戰者和防禦者需要在OutputRoot構成的Merkle樹中互動，確定哪個區塊的OutputRoot有爭議。

在確定爭議區塊後，我們就會下潜到GameTree的第二層級。 第二層級的樹也是一顆Merkle樹，底層葉子就是上文介紹的MIPS虛擬機器的狀態hash。 在欺詐證明場景下，爭議雙方在本地構造的GameTree的部分葉子節點會不一致，處理了某個操作碼之後的虛擬機器狀態hash會表現出不同。

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

至此，我們就完成了互動式欺詐證明的全部流程。 總結來說，互動式欺詐證明包含兩個覈心機制：

1.FDG先定位到需要上鏈執行的MIPS操作碼及此時的VM狀態資訊；

2.在乙太坊鏈上實現的MIPS虛擬機器裏執行該操作碼，獲得最終結果。

ZK化欺詐證明

我們可以看到上述傳統欺詐證明的互動極為複雜，需要在FDG流程裏進行多輪互動，然後將單條指令在鏈上重放。 但這種方案存在幾個難點：

1.多輪互動需要在乙太坊鏈上觸發，差不多需要幾十次互動，會產生大量gas成本；

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

3.鏈上實現特定VM來重放指令是較為複雜的，開發難度極高

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

上圖中的Challenger為挑戰者，而Defender是OP定序器。 在正常情况下，OP定序器根據接收到的交易生成區塊，並將不同區塊的狀態承諾提交到乙太坊上，可以將其簡單視為區塊的雜湊值。 Challenger可以根據區塊雜湊進行挑戰。 Defender接受挑戰後，會生成一個ZK證明以證明區塊的生成結果沒有錯誤。 上圖中的Bonsai實際上是一種ZK Proof生成工具。

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

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