作者：Davidson

来源：https://delvingbitcoin.org/t/implicit-deletions-and-improvements-in-utreexo-ibd/2881

Utreexo 是一种动态的累加器（accumulator），允许将整个 TXO（交易输出）集合表示为几个哈希值。它的办法是将数据结构化为完美默克尔树的森林，节点只需要保存这些默克尔树的根值，也就是 $O(log(n))$ 个哈希值。在比特币中， n 是添加到累加器中的 TXO 的数量 1。这让客户端在占用空间和磁盘读写上都更高效，可以运行在资源受限的环境中。

为了确定一个 UTXO 是否存在，交易或区块必须附带一个包含证明，而 Utreexo 节点在接受这个区块（交易）之前必须先验证这个证据。这些数据必须跟区块（或交易）一起传输，从而形成了额外的带宽负担。这就是 Utreexo 背后的主要牺牲，并且给定其累加器的工作原理，是不可避免地。在 IBD（初始化区块下载）期间，只保存着累加器的节点 —— 称为 “致密状态节点”，或 “CSN” —— 必须也下载在一个区块内被花费的所有 TXO 的一个批量证据。我们为整个区块计算一个体积巨大的证据，而不是给每一笔交易都计算一个证据，是因为这其中可能有 “重叠”：证明 A 存在时所用的材料，一部分在证明 B 时也是必要的，所以我们可以只发送一次，以此节约带宽。

一直到最近，我们都认为这是不可避免的、我们必须实现一种缓存策略来优化带宽的使用。如果没有优化，一个 Utreexo 证据的平均开销是跟区块的体积 100% 对应的。因此， 1 MB 大小的区块就需要附带一个 ~1 MB 的证据。那么，在 IBD 期间，总的下载量将大概是当前区块链体积的两倍，在当前大概是 1.3 TB 。

然而，灵机一动，我们知道 UTXO 常常会在诞生后的几个区块内就被花掉。通常来说，所有 TXO 的 80-90% 是在诞生后的 100 个区块内花掉的。使用少量的内存，也许就能为少量区块内就会变化的位置节约 60-70% 的带宽要求。 由 BIP-183 草案 2 定义的 P2P 消息，允许请求节点指明自己需要的位置。不过，给定今天区块链的体积，哪怕只有 30%，也是 ~200 GB 。现在全球的平均网速只有 ~118 Mbps，这依然是一个很大的问题。 如果能够消除额外的带宽需要、又不需要保存整片树林，那就最好了，因为保存整片数量就违反了 Utreexo 的初衷。

事实证明，这是有可能的 —— 并且办法非常简单、非常优雅！我们可以把叶子直接放在它们最终会在的位置，甚至无需删除。这篇文章就要解释这种新的方法，以及可能的优化措施。

Utreexo 添加和删除

在展示新算法之前，我先带各位简要回顾一下 Utreexo 的工作原理。

如 BIP-181 所定义的，Utreexo 累加器有三种操作：modify（修改）、 prove（证明）、verify（验证）。我们先看 modify。它实际上是给森林同时应用添加和删除操作。这两种方法不单独暴露，因为顺序会影响结果。如果你先 add（添加）、再 delete（删除），跟你先 delete 后 add 得到的结果是不一样的。在修改操作内，我们总是先移除被花费的 UTXO，然后再添加新创建的 UTXO 。一致这样做是保持共识的关键。

所谓森林，是这样形成的：将所有的叶子放在底部，两两哈希、层层向上哈希，得到根值；排列叶子的方式使我们最终总会得到 2 的幂数个根。然后，我们可以基于这些树有多少叶子、按降序（从多到少）来排列它们。一个带有 10 个叶子的森林看起来将是这样的 3：

14
|---------------\
12              13
|-------\       |-------\
07      08      09      10      11
|---\   |---\   |---\   |---\   |---\
00  01  02  03  04  05  06  07  08  09

在这里，11 和 14 都是根值。一个 CSN 可以删掉一切，只留下 11 和 14，只依赖于包含证明来了解分支和叶子。而包含证明就是一个普通的默克尔证明（包含目标叶子，给出通往树根的路径）。所以，叶子 01 的证明包含 00、08 和 13。有了这个证据，你就可以通过哈希 00 和 01 得到 07，哈希 07 和 08 得到 12，最终，哈希 12 和 13 得到 14 。

