将欺诈证明引入比特币，第一部分

现代欺诈证明是通用的

2024年12月12日

在过去几年中，区块链生态系统的一个重要演变是使用 欺诈证明，正如我们在 Arbitrum、Optimism、Base 和 BitVM 中所看到的。它展示了区块链系统中安全性和效率之间的权衡。

现代欺诈证明源于2011年Ran Canetti、Ben Riva 和 Guy N. Rothblum 发布的开创性论文“使用多个服务器的实用委任计算”。在那篇论文中，他们为x86程序（基本上是计算机可以运行的任何程序）构建了一个“乐观 Rollup”，使用了如今在EVM中用于欺诈证明的技术：二分法、Merkle哈希树和虚拟机。

在本文中，我们想提供欺诈证明的背景。在即将到来的第二部分文章中，我们将讨论比特币生态系统中的欺诈证明，特别是BitVM和基于OP_CAT的乐观证明验证。

欺诈证明概述

在欺诈证明中，计算是在链下完成的，结果发布在链上，如果结果不正确，每个人都可以挑战此结果并 使计算失效。否则，在一个被称为提款期的时间段后，计算将在链上完成。

为了使欺诈证明有用，有两个要求：

• （有效的链上挑战）计算可以在链上进行挑战，成本远低于运行整个计算的成本

• （数据可用性）须向公众提供足够的信息，以便重现计算

有效的链上挑战是通过EVM中的智能合约实现的，基本思想是挑战仅需要向智能合约展示计算的一小部分，这样的代价很低。

数据可用性是应用特定的，但例如，在乐观 Rollup中，公众需要知道：

• 执行之前区块链的状态

• 交易

公众希望计算结果包含所有交易的哈希和L2的新状态的哈希。

公众可以在以前的状态上本地执行这些交易，查看新状态是否与链上发布的结果相匹配。如果不匹配，就存在欺诈，公众可以挑战该汇总。

由于区块链的先前状态可以通过出现在链上的以前交易推导出来，因此实际的数据可用性归结为交易本身。有时，数据可用性可能是成本的一个重要部分。有不同的方法来降低这个成本。

无损压缩。 Arbitrum 和 Optimism 都使用 Brotli，这是谷歌的一种通用压缩算法，用于压缩批量交易数据。

压缩是在一批交易上应用，而不是单独对每笔交易进行压缩的原因是它可以提高压缩率。这个观察在一篇名为 MiniCrypt 的论文中得到了研究，该论文在一个实际数据集上显示批量处理将压缩率提高了约3倍。许多区块链交易彼此相似，这使得批量压缩更加有效。

目前尚未就“工程”压缩用于欺诈证明制定最终方案，因为我们仍在使用通用压缩算法，而不是专门用于以太坊交易的一种算法。实际上，即使通用压缩算法也可以采用 自定义字典 进行专门化。但也存在实际问题，因为更为专业的压缩技术会使整体系统的复杂性提高，而其价值取决于数据可用性成本。

替代数据可用性机制。 借助 EIP-4844 中引入的 blobs，rollups提供的以太坊对齐的数据可用性的费用显著降低。以前，rollup要么将数据作为常规 calldata 存储在Ethereum L1上并支付高额交易费用，或者采用第三方非以太坊对齐的方式存储数据。Blobs引入了一种更便宜的存储数据的选项，可以在以太坊上存储18天，这被认为足以让rollups实现去中心化和安全。

然而，blob费用可能会波动。在撰写本文时，发布一个128KB的blob，费用约为10美元，已是使用calldata费用的96％的折扣（参见 [1]， [2]），但仍然可观。在7个月内，我们的投资组合公司Taiko为blob支付了大约350万美元的ETH，我们的LP StarkNet支付了大约70万美元的ETH。相反，如果他们将blobs结算在 Celestia 上，费用将低至20倍。

一个项目还可以发起自己的数据可用性委员会，例如Arbitrum的 AnyTrust，以进一步降低这一成本。

替代数据可用性机制是rollups或应用决定的选项。使用它是可以的。不使用它也是可以的。这是信任假设和成本之间的权衡，而且也可以实现安全性。

对于比特币，L1的存储容量更加有限，因此替代的数据可用性机制可能是唯一可行的选择。例如，由于成本高且导致L1拥堵的不利后果，比特币rollup无法直接在比特币L1上结算数据，这违背了 使用比特币rollup缓解L1压力 的目的。因此，它需要一种替代的数据可用性机制，理想情况下是基于比特币安全性的去中心化机制。

