深入探讨BitVM - 表达图灵完备比特币合约的计算范式

原文：https://medium.com/crypto-garage/deep-dive-into-bitvm-computing-paradigm-to-express-turing-complete-bitcoin-contracts-1c6cb05edfca

作者：Ichiro Kuwahara https://twitter.com/1_LOW_0219

什么是 BitVM？

BitVM是Robin Linus提出的“表达图灵完备比特币合约的计算范式” ，不需要软分叉。

比特币脚本被设计为图灵不完备，因此不可能实现像基于虚拟机的链上实现的任意合约。之前在比特币上实现图灵完备合约的提议需要软分叉来激活新的操作码。BitVM 与这些提案不同，因为它不需要提案。

请注意，它仍然有重要的限制： ·合约仅限于两方之间的合约 ·需要两方之间进行大量的计算和交互（即数百 MB 到数 GB 的数据交互；本地存储） 尽管有这些限制，该提案引发了激烈的社区辩论。

下面的部分详细介绍了如何在证明者（断言他们知道特定问题的答案）和验证者（评估该断言的真实性）之间建立合同。 只要双方合作，任何合同都可以共同解决。 如果验证者不同意证明者的断言正确，则会启动“挑战与响应”计划（稍后将详细解释），如果发现断言不一致，则验证者有权扣押证明者的资金。

在讨论 BitVM 的工作原理之前，我们将提供一些预备知识。

预赛

⚫️逻辑电路 用编程语言编写的代码被编译器转换为二进制代码（一系列 0 和 1）。处理器读取该二进制代码并使用逻辑电路执行指令。 组成逻辑电路的组件的典型示例包括“与”门、“或”门、“非”门和“与非”门。与非门被称为“通用门”，因为它们可以用来构建所有其他门。

在本文中，与非门仅用于论证，以抽象出制作高效比特币脚本的所有复杂性。我们将该电路称为“二进制电路”。 作者认为， 在实践中，使用所有可用的比特币脚本操作码会使链上 TX 比仅使用 NAND 时小 10 倍至 100 倍。

下图显示了一个以 A、B、C 和 D 作为输入的二进制电路。证明者声称他（她）知道所有输入。

⚫️OP_NAND 比特币现有的操作码 OP_BOOLAND 和 OP_NOT 可以组合起来执行 NAND 操作的功能。

我们将 OP_BOOLAND 和 OP_NOT 的这种组合称为“OP_NAND”。

⚫️位值承诺 以下是证明者提交每个 NAND 门的输入和输出值（0 或 1）的脚本： 如果证明者提供 hash1 的原像，则将“1”压入堆栈。如果证明者提供了 hash0 的原像，则“0”被推入堆栈。

我们将这些操作码集称为“OP_BIT_COMMITMENT”。

OP_IF 
OP_HASH160 
<hash1> 
OP_EQUALVERIFY 
<1> 
OP_ELSE 
OP_HASH160 
<hash0> 
OP_EQUALVERIFY 
<0> 
OP_ENDIF

⚫️二元门承诺

以下是 Prover 通过组合 OP_NAND 和 OP_BITCOMMITMENT 提交到 LogicGate (NAND1) 的脚本。当它们提供以下三个值时，三组值（0或1），即A、B和E被压入堆栈。

・HashA0 或 HashA1 的原像
・HashB0 或 HashB1 的原像
・HashE0 或 HashE1 的原像

如果 A NAND B == E 成立，则该脚本可以解锁。

// 显示 hashE0 或 hashE1 的原像
<hashE0/1> 
OP_BITCOMMITMENT 
OP_TOALTSTACK 
// 现在“E”的位值在堆栈上
// 显示 hashB0 或 hashB1 的原像
<hashB0/1> 
OP_BITCOMMITMENT 
OP_TOALTSTACK 
// 现在位值“B”在堆栈上
// 显示 hashA0 或 hashA1 
<hashA0/1>的原像
OP_BITCOMMITMENT 
OP_TOALTSTACK 
// 现在“A”的位值在堆栈上
// 
// 验证“A NAND B == E” " 
// 
// 从替代堆栈中读取“B” 
OP_FROMALTSTACK 
#compute A NAND B 
OP_NAND 
# 从替代堆栈中读取“E” 
OP_FROMALTSTACK 
#Check A NAND B == E 
OP_EQUALVERIFY

⚫️Challenge and Response 当Verifier不同意Prover的断言正确时，就会发起Challenge and Response。如果发现断言不一致，验证者有权扣押证明者的资金。

验证者从电路中选择一个门，证明者公开输入和输出（我们将其称为打开门）。双方多次重复此过程，直到发现不一致，或者验证者耗尽了可能的挑战空间。 如果证明者声称当一个门打开时 D=1，但随后又声称当另一门打开时 D=0，则证明者模棱两可，验证者能够扣押证明者的资金。

