哈希之叶 - The Trail of Bits 博客

Trail of Bits 发布了 Indurative，这是一个密码学库，能够认证多种数据结构，而无需用户编写大量代码。Indurative 可用于从数据完整性到无信任分布式系统的各种场景。例如，开发者可以使用 Indurative 在仅八行代码内为包管理器添加二进制透明度——以便用户验证下载的二进制文件的真实性。

在底层，Indurative 使用 Haskell 的新 DerivingVia 语言扩展，自动将实例化 FoldableWithIndex 的类型映射到稀疏 Merkle 树表示，然后使用这些表示创建和验证包含（或排除）证明。如果您理解这意味着什么，恭喜您，可以下载 Indurative 并开始使用。如果不理解，那么您很幸运！博客的其余部分就是为您编写的。

“那看起来像棵树，我们就叫它树吧”

1979年，Ralph Merkle 申请了一项基于哈希的签名方案的专利。该专利引入了几个新颖的想法，或许最值得注意的是“认证树”，即现在众所周知的 Merkle 树。这种数据结构现在几乎肯定是 Merkle 最著名的作品，即使它在发布的专利中几乎是附带的，因为它极大地提高了各种密码学问题的效率。

基于哈希的签名需要一个“承诺方案”，其中一方发送对未来消息的承诺，使得 i) 只有一条消息可以满足承诺，ii) 给定消息，很容易检查是否满足承诺，iii) 承诺不会泄露消息内容。承诺方案从 Twitter 到多方计算无处不在。

通常，承诺只是消息的哈希（或“摘要”）。任何人都可以哈希消息并查看是否等于承诺。找到具有相同哈希的不同消息是一件大事。但这对于 Merkle 的方案不太适用：他想要承诺一整套不同的消息，然后提供包含证明，证明某个消息在集合中，而不揭示整个集合。为此，他想出了这种数据结构：

一个二进制哈希树的例子。哈希 0-0 和 0-1 分别是数据块 L1 和 L2 的哈希值，哈希 0 是哈希 0-0 和 0-1 串联的哈希（图片和说明来自 Wikimedia）

想象一个二叉树，每个节点都有一个关联的哈希。叶子节点各自与集合中消息的哈希关联。每个分支节点与其子节点哈希串联的哈希关联。在这个方案中，我们可以只发布顶部哈希作为承诺。为了证明某个消息包含在集合中，我们从与其哈希关联的叶子开始，向上遍历树。每次向上走到分支节点时，我们记录进入的方向和该分支另一侧节点的哈希。然后，我们可以通过在每个步骤重新进行串联和哈希来检查证明，并确保结果等于我们之前的承诺。

通过例子更容易理解。在上图中，为了证明 L3 的包含，我们的证明包括 [(Left, Hash 1-1), (Right, Hash 0)]，因为我们从左侧进入 Hash 1，另一侧是 Hash 1-1，然后从右侧进入 Top Hash，另一侧是 Hash 0。要检查此证明，我们计算 hash(Hash 0 + hash(hash(L3) + Hash 1-1))。如果这等于 Top Hash，则证明有效！伪造这些证明在每个步骤都像找到哈希碰撞一样困难，且证明大小与消息集大小成对数关系。

这有各种应用。Tahoe-LAFS、Git 和 ZFS（参见：Wikipedia）都使用它来确保数据完整性。它出现在从 IPFS 到比特币再到以太坊的去中心化应用中（再次参见：Wikipedia）。最后，它使证书透明度成为可能（稍后详述）。认证数据结构的能力解决了各种困难的计算机科学问题。

“你遇到了你的隐喻，而且很好”

当然，Merkle 树不是唯一可能的认证数据结构。不难想象将上述方法推广到任意分支宽度的树，甚至具有可选组件的树。我们可以为几乎任何类似 DAG 的数据结构构建认证版本，或者只是将结构的元素映射到 Merkle 树上。

事实上，正如 Miller 等人在 2014 年发现的那样，我们可以构建一种所有数据类型都经过认证的编程语言。在《认证数据结构，通用地》中，作者创建了 OCaml 编译器的一个分支来实现这一点，并证明其既可靠又高性能。这样做的机制很吸引人，但超出了本文的范围。我强烈推荐阅读该论文。

