💻 computer science

MHOT: Height-Optimized Authenticated Data Structure for Blockchain State Commitment

本文提出了 \textsc{Mhot}，一种高度优化的认证数据结构，它通过判别式位索引（discriminative bit indexing）和分层证明来取代以太坊的默克尔帕特里夏树（Merkle Patricia Trie），旨在实现最小化树高、大幅提升吞吐量和证明大小，并在无需可信设置的情况下提供针对 Nurgle 攻击的强健抵抗力。

原作者： Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

发布于 2026-06-11

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Sipeng Xie, Qianhong Wu, Minghang Li, Qiyuan Gao, Bo Qin, Qin Wang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，区块链就像一座巨大的、全球性的图书馆，每一本书（交易）都在改变整座建筑的状态。为了证明这座图书馆的组织架构是正确的，管理员（验证者）必须检查一个巨大的数字“目录表”，这个目录表被称为状态根（State Root）。

目前，以太坊区块链使用一种称为**默克尔-帕特里夏树（Merkle Patricia Trie, MPT）**的系统。你可以把它想象成一个文件柜，每个抽屉都贴有特定的前缀标签（比如“A”、“B”、“C”）。如果你想找一个文件，就沿着这些字母寻找。但问题在于：如果有人添加了一个与现有文件共享很长且单调的前缀的新文件（比如“A-B-C-D-E-F...”），系统就必须拆分抽屉，增加更多的隔板，从而使通往该文件的路径变得更长。

这就是**“纳格尔攻击”（Nurgle Attack）**。这就像是一个恶作剧的小淘气，他完全了解文件柜的工作原理。他可以通过大量投放具有长前缀的文件来冲击系统，迫使管理员为了存储仅仅几个新项目，就不得不建造一座高耸且不稳定的抽屉塔。这减慢了整个图书馆的速度，并消耗了巨额的能量（Gas）来维护，尽管这个淘气鬼付出的代价几乎为零。

新的解决方案：MHOT（“智能型”文件管理系统）

作者引入了 MHOT，这是一种全新的数据组织方式，它在不需要任何神奇的新数学理论或信任第三方的情况下修复了上述问题。

以下是 MHOT 的工作原理，我们使用简单的类比来解释：

1. 停止追踪前缀，开始寻找差异

旧系统（MPT）观察名字的前几个字母，然后说：“啊，这属于‘A’类箱子。” 如果两个名字都以“Alex”开头，它们会被放入同一个箱子，即使一个是“Alex”而另一个是“Alexander”。

MHOT 则更聪明。它会问：“这些名字究竟在哪里产生了差异？”

如果你有“Alex”和“Alexander”，MHOT 不在乎共同的“Alex”。它寻找的是它们发生分歧的第一个字母（即“n”与“a”的区别）。
它构建了一个“复合节点”（一个超级抽屉），这个抽屉通过使它们变得独特的精确比特位来同时容纳许多项目。
结果： 无论你添加多少个相似的名字，抽屉塔都不会变得更高。它保持着矮小且稳定，因为它只在必须的时候才会拆分，而不是仅仅因为前缀相同就拆分。

2. “双层”收据（层级证明）

在旧系统中，当你想要证明一个文件存在时，管理员必须递给你一张收据，列出你经过的每一个抽屉里的所有兄弟文件。如果一个抽屉里装有 32 个文件，这张收据就会变得又大又重。

MHOT 使用了双层收据：

第一层： 图书馆的主体结构。
第二层： 在每个超级抽屉内部，文件被排列在它们各自微小的、迷你树结构中。
神奇之处： MHOT 不再需要列出全部 32 个兄弟文件，它只需要列出迷你树中的几个“兄弟”哈希值（就像一个对数级的快捷方式）。
结果： 证明（收据）变得更小、更轻，使得轻量级设备（如手机）能够更快地进行验证。

3. “批量”交付卡车（批量提交）

在旧系统中，每当你放入一个单一文件时，管理员都必须重新计算从该抽屉一直到顶层屋顶的所有抽屉的哈希值（数字指纹）。这就像是每寄一封信，都要专门开车去一趟邮局。

MHOT 使用了批量流水线：

它收集一段时间内所有的变更。
它并行计算指纹（就像有一支团队在同时处理不同楼层的哈希运算）。
它只在最后将更新后的最终状态一次性写入硬盘。
结果： 图书馆处理更新的速度快了 9 倍，且写入磁盘的数据量减少了 4 倍。

