Utreexo：基于哈希函数的累加器

作者：Tadge Dryja
来源：https://btctranscripts.com/bitcoin-core-dev-tech/2018-10-08-utxo-accumulators-and-utreexo/
本文为 Tadge Dryja 在 Bitcoin Core Dev Tech 活动上的演讲的记录稿，由 Bryan Bishop 将音频转写为文字。

要是你听过 Benedikt 在两天以前的演讲，你应该能听出来，我们的演讲是有关联的。我们使用了不同的技术构造，但基本的目标是一样的。基本的想法就是 —— 我记得 Cory 在几个月前就在邮件组中讲到了 —— 不在 leveldb 数据库中存储所有的 UTXO，而是存储每一个 UTXO 的哈希值，仅此就可以将数据的体积减少一半；然后，你只需从输入的哈希值就能创建出它，这需要再多 10 字节左右。再然后，你也不必存储每一个 UTXO 的哈希值，你只需存储这些哈希值的一些压缩后的表达形式，然后用证据来传递它们。

在 Benedikt 的演讲中，这样的表达形式是基于 RSA 的累加器，或者可能是 “类群” 这种还完全没有得到验证的东西。我不了解。我在开发的是基于哈希值的累加器。虽说不同的累加器有不同的特性和操作，但一般来说，累加器的基本组成是：可以制作累加器的某种生成器；可以为累加器添加元素的 “添加” 操作，以及一种证明函数。生成器会返回一个累加器；而加操作则以一个已有的累加器和一个元素为输入，输出一个修改后的累加器；此外就是证明函数和验证函数，证明函数的作用是，假如我想证明某个元素存在于某个累加器中，函数会输出一个证据，而验证函数则以这样的证据和一个累加器作为输入，输出布尔值（是或否）。每一种累加器都至少有这三种函数，你需要能够添加、证明和验证。证明会产生证据，而验证则是测试某个证据对某个累加器的有效性。Alice 生成证据，Bob 检查证据的有效性。这就是最基本的构造。有的累加器还有一种证明某个元素不在其中的函数，得出的证据跟前面说的包含性证据不同，证明的是某个元素不在某个累加器中。有时候还会有一种 “删除” 操作，可以从某个累加器中删除某一个元素并返回一个修改后的累加器。

与此相关的第一篇论文提出了单向累加器，就是你可以一直向累加器添加元素，但你没法移除它们，它们会一直在哪里。其它类型的累加器就会有删除和证明非包含的功能。我要讲的这种累加器没有证明非包含的功能 —— 也许会有实现这种函数的办法，但可能会很丑陋。对于 UTXO 集来说，可能也不需要这种函数。

但也有一些理由会让你想拥有这些功能 —— 比如你想替代 leveldb。你准备不存储整个 UTXO 集合，仅存储这个累加器。每当有交易进来的时候，你就从你的累加器中删除一些元素并添加一些元素。每一笔交易的每一个输入，都有一个包含证据，然后你直接验证这个证据就行。这就是我正在思考的模式。它在比特币中可能还有别的应用场景，但我认为这个很酷，而且也会更快实现。

长期来说，累加器也有很好的作用，因为其背后的 UTXO 集的无限增长就没那么可怕了。一般来说，这些累加器和证据要么是固定大小的，要么是对数大小的。RSA 的累加器是固定大小的，我们用的是对数大小的。就算 UTXO 的数量增长到 100 亿个，也没问题。因为它将负担转移到了正确的地方。如果你是一个交易所，你拥有 2000 万个 UTXO，现在每个全节点都要在自己的 chainstate 文件夹中存储它们，但应用累加器之后，压力就转移到了交易所身上：他们要自己保存相关的证据，并向他人证明。

即使做不到这一点，即使只能做到将创建证据的负担转嫁到为每个人工作的节点上 —— 就像今天的节点为所有人都存储整条区块链 —— 依然有一些好处，因为我们为验证者移除了保管整个 UTXO 集的负担。矿工不再需要 UTXO 集，全节点也不再需要，而（创建证据）这样的服务你可以自己做，也可以交给别人来做，它并不对带宽敏感，速度慢也无所谓。每个区块都会有一个证据，从所有交易中组合出来。

不需要共识变更也可以实现，可以是 P2P 的。

