比特币中为无状态客户端优化的默克尔树

# 比特币中为无状态客户端优化的默克尔树 ## 1. 引言 比特币和其他加密货币是点对点系统，旨在维护有序的交易账本。节点通过区块链协议就账本状态达成共识，而系统状态主要由未花费交易输出（UTXOs）集合构成。每笔交易（除创币交易外）会花费一些 UTXOs 并生成新的 UTXOs，系统状态会在每个区块后更新。 然而，加密货币系统的状态规模可能非常大，例如比特币目前约有 7000 万个 UTXOs，存储需要约 4GB 空间，且还会不断增长，这成为加密货币可扩展性的主要问题。无状态加密货币系统，基于密码学累加器方案，是解决该问题的一个有前景的方案。 无状态客户端只需存储累加器（状态的紧凑表示），当获得特定 UTXO 的证明时，就能验证该 UTXO 是否属于系统状态，而计算能力有限的攻击者无法为不属于状态的 UTXO 生成证明。 密码学累加器可看作哈希函数的泛化，它不仅能提供一组值的紧凑表示，还能为集合中的元素生成短证明。动态累加器支持集合元素的添加和删除，对于实现无状态加密货币至关重要。 本文研究基于默克尔树的累加器方案在比特币无状态客户端中的设计。默克尔树通常是二叉树，节点包含指向子节点的哈希指针，叶节点指向 UTXOs，根节点的哈希值就是累加器，无状态节点存储该值。UTXO 集合的任何变化都会反映在累加器中，UTXO 的证明由从对应叶节点到根节点的树节点分支组成。 使用默克尔树作为累加器的想法由来已久，UTREEXO 项目将其应用于实际比特币数据。该系统由桥接服务器和无状态客户端组成，桥接服务器存储完整的默克尔树，无状态客户端存储少量树节点的哈希值。每个新块到来时，桥接服务器为无状态客户端提供所需的子树，以证明该块中交易消耗的 UTXOs 属于系统状态。UTREEXO 的设计使证明大小在实际应用中可行，但理论上默克尔树的证明大小可能很大，因此最小化每个块所需的平均证明大小是无状态加密货币系统的重要指标。 ### 1.1 我们的贡献 本文探索通过改变默克尔树的构造，进一步减少无状态比特币系统所需的证明大小。影响批量证明大小的因素主要有两个： - **默克尔树的高度**：具有 n 个元素的平衡（二叉）树高度为 Θ(log n)，k 个元素的总证明大小为 O(k log n)，UTREEXO 设计保持树的平衡。 - **批量证明所需 UTXOs 的位置**：多个元素的证明可能有重叠的树节点，在为单个块提供的证明数据中无需重复这些节点。如果所需证明的叶节点在树中位置相邻，批量证明大小将最小化。 虽然可以设计出确定平衡的默克尔树，但难以保证将一起花费的 UTXOs 放在相邻位置。因为新 UTXO 添加到树中后，可能在未来任何时间被花费，所以证明 n 个 UTXOs 中 k 个的最坏情况证明大小不能优于 Θ(k log n)。本文的主要见解是，分析平均情况证明大小而非最坏情况证明大小，能构建在实际中表现更好的系统。 比特币数据的实证分析表明，大多数 UTXOs 的生命周期非常短，即一个块中花费的大部分 UTXOs 可能是最近添加的。通过按 UTXOs 进入系统的顺序排列默克尔树中的 UTXOs，很可能使大部分被花费的 UTXOs 相邻，从而显著减少平均批量证明大小。 具体贡献如下： - **理论模型**：开发一个概率模型，其中 UTXOs 的生命周期遵循指数为 α 的幂律分布。在该模型下，证明每个块所需的批量证明大小为 O(d + kα)，其中 d 是树的深度，k 是每个块添加的 UTXOs 数量。 - **系统实现**：基于开源的 UTREEXO 项目，用 Go 语言实现了一个系统。具体实现了一个默克尔前缀树（Merkle Trie），其中 UTXOs 按进入系统的顺序存储。实验表明，该设计在每个块所需的平均证明大小方面显著优于 UTREEXO。 下面通过一个简单的 mermaid 流程图展示默克尔树验证 UTXO 的基本流程： ```mermaid graph TD; A[无状态客户端] --> B[获取默克尔树的根哈希值]; B --> C[获取特定 UTXO 的证明]; C --> D[验证证明路径]; D --> E{证明是否有效}; E -- 是 --> F[UTXO 属于系统状态]; E -- 否 --> G[UTXO 不属于系统状态]; ``` ### 1.2 相关工作 无状态加密货币的概念起源于 bitcointalk.org 论坛，Miller 首次提出使用红黑默克尔树作为比特币状态的累加器。 本文主要与 UTREEXO 项目进行比较，UTREEXO 考虑了一些本文未涉及的技术，如客户端缓存默克尔树数据以减少证明大小，以及在叶节点中包含块哈希以增强抗碰撞攻击能力。 除了基于默克尔树的累加器，还有其他形式的密码学累加器： - **非哈希基于累加器**：包括隐藏阶群累加器，依赖 RSA 假设或未知阶群。这类累加器在多个方面取得了进展，但许多构造需要可信设置。 - **基于双线性曲线配对的累加器**：证明大小非常小，但也依赖可信