utreexo：一种扩容方案

作者：Calvin Kim
来源：https://medium.com/@kcalvinalvinn/eli5-utreexo-a-scaling-solution-9531aee3d7ba

关于我：过去 7 个月里，我一直在给 Utreexo 实现贡献代码；同时我还是首尔 Bitcoin Meetup 的联合创始人，专门研究比特币和相关科技两年了。

Utreexo 是一种为比特币设计的哈希累加器，由 Tadge Dryja 提出（他也是闪电网络白皮书的联合作者）。这种技术有以下的优缺点。

优缺点

对比特币的四大好处

只需下载几千字节就可以成为一个新的全节点，机械硬盘（HDD）同步起来和固态硬盘（SSD）一样快
允许在节点初次加入网络、下载区块时并行化下载
让共识过程可以独立于数据库的实现，从而增强比特币的安全性（当前比特币软件的数据库是谷歌开发的）
不需要实施硬分叉，就可以将 Utreexo 引入比特币网络

两大缺点

在初次下载区块时要多消耗 20% 的带宽
Utreexo 存档节点（Archival node）有额外的存储要求

Utreexo 工作原理

一句话总结：使用了 Utreexo，一个全节点只需为每个区块保存一个哈希值；但在传统的模式中，即使是剪枝全节点（pruned full node）也需要保存每个区块里所有的 UTXO。

要理解 Utreexo，我们先要搞懂哈希树结构。我们以默克尔树为例，因为比特币已经在使用这种数据结构了。

一棵有 8 个叶子节点的默克尔树将如下图所示：

- 一棵典型的默克尔树 -

图中的每个数字都表示一个哈希值。

在比特币中，所有位于最底层的数字，都是一条 TXID（交易索引号）。而 08 是 00 和 01 两条哈希值前后拼接、再进行哈希结算的结果。13 则是 10 和 11 两条哈希值前后拼接、再进行哈希计算的结果。（08' = hash(00' + 03') ，此处的加号表示把后一串字符跟着写在前一串字符后面，从而形成一条新的字符串。）

在当前的比特币协议中，默克尔树用来生成区块头中的默克尔根（译者注：这个默克尔根是该块所打包的交易的 txid 哈希而成的，可以用来校验区块头与区块内容是否一致，也可以用来向轻客户端证明某笔交易已打包到了某个区块中）。Utreexo 则将默克尔树的概念用在了 UTXO 上。值得提醒的是，Utreexo 不会取代区块头中的默克尔根。

当前，如果你是一个比特币全节点，你必须存储当前所有的 UTXO。而在 Utreexo 中，作为全节点你只需存储 UTXO 的哈希树根。整棵树就像这样：

- 只有树根的 Utreexo 树。所有其它的哈希值都删掉了。 -

从 00 到 13 的所有哈希值，在验证之后都丢掉了，只保存 14（树根）。

如果用户要花费 UTXO 07，他们需要向 Utreexo 全节点证明这个交易输出存在。他们向验证节点提供 06、07、10、12 四条哈希值，验证节点将用这四条哈希值生成一棵独立的树：

- 用于验证的树。注意看树根是如何计算出来的 -

空白的位置 11、13、14 都可以使用这几条哈希值计算出来。如果得出来的树根与节点存储的 14 一致，那我们可以断定，用户要花费的 UTXO 存在。

实际上的 Utreexo 会比这里介绍的要复杂一些，原理也跟这个案例有所区别，但这个案例是其概念的一个缩影。

好处

1. 只需下载几千字节就可以成为一个新的全节点，机械硬盘（HDD）同步起来和固态硬盘（SSD）一样快

几千个字节就可以做全节点