关于 RSA 累加器，如果我们不想使用受信任的启动设置，那么它会很慢，它对比特币依然实用吗？我们不确定。也许不实用吧。类群呢？可能也不。我们没有数据，但看起来是不像。

如果你有一种累加器，…… 假设你从头开始，而不是像现在这样有 50 万个区块的历史。从一条新的区块链开始，并暂时忽略 “桥接节点问题” —— 桥接节点问题是说，假如你是第一个使用这个新软件的人，并且你没有完整的 UTXO 集，那么你需要每个输入的证据，但 Bitcoin Core 0.17 客户端并不能给你提供证据，那你就卡住了。你需要一些冷启动的办法。桥接节点是个很大的问题。

假设现在我们可以实现这些操作了，而且每个人都使用它，每个钱包都为自己拥有的每个 UTXO 保存着证据，而且有一种更新证据的办法 …… 这样的办法是添加和删除操作的某种结合，它会修改累加器，只不过，在你修改累加器的时候你可能也想修改证据。因为证据和累加器的状态总是一一对应的。每次变更累加器的时候就改变证据可能会非常昂贵。假设你有一个 UTXO，那么每个区块你可能都要做 5000 次更新证据的操作，以保证这个证据跟上最新状态。如果你有 100 万个 UTXO，这就是 10 亿次操作 …… 每次累加器变更的时候你都需要更新证据。

今天你就可以用上这些东西 —— 不需要跟硬盘交互，一切都在内存中。因为现在还没有几万亿个 UTXO。花一天来同步区块是很糟糕的事。现在的比特币运行得很好，不需要多快的电脑就能运行。但这种累加器技术让你很容易就可以在手机上运行比特币。

全节点可以在验证之后抛弃所有证据吗？可以，就像剪枝模式（pruning）一样。你可以在从头开始同步时创建证据。证据中的数据都是从区块链中计算出来的。所以你可以理解为这是一种优化。

再回过头来谈谈桥接节点的问题。这是一个大问题。桥接节点的意思是，这是一种保存了每一个 UTXO 的钱包。你自己的钱包只保存你自己的 UTXO 的最新状态。但桥接节点会保存所有 UTXO 的证据。它的工作模式大概是：你有一个 Bitcoin Core v0.17 节点，有一个桥节点，然后有一些 utreexo 客户端；这些客户端需要证据，但是 0.17 节点不知道什么是证据，于是把 UTXO 的消息发送个桥节点，桥节点会给每一个输入添加证据，然后广播出去。这是可行的，但效果要视具体情况而定。因为这样的桥节点要维护 6 千万个证据，如果这些证据很大，那可能会非常烦人 …… 当然，我们也可以不维护这样庞大的数据库，只在输入进入节点时再立即把证据重新计算出来。

那么它们要额外存储多少数据？如果使用 RSA 累加器，它可能会让桥节点陷入困境 —— 它可能需要 100 毫秒才能计算出一个证据。得到了证据，桥节点才能允许它进入交易池。你可以自己尝试预测一下这一点的影响。所以 RSA 累加器的桥节点必须保存所有的证据并不断地重复计算。如果使用 RSA，可能会很糟糕 —— 每出现一个区块都要更新很长时间的证据。你可以在服务器集群中分割任务，它是完全可分割的 —— 但可能必须是很大的数据中心才行。RSA 证据在验证的时候是很快的。Scaling Bitcoin 大会上宣布了一些新的进展。有一些技巧可以做到速度很快、体积很小，整个区块或者说整个区块链也只需几千字节。从体积上看效果非常好，但速度还不是很清楚。所以，RSA 累加器给人的感觉就是，它很小巧，但很难生成 …… 我的路线是 utreexo …… 至于 RSA 和类群，更新证据会比较慢，而这恰好是 utreexo（基于哈希函数的累加器）的优势。utreexo 证据也是可以聚合的。

验证 RSA/类群证据很快，只需几纳秒，最多可能是 1 毫秒吧。而 uxtreexo 证据验证起来也挺快的，但不算是非常快。RSA/类群的证据体积是 O(1) （固定的），在现实中就是 1.5 kB；累加器的体积也是 1.5 kB，也是 O(1)；证据也是可以聚合的 …… 更新操作是同时使用添加和删除操作。使用 RSA 累加器，你可以用固定大小的证据证明 100 万个元素的存在。而在 utreexo 中，证据的大小是 O(log(n))；可以做到每个区块只需要几百 kB，但这需要一大堆优化工作。我希望将基于哈希值的累加器的证据体积降下来，这里面有许多的技巧可用。RSA 累加器的体积是固定大小的；utreexo 累加器的体积是 O(log(n))，但在现实中是大约 800 字节。

