使用Merklix 树对UTXO集做检查点

在上一篇文章中，我介绍了Merkle tree作为一种描述无序集合或图的加密方法。这样可以证明一个元素在o(ln(n))的数据结构中包含或者不存在，尚力财经小编2022并利用这些证明来改变结构，即使它并不知道它的全部内容。

我现在将解释如何使用它来帮助处理像比特币这样的区块链技术中的UTXO集合。

在进入UTXO部分之前，我们先来演示一下如何用一棵Merklix树来证明一个集合中元素的存在或不存在。

在这个例子中，我们试图证明Item1在集合中。我们通过提供Item1或者它的hash 6 EEC来解释，因为我们不想显示Item1或者只是想让证明更简洁，它们在图中用红色标出。

然后我们提供一个路径到树的根。这条路径在图中用黄色标出。为了验证证明，6eec和3738的哈希得到bf1b，它用d9fe哈希自己得到2812，树的根。我们证明了元素确实在树中。

现在假设我们要证明Item5不在树中。它的hash是cd5a，其中c=1100。

相同，证明是从黄色元素中获得的。通过将bf1b和d9fe散列在一起，可以验证它们都是树的一部分，并且它们处于相同的级别。Bf1b以从0开始的所有元素为其子元素，d9fe是从111开始的元素。因此，Item5不能是这些子树中的任何一个。但是，如果它在树中，它将在这两个节点之间。因为这两个节点在同一层次，我们都知道它们之间没有任何东西，所以我们可以断定Item5不在集合中。使用Merklix proof更新树

因为树中的路径是由proof提供的，所以它也可以用来修改树本身。同样，这项工作不需要预先知道到根节点的路径。现在我们已经证明了Item5不在树中，但是也许我们要添加它？

树中的新节点用红色表示。图中的黄色部分表示校样中的块。如您所见，一旦插入了Item5，就可以仅使用证据中的散列来计算树的根节点。

我们还证明了Item1在集合中。还是删了吧。

尚力财经小编2022

同样，需要计算的删除结果的唯一散列要么包含在证明中，要么在插入Item5时计算。

从这一点我们可以得出结论，如果k ^ n，我们可以在o(k * ln(n))中的n个元素的Merklix树中保持一组k的变化，当k变大时趋于o(k)。变更集在图中以红色显示。用Merklix树生成关于UTXO集的证明

你可以用txid作为key(译者注：这里原来的key是“key”，我不确定这个翻译好不好)和一些不使用output的序列化值可以用Merklix树表示UTXO集。为了简单起见，在上面的例子中，我一直使用散列值作为键，但是没有这样的义务。我不会深入探讨未使用的输出是如何序列化的，知道这些就足以理解这个概念了。

通过网络发送交易时，也可以发送UTXO集合中输入的证书。这将允许接受事务和认证的节点避免查询它们的UTXO集合，这可能是一个缓慢的过程，特别是如果集合很大并且需要在磁盘上。

此外，这使节点能够删除UTXO集的一部分。他们可以使用存在证明来更新他们的UTXO集，包括被修剪的部分。如果一个事务没有证明，您可以向这部分未调整的UTXO集合中的另一个节点请求证明。如果证明显示输入在UTXO集合中，则可以在其他方面进行检查，如果这是有效的，则可以将事务转发到其他节点。 如果证据显示不存在，则交易被拒绝为无效。

一般认为网络上的节点不应该互相信任。如果不构成证明，这就不是问题。节点不能说谎。更糟糕的是，一个节点可以拒绝应答，在这种情况下，请求可以被转发到另一个节点。

因此，实际上需要查询其UTXO集的节点非常少，工作负载可以分布在很多节点上。这将是比特币区块链中第一个横向扩展的例子。通过这样的措尚力财经小编2022施，UTXO集合可以疯狂地增长到一个很大的规模，只需要一个节点子集就可以处理它的每个片段。子集中的节点负责自己对片段子集的请求。

例如，大约5000个节点，可以划分64条UTXO路径，每段大约有78个节点。

即使我们认为这些节点中有一半是不可信的，不会回答请求，每个片段也留下39个节点。

能有效降低每个节点的存储需求64，减少UTXO检查工作量2500。从绝对数量上来说，一个1.5Gb的UTXO集每个节点需要24Mb左右的内存，一个block只需要检查一小部分UTXO，这样网络就可以处理当前的工作负载。

如果节点采用智能策略，例如在内存中保持高速货币周转率，原文为：Suck as keep in memory high velocity money and commit to disk and pruning from memory a synchronous saving，提交的磁盘不从异步内存保存中切出，网络作为一个整体可以实现极高吞吐量的UTXO请求，例如，UTXO集允许增长几个数量级而不会形成大问题。？块

中UTXO集的检查点虽然一个节点可以通过遍历整个区块链的历史来重构UTXO集，但这意味着一个新节点的自启动时间是o(n*t)，其中n是事务量，t是时间。随着时间的推移，这只会变得更糟。如果一个节点可以获得根哈希的UTXO集，那么这个节点可以很快变得有效。

这可以通过把它放在coinbase事务中作为软fork来实现，但是最好把它放在块头中作为硬fork。这样，只要有一个节点连接上，就可以在网络上开始验证，并将已知有效块的验证反向，作为网络进程转发。[x]

标签： 2022 比特币