BitVM：图灵完备的 Taproot 智能合约

November 8th, 2023

BitVM [1] 是 Robin Linus 提出的一种用于表达具有图灵完备性的比特币智能合约的建议，并且声称 BitVM 能够在不对网络的共识规则进行任何改变的情况下实现。BitVM 的设计类似于 Optimistic Rollups，那么 Optimistic Rollups 又是如何实现的呢？

那么 Optimistic Rollups 又是如何实现的呢？在了解 BitVM 之前，我们先简单说说欺诈证明。

Optimistic Rollups

Optimistic Rollups [2] 是一种基于乐观性验证的二层扩容方案，它基于欺诈证明来避免无效的状态转移。

何为欺诈证明？

欺诈证明默认发生的状态转移是有效的（EVM 维护了一个庞大的状态机），发布者将交易前状态树的根哈希值以及交易发送到 Layer 1 上，Layer 1 上的智能合约确认交易前状态树根哈希是否和存储的根哈希一致。但是，Layer 1 上的智能合约并不能保证交易过程是正确的。在 Optimistic Rollups 中则默认这些状态的转变是正确的，其核心在于有挑战者发起挑战（说明状态的执行存在错误）时，证明交易前状态树的根哈希在执行这一组交易之后可以变为新的状态根哈希。

在默认交易的执行过程没有错误的情况下，Optimistic Rollups 的方案就较为简单：在 Layer 2 中执行一系列交易后得到的新的状态树哈希和交易存放到 Layer 1 上即可 [3]，而在发生挑战的情况下进入到欺诈证明的流程。而欺诈证明的流程不是本文的重点，不再进行赘述。

BitVM

BitVM 采用了类似 Optimistic Rollups 的方法：证明者和验证者（BitVM 考虑只有两者的简单情况以简化方案，也是后续会频繁提到的两个角色）将程序编译为巨大的二进制电路，证明者将电路提交到一个为电路中的每个逻辑门都有一个叶子脚本的 Taproot 地址中。并且证明者和验证者预签名了一系列交易以启用两者之间的挑战-应答。

在这里，证明者和验证者之间共享了这个二进制电路，并且被证明者提交到 Taproot 地址中，在有效的时间内执行欺诈证明的一系列操作。

从 0 和 1 开始

比特值承诺（Bit Value Commitment, BVC）是 BitVM 的最基本的组成部分，它允许证明者将特定位的值设置为 0 或 1。证明者可以在不同的脚本和 UTxO 中设置变量的值。而这会是实现 BitVM 的关键，它通过将运行时分布在多个交易中来扩展 Bitcoin 虚拟机。

一个 BVC 包含两个哈希值， $hash_0$ 和 $hash_1$ ，在此后的某个时刻，证明者可以实现下面的操作：

揭露 $preimage_0$ 将这个位设置为 0；
揭露 $preimage_1$ 将这个位设置为 1；
同时揭露 $preimage_0$ 和 $preimage_1$ 。此时验证者将它们用作欺诈证明，并收回证明者的存款，该操作被称为 equivocation；

在上面的这些操作中， $preimage$ 是 $hash$ 的原象，假设有一个哈希函数 $H$ ，那么有 $hash = H(preimage)$

结合 BVC 和时间锁能够强制要求验证者在一定时间内决定 bit 的值是 0 还是 1，这样的脚本可以表现为：

<0x47c31e611a3bd2f3a7a42207613046703fa27496>
<1>
OP_IF
  // 如果揭露的是 hash1，则 push 一个 1 到栈中
  OP_HASH160
  <0xf592e757267b7f307324f1e78b34472f8b6f46f3>
  <1>
OP_ELSE
  // 如果揭露的是 hash0，则 push 一个 0 到栈中
  OP_HASH160
  <0xb157bee96d62f6855392b9920385a834c3113d9a>
  <0>
OP_ENDIF

在这个示例中，验证者需要揭露 $hash_0$ 或 $hash_1$ 的原像来设置当前位的值，验证者选择了揭露 $hash_1$ 的原像并且设置值为 1。在后续为了简化流程，假设存在一个 OP_BITCOMMITMENT 的操作码，它接收两个哈希值和其中一个原像，通过判断原像可以将一个 bit 存放到脚本的执行栈中4。而这样的操作是一个最小单元，BitVM 可以将一系列的最小单元组合在一起，最终得到一个可执行的二进制程序。

NAND 逻辑门

任何的可计算函数都能够被表示为布尔电路，NAND 门（与非门）是一个普适的逻辑门，任何的布尔函数都可以通过它来组成。

脚本语言下的 NAND 门通过两个 BVC 来实现，实现一个验证$ A \ NAND \ B = C $的脚本为：

