詳解 Rollup 的兩種驗證狀態：欺詐證明和非互動式欺詐證明

原文標題：《真正理解 Layer2》

原文作者：web3探索者

Layer2的核心目標是提升區塊鏈處理速度，原因是無法在一層中同時滿足安全性、處理速度、去中心化（不可能三角）。

L2有三種模式：狀態通道（state channel）、plasma、rollup。三者因為各自的缺陷沒有成為主角，所以本文我們只介紹rollup機制，其他模式有興趣可以自行查閱。

一、Rollup

Rollup 的核心思路是在L1上保存能夠驗證交易過程的憑證，而將交易過程(計算過程)還有狀態存儲運行在L2中。

何為交易過程的憑證，我們知道交易執行的過程就是由1個狀態轉移到另外1個狀態的過程，如果L1知道了一組交易前的狀態和一組交易後的狀態還有這一組交易，自然可以驗證這組交易對應的狀態轉移是否正確。

如上圖所示，發布者將交易前狀態樹的根hash 交易後狀態樹的根hash以及交易發布到L1上，L1智能合約確認交易前狀態樹根hash是否和存儲的根hash一致。交易前的根hash一致說明起始狀態正確，那麼本次交易過程是否正確如何驗證呢？最安全的做法肯定是我們每次都在L1上重新執行L2的交易樹，進行狀態轉移，但這樣L2失去了意義，還是會面臨不可能三角中處理速度的問題。

如何去驗證狀態轉移是否正確也引出了2種不同的Layer2 Rollup機制。

第一種是欺詐證明，即默認相信存入的狀態是正確的，等待其他參與者提出欺詐證明挑戰，每一次L2發布到L1時的節點都要繳納一定的保障金，當欺詐被證明後 回滾到前一狀態，發布者保證金會被全部扣除，部分給到挑戰者，部分直接銷毀。如何證明欺詐，根據和L1交互程度的不同，分為交互式欺詐證明和非交互式欺詐證明，下面會詳細解釋。

第二種是零知識證明，每次存入狀態都需要給出證明，證明會在L1進行驗證，如果驗證根hash值是正確的，代表發布者的發布無誤，這裡的證明用了零知識證明相關研究。

• 欺詐證明

剛剛上面說到欺詐證明本著默認相信的原則。當沒有挑戰的時候，流程較為簡單, 即將狀態樹的根hash 交易信息存入L1中。核心在於有挑戰者發起挑戰時，如何證明交易前狀態樹的根hash經過這一組交易可以變為新的狀態根hash。這裡有2種思路。

1.非交互式欺詐證明，即在L1上將這組交易重新執行一遍，看看執行過後的狀態樹 根hash值和傳入的根是否一致即可。

2.交互式欺詐證明，由挑戰者和發布者在L2上進行多輪挑戰，最終挑戰者鎖定具體哪條指令具有欺詐性，由L1進行裁決。L1只需要執行存在爭議的最小指令即可。

• 非交互式欺詐證明

我們將以Optimism為例說明交互式欺詐。

欺詐證明過程解析：

非交換式欺詐，欺詐證明實現較為簡單，將L2中執行的交易在L1中再完整執行一次，以確定狀態根的hash是否一致來判斷欺詐行為。

如上圖所示，發布者發布信息到L1上，攜帶交易信息和新舊整體根hash, L1中的智能合約收到後會默認變更state為新的根hash，這時挑戰者提出挑戰，挑戰者需要提供符合舊根hash的merkle狀態樹，L1智能合約通過舊的狀態樹執行完整的交易流程得到根hash和發布者提供的新根hash比較，不相等則說明有欺詐行為。

重新執行就會遇到一個問題，區塊相關的屬性會因為執行環境不同而發生變化。

如上圖所示block.timestamp會獲取當前區塊的時間戳，但由於合約執行的環境不同得到的時間戳大概率是不一樣的。我們看看Optimism是如何設計OVM來解決這一問題的。

OVM

為了解決在L2和L1運行智能合約時所處環境不一致的問題，Optimism使用了虛擬化技術（實際上就是使用封裝方法屏蔽）的方式，讓智能合約直接獲取一些狀態變為經過OVM封裝後調用。

上面的那個例子，將不能直接調用block.timestamp，改為調用ovm封裝的1個方法ovm_getTimestamp(非真實隨意命名)。

交互式欺詐證明

我們將以Arbitrum為例說明交互式欺詐。

Arbitrum欺詐證明過程解析：

其實之前智能合約一文開頭講過智能合約執行的過程就是推進狀態變化的過程我們再次回顧狀態機的概念：

如圖所示，無論上L1上的狀態樹還是L2上的狀態樹，都是由一系列的交易(智能合約的執行也是一次交易的調用)，推動狀態轉換的，而由於智能合約，交易又可以拆分為更小的步驟指令。所以就變成了下面的樣子：

我們的問題轉化為證明狀態樹從狀態A 經過N個指令變成了狀態B，那麼這個證明過程是否是可分解的呢？我們用分治的方式不難想到二分法，將1個大問題拆兩個子問題，問題就變為證明狀態A 經過前N/2個指令變成狀態X和狀態X經過後N/2個指令變成狀態B。逐步二分最終定位到存在問題的指令，交由L1執行驗證即可。

