摘要:在这篇文章中,BitMEX 的受资助人 Calvin Kim 解释了为什么在 UTXO 下,区块被验证的顺序并不重要。这是因为磁盘空间的节省使 UTXO 快照成为现实,这反过来又使比特币区块链的验证得以平行进行。Calvin 继续解释说,人们可以通过验证累积器证明来检查传入的交易是否有效,摆脱了访问 UTXO 集的需求。这使得 Utreexo 节点可以消除磁盘访问要求,以换取更多的哈希运算,这可能是一个很好的权衡。Calvin 随后讨论了 Utreexo 如何改变我们对区块验证的思考方式。
![This image has an empty alt attribute; its file name is 1-1024x726.png](https://blog.bitmex.com/wp-content/uploads/2021/05/1-1024x726.png)
在另一篇文章中,我们展示了 Bitcoin Core v21.0.0 和我们带有 Utreexo 累加器 的节点之间的区块链验证速度差异的基准测试。我们能够做到这一点,因为 Utreexo 累加器允许对区块进行并行验证。
其总体思路与 assumeUTXO 式的异步验证相似。然而,通过 Utreexo 累加器,我们可以用几百个字节来表示 UTXO 集,允许我们直接在二进制中硬编码许多 UTXO 集的表示。只要所有这些硬编码集都得到验证,块的验证顺序并不重要,这允许我们同时验证多个块。Utreexo 累加器还取代了磁盘访问,用于更多的 SHA256 哈希处理,从而消除如果没有磁盘出现的写入/输出瓶颈问题。
用 Utreexo 累加器验证单笔交易
Utreexo 累加器是对 Merkle Trees 的一种修改。它的界面有四个动作:添加、删除、证明和验证。您可以从 Utreexo 累加器 中添加和删除元素。您可以生成一个累加器证明,向用户证明一个元素的存在。然后,另一个用户能够验证这样一个累加器证明。所有这些动作都可以只用所有默克尔树的根来完成,我们称之为 Utreexo 根。欲了解更多信息,请查看 Utreexo 的原始论文。
对于使用 Utreexo 累加器的比特币节点,我们不需要保留 UTXO 集。相反,我们可以只保留 Utreexo 的根,因为这是唯一的要求。任何想要花费 UTXO 的人必须向我们提供两样东西。首先,他们必须提供一个累加器证明,这是哈希到 Utreexo 根所需要的所有元素。第二,他们必须提供 UTXO 数据来证明他们能够花费 UTXO (主要是数字签名)。我们称这些信息为 Utreexo 证明。
![This image has an empty alt attribute; its file name is 1-1-1024x719.png](https://blog.bitmex.com/wp-content/uploads/2021/05/1-1-1024x719.png)
上述树中哈希 0-0 的 Utreexo 证明将是:哈希 0-0,哈希 0-1,哈希 1。为了验证这个证明,我们做如下工作:
- 将 Hash 0-0 和 Hash 0-1 放入 SHA256 中,得到 Hash 0
- 将哈希 0(我们计算出来的)和哈希 1 放入 SHA256 中,得到根值。
- 检查计算出的根值是否与我们存储的根值相符。如果不匹配,则 Utreexo 证明是错误的,我们拒绝该交易。
- 检查所有的 UTXO 数据。如果有任何数据是无效的,则 Utreexo 证明是错误的,我们拒绝该交易。
如何用 Utreexo 累加器验证单一区块?
要用 Utreexo 累加器验证一个单块,以下是所需的数据:
- 区块本身的数据。
- 所有正在花费在区块中的 UTXO 的 Utreexo 证明。
- UTXO 集的根。
我们从我们的同行那里收到区块的数据。不同的是,我们也会收到我们收到的区块的 Utreexo 证明。一个区块的有效性取决于(在其他共识规则中)该区块中所有交易的有效性。
Utreexo 节点的单笔交易的有效性取决于 Utreexo 证明的有效性,该证明由两部分组成。
- 累加器证明的有效性。
- 数字签名的有效性,证明您拥有 UTXO(或 UTXOs)。
请注意:(1)是不同的。在当前的比特币节点中,您不得不检查 UTXO 是否存在于您的 UTXO 集中,这需要访问磁盘。有了 Utreexo 节点,您只需验证累加器证明,并确保它是有效的,这需要 SHA256 哈希处理。需要注意的关键是,用 Utreexo 累加器,我们可以用 SHA256 哈希处理法代替磁盘访问。
Utreexo 累加器 消除了磁盘访问,以便在交易验证期间进行更多的 SHA256 哈希处理。
这种权衡是非常好的,因为 SHA256 可以非常快。相比之下,磁盘访问时间很慢(即使是最快的 NVMe 固态硬盘,也不会快多少)。
转变我们对区块验证的思考方式
许多人认为区块链是储存所有可供花费的代币的地方。然而,这并不完全准确。验证一个新区块或交易所需的信息存储在 UTXO 集。事实上,我们已经有一个比特币全节点模式,称为修剪节点,删除旧的、不需要的区块数据。
相反,块只是一个改变 UTXO 集的函数。每个区块都包含许多 UTXO 的所有权变化信息。所有过去的区块都是为了达到 UTXO 集的最新状态而需要的全部所有权的改变。当我们在验证一个块时,我们真正要做的是确保 UTXO 集的状态转换是有效的。
![This image has an empty alt attribute; its file name is 2-1-1024x518.png](https://blog.bitmex.com/wp-content/uploads/2021/05/2-1-1024x518.png)
如果一个比特币区块是 UTXO 集的单一状态转换,那么一个区块链就是 UTXO 集的多个状态转换。下面是比特币区块链的表现形式,如果我们把区块链看成是一系列 UTXO 集的修改。
![This image has an empty alt attribute; its file name is 3-1-1024x529.png](https://blog.bitmex.com/wp-content/uploads/2021/05/3-1-1024x529.png)
为什么我们需要按顺序验证所有的区块?
我们需要从区块 0 开始,逐一验证所有区块的原因是,在区块 500 的交易可以参考在区块 499 创建的 UTXO。如果我们没有在区块 499 修改发生后 UTXO 集的状态,那么我们就有可能把有效的交易标记为无效,并从比特币网络中分叉出去。
例如:如果爱丽丝给了鲍勃 50 个比特币,并且该交易被包含在区块 499 中,鲍勃将不得不参考在区块 499 修改后的 UTXO 集。如果我们的 UTXO 集没有在区块 499 修改过,那么我们就会错误的说,这 50 个比特币仍然属于爱丽丝,而不是鲍勃。当鲍勃花掉他的 50 个比特币时,其他人会说鲍勃的交易是有效的,而我们会说它不是。这将导致我们被从比特币网络中分叉出去。
失序块验证的总体思路
我们知道,一个完整的节点必须从一开始就逐一验证所有的块。那么,我们是如何做到失序块验证的呢?对于失序块验证,我们可以简单地提供验证一个块所需的 UTXO 集。这就是假设 UTXO 异步验证背后的想法。
让我们看看一个简单的失序区块验证的例子,我们正在验证 1-300,000 区块。
![This image has an empty alt attribute; its file name is 4-1-1024x572.png](https://blog.bitmex.com/wp-content/uploads/2021/05/4-1-1024x572.png)
我们对高度为 100,000 和 200,000 的 UTXO 集进行硬编码。由于我们知道高度为 100,000 和 200,000 的 UTXO 集是什么,我们可以分别验证 1-100,000;100,000-200,000;以及 200,000-300,000 的区块范围。当所有三个范围都验证完毕后,我们将有三个计算出的 UTXO 集:一个在 100,000 的区块;一个在 200,000 的区块;一个在 300,000 的区块。
然后我们将 100,000 区块的硬编码 UTXO 集与 100,000 区块的计算 UTXO 集进行比较。如果它们相等,那么硬编码的 UTXO 集就被证实是正确的。我们对 200,000 区块的 UTXO 集做同样的处理。如果它们也相等,那么我们就知道,在第 300,000 区块修改后的最新 UTXO 集一定是正确的。有了这个概念,我们就可以为一个失序块验证。
![This image has an empty alt attribute; its file name is 5-1024x584.png](https://blog.bitmex.com/wp-content/uploads/2021/05/5-1024x584.png)
如果我们对每个区块的所有 UTXO 集进行硬编码,我们就能够以任何给定的顺序在任何高度验证任何区块。
![This image has an empty alt attribute; its file name is 6-1-1024x588.png](https://blog.bitmex.com/wp-content/uploads/2021/05/6-1-1024x588.png)
区块验证功能可以简化成这样:
![This image has an empty alt attribute; its file name is 7-1-1024x583.png](https://blog.bitmex.com/wp-content/uploads/2021/05/7-1-1024x583.png)
开始 UTXO 集和结束 UTXO 集是块高度为 n 和 n+1 的 UTXO 集。区块数据是我们要验证的高度为 n 的区块的数据。规则是该区块高度的必要连锁规则。新的规则是通过软分叉引入的,所以它们也必须包含在这个函数中。规则包括:Segwit 规则是否被激活,Taproot 规则是否被激活,等等。
对 Utreexo 累加器的需求
在这种类型的区块验证中,需要 Utreexo 累加器 的原因有两个:
- Utreexo 很小。
- Utreexo 消除了磁盘访问。
- Utreexo 很小
失序区块下载理论上是可以做到的,不需要 Utreexo 累加器。然而,由于 UTXO 集的大小超过 4GB,它实际上是不可行的,因为您需要提供大量的 UTXO 集来验证整个区块链。为了验证链上的每个区块,人们需要 8GB 的数据。这很快就会增加(100 个区块需要 800GB),并使其无法硬编码到二进制中。
有了 Utreexo 累加器,这就变得可行了,因为我们可以用几百个字节表示 UTXO 集。这里有一个 json 中实际硬编码的 Utreexo Roots 的例子。
![This image has an empty alt attribute; its file name is 8-1-1024x567.png](https://blog.bitmex.com/wp-content/uploads/2021/05/8-1-1024x567.png)
然后,我们可以修改区块验证函数,用 Utreexo 累加器代替。区块验证函数将看起来像这样:
![This image has an empty alt attribute; its file name is 9-1024x540.png](https://blog.bitmex.com/wp-content/uploads/2021/05/9-1024x540.png)
开始 Utreexo 根 和结束 Utreexo 根 等同于高度为 n 和 n+1 的 UTXO 集。添加 Utreexo 证明是为了能够验证块数据。
2. Utreexo 消除了磁盘访问,以获得更多的 SHA256 哈希值
有了 Utreexo 累加器,我们就能解决块径问题。然而,这并不是 Utreexo 累加器 解决的唯一问题。Utreexo 累加器为更多的 SHA256 散列消除了磁盘访问。这一点极为重要,因为如果没有 Utreexo 累加器,您就会成为磁盘写入/输出的瓶颈。
有了 UTXO 集,交易验证将取决于从磁盘上获取所需的 UTXO。这将是一个微小的随机磁盘访问,我们知道,微小的随机磁盘访问并不快。对于一个区块验证,有许多微小的随机磁盘访问。对于一个并行的区块验证,这些微小的随机磁盘访问的数量将急剧上升,没有任何固态硬盘能够跟上这种需求。
Utreexo 在交易验证期间消除了磁盘访问,以获得更多的 SHA256 哈希值。由于一个区块是一个交易的集合,Utreexo 在区块验证过程中也消除了磁盘访问以获得更多的 SHA256 哈希处理。因此,验证一个区块基本上变成了计算 SHA256 哈希值(包括检查其他共识规则)。区块链只是一系列的区块,所以验证整个区块链不需要磁盘访问,而是需要更多的 SHA256 哈希处理。因此,IBD 过程将导致大量的 SHA256 哈希值被计算。这没关系,因为我们知道如何极快地计算 SHA256 哈希值。
由于这些原因,Utreexo 累加器在平行区块链验证中是必不可少的。Utreexo 累加器同时解决了两个大问题,使平行区块链验证得以完成。
总结
随着时间的推移,区块链中需要验证的数据量会增加。关键是要用软件优化来抵消需要验证的数据的增加,以保持作为进入壁垒的 IBD 最小化。有了 Utreexo 累加器,我们就能做到这一点。随着 Utreexo 累加器的更多优化有待探索,我对未来的研究和 Utreexo 累加器对比特币生态系统的潜力感到非常兴奋。您可以在 github.com/mit-dci/utreexo 加入我们的行动。