安全性

现在我们对欺诈证明的工作原理有了一个了解，我们可以谈谈欺诈证明的安全性。

当证明者将执行提交到L1区块链时，该执行尚未得到结算。例如，如果账户A想要向L1提取一些代币，则rollup将在L1上发布此提款请求，但代币尚未发放给A。

它需要等待通常为7天的提款期。然而，这个数字是有点任意的，且由于历史原因（闪电网络通常需要等待1000个比特币块，大约7天）。7天的提款期在不久的将来可能会发生变化：

• Arbitrum已在Orbit链上实施 “快速提款”，允许用户在15分钟内收到提款。这一数字是基于以太坊最终性计算的，大约为12.8分钟。

• 我们的投资组合公司RISC Zero发布了 Kailua，使乐观证明能够在1小时内完成最终性。对Kailua能提供1小时最终性的详细研究可见 这里，因为挑战协议可以通过挑战者或证明者显著缩短。

归根结底，欺诈证明的安全性与提款期的长短无关，而是归结为一个简单的问题：当rollup发生故障时，是否有诚实的参与者来运行挑战协议并使不正确的计算无效？如果答案是是，较短的最终性完全可行。如果答案是否定的，即使较长的最终性也不算安全。

这导致了实现欺诈证明安全性的四个因素：

• 降低rollup发生故障的风险： 可以通过复制来完成，只要rollup仍然高效。即使对于中心化的rollup，运行相同rollup功能的不同机器也是有好处的，结算到L1只能在这些机器达成一致的情况下进行。实现rollup功能的不同实现（称为 N版本编程）也有助于减少程序错误造成的影响。我们的LP StarkWare目前正在 开展这项工作。请注意，这与将排序者去中心化为网络参与者是不同的，这是为了活跃性和激励对齐，不过，如果没有更多，外部节点也可能像中心化节点一样故障。

• 促进诚实的一方： 协议需要方便诚实的一方在出现问题时挑战计算。成为一个诚实的一方并不容易。首先，需要有开源软件来发现差异并自动进行挑战协议，而且其用户体验必须足够出色，以免让人们不愿使用。其次，完成挑战协议的成本应该足够低，而不是要求挑战者投入大量资本。最后，确保不过度报复的机制是必要的。例如，如果诚实的一方需要进行KYC或列入白名单，他们可能会不那么愿意进行挑战，因为可能会面临报复。一个解决方案是使用ZK，这个项目 “可信匿名举报人” 在ETH Bogotá上使用RISC Zero是一个良好的示例。

• 允许完成挑战协议的时间充足： 不同的欺诈证明有不同的挑战协议，公开可用的数据量与轮数之间存在权衡。例如，在RISC Zero的 分析中，乐观 Rollup与ZK汇总及混合汇总（即Kailua）的比较中，对于经典的乐观 Rollup协议使用二分法，所需的轮数为D + log(N)，其中D是“计算深度”，N是批次中的区块数量。根据具体参数，总轮数可能轻易达到10轮或更多。提款期需要足够长，以便双方参与这些轮次，并为意外网络延迟留出一些缓冲，但同时也需考虑，一个长的提款期会影响用户体验。

• 进行演练： 通常，如果rollup操作员是诚实的，公众成员仅在执行不正确时挑战，那么挑战协议可能永远不会使用（通常称为“快乐路径”）。但这将导致缺乏实践：我们不知道是否有人在检查计算的正确性。一种解决方案是定期进行演练，由rollup操作员制造一些“虚假”执行实例，以测试仍有足够节点关注系统，并查看他们是否能够完成完整的挑战协议。

需要注意的是，欺诈证明并不等同于 惩罚，后者通常与 EigenLayer 和 Babylon （这两者都是我们的投资组合公司）相关。欺诈证明可以包含惩罚组件，以此作为对恶意行为的证明者和挑战者的经济威慑，但惩罚与欺诈证明不同，因为两者之间存在微妙之处。

