作者：Ruben Somsen
来源：https://gist.github.com/RubenSomsen/a61a37d14182ccd78760e477c78133cd
使用关于哪些输出将保持不花费的提示，实现近乎无状态的、完全可并行的比特币区块链验证。所有其它的 输入/输出 都会在一个哈希聚合值中高效划去；如果验证成功且提示都是正确的，这个聚合值最终会是零。
引言
验证是比特币的核心。验证速度上的所有提升都会给这个系统的可扩展性（以及所有建立在它基础上的东西）带来直接的影响。出于这个理由，提升验证性能可能是我们可做的最重要的事情之一。
SwiftSync 的一般观察是，如果我们有两个集合（在这里，是输入和输出），而我们想知道这两个集合的差别（也即 UTXO 集），验证这个问题的一个给定答案（在有提示的情况下）会比计算这个答案本身要容易得多。（就我所知）有创见的地方是，具体如何对这个集合应用上述观察。这种观察似乎在其它与区块链有关的环境中也是有用的，也许还不止于此。
当前，在 Bitcoin Core 中发生的常规验证需要按顺序遍历区块链（同时运行一些独立于上下文的微小检查）、向 UTXO 集添加输出、随后检索（被花费的）输出然后移除它们。通常 UTXO 集无法放进内存中，从而因为硬盘读写而进一步放慢速度。
SwiftSync 完全改变了这种模式，并且不会 改变安全假设。不再有数据库检索、内存使用量降低到近于零，而且所有验证都可以并行完成。这就从可能的瓶颈清单中划去了内存、硬盘读写和单线程性能。剩余的瓶颈是 CPU 和带宽，而且你在这两样上的条件越好，你验证起来就越快。
本协议的无状态性可能也使之非常适合内存受限的环境，比如使用专门的硬件（FPGA 和 ASIC）来验证区块链、构造零知识证据，或者仅仅为其它操作（比如 Schnorr 签名的批量验证）释放更多内存。你也可以轻松将验证负担分散到多台设备中。
我们需要进一步的基准测试来确定 SwiftSync 到底有多快，但非常初步的概念验证（还没实现任何并行化）已经显示出令人惊讶的 5.28 倍加速。
协议概述
对于链上的每一个输出，我们需要一个提示来表明这个输出到区块链顶端是否依然未被花费，但一个提示只需要一个比特（压缩之后小于 100 MB）。
如果提示是不正确的，验证就会失败（这是一个 DoS 界面），这样的提示应该来自一个可靠的来源（例如，你的全节点软件的二进制文件） [1]。
我们将依赖于 “assumevalid” 以跳过特定的检查。这并非必需的，但这样可以得到一个更优雅、更节约带宽的协议。assumeavlid 的具体后果、非 assumevalid 的版本以及 SwiftSync 跟 “assumeutxo” 的关系，我们会在后文解释。
我们以顺序独立（完全可并行）的方式来处理所有的输入和输出。我们唯一要求的状态是一个 32 字节长的哈希聚合值（不需要使用内存，也没有硬盘的随机读写）。本协议的性能随着可用的 CPU 和带宽而线性扩展。
对于每一个输出：
- 如果提示表明该输出到链顶端也不会被花费：
- 那就把它写入 UTXO 集（也即仅追加 —— 我们不需要这些数据，直到 SwiftSync 完成，回归常规验证模式）
- 反之：
- 哈希它的输出点，然后添加到哈希聚合值中
对每一个输入：
- 哈希它的输出点（输入本身会携带），然后从哈希聚合值中移除它
在我们完成 SwiftSync 的时候，哈希聚合值的数值应该是 0，从而证明我们写入 UTXO 集中的 输出都是未花费，而且其它输出都只花费了一次（没有重复花费）。
下文还有更多细节，不过本协议的核心就是如此了。
细节
关于哈希聚合值
我们所需的一切仅仅是，能够知道集合 A（被花费的输出）跟集合 B（输入）是否一致，不论顺序。这种独立于顺序的属性保证了：在添加之前移除一个元素也不会造成问题，也即使之完全可以并行化。
在数学上，直接哈希原像，然后 加入/减去 这个结果（模运算）几乎 就够了 —— 我们还需要加入一个秘密值盐，以保证数据不能从外部操纵（广义的生日问题）。 [2]
例子
花费掉的输出：outpoint_A、outpoint_B
输入：outpoint_C、outpoint_D
如果 hash(outpoint_A||salt) + hash(outpoint_B||salt) - hash(outpoint_C||salt) - hash(outpoint_D||salt) == 0，那就证明，我们的花费掉的输出的清单跟输入的清单是完全一致的（即 (A==C && B==D) || (A==D && B==C)），而剩下的就会跟 UTXO 集完全一致。
关于 assumevalid
根据当前已经实现的状态，assumevalid 仅仅用于跳过脚本验证。它背后的安全论证是，用户已经相信了自己的软件是正确的，所以他们也可以信任一个关于一条链的有效性的声明。除了脚本以外，还有别的东西可以跳过，但大部分剩余的检查都不昂贵，而且/或者 难以移除，可能这就是留下它们的原因。如果我们稍微扩大 assumevalid 的用法，我们可以显著减少验证输入所需的数据量。请看。
UTXO 集中的一个完整条目包含以下数据：
- 输出点
- 输出脚本
- Coinbase 标签
- 区块高度
- 数额
简单情形
没有 assumevalid 的时候，若要检查输入，所有这些数据都必须可用。在 assumevalid 版本的 SwiftSync 中，我们只使用输出点（即上面这个清单中的（1））。这是很方便的，因为这个数据在每一个输入的内部就有。省略（2）是很容易理解的 —— 反正在 assumevalid 中，脚本是不检查的 —— 但其余数据呢？
跳过（3） coinbase 标签意味着我们不再能够检查一个从 coinbase 中创建的输出是否早于允许花费的时间就被花掉了 —— 这些输出本质上都有一个暗含的长达 100 个区块的相对时间锁。为了检查这样的相对时间锁，我们也需要知道（4）区块高度。类似地，交易中的 nsequence 字段也可以用来启用（我们不会检查的）相对时间锁。
区块高度这个数据也会间接帮助一些仅在并行验证情形中才会遇到的事情：它保证了输出会在被花费之前（而非之后）创建。注意，仅有区块高度可能是不够的，因为一个输出可能会在被创建的同一个区块中就被花掉。稍后我们会详细讨论这个问题，因为我们需要在非 assumevalid 版本中明确地处理这个问题。
另一个我们会在稍后处理的问题是 BIP30，当前，它需要完全访问 UTXO 集。UTXO 集是完全可寻址的，但对 assumevalid 版本来说，应该不需要它。
在 assumevalid 模式下包含跳过上述检查，应该是完全没有争议的，因为没有一项检查的重要性比得上脚本检查（也就是 assumevalid 已经跳过的检查） [3]。
更难的情形
跳过（5）数额检查是可以辩论的，因为没有数额检查，你就不再能主动检查通胀 bug。幸运的是，这是有解决办法的 —— 我们可以将来自 UTXO 集的数额加总起来，然后检查它有没有超过总的货币发行量。注意，这也应该包含 OP_RETURN 输出的数额。
这种办法的局限性之一是，没有能够计算出矿工 没有 取走的资金的简单办法，因为我们隐式地跳过了手续计算。理论上来说，如果某人拿走了这些未被申领的资金，我们也不会注意到。从稀缺性的角度看，这并不比 assumevalid 的最坏情形 —— 通过一个无效的脚本，不正当地取得了资金 —— 更糟。此外，可以这样拿走的资金的数量是非常少的 [4]。
最后，还有一种后果无疑 是个缺点，但不是太大。因为在检查一个区块的输入的时候，我们没有完整的前序输出数据，所以我们也无法生成所谓的 “undo” 数据 —— 在区块链重组事件中回滚区块链所需的数据。这就意味着，我们无法回滚得比 assumevalid SwiftSync 点更深。以剪枝（pruned）模式运行 Bitcoin Core 会有完全一样的局限性。有一种实用的处理办法：对最新的 X 个区块，不实用 assumevalid SwiftSync ；X 只需要取你认为不太可能发生重组的深度即可。
简而言之，通过依赖于一个最小延申的 assumevalid 定义、接受（跟剪枝节点一样）遇到深度重组就必须重新同步的要求，我们就可以得到一个非常干净、简单的协议。当然，在非 assumevalid 模式下验证的能力也是很重要的，所以我们接下来就讨论这部分。
不用 assumevalid
不用 assumevalid 的 SwiftSync 可以完全验证所有的共识规则，但我们需要一些额外的步骤。除了加入和减去哈希后的输出点，我们还需要将检查一个输入所需的所有东西（见上文的 5 数据列表）都包含在哈希值中。
添加这些到哈希聚合值中是容易的，因为在需要添加的时刻（处理输出的时候），这些数据我们都有。但想要移除它们的时候（处理输入的时候），我们只有输出点 —— 所以没只好重新下载缺失的数据。相比于常规的完全验证，可能需要额外 15% 的数据，这里面还有大量可以高效编码的空间 [5]。
我们可以让用户在外部下载这些数据，但也可以考虑让点对点网络来提供这些数据。可能幸运的是，大部分的节点都已经拥有这些数据了 —— 前面提到过允许节点重组区块链的 undo 数据就是我们需要的 [6]。注意，我们还需要给我们提供提示的同一个来源给我们提供 undo 数据的一个哈希值，以保证随机对等节点不会给我们无效的数据、导致验证失败 [7]。
因为我们现在会检查数额，所以对 UTXO 集的单独通胀检查就不需要了，但我们确实会遇上一些（上一节已经提及的）新问题。
区块内的交易顺序
因为并行化在 SwiftSync 中是默认选项，我们并不必然知道输出会不会在被创建之前就被花掉，比如说，输出可能在同一个区块中被创建然后被花掉（在所有其它情形中，检查区块高度就足够了）。
虽然这个问题的存在是不可否认的，但如果你深入思考，会觉得它的后果没什么大不了的 [8]。但我们确实可以解决这个问题，而且只要我们处理了它，就会更容易讨论安全问题。
最直接也最实用的方式是，使用一种逐区块的缓存。你可以认为它是一种逐区块的微型 UTXO 集（技术上来说，它只需要能够证明顺序的数据就足够了），是按顺序构造出来的。我们只需要在一个输入的（创生）区块高度与当前区块相同的时候，检索输入就可以了，虽然可能有理由做更多 [9]。这会让协议不那么优雅，因为我们加回了一些状态，而且做了顺序搜索，但这会局限在单区块的环境下 —— 我们依然可以完全自由地并行处理所有区块。
如果我们想坚持无缓存策略、完全避免搜索和顺序检查，还有更多的选择 [10]，但对于运行在常规硬件上的全节点来说，区块缓存应该已经够好了。
BIP30 验证
为了让 SwiftSync 等价于常规的完全验证，它也需要满足 BIP30 的要求，即使它不能访问 UTXO 集。BIP30 是在 2012 年 3 月才激活的，但它的执行范围是从创世区块开始到 BIP34 激活的时刻（区块高度 227931，2013 年 3 月）。BIP30 通过无效化产生已经存在的未花费输出的区块来防止重复输出。理论上，BIP30 并不能完全防止重复交易（BIP34 可以，但也带来了一些没有解决的问题），因为创建、花费然后重新创建依然是可以的，虽然在现实中这从没发生过。
在 BIP30 激活以前，出现过两个重复输出，相同的 coinbase 交易输出被创建了两次。第二个输出就覆盖了第一个，实际上让第一个输出无法花费。这些实例在 BIP30 中被当作例外。更多信息可以在这里找到。
SwiftSync 没有 UTXO 集的概念，所以我们无法跟踪一个输出是否已经存在。幸运的是，可以设计出另一种方法，给我们相同的结果。我们可以直接保存一个包含了每一笔 coinbase 交易 id 的缓存，从而检查它们的唯一性。这只需要占用 227931 * 32 字节 ~= 7MB 的内存，而且我们还可以进一步优化它，甚至让它变成无状态的，只要我们想 [11]。它不仅等价于 BIP30，也是我们今天的做法的更快速的直接替换。
还有一种理论上存在的场景，就是一次狂暴的重组，回滚到 2013 年，导致 BIP34 永不激活、BIP30 永久持续。与其解决这个若有若无的情形，更实用的解决方案是（如果发生了这种事，就）直接返回非 SwiftSync 验证。
SwiftSync 与 assumeutxo
Assumeutxo 和 SwiftSync 是完全正交的。Assumeutxo 从一个假设是正确的 UTXO 集开始，然后在后台执行验证，从而验证这个假设的真伪。后面这部分就是我们可以使用 SwiftSync 的地方。
assumeutxo 所导致的一种复杂性是，它需要两套状态：一套是从 assumeutxo 点到当前的链顶端，一套是从创世区块到 assumeutxo 点。一旦后台的验证完成，我们将再次回到一套状态。因为 SwiftSync 是近于无状态的，所以在后台验证中使用它可能会让事情变得更简单。
一个重要但非常容易解决的差别在于，虽然我们不再需要构造出一个 UTXO 集，我们依然需要验证作为起点的 assumeutxo 的 UTXO 集，跟可以从 SwiftSync 提示中导出的 UTXO 集是完全一样的。我们可以通过相同的哈希聚合技巧来实现这一点。
每次我们处理一个被提示会留在 UTXO 集中的输出时，我们就将它加入哈希聚合值中（这将是完整 UTXO 集数据的一个哈希值，不仅仅是输出点）。类似地，我们哈希 assumeutxo 的 UTXO 集中的每一个条目，然后从哈希聚合值中移除它们。如果两者都是正确的，那么我们最终也会得到一个 0。
令人满意的是，此时如果使用的是非 assumevalid 版本的 SwiftSync，甚至不再需要每个输出一比特的提示，因为不论一个输出最终会不会存在于 UTXO 集中，你添加到哈希聚合值中的数据都将是完全一样的（即 输出 - 输入 - UTXO == 0）。这样的优雅让我陶醉。
致谢
验证过程的优化是人们经年累月讨论的一个话题。许多人都走在我前面，探索了相关的想法。Cory Fields 的 UHS 可能是与本协议最相似的，而它本身又是 Bram Cohen 的 bitfields 想法的改进。Tadge Dryja 的 utreexo 也在状态缩减、并行化以及跟缓存相关的初始化区块同步（IBD）提示方面与本协议有重叠。
感谢 theStack 和 0xb10c 给出最初的基准测试和统计数字。我也想感谢积极开发 IBD 优化的 Bitcoin Core 开发者们 —— davidgumberg、l0rinc 以及 andrewtoth —— 以及给出了有益讨论的人，以及提供了反馈的其他许多人。
脚注
1. 在接收提示上，我们还有没有别的选择？依赖于存放在你的软件中的数值的一个缺点是，软件可能是几个月前发行的。而在利用完其中的提示之后，验证过程又会显著慢下来。另一种可能是从一个受信任的第三方处接收[非 assumevalid 的 SwiftSync]提示。在最坏情形下，这个第三方会说谎，你的验证最终会失败。重要的是，你不会因此认为无效的链是有效的。两种方法混用也是可以做到的（即是在你的节点离线的时候也能追上），但这样的话我们就要加入额外一些逻辑，以从 SwiftSync 会话之间的集合中移除 UTXO。最后，提示也可以承诺到链上，但这就需要一次软分叉。 ↩
2. MuHash 和 XOR 堆叠跟使用秘密盐的哈希聚合值孰优孰劣？MuHash是可行的替代，如果我们希望移除秘密盐的要求的话（比如说，为了允许客户端之间的状态比较），但这对我们的应用场景来说似乎太过了。XOR 是不够的，因为元素出现两次之后就会相互抵消（一次是输入，一次是输出）。可以通过额外的检查来弥补这一点，但那就跟我们这里提出的方法非常接近了。 ↩
3. 如果我们忽略时间锁和交易排序，在最坏的情况下会发生什么事？未被强制执行的时间锁或者失序的交易仅仅意味着一些资金会过早被花费，或者交易的顺序出现了一些奇怪的事情（先是资金从一个还不存在的输出中花掉了，也就是制造了通胀，后来这个不存在的输出又被创建了出来，从而抵消了通胀）—— 如果这个通胀最终没有被纠正，SwiftSync 验证就会失败。最重要的是，这不会被 assumevalid 的最坏情况 —— 无效的脚本花掉了一个输出 —— 更坏。 ↩
4. 如果我们 确实 想对矿工没有取走的资金作一个更加精确的检查呢？理论上，我们可以给矿工没有取走全部应得手续费的区块的所有输入添加数额提示，也就是哪些输出在这些区块中被花掉的提示。对于这些具体的实例，我们可以在哈希值中包含数额。矿工可以通过总是留下 1 聪来发动骚扰。要求承诺总手续费或者不允许遗留手续费的软分叉会是更彻底的解决方案。也就是说，考虑到最差的情形也不会比 assumevalid 已经假设的情形更差，所以接受这种局限性是完全合理的。在乎的人应该选择禁用 assumevalid。 ↩
5. 我们如何为非 assumevalid 版本压缩所需的数据？这里有大量的高效压缩和去重机会。有许多重复的模式（例如，标准交易）、我们知道其原像的哈希值（例如，P2SH）以及频繁出现的输出（例如，近期区块高度出现的绝大部分输入）。来自 BIP337 的部分观念没准也可以重用。 ↩
6. 通过 P2P 网络来提供 undo 数据的办法还能对别的用途有用吗？它让剪枝节点可以回滚得比自己的修建点更深，只要他们保存了被修剪的 undo 数据的一个哈希值（很遗憾，assumevalid 的 SwiftSync 无法做到这一点），并且对等节点愿意为他们分叉出去的区块提供 udo 数据。因为 undo 数据基本上让你可以脱离环境、完全地验证区块，像 “PoW 欺诈证明”（通过选择性验证分叉区块的低带宽区块链验证）这样的协议也可以从中受益。 ↩
7. 还有别的办法，可以提供 undo 数据而不带来 DoS 问题吗？最直接的办法就是哈希这一数据、放到每一个区块里面，然后使之成为共识的一部分；但软分叉是很难的。还有一种理论上的点对点方法是，在对等节点之间比较 undo 数据的状态，如果有差异，就找出哪个对等节点在说谎（只要至少一个对等节点是诚实的，就可以奏效），但这也相对复杂。这样做的一个例子（虽然是在不同的环境下）可以在这里找到。 ↩
8. 假设我们不检查区块内的交易排序，攻击者可以如何利用这一点？接受一条交易排序不正确的链不会对资金所有权和通胀产生 任何 影响。唯一的问题是，常规的完全验证节点会拒绝这种替代性排序，所以它会成为一个硬分叉。然而，这种分叉不会发生，除非这个替代性排序真的出现在了最多工作量证明的链上。要设想一个攻击者可以实质上利用这一点的情形是非常困难的。这里作一个尝试：（1）颠覆当前具有最多工作量证明的链，挖出一个使用这种替代性排序的区块；（2）让受害者执行一路执行 SwiftSync 验证到链顶端，从而让他们相信你的替代性排序（也许要先污染他们用的软件？）；（3）让受害者在这个 “错误” 链上跟你购买比特币。最终，“好” 的链会再次打败你的 “坏” 的链。总而言之，看起来这种攻击并不会比你直接卖出你的比特币，然后重组掉这些交易更高效。即使攻击者的目标仅仅是制造混乱，也无法说出大规模重组与这种攻击在效果上有什么区别。 ↩
9. 也许我们可以通过缓存而不是重新下载每一个 UTXO 来节约带宽？是的，而且也有很好的处理方法，但确实会增加更多复杂性，并让整个验证过程更连续（难以并行）。你可以让缓存覆盖多个区块，甚至可以进一步，提供哪些输出将被花费的提示。这这能会让一些瓶颈又回来，比如带宽。 ↩
10. 如果我们没有缓存，该如何检查区块内的排序？我们可以向 UTXO 集加入一个额外的元素：一个正统的交易编号（输出编号也可以，而且出于其它原因很有吸引力，但其精确性超出了我们的需要）。现在，加入一个输出要被花费了，而其创生区块高度与当前高度相同，那么我们就检查交易编号，以验证它在我们正在求值的交易 之前 就创建出来了。这种方法的缺点在于，它会增大完整的 UTXO 集的大小（每个条目要增加 2 字节）。更有趣的方法可能是为每一个我们知道其会在同一个区块中被花费的输出加入额外的提示。具体来说，我们提示将要花掉它的交易的编号（必须大于包含它作为输出的交易的交易编号 —— 我们只需要编码两者的差值就可以了），然后将这个提示包含在哈希值中。现在，当我们遇到一个其创生高度与当前高度匹配的输入时，我们就在哈希中包含其交易编号，然后将它从聚合值中移除。不幸的是，一个输出在创生的同一个区块中就被花掉的情形非常常见，所以必要的提示数据可能会增加很多。虽然缓存是一种更显然的办法，比较它与无缓存替代方案的基准应该还是有趣的。 ↩
11. BIP30 是另一个要用到缓存的地方 —— 该如何优化呢？我们可以通过截断 txid 来减少数据集。一般来说，我们会担心碰撞，但我们可以通过预先计算具体的、需要保留的比特来保证没有碰撞，从而保证在这条具体的链上有一个无碰撞的结果（使用一个盐来重新哈希也可以做到，但计算起来更慢）。从信息理论上来说，这可以让每个 txid 降低到 18 比特，虽然这在计算上是做不到的。实际来说，我们应该可以做到 4 字节内（甚至 3 字节以内）。这样，数据体积就减少到小于 1 MB。我们也可以更进一步，抛弃这个状态，在哈希聚合值的帮助下搜索。为此，我们要提供一个截断后哈希值的有序列表。我们要遍历这个列表，检查每一个元素都比上一个元素更大（从而证明唯一性），同时将它们添加到哈希聚合值中。当我们在区块中遇到它们的时候，再从哈希聚合值中移除它们（如果最后我们会得到 0，就证明了集合等价）。 ↩
