欺诈证明与ZK Fraud Proof的实现思路

欺诈证明是区块链领域广泛应用的技术方案,最早起源于以太坊社区,被Arbitrum和Optimism等Layer2项目采用。2023年比特币生态兴起后,Robin Linus提出了BitVM方案,以欺诈证明为核心,在比特币既有技术基础上为二层或桥提供了新的安全模型。

BitVM经历了多个版本演进,从早期的逻辑门电路为基元的BitVM0,到后来以ZK Fraud Proof和Groth16验证电路为核心的BitVM2,相关技术路径不断成熟。多个项目如Bitlayer、Citrea、BOB等均以BitVM为技术基础进行了不同实现。

本文将以Optimism的欺诈证明方案为例,解析其基于MIPS虚拟机和交互式欺诈证明的方案,以及ZK化欺诈证明的主要思路。

OutputRoot和StateRoot

Optimism是知名的Optimistic Rollup项目,其基础架构由定序器和以太坊链上智能合约组成。定序器处理交易后,会将数据发送到以太坊上。运行Optimism节点客户端可以下载这些数据并在本地执行,计算出当前状态集hash。

如果定序器上传错误的状态集hash,本地计算结果会不同,此时可通过欺诈证明系统发起质疑。

EVM系区块链通常用Merkle Tree数据结构记录状态集,称为World State Trie。交易执行后,World State Trie会变化,其最终hash也会更新。以太坊将此hash称为StateRoot,用于表示状态集变化。

Optimism的账户体系与以太坊类似,也采用StateRoot字段。定序器会定期将OutputRoot上传到以太坖,OutputRoot由StateRoot和其他两个字段计算得出。

MIPS虚拟机与内存Merkle Tree

为在链上验证OutputRoot正确性,最简单的方法是在以太坊上实现OP节点客户端,但存在两个问题:

1. 智能合约无法自动获取欺诈证明所需输入参数
2. 以太坊Gas Limit有限,不支持复杂计算任务

第一个问题可通过PreimageOracle合约解决。对于第二个问题,OP团队用Solidity编写了MIPS虚拟机,实现了部分OP节点功能。

OP开发团队用Golang编写了简化程序,功能与OP节点执行交易、生成区块及OutputRoot模块基本一致。但由于计算开销过大,无法在链上完整执行所有交易。

为此,Optimism设计了交互式欺诈证明系统,将交易处理流程细化为MIPS操作码的有序处理。每个操作码执行后,虚拟机状态hash会变化,这些记录汇总为一棵Merkle树。

在交互式欺诈证明中,需确定哪个MIPS操作码导致虚拟机状态hash出错,然后在链上重现当时状态并执行该操作码,观察结果是否一致。这需要将部分MIPS虚拟机状态信息上传到链上。

链上欺诈证明相关合约通过Step函数完成MIPS操作码执行:

solidity function step( bytes memory _stateData, bytes memory _proof ) public returns (bytes32) { // ... }

_stateData和_proof参数包含单条MIPS操作码执行的依赖数据,如寄存器状态、内存状态hash等。

OP采用32位MIPS架构,内存可组织成28层二叉Merkle Tree,底层有2^27个叶子记录各内存地址数据。所有叶子数据汇总后的hash为memRoot。

交互式欺诈证明

为定位有争议的MIPS操作码,OP团队开发了Fault Dispute Game(FDG)协议。FDG中包含挑战者和防御者两个角色,双方需在本地构建GameTree。

GameTree由两层树构成:第一层叶子为不同区块的OutputRoot,第二层叶子为MIPS虚拟机的状态hash。争议双方在链上多次交互,最终定位需要链上执行的单条MIPS操作码。

总结来说,交互式欺诈证明包含两个核心机制:

1. FDG定位需上链执行的MIPS操作码及VM状态信息
2. 在以太坊链上的MIPS虚拟机执行该操作码,获得最终结果

ZK化欺诈证明

传统欺诈证明交互复杂,存在以下问题:

1. 多轮交互产生大量gas成本
2. 交互过程较长,期间Rollup无法正常执行交易
3. 链上实现特定VM开发难度高

为解决这些问题,Optimism提出了ZK Fraud Proof概念。核心是挑战时指定需重放的交易,定序器给出ZK证明,由以太坊合约验证。

相比交互式欺诈证明,ZK Fraud Proof将多轮交互改为一轮ZK证明生成和验证,节省时间和成本。相比ZK Rollup,基于ZK Fraud Proof的OP Rollup只在被挑战时生成证明,降低了计算成本。

ZK化欺诈证明思路也被BitVM2采用。采用BitVM2的项目如Bitlayer、Goat Network等,通过比特币脚本实现ZK Proof验证程序,并极大精简了上链程序尺寸。