当前的比特币网络有两种全节点：存档全节点（Archival）和剪枝全节点。剪枝全节点仅保存未花费的交易输出（即 UTXO）。Utreexo 使得另一种全节点模式，可称为“压缩状态节点（Compact State Node，CSN）”，得以出现。这种模式的全节点仅存储 UTXO 根值和钱包信息。所以，这种全节点不同于现在的全节点（用户至少要存储几个 GB 的数据），只需不到 1 KB 就足够了。

这种只存储与用户有关的 UTXO 信息的能力，会随着比特币的普及而变得越来越重要。一个用户至少需要一个 UTXO（考虑到隐私，还需要更多），用户的增加必定带来 UTXO 数量的增加。我们可以从下图中清晰地看到 UTXO 数量的增长。

- UTXO 数量统计。已排除使用 OP_RETURN 的 UTXO -

因此，剪枝节点的存储要求会逐渐提高，导致比特币全节点的最低存储要求不断提高。Utreexo 可以让用户修剪不属于自己的 UTXO，从而缓解这个问题。

初始区块下载在机械硬盘上可以跟固态硬盘上一样快

因为压缩状态节点可以用不到 1 KB 的数据代表整个 Utreexo 状态，那就不需要在初始区块下载中查询硬盘。这使得初始区块下载可以完全在内存中发生，使得机械硬盘节点同步起来可以跟固态硬盘节点一样快。

2. 允许初次下载区块时并行化下载

UTXO 快照是保存某个区块高度时候的所有 UTXO。一个可能的用途是 assumeUTXO 项目，允许用户从被快照的高度开始同步区块链。快照的主要麻烦在于其体积，如果给当前的区块高度做快照，快照的大小是 5 GB 左右，是非常大的。而且快照的大小也会不断增长，就像优势 1 里说的那样。但有了 Utreexo，在最差的情况下也不到 1 KB 就可以完成 ¹（最好的情况下大约100 字节）。有了 Utreexo，UTXO 快照就会变得非常简单；而且 ZkVM 项目已经实现了 Utreexo，并通过在区块头中包含 Utreexo 树根来保存区块链状态。

当快照变得如此便宜，就有可能每个区块高度都快照一次。有了这种技术，未来就可以实现并行化的区块链同步方法，意味着一台电脑（CPU 核心）可以同步从 0 到 300000 的区块，而另一个可以同步从 300001 到 600000 高度的区块。然后，同步方法的优化就将围绕时钟速度转向围绕数量、GPGPU 也可以运用起来，这些异步的区块同步方法可以进一步降低启动一个比特币全节点所需的时间。

3. Utreexo 强化了比特币的安全性

让共识代码可以独立于数据库的实现

libconsensus 项目曾致力于将共识代码从 Bitcoin Core 软件中分离出来，使得：

与共识无关的代码可以改变而无需担心打破共识机制
让不同的比特币软件实现可以使用同一个共识 API

这个项目最终被抛弃了，因为让数据库（leveldb）从共识代码中独立出来非常困难。这是一个亟待解决的非常重要的问题，因为在 2013 年，Bitcoin Core 软件从 Berkeley DB 迁移到了 levelDB，然后就遭遇了一次意料之外的临时硬分叉，一次意料之外的临时软分叉，以及一次硬分叉（BIP50）。

当前，共识是依赖于 levelDB 的功能的，因为你需要获得存储好的交易。这就意味着，如果 levelDB 的功能出错了，就有可能跟使用另一种数据库的另一个客户端产生分叉。

有了 Utreexo，你可以根据 Utreexo 来验证收到的交易和区块，无需访问数据库。收到的交易所花费的 UTXO 的存在性可以使用包含证明（included proof）来检查。

4. 无需硬分叉

Boneh 等人提出的 RSA 累加器，在体积上比 Utreexo 更加高效。但是，实现 RSA 累加器需要一次软分叉。比特币是一个比较保守的系统，即使软分叉也会伴随极端的谨慎，所以这些累加器是很难在比特币中实现的。 Utreexo 不需要任何分叉。用户只需自己选择是否运行 Utreexo 节点。