哈希之叶 - Trail of Bits博客

Trail of Bits于2019年6月17日发布了Indurative——一个密码学库，能够对多种数据结构进行认证，且无需用户编写大量代码。该库从数据完整性到无信任分布式系统都有广泛应用。例如，开发者仅用八行代码就能通过Indurative为包管理器添加二进制透明度功能，使用户可验证下载二进制文件的真实性。

在底层，Indurative利用Haskell的新DerivingVia语言扩展，自动将实例化FoldableWithIndex的类型映射到稀疏默克尔树表示，并使用这些表示创建和验证包含（或排除）证明。如果您理解这些技术细节，可以直接下载Indurative开始使用；如果不理解，本篇博客的其余部分正是为您准备的。

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

1979年，Ralph Merkle申请了一项基于哈希的签名方案专利。该专利引入了多个创新概念，其中最著名的或许是“认证树”，即现在所称的默克尔树。尽管该结构在专利中几乎是附带提及，但它极大提升了多种密码学问题的效率，现已成为Merkle最著名的成果。

基于哈希的签名需要“承诺方案”：一方发送对未来消息的承诺，使得：i) 只有唯一消息能满足承诺；ii) 给定消息时易验证是否满足承诺；iii) 承诺不泄露消息内容。承诺方案从Twitter到多方计算都有应用。

通常，承诺只是消息的哈希（或“摘要”）。任何人都可哈希消息并检查是否与承诺匹配。找到具有相同哈希的不同消息是重大突破。但这对Merkle的方案不够：他需要承诺整个消息集，然后提供包含证明以验证某消息在集合中而不泄露全部内容。为此，他设计了此数据结构：

想象一棵二叉树，每个节点有关联哈希。叶子节点与集合中消息的哈希关联。每个分支节点与子节点哈希串联后的哈希关联。在此方案中，我们只需发布顶部哈希作为承诺。为证明某消息在集合中，我们从其哈希关联的叶子开始向上遍历树。每次向上移动时，记录进入的分支侧和该分支另一侧节点的哈希。然后通过每一步重新计算串联和哈希来验证证明，确保结果与先前的承诺匹配。

通过示例更易理解。在上图中，为证明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）。最后，它使证书透明度成为可能（后续详述）。认证数据结构的能力解决了多种困难的计算科学问题。

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

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

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

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

稍加思考可知这是正确的。如果我有包含数百万元素的默克尔树，可将其交给第三方，仅保留顶部哈希，然后查询数据并期望返回值和包含证明。只要证明验证通过，我就知道数据未被篡改。在无信任分布式系统中，这意义重大（后续会解释原因）。

实际上，我不仅可以认证读取，还可以认证写入！验证包含证明时，结果是哈希，我将其与保存的摘要核对。如果请求树中某索引的值，保存证明，然后请求写入同一索引，通过用写入值评估旧证明，我可以了解写入后的摘要将是什么。再次，示例可能有助理解。

回顾先前（图示）示例，为证明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年以来，认证数据结构领域已有一些极其 impressive 的发展。

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

然而，仍有索引问题。到目前为止，我们一直在描述默克尔树叶子的访问。这对数组等数据结构很有效，但验证哈希映射等内容要难得多。将键映射到叶子很简单，但如何验证给定键是否有定义值？

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

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

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

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

稀疏默克尔树虽然相对年轻，但已受到业界的 serious 兴趣。显然，它们 behind 撤销透明度，但也正被考虑用于以太坊和Loom。有多个库（Trillian最著名）仅实现稀疏默克尔树数据存储。在其上构建工具并不特别困难（查看此酷示例）。

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

尽管所有这些发展令人兴奋，人们可能仍希望“集所有优点于一身的”解决方案：数据结构认证语义如Miller等人的易用，实现如Atkins的轻量库，并支持Laurie和Kasper的自然索引和排除证明。这正是Indurative实现的。

Indurative使用去年夏天登陆GHC 8.6的新GHC功能DerivingVia。DerivingVia旨在允许实例化多态函数，而无需容易出错的手写实例或hacky、不健全的模板和quasiquotes。它使用Haskell的newtype系统，以便库作者可以编写一个通用实例，开发者可以自动专门化到其类型。

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

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

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

如果您有困难的密码工程问题，并且认为Indurative可能是解决方案，请与我们联系。

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

页面内容 “这看起来像棵树，我们就叫它树吧” “你遇到了隐喻，而且它很好” “我们爱事物本身” “给我一片枝叶茂盛的土地” 近期文章 用Deptective调查您的依赖项 系好安全带，Buttercup，AIxCC的评分回合正在进行中！ 使您的智能合约超越私钥风险 Go解析器中意外的安全隐患 我们审查首批DKLs23库的收获 Silence Laboratories的23个库 © 2025 Trail of Bits。 使用Hugo和Mainroad主题生成。