BitVM：在比特币中实现高效可验证计算

介绍

比特币是历史上第一个区块链，首次实现了点对点电子现金系统。由 Satoshi Nakamoto 于 2008 年 提出，它提供了一个优雅而简单的构造，使来自世界各地的人们能够在无需许可且抗审查的网络上存储和交换价值。

所有区块链的一个重要缺点是它们都存在可扩展性问题，这源于安全性、去中心化和可扩展性之间的区块链不可能三角。所有节点都必须做相同的工作来保护网络这一事实限制了吞吐量，因为能力较弱的节点会成为瓶颈。零知识证明允许一方（证明者）说服另一方（验证者）某个给定的陈述是真实的，而除了陈述的有效性之外不泄露任何其他信息。这些证明的验证速度比朴素的重新执行快得多。

比特币中的智能合约能力仅限于基本类型，例如签名、时间锁和哈希锁。此外，比特币的区块大小和堆栈（限制为 1000 个元素）在运行程序时是重要的约束。比特币的设计目的不是为了执行有状态计算，即可以通过多次交易和用户交互持续存在的计算。有几种方法可以实现具有不同安全假设的有状态计算：

1. 多重签名：预先确定的一组 nn 方监督计算。它假设对于安全性和活跃性，至少有 tt-of-nn 个诚实方。虽然这是最直接的构造，但它对于抗审查和无需许可的网络具有不良的安全假设。
2. Covenant：它们允许锁定脚本约束支出交易。这允许比特币中的数据和逻辑持久性，而无需额外的假设。但是，covenant 在比特币中不可用，需要升级。
3. ColliderScript：使用大量的计算来模拟 covenant。从好的方面来说，它不需要受信任的各方，并且具有与 covenant 基本相同的安全保证。

BitVM 是一种范例，允许在比特币中执行任意程序，在保持比特币共识安全性的同时实现更大的表达能力。还有其他建议，例如 ColliderVM。在这篇文章中，我们将讨论 BitVM 的一些设计及其权衡。拥有更通用的计算能力将使我们能够在比特币之上构建桥梁、L2 和通用智能合约。

针对这些方法已经有一些进展和批评。例如，请参见

• BitVM 的进展和突破，
• X 上的 BitVM，
• Fairgate Labs 的所有权转移，
• Alpen Labs 关于证明配对，
• 为什么 BitVM 桥是不安全的，
• 如何添加一个简单的 opcode 可以使 zk 在比特币中成为现实，
• 关于电路大小的工程挑战。

挑战

比特币脚本的表达能力有限，使得执行任意程序的成本极高。例如，执行 Groth16 证明的验证，在消费级笔记本电脑上可以在几毫秒内完成，但在比特币上需要高达 3GB 的存储空间——几乎比目前可用的 4MB 区块空间大三个数量级！在链上进行操作在空间和资源浪费方面都很昂贵，因此尽可能多地将计算转移到链下可以提高效率。在以太坊中，使用 ZK 证明更直接，因为验证合约部署一次，我们可以随时调用它们。即使验证非常昂贵，我们也可以始终使用递归证明验证（例如 Aligned 的证明聚合模式）将多个证明合并为一个，并在组成证明之间分摊成本。

在比特币中，我们将不得不利用乐观计算，假设提交证明的一方行为是诚实的，并且不同的各方可以挑战他，迫使他披露中间步骤，并允许他们提供欺诈证明，以表明提交者在哪里作弊。这样，除非受到质疑，否则证明者不必展示大多数步骤。这实际上是 naysayer's proof 的一个例子，它可以帮助显着减少链上负担。

该构造的一个积极之处在于，我们不需要在比特币的共识层面实施更改。

BitVM-1

这是 第一个设计，可以在比特币之上实现可验证的计算。基本点是，证明者可以声明给定函数在某些输入上的计算结果。如果该声明不正确，则验证者可以触发争议，提供简短的欺诈证明并惩罚证明者。

在这种情况下，该设计只涉及两方：证明者和验证者。该协议所需的链下计算负担和通信量很大，限制了可以执行的程序类型。未来的设计改进了这些方面，允许多方互动，并进一步减少了争议的大小以及链下通信和计算负担。

证明者和验证者将程序编译成二进制电路。任何任意计算机程序都可以表示为 1 和 0 的电路，这些 1 和 0 通过诸如 AND、OR 和 NAND 之类的逻辑门流动。BitVM 选择 NAND（NOT-AND）门，因为它们是通用的——任何计算都可以使用足够的 NAND 门来构建。然后，证明者将二进制电路提交到 Taproot 地址，该地址为电路中的每个二进制门都有一个叶子脚本。 Taproot 树或 taptree 通过满足某些条件使 UTXO 可花费；花费条件是 Merkle 树的 tap-leaves。然后，他们预先签署一系列交易，以实现挑战-响应动态。之后，他们可以在链上存款到该地址，这会激活合约，并且他们可以开始交换链下数据以产生电路中的变化。如果证明者提出虚假主张，验证者可以拿走他的存款。