欺诈证明不依赖于惩罚。如果计算错误，总有一种方式可以挑战并使计算失效，从而确保不正确的状态永远无法在L1链上实现。惩罚协议则依赖惩罚。如果所有节点都不怕被惩罚（例如，有人收买他们使其不当行为，并会对此进行补偿），即使计算错误，仍然可能被接受，因此在EigenLayer或Babylon中构建合适的经济激励非常重要。

话虽如此，欺诈证明并不取代EigenLayer或Babylon，因为EigenLayer和Babylon解决的问题是我们所称的“跨主观性”问题，例如“数据是否可用？”（这就是为什么有EigenDA）和“1 BTC = 1 USD？”（这需要来自中心化交易所的数据），这些问题的答案是通过广泛的共识和约定形成的，而不是以某种数学定义或“计算”得出的。这也是为什么EigenLayer和RISC Zero这两家我们的投资组合公司能够宣布合作关系（参见 此处），在其中使用ZK使重新质押和惩罚更加高效，因为欺诈证明或ZK无法解决EigenLayer正在解决的这些跨主观性问题。

简而言之，欺诈证明目标在于计算，它的安全性基于计算。如果有计算需要验证，欺诈证明很可能是有效的。

欺诈证明中的权衡

现在，我们将更深入地了解欺诈证明中的权衡。

计算的粒度。 考虑一个提交100,000个交易的乐观 Rollup。在欺诈证明中，计算被切分为小块。每个小块从某个中间状态开始，并在计算结束时达到新的状态，而新状态将作为下一个小块的初始状态。

挑战协议指出含有至少一个错误的小块。如果计算不正确，可以很容易地看出至少必须存在一个这样的块。

有许多方法可以切分计算，但每个块应该多大呢？例如，给定100,000个交易，我们可以将它们分成12块，每块大约有8,000个交易，或者分成更多的块，每个块大约有3,000个交易。在实践中，我们可能会分得更细，以便每个小块只有少量交易，这样链上的挑战成本较低，但这需要平衡。

轮数。 拥有过多的小块是需要成本的。在挑战错误的小块时，公众需要知道每个小块的初始状态的哈希和该小块计算后的新状态的哈希。证明者提供这些哈希的方式有两种，每种方式的费用根据小块数量的增加而增加：

• 按需获取， 在此情况下，证明者在通过二分协议被请求时提供哈希。这需要O(logN)轮，其中N是小块的数量。

• 提前发布， 在此情况下，证明者在数据可用性层中包含哈希，以便公众可以直接使用这些哈希找到不正确的小块，而无需与证明者对峙。这的好处是没有轮数的待完成，但需要发布O(N)个哈希。

这两种方法可以混合使用，每种方法都是可调的。例如，为了减少轮数，最初可以发布K个哈希，从而减少轮数到O(log(N/K))。此外，在每一轮中，证明者可以不严格“二分”计算，而是提供若干哈希。假设在每一轮中，证明者将剩余计算切分成S个部分，则轮数变为log_S(N/K)，而不是log_2(N_K)。这可能是显著的，因为将S设置为32而不是2是合理的，这样已经减少了轮数的80%。

在实践中，这些参数由L1链上数据可用性的成本决定（因为可以看出，非常大的K或S会导致很多数据发布）以及挑战完成所需的期望轮数（如果K=1且S=2，则可能会有很多轮）。需要注意的是，挑战的成本在我们所谓的“快乐路径”和“痛苦路径”中有所不同。

• “快乐路径” 是当计算正确且无人挑战时的情况。在这种情况下，仅产生的唯一数据可用性成本是K，这是一轮挑战之前发布的数据（即，在任何挑战的轮次之前）。没有任何轮数。

• “痛苦路径” 是当公众成员开始挑战协议时的情况。通常，这个挑战者将支付一个押金，这笔费用覆盖了证明者应对挑战的成本。这个成本还包括对于log_S(N/K) * S个状态哈希的数据可用性费用。在每一轮中会有S轮，每轮都有两个交易，一个来自挑战者，一个来自证明者。

为了优化快乐路径，将K设为小数字是可以的，而在痛苦路径中的轮次不必都使用相同的S。例如，在痛苦路径的第一轮中，可以将计算划分为K个部分，其中K > S，以减少轮数。

快速确认。 由于延迟将影响欺诈证明系统中的用户体验，因此有许多临时设计试图缓解此问题，并为用户提供某种快速确认的水平。