但是，因为 Utreexo 是动态的，我们并不能提前预知这个森林在某个区块高度时候是什么样的。所以，“添加” 操作必须再智能一些，不能像静态的默克尔树那样，仅仅是把东西拼接起来然后哈希。

Utreexo 添加

为了添加一个新的元素，我们必须使用一种 先摧毁后移动 循环：

  1. 令 i 从 0 开始，令 curr _ add 为准备添加到累加器的一个 UTXO 的哈希值。
  2. 如果第 i 个根是空的：
    1. 移动 curr _ add 到这个位置，并让叶子计数增加 1
    2. 返回。
  3. 弹出在这个位置的值，换成一个空值。
  4. 令 curr _ add 为该根值与 curr _ add 的拼接的哈希值。
  5. 令 i 增加 1 。
  6. 回到第 2 步。

用图形来表示，我们假设现在的森林有 5 个叶子。我给底部给每一棵树增加了索引，每棵树都有 $2^n$ 个叶子，其中 $n$ 就是索引号。为了避免混淆，森林的节点都使用字母来表示，并且创建它们的顺序与字母顺序相同。到最后，你应该能明白它们为什么会长成这种楼梯的样子。

G
|-------\
C       F
|---\   |---\
A   B   D   E             H
————————————————————————————
      02          01      00

在添加一个新的元素（记为 I）时，我们先看第 0 号根，看看它是不是空值。在这里，H 占据了这个位置，它不是空值，所以我们 “摧毁” 它 —— 移除它，计算 J = H ( H || I ) 从而创建一个新的根。现在，我们要添加 J。

G
|-------\
C       F              J
|---\   |---\          |---\
A   B   D   E          H   I
————————————————————————————
      02          01      00

现在就变成了要添加 J。下一个根值 —— 01 号位置的这个 —— 是个空值，所以我们直接放在这个位置就行了。

G
|-------\
C       F       J
|---\   |---\   |---\
A   B   D   E   H   I
————————————————————————————
      02         01      00

这就是我们最终得到的森林。现在，我们有根 G 和 J，而一个 CSN 节点可以抛弃一切，只留下这两个根。这里面的非常重要的属性是：添加操作只与根有关，我们不需要知道任何别的东西。这是非常高效的，每次添加只需要 O(log(n)) 次哈希运算，但平均来说，哈希次数还会少得多，因为你会非常频繁的摧毁较小的树。

删除

删除甚至更加简单。在删除节点 B 时，我们只需将它的兄弟节点移到其双亲节点的位置。所以，对于我们上面这片森林，在删除 B 时，只需要将 A 移动到原来属于 C 的位置。

G
|-------\
A       F       J
|---\   |---\   |---\
-   -   D   E   H   I

在重新哈希到根时，将节点 G 的值更新为 H ( A || F )。如果你是一个 CSN，你依然可以做到这一点，但你需要通过包含证明来了解其兄弟节点以及哈希到根值所需的所有信息。在这里，你需要的证据是 [A , F] 。

隐式删除

事实证明，你可以通过考虑一个 TXO 会被花费的事实来更新添加算法。如果你能提前知道（它什么时候会被花费），那么在添加时，你就不必哈希它，你可以直接移动根值！这一项简单的变更，就足以完全消除前面所述的显式删除阶段的必要性。

为了用图形来表示它，设想我们想要得到上面那样的森林，但我们从一个空的森林开始。我会展示每一个步骤。请记住我前面讲到的算法。

添加 A —— 因为 00 号根是空的，所以我们把它留在这里。

                          A
————————————————————————————
      02         01      00

添加 B —— 因为 00 号已经被占据了，所以我们必须先摧毁 00 号的数值。不过，我知道 B 号会被删除，所以我不需要计算 H ( A || B ) ，我直接把 A 移到 01 号位置就行了。

                A
                |---\
                -   -
————————————————————————————
      02         01      00

现在，添加 D —— 00 号位置是空的，所以我们把它放在这里。

                A
                |---\
                -   -    D
————————————————————————————
      02         01      00

添加 E —— 我们必须先摧毁 00 和 01，然后将它们移到 02 号位置。