证明者如何提交电路？基本上，对于他想要提交的每个 bit，他都有两个哈希值 hash0 和 hash1。如果他想将 bit 设置为 0，他会显示 hash0 的原像；如果他想将 bit 设置为 1，他会显示 hash1 的原像。如果证明者在某个时候最终显示了两个原像，那么验证者可以使用它们来惩罚证明者。通过散列原像并检查其是否与其中一个哈希值匹配，可以在堆栈中设置位的值。可以通过提供对输入的两个承诺和对输出的一个承诺来提交任何门。毋庸置疑，这会导致内存占用量的大幅增加，因为每个位将需要两个哈希值，并且程序必须由布尔电路表示，这可能不是表示它的最有效形式。使用其他操作，例如涉及 u32 的操作，可以产生更紧凑的表示。

一切设置好后，证明者和验证者可以进行挑战和响应游戏。如果在某个时候他们中的任何一个停止合作（有时间限制)，则另一方可以索取存款。只有当知道验证者持有的原像时，才能花费证明者树中的叶子（代表门）。如果证明者试图更改门中使用的至少一个值，他将显示未公开的哈希值(hash0 或 hash1)的原像，并且验证者将拥有两个原像，并且可以因不当行为而惩罚证明者。使用二进制搜索，验证者可以在几轮交互中有效地找到错误。为了减少链上占用空间，证明者和验证者可以离线交换原像。如果证明者不想合作，验证者可以强迫他在链上披露。一个巨大的缺点是反驳计算需要近 70 笔交易。

BitVM-2

BitVM-2 在安全性和效率方面实现了多个优势。例如，我们可以解决在设置期间从 t-of-n 诚实多数到存在诚实（1-of-n）的桥接问题。新的设计启用了多个验证者（允许无需许可的挑战）以及在其之上开发的桥梁，这是 L2 层的核心组件。

为了能够执行任意程序，我们将利用 SNARK 来生成程序正确执行的证明，并在比特币上验证该证明。由于验证证明仍然很昂贵，我们可以让证明者承诺结果，如果观察者认为他正在作弊，则可以挑战他。争议只需 3 笔链上交易即可解决，这比 BitVM-1 少得多。为了能够运行验证，我们按如下方式进行：

1. 验证程序（对于 Groth16，优化后至少 1.2 GB）被分解为子程序，每个子程序最多 4 MB。每个块都可以在单个比特币区块中运行。这些程序按顺序运行，并且每个程序都依赖于前一个程序的输出。
2. 证明者/运营商承诺执行该程序，预先签署经过特殊设计的消息和 Taproot 树，以确保他可以提取资金并且仍然可以因不当行为而受到质疑。
3. 当他想要提取资金时，他必须在链上提供 SNARK 验证器的输出并质押资本。
4. 任何人都可以通过他们（本地）执行的 SNARK 验证器和公共输入（应该是可用的）来检查结果。换句话说，其他方可以在链上运行完整的验证，并将他们的结果与证明者发布的结果进行比较。
5. 如果存在差异，任何人都可以挑战证明者，证明者将被迫在链上显示整个计算过程。
6. 然后，任何人都可以找到错误的块，在链上执行它们，证明子程序的结果不匹配，并削减证明者的资金。

为了避免恶意验证者挑战正确的执行只是为了增加证明者的成本，验证者必须支付费用，该费用应至少等于发布中间步骤的成本。

如果比特币中提供 Covenant，则可以以更简单的方式实现 BitVM-2。这是一类拟议的支出约束，允许锁定脚本限制 UTXO 中的币将来如何花费。为了避免这种情况，在 BitVM 的每个实例的设置阶段，一个由 nn 个签名者组成的委员会创建一个新的密钥对，预先签署消息和 UTXO 花费的密钥，确定必须达到一个 nn-of-nn 的法定人数。然后，成员删除他们的密钥，确保事情只能以预定的方式花费。只要其中一个符合此要求，我们就可以确保强制执行约束。

对此设计有一些反对意见，特别是桥梁。例如，这里 显示，只要运营商的抵押品至少为 1:1，桥梁就是安全的。以下讨论 中考虑了不同的选项。安全需要非常大的流动性这一事实构成了巨大的威胁，并且具有实际意义。该设计的另一个缺点是声明和反驳交易的成本仍然很高，链上占用空间很大。

BitVM-3

BitVM-3 使用乱码电路来减少其前身的链上占用空间。该电路的设计目的是仅当乱码者提供无效的 SNARK 证明时才有条件地揭示一个秘密，充当欺诈证明。 乱码电路是来自安全两方计算（Yao 协议）的技术，其中一方（乱码者）创建布尔电路的加密版本，并为输入值提供“密钥”，以便另一方（评估者）可以评估电路而无需了解中间值——除了最终输出，在某些情况下可以是秘密揭示。在 BitVM3 的上下文中，这个想法是证明者以这样一种方式对 SNARK 验证器电路进行乱码，即如果提供的 SNARK 证明无效，则乱码电路的输出会泄露一个秘密（用作欺诈证明）。

