Collider_: 一个价值5000万美元的比特币契约，没有新的操作码

在过去一两年中，已经出现了一些关于提议要对比特币进行契约提议扩展的提案，但专家们一直怀疑，可能不需要进行任何扩展就可以实现契约。支持这一观点的证据有两种形式：一种是此前认为不可能的计算方法不断扩展（最终在BitVM项目中实现了每个RISC-V操作码），另一种是一系列“险些成功”的情况，即比特币开发人员已经找到了契约本来是可能的的方法，只是因为某些晦涩的历史怪事而未能实现。

Ethan Heilman、Avihu Levy、Victor Kobolov和我开发了一种方案，证明了这种怀疑是有根据的。我们的方案 Collider*，可以在今天的比特币上进行契约，基于相当合理的密码学假设，并且每笔交易的成本可能约为5000万美元（加上一些硬件研发）。

尽管使用Collider的费用高昂，但设置它非常便宜，并且（与普通的花费机制一起，使用Taproot将两者分离）可能会保护您的硬币，以防量子计算机突然出现并炸毁它。

毫无疑问，许多读者在阅读这些说法后，会抬起一只眉毛看天空。当你读完本文时，另一只眉毛也会一样高。

01928374656574839201

对于那些不熟悉的人来说，这次讨论的背景是，比特币内置了一种名为比特币的编程语言，用于授权支出。在早期，比特币包含了丰富的算术操作码集，可以用来实现任意计算。但在2010年夏天，聪禁用了其中许多操作码，以消除一系列严重的错误。（恢复到2010年之前的比特币版本是“大恢复项目”的目标；OP_CAT是一个在同一方向上不太雄心勃勃的提议。）几年后才出现了契约的概念——使用比特币来控制其货币的数量和目的地——意识到这些操作码足以实现契约的想法甚至更晚才出现。到了那个时候，社区已经变得太庞大和谨慎，不可能简单地“重新启用”旧的操作码，就像它们被禁用的方式一样。

契约是假设性的构造，可以使用户不仅控制花费比特币的条件，还可以控制比特币的去向。这是许多关于比特币的构造的基础，从保险库和限制转账钱包，到新的费用市场机制如支付池，再到一些不太可取的构造如分布式金融和最大可提取价值(MEV)。已经花费了数百万字来讨论契约的可取性以及它们对比特币性质的影响。

在本文中，我将回避这场辩论，并简单地认为，在比特币上已经可能存在契约；我们最终会发现它们如何可能存在（不需要巨大的计算成本或有问题的密码假设）；我们关于对比特币的新扩展的辩论不应该被框定为个别变化将成为比特币未来有无契约的分水岭。

历史

多年来，发展了一种传统，即即使受到有限的限制，也要找到做非平凡事情的创造性方法。闪电网络就是其中之一，还有一些不太为人知的想法，比如概率付款或者用于哈希函数的碰撞赏金。像SIGHASH_SINGLE bug或使用公钥恢复在解释器内获取“交易哈希”这样的边缘案例被注意到并探讨过，但从未有人找到一种方法使它们变得有用。与此同时，比特币本身也在不断演进，变得更加严格定义，关闭了许多这样的可能性。例如，隔离见证消除了SIGHASH_SINGLE bug，并明确分离了程序数据和见证数据；Taproot摆脱了公钥恢复，这种灵活性曾以可能损害适配器签名或多重签名的安全为代价。

尽管发生了这些变化，黑客攻击仍在继续，死忠者仍然相信，以某种方式可以找到一些边缘案例，从而使契约在比特币中得到支撑。 在2020年初，特别是有两个发展引起轰动。 其中之一是我自己发现，基于签名的契约并没有随着公钥恢复而消失，特别是，如果我们甚至有一个禁用的操作码 -- OP_CAT -- 这就足以构建一个相当高效的契约。 另一个是BitVM，这是一种在跨多个交易中进行大量计算的新颖方法，它激发了对单个交易中基本计算的大量研究。

这两个发展激发了许多关于契约的活动和兴奋，但它们也使我们对的基本限制有了更清晰的思考。特别是，似乎没有新的操作码，契约可能是不可能的，因为交易数据只能通过64字节的签名和32字节的公钥输入，而支持BitVM的操作码只能处理4字节的对象。这种分歧被称为“Small”和“Big”，在我看来，找到两者之间的桥接成为了找到契约构造的同义词。

函数加密和PIPEs

有人还观察到，通过一点点的月球数学，可能可以在签名本身内完全执行契约，而无需离开Big，这个想法是Jeremy Rubin在他的论文FE'd Up Covenants中阐述的，该论文描述了如何使用一个名为functional 加密的假想加密原语来实现契约。几个月后，Misha Komorov提出了一个名为PIPEs的具体方案，似乎使这个假想的想法变为现实。

这是一个令人兴奋的发展，尽管它存在两个主要限制：一个是它涉及到一个值得信赖的设置，这意味着创建契约的人可以绕过它的规则。（这对于像金库这样的东西来说是可以接受的，因为拥有硬币的人可以相信他不会破坏自己的安全性；但对于像支付池这样的东西来说是不可以接受的，因为契约中的硬币不是契约的创建者所拥有的。）另一个限制是它涉及到具有不明确安全特性的尖端加密技术。这后一个限制将随着更多的研究而消失，但值得信赖的设置对功能-01928374656574839201的方法是固有的。

碰撞器

这一概述将我们带到了当前的情况:我们希望找到一种方法来使用现有形式的比特币来实施契约,我们相信这样做的方法是找到某种方式在交易签名的“大”和任意计算的“小”之间进行桥接。看起来没有操作码可以直接形成这个桥接(请参阅我们论文附录A，了解所有操作码的输入和输出大小的分类)。如果存在某种桥接，那么它将是一种构造，接受一个大对象并证明它恰好等于几个小对象的串联。根据我们对操作码的分类，这似乎是不可能的。