第一个想法是在7天之内设定某种“首次挑战窗口”。如果在该“首次挑战窗口”内没有人挑战该计算，则假设该计算是正确的，挑战窗口会提前关闭，计算可以完成。在“首次挑战窗口”之后，即使计算不正确，没人也无法挑战。但是，如果公众成员感到计算不正确，只需在“首次挑战窗口”内提出第一个挑战。此后，这个挑战者有更多时间提交后续的挑战。这也是RISC Zero的Kailua如何减少提款期的核心想法。

这个想法的唯一问题是，那些恶意挑战者总是可以在“首次挑战窗口”中进行挑战，以便延迟提款过程中无法提前完成提现。设定高额押金以防止这类恶意挑战者虽是可行的，但会提高诚实挑战者的门槛。此外，衡量这个押金应是多少也比较困难，因为由于延迟而给用户带来的损失很难计算。

另一个想法是，既然正确的计算，即使被挑战，最终也会得到结算，因此可以为用户“提前垫付”资金。例如，假设一个用户想要从L2提取10美元的USDT，L2汇总操作员可以立刻付钱给用户，在提款期结束后从L1索回用户的10美元。这显著改善了用户体验，而且汇总操作员实际上并没有承担真正的风险。

这也是为什么中心化交易所和桥接（例如 Polyhedra、我们的投资组合公司，以及 Orbiter Finance）允许用户在不等待7天的情况下从乐观 Rollup中存入和提取资金的原因。具体而言，他们不必信任rollup操作员，因为他们可以通过发布的数据自行检查计算。如果计算正确，没有办法让该计算被事后无效化。

BitVM也依赖于操作员能够提前垫付资金并在之后进行证明。当然，这会导致对操作员的流动性需求增加，有时可能会麻烦（见 [1]， [2]）。只要rollup操作员能承担流动资金，这样的做法会非常有效，且操作员甚至可以提取“快速提款”费用来为此提供补偿。然而，如果用户想提取1亿美元，但rollup操作员并没有那么多流动性，那么情况可能就不太好。用户也不会希望在恐慌中发生大规模提现。

关于快速确认的另一个想法是利用ZK证明。

极端的形式是在必要时进行全证明。设想一下，如果rollup操作员想加快提款期，可以通过提交ZK证明来实现，一旦在链上进行验证，将立即结算所有交易，跳过整个提款期。基本上，这是将乐观 Rollup按需转换为ZK汇总的能力。

这对想快速提取1亿美元，并愿意支付汇总操作员高额费用以覆盖成本的用户来说是有用的。操作员不需要手中拥有1亿美元。假设操作员只有1000万美元的流动资金，可以给用户提现1000万美元，并从L1合约声称对应的1000万美元，再提现1000万美元给用户，再从L1合约主张另一1000万美元，如此重复，直至完成100,000,000美元。这完全是因为ZK证明，尤其是为了证明一次提现，可以快速生成和验证。

但实现快速确认不必如此极端。我们投资组合公司RISC Zero的 Kailua 力求通过将挑战协议缩短为单轮进行，只需一轮，在该轮中，挑战者需要指出未进行形态的计算部分，并请求证明者提供有效证明。因为这种证明预计只需一小时即可生成，最终性可以在大约一小时内实现（即证明提交时立即确定）。

话虽如此，我们可以总结现代欺诈证明协议具有很大的灵活性，其效率在很大程度上是可调的。特别是，它不必与ZK分开，但确实在某种程度上是正交的。

欺诈证明与ZK

在过去，我们将欺诈证明与ZK视为两种不同家族的协议，并曾将乐观 Rollup描述为“无辜，直到被证明有罪”，而ZK汇总则描述为“有罪，直到被证明无辜”。这并没有正确地捕捉到欺诈证明也被视为“有罪”，例如，7天过去了，没有人能证明rollup操作员不当行为，因为在此提款期间资金不可用。

将欺诈证明视作灵活的，类似于某人被警察拘留进行调查，而没有被指控，警方必须在7天“提款期”后释放此人。这并不听起来像是“无辜，直到被证明有罪”，因为如果你信任rollup操作员，它根本不需要首先被拘留。

通过这一相似性，可以看出，欺诈证明与ZK并没有那么不同。这引出了一个问题：如果它们相似，欺诈证明和ZK优雅地协作的方式有哪些？