最大的成本涉及共享电路，这需要 5 TB 的内存。虽然这可能需要几天时间，但这是一次性设置成本。声明交易大约需要 56 kB，而反驳交易大约需要 200 字节（而 BitVM-2 中则为 2 到 4 MB）。这种成本降低使比特币中的证明验证成为可行，尽管我们仍然需要克服电路的大量通信成本，幸运的是，通过进一步的优化，这将降低。

电路的乱码依赖于 RSA。电路中的每条线都有两个可能的密钥，分别对应于 0 或 1。乱码者（证明者）生成这些密钥，以便只有正确的组合才能产生有意义的输出密钥。根据 BitVM3 文本，乱码者选择一个 RSA 模数 N=(2p+1)(2q+1)N=(2p+1)(2q+1)（两个安全素数的乘积）和一些公共指数 e,e1,e2,e3,e4e,e1,e2,e3,e4。还有秘密指数 d,d1,d2,d3,d4d,d1,d2,d3,d4 和 h=e1e4d2−e3h=e1e4d2−e3。 eiei 和 didi 是模 ϕ(N)/4=pqϕ(N)/4=pq 的逆，即 eidi≡1(modpq)eidi≡1(modpq)。使用 NN 的秘密因子（陷阱），乱码者计算线路标签值，以便它们之间的关系仅当满足门的逻辑真值表时才成立。对于电路的输出标签 c0,c1c0,c1，他从以下等式计算秘密输入线 a0,a1,b0,b1a0,a1,b0,b1：

b0=(c1c−10)h−1(modN)b1=be1d20(modN)a0=cd0b−e1d0(modN)a1=cd0b−e3d0(modN)b0=(c1c0−1)h−1(modN)b1=b0e1d2(modN)a0=c0db0−e1d(modN)a1=c0db0−e3d(modN)

可以有效地计算这些幂运算，因为指数 eiei 被选择为小数字。此外，bd0b0d 和 cd0c0d 只能计算一次，并在计算中重复使用。

乱码者从电路的输出开始并向后工作，为每个门生成标签 a0,a1,b0,b1a0,a1,b0,b1。对于具有输出馈入下一个门的第一输入的先前门，使用 c0=a0c0=a0 和 c1=a1c1=a1，如果是对于另一个输入，则使用 b0b0 和 b1b1。

为了能够处理更一般的门（扇出 > 1，即多个输出），乱码者预先计算并发布静态因子 TikTik。对于使用标签 ly0,ly1ly0,ly1 的输出线 WyWy，馈送输入线 WxWx，静态因子由下式给出

lxi,k=lyi,kTiklxi,k=lyi,kTik

因此 Tik=lxi,kl−1yi,kTik=lxi,klyi,k−1。适配器成为电路公共参数的一部分。

我们还可以多次重新盲化标签（这相当于多次重复使用电路）。这对于定义多次使用但较小的子电路（例如，字段算术或椭圆曲线运算）很有用。对于每一轮重新盲化，乱码者需要发布一个新的 ukuk，该 ukuk 与前几轮的指数成对互质（ukuk 和 uiui 的唯一公约数必须为 1）。

如果对于字段操作我们使用不同的子电路，我们需要添加连接器，将一个子电路的输出链接到另一个子电路的输入。为了避免伸缩攻击，存在每个子电路的两个副本（例如，MulA 和 MulB），并禁止连续两次使用相同的类型。

验证者可以通过以明文形式检查每个门来检查乱码电路结构的正确性。因此，乱码者只需要以零知识的方式证明电路的输入已被正确地重新盲化，这只涉及少数几个指数运算。如果证明者通过提供错误的计算来不当行为，则电路将显示输出标签 0（短字符串）的哈希值，该哈希值用作欺诈证明。

总结

BitVM 及其变体是比特币发展中的一个重要里程碑，它表明可以在比特币之上（如以太坊）进行通用计算，而无需更改比特币的共识工作方式。核心思想基于 naysayer's proof，这减少了链上占用空间，代表了协议中最高的成本。由于在链上验证证明的成本很高，我们可以让证明者在链上发布声明，并且观察者/验证者可以离线进行检查，并使用链上的简短证明来质疑证明者的声明。BitVM 有一个大的挑战和响应游戏，涉及多个事务，并且最终确定性很大。BitVM-2 将响应和挑战游戏减少到仅 3 个事务，但成本仍然很高。BitVM-3 使用乱码电路来进一步减少证明和挑战的成本，分别降至 56 kB 和 200 字节，但代价是非常大的设置。 显然，研究和工程在过去一年中一直在改进，并且不久之后我们就会在比特币上拥有信任最小化的桥梁、L2 和通用智能合约。 在即将发布的文章中，我们将更深入地介绍比特币的不同方面、其 L2 解决方案和其他虚拟机。

• 原文链接： blog.lambdaclass.com/bit...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～