然而，在密码学中，我们经常削弱“完全相等”这样的概念，而是使用“计算上无法区分”或“统计上无法区分”这样的概念，从而规避了不可能的结果。也许，通过使用大型的内置加密构造 - 哈希和椭圆曲线签名 - 并通过在Small中使用BitVM构造进行镜像，我们可以找到一种方法来证明一个大对象与一系列小对象“在计算上无法区分”？这正是我们在Collider中所做的。

这是什么意思呢？嗯，回想一下我们之前提到的哈希函数碰撞赏金。这个赏金的前提是，任何能够通过提供两个具有相同哈希输出的输入来“碰撞”哈希函数的人，在Big中可以证明他们这样做了，并因此获得赏金。由于哈希函数的输入空间要比输出空间大得多（所有大小最多为520字节的字节串），数学上必须存在许多这样的碰撞。然而，除了SHA1之外，没有人发现比一遍又一遍地调用哈希函数并查看结果是否与之前尝试的结果相匹配更快地找到这些碰撞的方法。

这意味着，对于一个像SHA1或RIPEMD160这样的160位哈希函数，平均而言，用户需要至少进行2^80次工作，或者一百万亿亿次迭代，才能找到碰撞。（在SHA1的情况下，如果用户能够使用特定形式的输入，可以有一种快捷方式；但是我们的构造禁止了这些攻击，因此在我们的目的下，我们可以忽略这种攻击。）这假设用户拥有有效的无限内存来处理；基于更现实的假设，我们需要增加大约一百的因素。

如果我们假设SHA1和RIPEMD160可以像比特币ASIC一样高效地计算SHA256，那么这样的计算成本将与200个区块的成本相当，约为625比特币（4600万美元）。这是一大笔钱，但很多人都有这样的资金，所以这是可能的。

要找到一个三重碰撞，或三个输入等于同一结果，即使对内存访问有非常慷慨的假设，也需要大约2^110的工作。要得到这个数字，我们需要为我们的成本再增加1600万倍，从而使我们的总成本超过700万亿美元。这也是一大笔钱，而且今天没有人能够接触到。

我们构造的关键点如下：为了证明一系列小对象等效于一个大对象，我们首先找到了我们的目标对象（我们假设它可以以某种方式重新随机化，否则我们将执行"二次预像搜索"而不是碰撞搜索，这将更加困难）和"等效测试对象"之间的哈希碰撞。这些等效测试对象以一种可以在大型和小型环境中轻松操作的方式构建。

然后，我们的构造在比特币中检查，我们的大对象与我们的等价测试器碰撞（使用与哈希碰撞赏金完全相同的方法），并且我们的一系列小对象与等价测试器碰撞（使用部分借鉴自BitVM项目的复杂构造，并在论文中详细描述）。如果这些检查通过，那么要么我们的小对象和大对象是相同的，要么用户发现了三重碰撞：两个不同的对象都与测试器碰撞。根据我们上面的论述，这是不可能的。

结论

桥接小和大是我们契约建设中最困难的部分。要从这个桥接到实际的契约，还有一些比较容易的步骤。特别是，契约首先要求用户使用特殊的"生成器密钥"签署交易，我们可以使用OP_CHECKSIG操作码进行验证。使用这个桥接，我们将这个签名分割成4字节的块。然后验证它的nonce也等于生成器密钥，一旦签名被分割，这就变得很容易。最后，我们使用Schnorr技巧从签名中提取交易数据，然后可以根据契约的要求对其进行约束。

我们还可以做一些其他事情：附录C描述了一种环签名构造，可以允许硬币由一组公钥中的一个进行签名，而不会透露使用了哪一个。在这种情况下，我们使用桥接来分解公钥，而不是签名。出于与Taproot相关的技术原因，这样做相对于契约构造给我们带来了显著的效率改进，并在论文中进行了详细描述。

我想要引流的最后一个应用是在论文的第7.2节中简要讨论的，即我们可以使用我们的契约构造从Schnorr签名中提取出交易哈希，然后只需使用Lamport签名对哈希进行重新签名。

为什么我们要这样做？正如上面的链接所提到的，用Lamport签名的方式对签名进行签名，使其成为交易数据上的量子安全签名；如果这种构造是签署某些硬币的唯一方式，它们将免受量子计算机的盗窃。

当然，由于我们的建筑需要数千万美元来使用，没有人会将这种建筑作为签署他们硬币的唯一方式。但没有任何阻止某人将这种建筑添加到他们的硬币中，除了他们现有的非量子安全的花费方法之外。

然后，如果明天我们醒来发现存在能够破解比特币签名的廉价量子计算机，我们可能会提出一个紧急软-分叉，禁用所有椭圆曲线签名，包括Taproot关键花费和OP_CHECKSIG操作码。这将有效地冻结每个人的硬币；但如果另一种选择是每个人的硬币都可以自由被盗取，也许这不会有任何区别。如果这个禁用签名的软-分叉允许在使用生成器密钥时调用OP_CHECKSIG操作码（这样的签名不提供任何安全性，只是作为我们这样复杂构造的基础），那么我们的Lamport签名构造的用户可以继续自由花费他们的硬币，而不必担心被查封或被盗窃。

当然，他们需要花费数千万美元来实现这一点，但这比“不可能”要好得多！我们期望并希望看到这个成本大幅降低，因为人们在我们的研究基础上建设。

这是Andrew Poelstra的客座文章。所表达的观点完全属于他们个人，并不一定代表比特币公司或比特币杂志的观点。