另一方面的取舍就是信任，或者说安全假设。这也是一个重要的问题。RSA 累加器跟 RSA 算法有类似的重要假设：N = PQ（N 是两个大质数的乘积）是无人知晓的；我不了解类群，所以无法进一步推敲。而 utreexo 的假设是抗碰撞的哈希函数，这是比特币已经在使用的假设，因为比特币也使用了 SHA 算法。还有量子安全性，这就难以定论了。使用 RSA 的时候，你需要一个无人知晓其因数的大质数，对比特币来说这基本上不是一个好的假设。

但是，这些东西你都可以做，不必动用分叉。我正在运行一个测试节点和测试桥节点，无人知晓，这挺好的 …… 你可以实现一个类似于 electrum 的东西，产生地址索引，然后你可以把它变成一个需要证据的客户端；然后你再实现一个提供证据的服务端。但更好的模型是把它做进客户端里面，让这些客户端可以点对点地传播这些证据。但你可以不管这些，直接开始测试，这很棒。

优化基于哈希函数的累加器的证据体积的主要办法就是 …… 基于哈希函数的累加器的基本原理是，使用默克尔树来表示状态，UTXO 就是这些默克尔树的叶子；你可以删除其中任意的元素，然后重新洗牌，以保持完美的树形态（perfect trees）。我后面会讲得详细一些。总的来说，每个元素都需要一个证据，证据的大小跟树的高度相关。如果你要证明两个表亲，也即它们的默克尔路径有交集，那你就可以省去一些重复的证据数据。同时，每次新区块出现，默克尔树都不会全部改变，只有少数默克尔树会变化。

当你要运行初始化区块下载时，你连接到的全节点拥有全部区块，所以它知道你的节点的状态将发生怎样的变化，如果他们愿意帮助你，你可以大大加快同步速度。比如，他们可以告诉你，你现在添加的 UTXO 在下一个区块中会被删除，所以请把它留在内存里，这样你就不必缓存它或做其它操作；默克尔树的某一部分会在接下来的 5 年里保持不变，所以你可以从内存中删除它们，我稍后会为你证明它们。他们还可以帮助你清理 leveldb 的缓存。这可以降低证据的体积。

那么 800 字节的累加器体积是怎么来的呢？这是因为你存储了各个子树的根值。我来讲讲这种基于哈希的累加器的构造吧。你有一片默克尔树的森林 —— 它们都是完美的树，叶子的数量总是 2 的幂。当你完全使用二叉树来表示所有的 UTXO 时，就会出现一些有趣的比特位移技巧，所以这 15 个元素就可以表示成 0b1111。如果我要删除两个元素的话，我最终会把这一位改成 0，然后这个子树就消失了，这很酷。添加操作也很简单，你只要把元素放在一边，然后重新计算出树即可。如果我要在树的末尾添加什么元素，我是不知道树里面有什么的，因为我只存储了树的根值，但我可以计算出最后一个元素的父节点，并且一路向上重新计算，为整个状态计算出一个哈希值。

假如你删除了某个元素，这个元素相邻的叶子就会变成 “孤儿”。那么该孤儿就会从树的末端弹出，（树会因此分裂），有很多东西会因此移动到树的末端，你会把它们打成 4 棵子树，就像前面一样。元素的证据本身跟该元素的邻居及其所在的子树相关，如果你要删除一个元素，证据中列出的这些哈希值就会变成新的（因为删除元素、树分裂而产生的）四棵子树的根值。这些证据是可以聚合的，所以，如果你要一次性删除许多元素 …… 这个功能还在开发中，但确实是可以做到的 …… 你要做的第一件事情就是找出同时被删除的兄弟的位置 —— 你有一个被删除的元素的列表，然后你找出其中同时被删除的兄弟叶子，然后你就可以删除父叶子。要是删除的次数是单数次，会留下孤儿，你可以把这些兄弟换到别的子树上去。保证较旧的元素放在左边、较新的元素放在右边，因为更新的元素更有可能先被花费，这样一来其证据的体积会小一些。

