作者：Robin Linux 译者：登链社区翻译小组
摘要
BitVM 是一种计算范式，用于表达图灵完备的比特币合约。这不需要对比特币网络的共识规则进行任何更改。与在比特币上执行计算不同，它们仅仅是被验证，类似于乐观 Rollups。证明者声明某个给定的函数对某些特定的输入求值得到了特定的输出。如果该声明是错误的，那么验证者可以进行简明的欺诈证明并惩罚证明者。使用这种机制，任何可计算的函数都可以在比特币上进行验证。
在 Taproot 地址上承诺一个大型程序需要大量的链外计算和通信，然而其在链上的占用空间很小。只要双方合作，他们可以进行任意复杂的、有状态的链外计算，而不在链上留下任何痕迹。只有在争议的情况下才需要在链上执行。
1 简介
按设计，比特币的智能合约功能被限制为基本操作，如签名、时间锁和哈希锁。BitVM 为更具表达力的比特币合约和链外计算创造了一个新的设计空间。潜在的应用包括象棋、围棋或扑克等游戏，以及比特币合约中有效性证明的验证。此外，可能还可以将比特币桥接到外部链、构建预测市场或模拟新的操作码。
这里提出的模型的主要缺点是它仅适用于有两方的设定，即证明者和验证者。另一个限制是，对于证明者和验证者，需要大量的链外计算和通信来执行程序。然而，这些问题似乎有望通过进一步的研究得到解决。在这项工作中，我们仅关注两方 BitVM 的关键组成部分。
2 架构
与乐观 Rollups 1[2]和 MATT 提案（Merkelize All The Things）2[3]类似，我们的系统基于欺诈证明和挑战-响应协议。然而，BitVM 不需要对比特币的共识规则进行任何更改。底层的原语相对简单。它主要基于哈希锁、时间锁和大 Taproot 树。
证明者逐位地将程序提交到链上，但是在链上验证所有内容将会消耗过多的计算资源，因此验证者会执行一系列精心设计的挑战来简洁地证伪证明者的错误主张。证明者和验证者共同预签名一系列挑战-响应交易，以便日后解决任何争议。
该模型旨在简单地说明这种方法允许在比特币上进行通用计算。对于实际应用，我们应考虑更高效的模型。
协议很简单：首先，证明者和验证者将程序编译成一个巨大的二进制电路。证明者将该电路提交到一个 Taproot 地址中，该地址的每个逻辑门都有一个叶子脚本。此外，他们预签名一系列交易，为证明者和验证者之间的挑战-响应游戏提供支持。现在，他们已经交换了所有所需的数据，因此可以将他们的链上存款转入生成的 Taproot 地址。
这将激活合约，他们可以开始交换链下数据，以触发电路中的状态变化。如果证明者提出了任何错误的声明，验证者可以拿走他们的存款。这确保了攻击者总是会损失他们的存款。
3 位值承诺（Bit Value Commitment）
位值承诺是该系统中最基本的组件。它允许证明者将特定位的值设置为“0”或“1”。特别地，它允许证明者在不同的脚本和 UTXO 之间设置变量的值。这是关键的，因为它通过将比特币的虚拟机执行时间分割成多个交易来扩展执行运行时。
承诺包含两个哈希值，hash0 和 hash1。在稍后的某个时刻，证明者通过揭示 preimage0（hash0 的原像）将位的值设置为“0”，或者通过揭示 preimage1（hash1 的原像）将位的值设置为“1”。如果在某个时刻，他们同时揭示了 preimage0 和 preimage1，那么验证者可以将它们用作欺诈证明，并拿走证明者的存款。这被称为矛盾陈述。能够惩罚矛盾陈述是使承诺具有约束力的原因-它是一种“基于激励的承诺”。
将位值承诺与时间锁结合，使验证者能够强制证明者在给定的时间范围内决定特定位的值。
图 1：位值承诺的具体实现
图 1：1 位承诺的具体实现。为了解锁此脚本，证明者必须揭示 hash0 或 hash1 的原像之一。在此示例执行中，证明者揭示了 hash1，并将位的值设置为“1”。我们可以复制此承诺以在不同的脚本中强制执行特定的值。
为了简化起见，从这里开始，我们假设有一个名为 OP BITCOMMITMENT 的操作码，它是上述脚本的简写。该操作码消耗两个哈希和一个哈希的原像。根据与原像匹配的哈希，它将一个位值放在堆栈上。
4 逻辑门承诺
任何可计算的函数都可以表示为布尔电路。NAND 门是一种通用逻辑门，因此任何布尔函数都可以由它们组成。为了保持我们的模型简单，我们展示了我们的方法如何适用于简单的 NAND 门。此外，我们还展示了如何任意组合门。这一切都证明了 BitVM 可以表示任何电路。
NAND 门承诺的实现很简单。它包含两个表示两个输入的位承诺和一个表示输出的位承诺。脚本计算两个输入的 NAND 值，以确保它与承诺的输出位匹配。
图 2：NAND 操作的逻辑门承诺
图 2：NAND 操作的逻辑门承诺。执行此脚本需要揭示位承诺 A、B 和 C 的值，使得 A NAND B = C 成立。
（在这里，为了简化起见，我们假设存在一个名为 OP NAND 的操作码。实际上，它并不存在，但可以使用 OP BOOLAND 和 OP NOT 轻松实现。）
5 二进制电路承诺
在前一节中，我们定义了 NAND 门承诺。我们可以通过组合门承诺来表示任何电路。执行的每一步都在 Tapleaf 中进行承诺。它们都被合并到同一个 Taproot 地址中，以便证明者可以执行电路中的任何门。执行门需要证明者打开相应的门承诺，并为其输入和输出位设置值。
Taptree 可能会变得庞大，并且拥有十亿个 Tapleaf 脚本，但其链上占用空间很小。
图 3：一个随机示例电路
图 3：一个随机示例电路，其中包含 8 个不同的 NAND 门和 4 个输入 A、B、C 和 D。使用数十亿个门可以定义基本上任何函数。
图 4
图 4：对于每个门，证明者的 Taproot 地址包含一个具有相应门承诺的叶脚本。这使得证明者可以在任何时间点上设置电路的输入值（这里是 A、B、C 和 D）。
6 挑战与响应
仅仅承诺一个电路是不够的。为了反驳错误的声明，验证者必须能够挑战证明者的陈述。这可以通过在设置过程中预签名一系列交易来实现。这些交易按照挑战→响应→挑战→响应→...的方式链接。如果其中一方停止参与，那么在一段超时时间后，另一方将赢得挑战并可以拿走双方的存款。只要双方合作，他们可以通过 2-of-2 签名共同解决任何合约。以下机制仅在存在欺诈行为时才需要。
图 5：预签名的一系列交易
图 5：预签名的一系列交易，用于执行多轮挑战和回应。此序列在设置过程中生成。
Vicky 通过打开她的 Tapscript 叶子中的一个哈希锁来选择一个挑战。这将为 Paul 解锁一个特定的 Tapscript，并迫使他执行它。该脚本强制 Paul 揭示 Vicky 挑战的门承诺。通过对几轮查询重复此过程，可以快速反驳任何不一致的声明。
如果证明者停止与验证者进行链下合作，验证者需要一种方法来迫使证明者在链上采取行动。验证者通过解锁哈希锁来实现这一点：证明者的 UTXO 中的每个 NAND Tapleaf 只能在证明者知道验证者持有的原像的情况下花费。因此，证明者可以通过揭示其输入和输出来证明给定的 Tapleaf 正确执行，但前提是验证者通过揭示保护该 Tapleaf 的哈希的原像来为其“解锁”。通过应用二分搜索，验证者可以在仅经过几轮挑战和回应后快速确定证明者的错误。
图 6：在每次响应后，Vicky 可以惩罚模棱两可的行为。如果 Paul 对一个变量公开了两个冲突的值，那么 Vicky 立即赢得挑战，并被允许拿走他的押金。Vicky 通过揭示任何他的位承诺的两个原像来证明 Paul 的模棱两可。
7 输入和输出
证明者可以通过揭示相应的位承诺来设置输入。理想情况下，他们在链下揭示承诺以最小化链上的占用。在非合作情况下，验证者可以强制证明者在链上揭示他们的输入。
可以通过提前交换加密的方式来处理大量数据。这样，证明者可以在以后的某个时间点上揭示解密密钥。
多方输入也是可能的。门可以有来自双方的位承诺。
8 限制和展望
用简单的 NAND 电路来表示函数是低效的。通过使用更高级的操作码，可以更有效地表示程序。例如，比特币脚本支持添加 32 位数字，因此我们不需要二进制电路。我们还可以有更大的位承诺，例如，可以在单个哈希中承诺 32 位。此外，脚本的大小可以达到约 4 MB。因此，我们可以在每个叶子脚本中实现远远超过一个 NAND 指令。
这里提出的模型仅限于两方。然而，可能可以有双向通道，并将它们链接起来形成类似闪电网络的网络。探索两方设置可能会产生有趣的泛化可能性。例如，我们可以为网络探索 1 对 n 的星形拓扑结构。另一个研究问题是，我们是否可以将我们的模型应用于 n 对 n 的设置，并创建更复杂的通道工厂。此外，我们可以将我们的系统与不同的链下协议（例如闪电网络或 rollups）结合起来。
其他研究方向包括跨应用内存，如何对刻在链上的任意数据进行陈述，或者链下可编程电路，即链下虚拟机。还可能应用更复杂的采样技术，类似于 STARKs，在单回合中检查电路。
下一个重要的里程碑是完成一个具体的 BitVM 设计和实现，以及 Tree++，一种用于编写和调试比特币合约的高级语言。
9 结论
比特币在某种意义上是图灵完备的，因为在大型 Taptrees 中编码欺诈证明可以验证任何程序的执行。这个模型的一个主要限制是它仅适用于两方的情况。希望在进一步的工作中可以进行泛化。
致谢
特别感谢 Super Testnet 和 Sam Parker，他们始终坚信比特币不会是图灵完备的。
参考资料
[1] Ethereum Research. 乐观 Rollups. https://ethereum.org/en/developers/docs/scaling/optimistic-rollups/ 2022.
[2] Salvatore Ingala. Merkleize all the things. https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html , 2022.
参考资料
[1]翻译小组: https://learnblockchain.cn/people/412
[2]乐观 Rollups 1: https://ethereum.org/en/developers/docs/scaling/optimistic-rollups/
[3]MATT 提案（Merkelize All The Things）2: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021182.html
