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的文章来深入理解其实现路径，敬请期待！