（译者注：Utreexo 对 UTXO 集的表示不是单一的一棵默克尔树，而是二叉默克尔树所构成的森林；这是为了适应 UTXO 会被删除的特点。其基本操作是这样的：每当添加一个元素（叶子），该叶子要么自成一棵树，要么加入另一棵单叶子的树，形成两层的默克尔树；这样的合并操作会一直持续，直至无法再合并；每当删除一个叶子时，该叶子所在的树也沿着该叶子的默克尔路径分裂，并导致树高降低。这样的操作使得森林中的每一棵树都是 “完美的树”，即叶子数量为 2 的幂的树；同时，在删除一个叶子时，为该叶子提供的存在性证据，就是删除叶子之后节点所需存储的树根；同时，因为邻居被删除而孤立成树的叶子，也可以在新叶子加入后重新跟原来的表亲合并，这些表亲所在的子树不必重新计算。）

对于非桥节点来说，这种累加器是非常快而且容易使用的。就是对许多的分支作大量哈希计算而已。你面临的主要麻烦，或者说主要的牺牲，就是内存和带宽。如果你要检查很多区块 —— 比如你要执行初始化区块下载，你连接到的全节点和告诉你哪个 UTXO 将在什么时候被花费，那么你可以把所有东西都长期放在内存里，也就是把所有接下来要花的 UTXO 都放在内存里。…… 要是你保存了所有东西，那么你就完全不需要下载任何证据，所以证据的总体积就成了零。但如果你完全不使用内存，每个区块都需要下载新的证据，那么最终你将需要多下载 160 GB 的数据，而区块链数据的体积本身只有 200 GB 。我觉得这里的权衡曲线实在是太陡峭了。我还没有搞清楚所有东西，但直觉上来说，要是你存储了所有东西，你就永远不需要下载。这条曲线太陡峭了，而且，因为许多 UTXO 很快就会被花掉 …… 如果你有几百 MB 的内存，那么你可以在初始化区块下载期间临时存储许多证据。从空间上来看，RSA 累加器极为高效，因为它总是 1.5 kB。

那么，我们能不能把这些累加器做成软分叉呢？反正我们喜欢软分叉，而且也很容易实现不是吗？我们可不可以把这种累加器的根值或者 RSA 累加器自身放进 coinbase 交易的一个 OP_RETURN 输出中，这样别人就完全不需要验证任何东西了，可以相信矿工会验证一切。也许我们可以将一个区块所有的证据都放在一个 OP_RETURN 输出中，而且你也知道它为什么很重要 …… 因为它需要 DoS 抗性。现在，无论我什么时候验证区块，我都会先执行 PoW 检查，这很便宜，而且如果 PoW 检查都不通过，我就不必继续执行验证了。因为所有进入我的验证函数的数据，都是由 PoW 承诺的，要是某人在 P2P 网络中传播数据时做了手脚，那么 PoW 就会失效，我也不必费心了。另一方面，如果一个块能通过 PoW 检查，但依然是无效的，我可以把它标记成永久无效的区块 —— 因为无效的是区块本身，而不是围绕它的辅助数据。这样我也不会重复检查同一个区块两次。如果你所在的网络要求辅助数据有效、区块才有效，那么你就无法区块是块无效还是辅助数据无效。（如果没有这样的设计）这（辅助数据）就会产生一种 DoS 攻击向量。比如，你得到了一个区块，其中的证据是修改过的，这时候你没法追究，你可以断开给你这个区块的节点，但你不知道这个区块从一开始就是无效的，还是这个节点正在攻击你。要是我们不能推动这个软分叉，那么在现实中，就会遇上问题。

……

能不能承诺累加器的状态，而不是完整的状态？不行，因为这会鼓励人们不验证。人们已经讨论 UTXO 承诺很长时间了 …… 如果你在区块中承诺 UTXO 集，那么它可以帮助人们了解正确的 UTXO 集，然后也可以下载这样的集合。只要你添加了这个，未来就会这么发生。你可以设想一个非常强大的版本，你可以在区块高度 50 0000 处硬编码说这就是 UTXO 集的哈希值，前面的你都不必看了，从这一点开始验证吧。这是一把双刃剑：它很酷，也有应用场景，比如先在我的笔记本上同步、完全验证所有东西，然后扫描一下我的手机上的客户端显示的一个 QR 码，然后我的手机就将获得状态。但有些人可能会去 blockchain.info 上下载累加器状态。

