作者：Shew & Noah，仙壤GodRealmX
眾所周知，欺詐證明是一種在區(qū)塊鏈領(lǐng)域中被廣泛應(yīng)用的技術(shù)方案，其最早發(fā)源于以太坊社區(qū)，并被Arbitrum和Optimism等知名以太坊Layer2所采用。2023年比特幣生態(tài)興起后，Robin Linus提出了名為BitVM的方案，以欺詐證明為核心思想，在Taproot等比特幣既有技術(shù)的基礎(chǔ)上，為比特幣二層或橋提供了新的安全模型。
BitVM曾先后推出過多個理論版本，從最早的以邏輯門電路為基元的BitVM0，到后來以ZK Fraud Proof和Groth16驗證電路為核心的BitVM2，與BitVM相關(guān)的技術(shù)實現(xiàn)路徑在不斷的演化并趨于成熟，吸引了許多從業(yè)人員的關(guān)注。大家所聽聞的Bitlayer、Citrea、BOB、Fiamma和Goat?Network等項目均以BitVM為技術(shù)根基之一，在此基礎(chǔ)上進行了不同版本的實現(xiàn)。
鑒于市面上系統(tǒng)解釋BitVM的資料比較稀少且晦澀難懂，我們推出了以BitVM知識科普為目的的系列文章。考慮到BitVM與欺詐證明之間根深蒂固的關(guān)系，本篇文章將以欺詐證明和ZK Fraud Proof為主要話題，以盡可能易懂的語言為大家展開解讀。
我們將以O(shè)ptimism的欺詐證明方案為素材，為大家解析其基于MIPS虛擬機和交互式欺詐證明的方案，以及ZK化欺詐證明的主要思路。
（Optimism交互式欺詐證明的機制原理）
OutputRoot和StateRoot
Optimism是知名的Optimistic Rollup項目，其基礎(chǔ)架構(gòu)由定序器 (主要模塊包含op-node、op-geth、op-batcher和op-proposer) 和以太坊鏈上的智能合約組成。
當(dāng)定序器處理了一批交易數(shù)據(jù)后，這些DA數(shù)據(jù)會被發(fā)送到以太坊上。只要你有能力運行Optimism節(jié)點客戶端，就可以把定序器上傳的數(shù)據(jù)下載到本地，之后你可以在本地執(zhí)行這些交易，計算出Optimism的當(dāng)前狀態(tài)集hash（包括但不限于每個賬戶的當(dāng)前余額等數(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)不同賬戶的余額，智能合約賬戶關(guān)聯(lián)的代碼hash等數(shù)據(jù)都會被匯總到World State Trie中，并依此計算出stateRoot。
Optimism的賬戶體系及其數(shù)據(jù)結(jié)構(gòu)大致上與以太坊一致，也采用StateRoot字段來體現(xiàn)狀態(tài)集的變化。OP定序器會定期把名為OutputRoot的關(guān)鍵字段上傳到以太坊，而OutputRoot字段是由StateRoot和其他兩個字段共同計算得出的。
繼續(xù)回到最初的問題，當(dāng)你運行OP的節(jié)點客戶端并在本地計算出StateRoot，以及當(dāng)前的OutputRoot后，假如你發(fā)現(xiàn)自己算出的結(jié)果和OP定序器上傳的結(jié)果不一致，便可發(fā)起欺詐證明。那么其具體的機制原理是怎樣的？下面我們將依次介紹MIPS虛擬機狀態(tài)驗證與交互式欺詐證明。
MIPS虛擬機與內(nèi)存Merkle Tree
前面我們提到，假設(shè)我發(fā)現(xiàn)OP定序器提交的OutputRoot有問題，就可以發(fā)起“挑戰(zhàn)”，挑戰(zhàn)流程需要在鏈上完成一系列交互動作，交互完成后，相關(guā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有限，不支持復(fù)雜度過高的計算任務(wù)，我們無法在鏈上完全實現(xiàn)OP節(jié)點客戶端
第一個問題等價于讓鏈上智能合約讀取鏈下數(shù)據(jù)，可以通過類似預(yù)言機的方案來解決。OP在以太坊鏈上專門部署了PreimageOracle合約，欺詐證明相關(guān)合約可以在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ū)塊中包含的交易全都放到鏈上去跑，證明對應(yīng)的OutputRoot有錯，是不現(xiàn)實的。
此外，每筆交易的執(zhí)行流程中，又涉及到一連串MIPS操作碼的有序處理，你不可能把這一串操作碼都放到鏈上合約實現(xiàn)的MIPS虛擬機中去跑，因為涉及的計算開銷和Gas消耗量太大。
（MIPS指令集工作原理）
為此，Optimism團隊設(shè)計了交互式欺詐證明系統(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)出當(dāng)時MIPS虛擬機的狀態(tài)，執(zhí)行操作碼，觀測之后的狀態(tài)hash是否與定序器提交的結(jié)果一致。由于只在鏈上執(zhí)行一條MIPS操作碼，復(fù)雜度不高，可以在以太坊鏈上完成計算流程。但要做到這些，我們需要把MIPS虛擬機的狀態(tài)信息如部分內(nèi)存數(shù)據(jù)上傳到鏈上。
在代碼實現(xiàn)層面，以太坊鏈上與欺詐證明相關(guā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是最為精妙的設(shè)計。眾所周知，一段程序在執(zhí)行過程中會占用大量內(nèi)存，CPU會與部分內(nèi)存地址中的數(shù)據(jù)產(chǎn)生讀寫交互。所以當(dāng)我們在鏈上通過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操作碼，F(xiàn)DG協(xié)議要求參與者都要在本地構(gòu)建一顆Merkle樹，稱為GameTree，其具體結(jié)構(gòu)如下:
我們可以看到GameTree其實比較復(fù)雜，有層級嵌套的關(guān)系，由第一層級的樹及第二層級的子樹構(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)欺詐證明的交互極為復(fù)雜，需要在FDG流程里進行多輪交互，然后將單條指令在鏈上重放。但這種方案存在幾個難點：
1. 多輪交互需要在以太坊鏈上觸發(fā)，差不多需要幾十次交互，會產(chǎn)生大量 gas 成本；
2. 交互式欺詐證明的過程較長，一旦交互啟動，Rollup就無法正常執(zhí)行交易；
3. 鏈上實現(xiàn)特定VM來重放指令是較為復(fù)雜的，開發(fā)難度極高
為了解決這些問題，Optimism官方提出了ZK Fraud Proof的概念。核心在于當(dāng)挑戰(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驗證程序，并對需要上鏈的程序尺寸進行了極大程度的精簡化。限于篇幅，本文不展開贅述，大家可等待我們之后關(guān)于BitVM2的文章來深入理解其實現(xiàn)路徑，敬請期待！
喜來順財經(jīng)
