BitVM 背景知识：欺诈证明与 ZK Fraud Proof 的实现思路

Optimism 基于 MIPS 的交互式欺诈证明与 ZK 化欺诈证明是怎么实现的？

撰文：Shew & Noah，仙壤 GodRealmX

众所周知，欺诈证明是一种在区块链领域中被广泛应用的技术方案，其最早发源于以太坊社区，并被 Arbitrum 和 Optimism 等知名以太坊 Layer2 所采用。2023 年比特币生态兴起后，Robin Linus 提出了名为 BitVM 的方案，以欺诈证明为核心思想，在 Taproot 等比特币既有技术的基础上，为比特币二层或桥提供了新的安全模型。

BitVM 曾先后推出过多个理论版本，从最早的以逻辑门电路为基元的 BitVM0，到后来以 ZK Fraud Proof 和 Groth16 验证电路为核心的 BitVM2，与 BitVM 相关的技术实现路径在不断的演化并趋于成熟，吸引了许多从业人员的关注。大家所听闻的 Bitlayer、Citrea、BOB、Fiamma 和 Goat Network 等项目均以 BitVM 为技术根基之一，在此基础上进行了不同版本的实现。

鉴于市面上系统解释 BitVM 的资料比较稀少且晦涩难懂，我们推出了以 BitVM 知识科普为目的的系列文章。考虑到 BitVM 与欺诈证明之间根深蒂固的关系，本篇文章将以欺诈证明和 ZK Fraud Proof 为主要话题，以尽可能易懂的语言为大家展开解读。

我们将以 Optimism 的欺诈证明方案为素材，为大家解析其基于 MIPS 虚拟机和交互式欺诈证明的方案，以及 ZK 化欺诈证明的主要思路。

（Optimism 交互式欺诈证明的机制原理）

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 消耗量太大。

（MIPS 指令集工作原理）

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