请注意，证明者不需要打开每个门。 在下面的示例中，Verifier 要求 Prover 按顺序打开 NAND7、NAND1、NAND3、NAND6 和 NAND5。

最初，当请求打开 NAND6 时，证明者断言“I=1”。然而，随后当被要求打开 NAND1、NAND3、NAND6、然后 NAND5 时，Prover 被迫给出“I=0”的矛盾响应。当被要求打开 NAND6 时，如果证明者意识到它会给出关于 I 值的矛盾答案并且不打开它，则验证者可以在一段时间后扣押证明者的资金。

⚫️挑战 Taptree 和响应 Taptree Taptree 用于双方承诺挑战和响应方案。Taptree 是由脚本作为叶子和根（Taproot）组成的 Merkle 树，可用于调整密钥，从而可以使用密钥（密钥路径）或 Taptree 中的脚本（脚本）路径）来解锁输出。 在下面的示例中，验证者通过公开挑战抽头树的解锁条件来选择 Gate7，证明者通过公开响应抽头树的解锁条件来打开 Gate7。

如果证明者对同一变量公开不同的值（例如 E=0 && E=1 ），则证明者的声明为假，验证者可以获得所有资金。该模型是通过遵循Equivocals Taptree来实现的。

到目前为止，我们已经了解到证明者和验证者使用比特币脚本的组合致力于逻辑门，并且 Taptree 用于基于挑战和响应协议进行证明验证。 在以下部分中，我们将解释 BitVM 协议的详细信息。

BitVM 协议详细信息

以下是声称知道满足某个任意方程的值的证明者与验证者之间使用 BitVM 签订合约的流程。

1. 电路构建 合约以编程语言实现，并编译成大型二进制电路；证明者声称给予电路的一组特定输入评估为特定输出。

2.交易构建和预签名 Prover和Verifier之间构建并预签名交易，以承诺二进制电路输入值证明​​和验证方案。

3.合约执行 双方签署并广播下图的Tx1以锁定资金。一旦交易确认，合同即被执行。

Tx1已上链，而Tx2~Tx4尚未广播。Tx2 和 Tx4 由验证者持有，Tx3 由证明者持有。

请注意，上图与原始提案有所不同。上图中，第一笔交易的输出分为两部分，并使用ighasg_all进行预签名。如果输出不被分割，则所有可能使用的 Tapleaf 都必须预先签名。详情请参阅此处。

如果验证者接受证明者的声明是正确的，他们会跳过“4”。挑战与响应”步骤并继续到“5. 结算步骤。如果验证者认为证明者的声明不正确，他们将继续进行“4”。挑战与响应步骤。

4.挑战和响应 验证者通过暴露挑战Taptree的解锁条件来选择他选择的门，证明者通过暴露响应Taptree的解锁条件来打开门。 理想情况下，这种交互是在链外执行的。（尽管也可以在链上执行） 双方重复此过程多次，直到发现不一致，或者验证者耗尽了可能的挑战空间。

以下是证明者和验证者在链下重复挑战和响应两次并发现不一致的示例。

在第一个挑战中，验证者选择 NAND1 门，证明者公开其输入和输出（A=1、B=1、E=0）。在第二个挑战中，验证者选择 NAND4 门，证明者公开其输入、输出（E=1，F=1，H=0）。 请注意，Prover 的响应不一致，第一次 E=0，第二次 E=1。由于证明者模棱两可，验证者继续进行“5”。扣押证明者资金的和解步骤。

5. 和解 如果验证者承认证明者在'3.中的主张是正确的。合同执行”步骤，他们跳过“4. 挑战和响应步骤。只要双方合作，任何2-of-2签名的合同都可以共同结算。

如果证明者的响应不一致，则在 '4. 挑战与响应步骤如第一次E=0，第二次E=1，验证者获得原像（E=0）和原像（E=1），这是Equivocas Taproot地址可以解锁的条件。 验证者通过广播 Tx6 来获得证明者的资金，如下所示。

进一步的发展

・更高级的操作码以提高效率 Robin Linus 表示，使用 NAND 只是为了论证，以抽象出制作高效比特币脚本的所有复杂性。 他认为，在实践中，使用所有可用的比特币脚本操作码使得链上 TX 比仅使用 NAND 时小 10 倍至 100 倍。 这就是为什么创建一些更高级的操作码，例如 u32 加法、u32 异或、u32 旋转等。

・更一般的合同 拟议的模型仅限于两方。需要更多的研究来将该模型开发为 N:N。

・无脚本脚本 BitVM ZmnSCPxj通过用点和标量替换散列和原像来表述“无脚本脚本 BitVM”。使用这个技巧，我们可以减少 Tx 大小和链上占用空间。

结论

BitVM 是一个无需软分叉即可实现图灵完备比特币合约的项目。 如果您想贡献，这里是 Repo。您也可以在Telegram 组中讨论这个主题。