讓我們完整描述整個運行過程，假設Ｘ是發布者發布從狀態A經過N條指令轉移到狀態B ，Y是挑戰者。

Y向Ｘ提出挑戰，要求給出經過 N/2條指令處的狀態，Ｘ給出狀態後，Y會自行驗證是否正確。如果驗證正確，則代表前N/2指令執行無問題，問題在後N/2，如果驗證錯誤，則代表前Ｎ/2條指令執行就有問題。Y繼續向Ｘ詢問存在問題的指令區間N/2處狀態，循環往復，直至找到有問題的指令(這裡不是指令有問題，是執行指令前的狀態無法通過執行指令得到執行指令後的狀態)。

在實際應用中Arbitrum不是使用二分的方式，而是使用了K分，即每次將N個指令分為N/K組去尋找欺詐指令，效率更高。

AVM

Arbitrum 設計 AVM和EVM不同的核心點在於：AVM不僅僅要支持EVM完全兼容的執行邏輯，還要支持交互式欺詐證明的證明邏輯。

證明過程中，要保證當前程序計數器中指令的正確性。這時採取了類似區塊鏈的做法，PC(當前的程序計數器位置)不僅存儲操作碼，而且存儲PC+1處的hash值，這樣就可以在指令執行過程中驗證每個指令是否正確。

由上述對比來看交互式欺詐證明除了實現難度較高外，主要特性都優於非交互式欺詐證明。具有代表性非交互式欺詐證明使用者Optimism也準備切換到交互式欺詐證明。可以預見未來交互式欺詐證明將會是欺詐證明的主流。

欺詐證明大都存在1個問題較長的提款周期，這是因為需要足夠多的時間，讓挑戰者提出挑戰。受益於密碼學的較新研究成果，zk-rollup將解決這一問題。

二、ZK-Rollup

• 零知識證明的含義

零知識即在參與者解出問題結果但不告知驗證者結果的情況下，讓驗證者相信參與者解出的问题結果是正確的。我們舉2個比較有名的例子。

• 著名的阿里巴巴

很久很久以前，有一個藏著財寶的山洞，阿里巴巴因為知道開啟山洞石門的咒語，而被強盜抓住。如果說出咒語，失去利用價值也是一死；如果堅持不說，強盜也會殺死他。
兩難的阿里巴巴卻想了1個好辦法，他讓強盜隨機下指令："你們只需離我一箭之遙，用弓箭指著我，你們舉起右手我就念咒語打開石門，舉起左手我就念咒語關上石門，如果我做不到或伺機逃跑，你們就用弓箭射死我。"
重複多次後，強盜始終無法獲知咒語，卻可以相信阿里巴巴擁有咒語的事實，阿里巴巴也保住了性命。

• 數獨問題

有一組9*9的數獨，A已經解出答案，A在不透露答案的前提下想讓B相信A已經成功解出。

解決方法是：讓B隨機挑選1行或1列，A將這一行或一列取出打亂展示給B，包含了1～9，重複多次B就會相信A得出正確答案。

• ZK-SNARK是如何解決問題的

目前ZK機制較為成熟的是zk-SNARK 所以後面指的zk算法都以zk-SNARK為例。

ZK-SNARK工作流程分為2步:

1.通過將問題轉換為電路再轉化為多項式，即從真實的零知識證明問題轉化為數學的零知識證明問題

2.驗證這個多項式零知識證明 隨機給出1些檢查點都可以得出符合條件的解，則驗證成功。

關於zk證明我們後面會單獨再來1篇文章來介紹，因為zk證明不僅僅會運用在以太坊擴容，更多會運用在隱私保護領域，比如較為熱門的DID。

我們以starkware為例介紹zk-rollup的機制，starkware流程圖如下圖所示。

當發布者發布交易到L1上時，需要將交易以及L2上狀態打包交給1個證明生成服務，證明生成服務經過大量運算，生成這次發布的證明。證明服務將證明發送給L1的驗證服務。同時發布者將狀態根hash值提交到L1，L1中接收到根hash值會詢問L1上的驗證服務，驗證服務根據證明驗證根hash值是否正確，如果正確L1會將狀態根切換成新的hash值。

在這個過程中本來驗證狀態樹的根hash是需要前一次完整狀態樹執行這次發布的所有交易得到新的交易樹，從而計算新的根hash值，最終根據發布者提供的根hash值和新的hash值進行比較判斷發布是否合法。由於引入了zk證明，我們不需要知道具體的狀態和交易就可以判斷hash值是否正確。這就是zk證明在以太坊擴容的應用。

• ZK證明的發展

SNARK(零知識簡明非交互式知識證明) 和STARK(零知識可擴展透明證明)對比：

相比SNARK而言，STARK發展還處於早期，但就安全性和抗量子性較好的表現，有望在接下來取得更大的發展。

三、結尾

本文我們介紹主要介紹了rollups這種主流layer2技術，rollups中根據何時去驗證L2提交的狀態是正確的時機分為欺詐證明和zk rollups ，欺詐證明又根據挑戰者是否需要和發布者交互分為非交互式欺詐證明和交互式欺詐證明，經過對比發現無論是運行成本還是EVM兼容性，交互式欺詐證明都處於優勢。而zk這一密碼學較新的研究成果給我們帶來了新的方向zk rollups得以更快地驗證發布者的發布。並且zk還為隱私保護等其他方向帶來了新的可能。