G
|-------\
A       F
|---\   |---\
-   -   D   E

最后，我们把两个遗漏的节点添加进来 —— 添加过程跟上面的情况没有什么两样。

G
|-------\
A       F       J
|---\   |---\   |---\
-   -   D   E   H   I

你看！我们得到了跟前面一模一样的森林，但我们不必显式删除任何东西！

不过，请注意，这种办法只有在一定区块高度以前才能使用。得到提示的最大高度之后，所有的 UTXO 都会在自己应该在的位置，如果你还要再删除东西，就必须先有证据，才能删除它，因为你已经把它加进去了。

在完成 IBD 之后，你就会运行常规的 Utreexo 流程，使用包含证明以及常规的删除方法。本方法只能用来提升 IBD 的效果。

如何知道某些东西将被花费

问题来了：我如何在不必信任他人的前提下，知道某个 TXO 将被花费呢？其他人可以骗我说某个 UTXO 已经被花掉了，这就变成了一种 DoS 攻击，不是吗？这会让我的累加器偏离网络，让它无法接受正确的证明。

我们是通过 “Swift Sync” 4 来做到这一点的。我们的花费情形的断言机是 Swift Sync 的提示文件，这个文件可以告诉我们一个 TXO 会不会花掉。为了验证这个提示，我会保存一个哈希聚合值；如果这个提示文件是正确的，那么在处理完之后，这个哈希聚合值将是 0 —— 所有输入都被移除，所有被花费的交易输出（STXO）都已添加。恶意人无法迫使我产生一个偏离正轨的累加器。

性能优化

除了减少带宽使用，这个设计还让我们可以将 IDB 并行化。我们正在开发的 AssumeValid 模式 Swift Sync 5 实现会按照我们收到区块的任意顺序来处理它们。速度较慢的对等节点不会拖慢我们的进度，因为我们可以先处理更快的对等节点传给我们的区块。我们可以将系统资源用到极限。在我们运行的所有测试中，网络连接的速度从 ~30Mbits/s 到 2 Gbps 不等，我们基本上只受制于带宽，哪怕是便宜的树莓派电脑上。这表现出了快速、便宜 IBD 的强大潜能。这个过程中唯一的串行部分是对我们的累加器应用变更。我们有一个线程只干这件事：它收到一个关于变更的清单后，先扣住一些因为其祖先还不可得而无法应用的，然后一旦能应用就变更累加器。不过，这个线程的资源用量还是很低，CPU 使用量微不足道。

非 AssumeValid 版本还在积极开发中，我后面会再报告。不过，我们确实想出了一种办法来实现充分的并发并提高带宽效率。

（译者注：“AssumeValid” 同步模式会假设区块链上足够深的区块只包含有效交易，不包含无效交易，因此，不再验证这些交易的见证（比如签名），只关注交易处理完之后的效果 —— 它花费了哪些 UTXO、创造了哪些 UTXO 。）

未来的研究

我们有一些关于并行地预先计算添加的想法，这回让上述串行线程的工作更加简单。我们也可以从删除操作预算计算根集合，让串行线程只需检查根集合的有效性、然后直接应用到累加器的当前状态。这会让我们的绝大部分工作负载都变成并发处理的，哪怕是在常规的 Utreexo 操作期间。

致谢

尤为感谢 Vinteum 6、2140 7 和 HRF 8 支持提出这些想法的人并主持让我们得以讨论这些话题的私人活动。

这项工作来自 Tadge Dryja、Calvin Kim、Ruben Somsen、我，以及其他帮助审核这些想法和我们的代码的人。

- - -

1. 在 Utreexo 中，我们不会添加诞生后在同一个区块就被花掉的 TXO 以及可以证明无法花费的 TXO 。因此，进入累加器的 TXO 的数量会少于存在过的 TXO 的总数。 ↩

2. https://github.com/utreexo/biptreexo/blob/917bdf3d344e69bfe387af5c0d761c93a91bbd95/bip-0183.md ↩

3. 我用了一个顺序编号系统，但这并非我们给事物编号的方式。详情见 BIP-181 。 ↩

4. Swift Sync：使用提示实现更聪明的同步 （中文译本） ↩

5. https://www.vinteum.org/ ↩

6. https://2140.dev/ ↩

7. https://hrf.org/ ↩