为什么这很重要（研究结果）

论文将 MHOT 与当前的以太坊系统以及其他一些实验性系统进行了对比测试：

速度： MHOT 写入新数据的速度快了高达 9 倍。
效率： 它浪费的存储空间（写放大）减少了 4 倍。
证明大小： “收据”变得更小了 2 倍，使得轻量级设备（如手机）更容易验证区块链。
安全性： 当“纳格尔”淘气鬼试图通过大量投放相似键值来破坏系统时，MHOT 完全阻断了攻击（成功率为 0%）。而旧系统在攻击下崩溃了（攻击者的成功率高达 99.97%）。

核心结论

本文认为，我们不需要复杂的、全新的密码学魔法（如可信设置或高深数学）来解决区块链的扩展问题。相反，我们只需要一个更好的数据结构。通过基于事物实际产生差异的地方而非它们所共享的部分来组织数据，并利用智能的“双层”收据，MHOT 让区块链变得更快、更便宜，并且能够免疫这种困扰了多年之久的特定类型攻击。

这提醒了我们：有时候，最好的解决方案并不是一种新的超级武器，而是一种更聪明的整理文件柜的方式。

技术摘要：MHOT —— 用于区块链状态提交的高度优化认证数据结构

1. 问题陈述

在现代区块链系统（尤其是以太坊）中，状态根（state root）计算消耗了大约 70–80% 的总区块处理时间。当前的规范认证数据结构（ADS）—— Merkle Patricia Trie (MPT) 存在两个关键局限性：

对 Nurgle 攻击的结构性脆弱性： MPT 使用固定前缀索引，其中每个树层级消耗固定数量的连续键位（key bits）。这种结构允许攻击者利用长公共前缀（通过哈希碰撞）来人为地增加路径深度。所谓的“Nurgle 攻击”（S&P '24）展示了攻击者如何以极低的 Gas 成本，通过迫使 Trie 将压缩路径展开为更深的结构，从而降低系统性能并增加 I/O 开销。
跨度–证明权衡（Span–Proof Trade-off）： 为了缓解深度增长，人们可能会增加“跨度”（即每层消耗的位数）。然而，在基于前缀的 Trie 中，增加跨度会呈指数级增加“扇出”（fanout，即子节点槽位的数量， $2^{span}$ ）。这导致了一个权衡：高跨度虽然限制了高度，但会使节点大小和证明大小呈指数级膨胀；低跨度虽然能保持证明紧凑，却会让树容易受到深度增加攻击的影响。

现有的替代方案（如 Verkle Tries 或 LVMT）通过向量承诺（代数技术）将证明大小与扇出解耦。然而，这些方案需要可信设置仪式（trusted setup ceremonies），引入了更高的算术验证成本，并且通常缺乏对状态同步至关重要的范围证明（range proofs）的原生支持。

2. 方法论：MHOT

作者提出了 MHOT（高度优化认证数据结构），这是一种持久化的、基于哈希的 ADS，它在无需可信设置或特殊密码学手段的情况下实现了高度最优性。MHOT 通过四个关键机制将 高度优化 Trie (HOT) 结构适配到区块链状态提交中：

A. 判别位索引（结构基础）

与消耗固定连续前缀的 MPT 不同，MHOT 基于**判别位（discriminative bits）**进行分支。判别位是指子树中至少有两个键存在差异的位置。

线性耦合： 这种方法使跨度（span）与扇出（fanout）呈线性耦合而非指数耦合。一个具有 $k$ 个扇出的复合节点最多消耗 $k-1$ 个判别位，而一个具有相同扇出的基于前缀的节点则需要 $\log_2 k$ 个连续位。
自适应跨度： 节点根据实际的键分布进行调整。密集区域使用较少的位数；稀疏区域使用较多的位数。这确保了对于任何给定的键集，都能实现可证明的最小树高。
Nurgle 抗性： 由于结构是由实际的键差异而非固定前缀决定的，因此通过内部重构（例如：叶子下推、父节点上拉）进行的对抗性插入可以被吸收，而不会必然增加全局树高。

B. 分层证明（证明优化）

直接对复合节点中的 $k$ 个子节点进行哈希会导致 $O(k)$ 的证明开项。MHOT 引入了两层 Merkle 构造：