Miller 等人的论文中一个有趣的事情是，他们重新情境化了认证数据结构的动机。在本文前面，我们讨论了 Merkle 树对承诺方案和数据完整性保证的有用性，但 Miller 等人选择将其框架为对数据委托的有用性。具体来说，论文将认证数据结构定义为“其操作可以由不可信的证明者执行，验证者可以高效检查结果真实性”的数据结构。

如果我们花点时间思考，可以看到这确实是正确的。如果我有一个包含数百万个元素的 Merkle 树，我可以将其交给第三方，只保留顶部哈希，然后向这些数据发出查询，期望返回一个值和一个包含证明。只要证明检查通过，我就知道我的数据没有被篡改。在无信任分布式系统的背景下，这很重要（我们稍后会回到具体原因，我保证）。

事实上，我不仅可以认证读取，还可以认证写入！当我评估包含证明时，结果是一个哈希，我将其与保存的摘要进行比较。如果我请求树中某个索引的值，保存证明，然后请求写入同一索引，通过用我正在写入的值评估旧证明，我可以了解写入发生后摘要将是什么。再次，一个例子可能有帮助。

回想我们之前的（图示）例子，为了证明 L3 的包含，我们的证明包括 [(Left, Hash 1-1), (Right, Hash 0)]。如果我们想写入一个新值，我们首先检索 L3 和关联的证明。然后，就像我们通过计算 hash(Hash 0 + hash(hash(L3) + Hash 1-1)) 并确保它等于根哈希来检查证明一样，我们计算 hash(Hash 0 + hash(hash(new_L3) + Hash 1-1)) 并将保存的摘要更新为结果。如果这不直观，回顾图表可能很有帮助。

认证读取和写入的组合允许一些非常强大的新构造。具体来说，通过在 Miller 等人的新语言中谨慎地向程序添加认证“检查点”，我们可以密码学地确保客户端和服务器始终就程序状态达成一致，即使客户端不保留程序操作的任何数据！这对于将计算分发到半可信节点的系统（是的，像区块链）来说是改变游戏规则的。

这听起来像一个带有各种警告的疯狂保证，但它远没有那么令人兴奋。程序最终在过于复杂的图灵机上运行。程序状态只是写入磁带的内容。一旦您接受了所有读取和写入都可以为您想要的任何数据结构进行认证，其余的就微不足道了。Miller 等人的大部分贡献最终只是更好的语义！

“我们爱事物本来的样子”

到目前为止，我们已经取得了一些相当奇幻的结果。我们可以像往常一样编写代码，并密码学地确保客户端和服务器状态同步，即使其中一方没有操作的数据。这是一个强大的想法，很难不阅读并寻求扩展它或将其应用到新领域。因此，自 2014 年以来，认证数据结构领域出现了一些极其令人印象深刻的发展。

我发现一个特别值得注意的工作是 Bob Atkins 在 2016 年编写的《认证数据结构，作为库，免费！》。Atkins 在 Miller 等人的工作基础上构建，使其不再需要自定义编译器，这是向实际采用迈出的一大步。它确实要求开发者为其数据类型提供显式序列化以及自定义检索函数。它现在与 OCaml 中的真实生产代码相对无缝地工作。

然而，仍然存在索引问题。到目前为止，我们一直在描述基于 Merkle 树叶子的访问。这对于像数组这样的数据结构效果很好，但弄清楚如何认证像哈希映射这样的东西要困难得多。将键映射到叶子是微不足道的，但如何验证给定键首先有定义的值呢？

考虑一个从字符串到整数的简单哈希映射。如果认证哈希映射的保管人声称某个键“hello”没有定义值，我们如何验证？委托者可以保留所有键的列表并进行认证，但这丑陋且不优雅，并且有效地使我们的摘要大小随数据集大小线性增长。理想情况下，我们仍然希望只保存一个哈希，并且在客户端和服务器之间同步此键列表是滋生错误的肥沃土壤。