// 揭露哈希 c1 或 c0 的原像
<0xc468a29472cacf3ef179ba2352f88587b91e3e15>
<0x829923b22b9e831822e0a783f92687d27128157b>
OP_BITCOMMITMENT
// 此时将 C 的比特值移动到 ALT 栈中
OP_TOALTSTACK

// 揭露哈希 b1 或 b0 的原像
<0x34f0132278e874836da82f8a6c1e10a21a153d17>
<0xf9fce46cefe9d9392108480ad42b4ce69557d27d>
// 此时将 B 的比特值移动到 ALT 栈中
OP_TOALTSTACK

// 揭露哈希 a1 或 a0 的原像
<0x5acfde72a8e37111cba96d3dd705ba983f47af4d>
<0xa0172816a2d1b20ef0d5a1093958e9564e590baf>
// 此时将 A 的比特值在主运行栈中，此时栈中的情况为 A
// 验证 A NAND B == C

// 从 ALT 栈中取出 B，此时栈中的情况为 B、A
OP_FROMALTSTACK
// 执行 NAND 位运算操作，此时栈中情况为 B NAND A
OP_NAND
// 从 ALT 栈中取出 C，此时栈中的情况为 C、B NAND A
OP_FROMALTSTACK
// 判断是否相等，取出 C 和 B NAND A，并判断它们是否相等
OP_EQUALVERIFY

OP_TOALTSTACK 将主运行栈的值放入到另外一个被称为 ALT 栈的栈顶，并将它从主运行栈中弹出。

而 OP_NAND 是一个假设存在的操作码，它在实际的 Bitcoin 脚本语言中并不存在，它可以容易地使用 OP_BOOLAND 和 OP_NOT 操作码来实现。

二进制电路

通过组合一系列的 NAND 门可以表达任何的电路，每一步都在 Taproot 的叶子节点下进行提交，最后合并到同一个 Taproot 地址中[5]，以便于证明者可以执行电路中的任何门。执行门需要证明者打开相应的 NAND 门并且设置输入和输出位的值。二进制电路在链下的结构可以非常巨大，但是由于 Taproot 的特性，可以使得它在链上的占用空间非常小。

上图是一个具有 8 个不同的 NAND 门的电路，它具有四个输入，而这样的门电路的输入脚本可以表示为

这样的脚本允许证明者在之后的任何时间点设置门电路的输入

挑战-应答

除了允许证明者提交到一个电路之外，还需要验证者能够挑战证明者的声明。这可以在加载时预签名一系列的交易来实现。这些交易通过**”挑战->应答->挑战->...“**的方式连接。如果某一方停止一段时间后，另外一方就会赢得挑战并回收双方的存款。

上图展示了一系列预先签名的交易：

挑战：Vicky （验证者）在脚本路径中释放一个原像（这些原像只有验证者知道），用作对证明的挑战的锁；

应答：Paul （证明者）执行对应的逻辑门，将资金发回初始的脚本中；

在几轮的查询后可以迅速驳斥任何一个不一致的声明。如果证明者停止在链下与验证者合作，验证者就会强制证明者在链上合作：验证者解锁一个哈希锁，使得证明者的 UTxO 中的每个 NAND 门对应的 Taproot 叶子节点只有在证明者知道验证者持有的一个原像时才可以被花费。证明者可以通过揭示其输入和输出来证明给定的 Taproot 叶子节点执行正确。其前提是验证者通过揭露对应 Tapleaf 的哈希的原像来解锁它，通过二分查找的方式，验证者可以在经过有限轮（$O(logn)$）的挑战和应答后锁定证明者的错误。

结语

BitVM 采用了类似 Rollups 的思想，在链下执行复杂程序，再将关键的证据放到链上。它设计了一种最简的”电路单元“，并且利用了 Taproot 的可组合性将这些单元组合起来，以达到在比特币区块链上实现任意的可执行函数的能力。但是它所需要处理的数据量是极其庞大的，所需要的 Taproot 脚本树的叶子节点数量可能达到上亿个，这也使得链下存储的成本非常高，是 BitVM 实现的一个局限。另外就是目前的 BitVM 是作为一个简单的单一证明者和单一验证者之间实现的协议，这使得需要实现 N-N 的交互还需要更为复杂的逻辑设计，而且它本身是一个交互性的欺诈证明，这就使得所有的参与方都需要在线进行操作。

当然，本文并没有完全深入讲解更具体的原理，例如如何构建这样的 Taproot 树？以及执行的具体过程是怎么样的？这些具体的流程也会是 BitVM 在未来实现上所需要考虑的，它目前还处在白皮书的阶段，还需要长期的探索。