层间层（Inter-node Layer）： 连接复合节点。
层内层（Intra-node Layer）： 每个复合节点在其 $k$ 个子节点之上维护一个内部二进制 Merkle 树。

结果： 证明某个子节点的成员身份仅需内部树中的 $O(\log k)$ 个兄弟哈希，从而将证明大小从相对于扇出的线性关系降低为对数关系。这打破了证明大小与跨度的线性依赖。

C. 内容寻址持久化

为了支持区块链状态提交，MHOT 修改了原始的内存中 HOT 设计：

确定性标识符： 节点通过其序列化内容的哈希进行标识（内容寻址），确保了结构确定性（相同的键集产生相同的树）以及信任最小化。
写时复制（CoW）： 修改操作会创建新节点并使祖先哈希失效，这与区块链的状态语义保持一致。

D. 批量提交流水线

为了处理重新计算路径的计算成本：

延迟哈希： 哈希计算被延迟到区块提交阶段。节点在交易阶段使用临时 ID。
高度分层并行化： 在提交时，节点按高度（从叶子到根）进行分批最终化。由于同一高度的节点之间没有数据依赖，哈希计算可以高效地并行化。
LSM-Tree 友好的布局： 存储键由区块版本和高度前缀组成，从而实现顺序批量写入和高效的压缩。

3. 核心贡献

识别了跨度–证明耦合： 论文指出，在基于前缀的 Trie 中，跨度与扇出之间的指数耦合是无法同时保证有界最坏情况高度和紧凑证明的根本原因。
MHOT 实例化： 将 HOT 适配于区块链用途，提供了一种通过判别位跟踪和高扇出复合节点来抵御对抗性键分布的、高度优化的 ADS，且仅使用标准哈希承诺。
分层证明： 提出了一种新型的两层 Merke 构造，将每个节点的证明开销从 $O(k)$ 降低到 $O(\log k)$ ，从而实现即使在高扇出下也能保持紧凑的证明。
持久化 HOT： 通过引入内容寻址索引和并行提交流水线，解决了 HOT 在磁盘部署上的开放性问题。
全面评估： 在以太坊主网工作负载下对 MHOT 与 MPT、RainBlock 和 LVMT 进行了基准测试。

4. 实验结果

在以太坊主网工作负载（区块 13.5M–13.51M）和合成数据集上进行的评估显示：

吞吐量： MHOT 的写入吞吐量比 MPT 高出达 9 倍（在 10 万个键时，26 万 ops/s 对比 2.9 万 ops/s），并显著超越了 LVMT 和 RainBlock。
写放大： 由于采用了批量刷新和减少了树深，MHOT 的写放大比 MPT 降低了 4 倍（0.9–1.6 对比 2.7–4.8）。
证明大小： 由于采用了分层证明结构，MHOT 的证明比 MPT 小 2 倍（1.1–1.4 KB 对比 2.3–2.9 KB）。
Nurgle 攻击抗性： 在对抗者控制整个区块 Gas 预算（约 15,000 次插入）的最坏情况下：
- MPT： 增加目标键深度的成功率为 99.97%。
- MHOT： 成功率为 0%。该结构通过内部重构吸收了碰撞，而没有传播深度增加。
验证延迟： MHOT 的验证操作在微秒级（与 MPT 相当），而依赖于 KZG 配对的 LVMT 则会产生毫秒级的延迟（慢 3–4 个数量级）。

5. 重要性与主张

论文认为，高度最优性（而非引入新的密码学原语）才是实现可扩展且具攻击韧性的区块链状态提交的关键抽象。

结构性方案 vs 密码学方案： MHOT 证明了可以通过判别位索引这一结构化手段，解决树高、证明大小和攻击抗性之间的权衡，从而避免了向量承诺方案（Verkle, LVMT）带来的信任假设和高昂的验证成本。
即时部署性： 通过仅依赖标准哈希函数（Keccak-256 或 Blake3）和现有的 Merkle 认证原则，MHOT 提供了一条在无需为了可信设置仪式或代数验证变更而进行硬分叉的情况下，提升性能和安全性的路径。
韧性： 结果表明，优化数据结构的高度和自适应性足以中和 Nurgle 攻击向量，而此前该攻击似乎需要通过经济或密码学手段来应对。

作者总结道，精心的数据结构设计可以从根本上改善区块链状态提交的扩展性和鲁棒性，为当前的 MPT 标准提供了一个实用的替代方案。