首先，Kailua可以被视为“基于需求的ZK有效性证明的乐观 Rollup”。提交的计算是对L2上交易的执行，并在挑战期间，可以通过现有的挑战协议或无法按要求提供ZK证明来将其“证明为有罪”。我们可以总结Kailua如下：

-------------
Kailua来自RISC Zero
-------------
提交的计算：
- 交易执行
证明其有罪的方法：
- 请求验证ZK证明，但未在规定时间内进行验证
- 被挑战者展示该部分有效的ZK证明以证明执行错误
- 或进行委督计算
证明无罪的方法：
- 在提款期间未被证明有罪
-------------

我们也可以同样总结乐观 Rollup和ZK汇总。

-------------
乐观 Rollup
-------------
提交的计算：
- 交易执行
证明其有罪的方法：
- 委督计算
证明无罪的方法：
- 在提款期间未被证明有罪
-------------

-------------
ZK汇总（例如Taiko和StarkNet）
-------------
提交的计算：
- 交易执行
证明其有罪的方法：不适用
证明无罪的方法：
- 对计算的ZK证明进行验证
-------------

另一个例子是BitVM，我们的投资组合公司Fiamma和Nubit正在为此工作。BitVM与之前的示例不同，提交的计算本身是对交易执行的ZK证明验证。

-------------
BitVM（如BitVM 2桥接）
-------------
提交的计算：
- 验证ZK证明，以证明交易的执行
证明其有罪的方法：
- 委督计算
证明无罪的方法：
- 在提款期间未被证明有罪
-------------

我们的比特币STARK验证器为StarkWare的CairoVM而构建，旨在假设OP_CAT的情况下在比特币L1上验证一个ZK证明，可以在不进行乐观验证的情况下运行，并作为仅有效性系统像ZK汇总一样工作。

-------------
比特币STARK验证器（类型 I，仅有效性）
-------------
提交的计算：
- 执行CairoVM
证明其有罪的方法：不适用
证明无罪的方法：
- 运行ZK证明验证
-------------

但它也可以添加一些乐观验证，这将使其更加高效和轻量，因为在快乐路径中不需要进行ZK证明验证。当然，乐观验证会增加一些延迟。

-------------
比特币STARK验证器（类型 II，对有效性证明的乐观验证）
-------------
提交的计算：
- 验证ZK证明，以证明交易的执行
证明其有罪的方法：
- 委督计算
证明无罪的方法：
- 在提款期间未被证明有罪
-------------

请注意，即使类型II版本仍存在证明生成成本。即使没有人来挑战证明，操作员仍需提交ZK证明的验证，这意味着操作员即使没有人打算挑战他，也需要生成ZK证明。这提醒我们，我们可以在此基础上添加RISC Zero的Kailua思想，从而创造出类型III比特币STARK验证器。

-------------
比特币STARK验证器（类型 III，带Kailua）
-------------
提交的计算：
- 执行交易
证明其有罪的方法：
- 请求对计算部分的ZK证明验证但未及时提供
- 或在提供ZK证明验证后，关于该部分的委督计算
证明无罪的方法：
- 在提款期间未被证明有罪
-------------

该版本的好处是ZK证明仅在被挑战时生成，ZK证明不必是完整证明，而是可以集中于整个计算的一部分。这并非没有权衡。希望监控计算的公众成员必须获取交易，执行它们并检查结果，而如果已有ZK证明，他们只需检查ZK证明，而无需下载交易。此外，记住在挑战协议中，挑战者需要支付押金以支付请求ZK证明的费用，而这个押金并不小，并会随着计算中的交易数量而提升。如果这个押金太大，则会成为挑战者的门槛。

总结来说，我们可以看出，欺诈证明和ZK并不是彼此分开的，从RISC Zero的Kailua的例子可以看出，确实有许多不同的组合使欺诈证明和ZK能够合作。

下一篇文章

在本文中，我们提供了现代欺诈证明的背景，并表明它们是一个十分多功能的协议家族。我们的一些投资组合公司正在相关领域开展工作，包括RISC Zero、Fiamma和Nubit。

在下一篇文章中，我们将重点关注BitVM和启用OP_CAT的比特币STARK验证器中的欺诈证明。请关注第二部分文章的发布。

在 l2iterative.com 找到 L2IV，并在 Twitter 上关注 @ l2iterative

作者：Weikeng Chen，研究合伙人，L2IV

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