幸运的是，Google 的 Ben Laurie 和 Emilia Kasper 在 2016 年开发了一种新颖的解决方案。他们的工作是 Trillian 的一部分，该库在 Chrome 中实现证书透明度。在《撤销透明度》中，他们引入了稀疏 Merkle 树的概念，这是一种大小不可行的 Merkle 树（在他们的例子中，深度为 256，所以每个节点对应宇宙中的一千个原子），我们利用该树中几乎所有叶子具有相同值的事实，在高效时间内计算证明和摘要。

我不会深入技术细节，但基本上，有 2^256 个叶子，每个叶子可以分配一个 256 位索引。这意味着给定一些键/值数据集，我们可以哈希每个键（产生一个 256 位摘要）并获得树中的唯一索引。我们将值的哈希与该叶子关联，并为不与任何值关联的叶子设置特殊的空哈希。下面有另一个我发现非常有帮助的图表：

“一个高度=4（4 位键）的示例稀疏 Merkle 树，包含 3 个键。3 个键以红色和蓝色显示。默认节点以绿色显示。非默认节点以紫色显示。”（图片和说明来自 AergoBlog）

现在我们也知道每个第二层分支的哈希，这些分支不直接位于我们定义的节点之上，因为它只是 hash(hash(null) + hash(null))。进一步扩展，对于给定计算，我们只需要跟踪至少一个定义节点上方的节点，每个其他值都可以按需快速计算。计算摘要、生成证明和检查证明都与数据集大小成对数关系。此外，我们可以通过简单地返回对空哈希有效的检索证明来验证键没有关联值。

稀疏 Merkle 树虽然相对年轻，但已经引起了行业的严重兴趣。显然，它们支持撤销透明度，但它们也被考虑用于以太坊和 Loom。有不止几个库（Trillian 是最著名的）只实现稀疏 Merkle 树数据存储。在其上构建工具并不特别困难（查看这个很酷的例子）。

“给我一片枝叶繁茂的土地”

尽管所有这些发展令人兴奋，但人们可能仍然希望一个“所有世界最佳”的解决方案：像 Miller 等人的一样易于使用的数据结构认证语义，像 Atkins 的一样作为轻量级库实现，并具有 Laurie 和 Kasper 的自然索引和排除证明支持。这正是 Indurative 实现的。

Indurative 使用了一个名为 DerivingVia 的新 GHC 功能，该功能于去年夏天在 GHC 8.6 中落地。DerivingVia 旨在允许实例化多态函数，而无需容易出错的手写实例或 hacky、不可靠的模板和准引用。它使用 Haskell 的 newtype 系统，以便库作者可以编写一个通用实例，开发者可以自动专门化到他们的类型。

DerivingVia 意味着 Indurative 可以为基本上任何可以用二进制可序列化键和值迭代的索引类型提供认证语义。Indurative 开箱即用地适用于标准库、containers 和 unordered-containers 中的容器。它可以为满足这些约束的任何容器派生这些语义，使用任何哈希函数（和树深度），以及任何可序列化的键和值，而用户无需编写一行代码。

早些时候我们简要讨论了在不到十行代码内为包管理服务器添加二进制透明度的例子。如果开发者不必在他们已经使用的数据结构和他们的 Merkle 树认证存储之间维护并行状态，我们希望他们可以专注于发布功能，而不放弃密码学真实性保证。

Indurative 仍然是 alpha 软件。它还不很快（可以变得快得多），可能有错误，并且使用有点可疑的 Haskell（UndecidableInstances，但我认为我们这样做是可靠的）。它也是新的、未经测试的密码学软件，所以您可能还不想依赖它进行生产使用。但是，我们努力注释所有代码并编写测试，因为我们认为即使它不成熟，也真的很有趣。请尝试它，让我们知道它如何工作，并告诉我们您想看到什么。

如果您有困难的密码学工程问题，并且认为像 Indurative 这样的东西可能是解决方案，请给我们留言。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News

页面内容 “那看起来像棵树，我们就叫它树吧” “你遇到了你的隐喻，而且很好” “我们爱事物本来的样子” “给我一片枝叶繁茂的土地” 最近帖子 非传统创新者奖学金 劫持您的 PajaMAS 中的多代理系统 我们构建了 MCP 一直需要的安全层 利用废弃硬件中的零日漏洞 Inside EthCC[8]：成为智能合约审计员 © 2025 Trail of Bits。 使用 Hugo 和 Mainroad 主题生成。