假设我们找出了一种让类群变得非常高效的办法？不幸的是，这是一种全新的密码学假设。人们已经假设了这是一个很难的问题，而且已经很长时间（快 200 年了），而且从未用在任何实际上的协议中。所以，我们应该不会让它进入共识。但如果你信任它，想建立一个基于它的 P2P 网络，那也没什么不可以。或者，甚至于，如果我们先发明了一种很棒的基于哈希函数的累加器，但一两年后有人发明了更好的东西，有 10 倍的效率提升，但我们已经用软分叉引入了前者，那么我们就会在前者上止步不前。我猜我们最后会实现一次基于激活日期的软分叉，但说这些还为时尚早。我也说不好。这是一种也许可以让事情加速的办法。客户端可以自己选择，比如保持原来的不使用 UTXO 集承诺的模式。但如果你想移除矿工维护 UTXO 集的需要（就需要这样的软分叉）。（而且有了这样的累加器）全节点也会变得更加便宜。

如果你使用一种证据会过时的累加器，即使不是所有证据都会过时、仅仅是大部分证据会过时，也意味着你需要看到完整的区块才能更新你的证据，这就完全排除轻客户端利用这种技术的可能性。轻客户端需要依赖于他人的服务才能更新证据。我认为，可以合理设想我们会拥有一个可以提供这样的服务的生态系统。所以我认为，桥节点将是必需的。

Electrum 服务端软件可以提供地址索引和 SPV 证据，而在累加器模式中，它也会是一个桥节点。在基于哈希函数的模式中，桥节点会比地址索引更小、更易于运行。而在 RSA 模式中，它虽然体积小，但计算强度很高。

如果没有桥节点，那么在 SPV 模式中，你依然可以不验证，但依然要做很多工作来保证你的 UTXO 证据是有效的。这依然会提高那些拥有许多 UTXO 的人的代价。但这样会让这项技术对那些本来就想阻止它的人变得又慢又讨厌，比如使用 SPV 模式的人和拥有一大堆 UTXO 的人。

在基于哈希函数的累加器中，桥节点没有额外的 CPU 工作，因为你要执行的不过是哈希运算 …… 在桥节点中，你要存储完整的树，而不仅仅是根节点；也就是说，这些哈希运算原本就少不了，只不过现在你要把所有中间哈希值都保存在硬盘里。需要更多的硬盘读写，只不过非桥节点就可以在整体上存储更少的数据。在基于哈希函数的累加器模式中，桥节点不需要执行更多的 CPU 计算，只需要更多的硬盘读写。

哈希累加器下的桥节点的运行速度 ……。我所有的软件都是单核的，也没有专门优化过，但还是相当快。是用 golang 语言写的。我写好了，但没有实现 P2P 层，主要是为了获得基准测试结果，所以没有做硬盘读写优化，这也没啥。只要你的带宽够，可以用到 100% 的 CPU，但现在它只用了 10%。我不知道它有多小众。人们为什么要运行全节点？我不知道。

在小型硬件环境（比如硬件安全模块）中证明 UTXO 的存在性，可能是非常有用的。这种模块允许你完全私密地运行计算。主机作为桥节点，这个模块传出证据。

另一个可能的特性是 libconsensus —— 实现一种函数，以区块链的完整状态作为输入，然后判定这个状态是否有效。用了累加器，这样的函数就更容易实现了。语句是这里有一个区块，这是完整的状态，然后返回一个布尔值和一个新的状态。这是人们一直想实现的东西，而累加器技术可以帮助你实现它。可能会有所帮助。

我正在撰写一篇论文，尝试论证其合理性。我也在用 golang 写代码。看起来很用去，从长期来看，应该是一种更好的模式。

不必携带巨大的状态来参与验证，我们也许就能做到更加优雅。想要更大的区块？Utreexo 可能也会帮上忙。我知道 BCash 那些人不喜欢我，因为我是闪电网络概念的提出者，但也许他们会喜欢 Utreexo（哈哈哈哈）。

你不能在门罗币中实现有序的插入，因为你需要证明一笔花费不包含在花费集合中。你可以有一个花费交易的输出集 …… 但你不知道花费是什么样的。所以它（utreexo）不能用在门罗币上。

后续进展

http://diyhpl.us/wiki/transcripts/mit-bitcoin-expo-2019/utreexo/

https://github.com/mit-dci/utreexo

其它类型的 UTXO 集承诺

（完）