MerkleDB审计 - Openzeppelin

目录

• 目录
• 概要
• 范围
• 系统概述
  • 方法论
  • 评估
• 高危
  • 能够生成Trie中存在的键的有效排除证明
• 低危
  • RecordKeyChange忽略ErrorNotFound
  • 如果没有现有的子节点，函数addPathInfo将使用先前的compressedKey
  • 删除节点时，recordKeyChange函数的不正确参数值
• 注释和补充信息
  • 验证证明时，Trie构建的可能优化
  • ViewNodeCacheMiss从未使用
  • 代码风格不一致
  • 误导性注释
  • 变量遮蔽
• 结论

概要

本次审计在 MerkleDB 投入生产使用之前进行。任何已识别的问题均未影响 MerkleDB 的生产实例。 TypeInfrastructureTimelineFrom 2024-01-08To 2024-02-16LanguagesGolangTotal Issues9 (8 resolved)Critical Severity Issues0 (0 resolved)High Severity Issues1 (1 resolved)Medium Severity Issues0 (0 resolved)Low Severity Issues3 (3 resolved)Notes & Additional Information5 (4 resolved)

范围

我们审计了来自 ava-labs/avalanchego 仓库 commit 73c4c0f 的 x/merkledb 和 x/sync 包。

审计范围包括以下文件：

 x
├── merkledb
│   ├── batch.go
│   ├── cache.go
│   ├── codec.go
│   ├── db.go
│   ├── history.go
│   ├── intermediate_node_db.go
│   ├── key.go
│   ├── metrics.go
│   ├── node.go
│   ├── proof.go
│   ├── tracer.go
│   ├── trie.go
│   ├── value_node_db.go
│   ├── view.go
│   └── view_iterator.go
└── sync
    ├── client.go
    ├── db.go
    ├── manager.go
    ├── metrics.go
    ├── network_client.go
    ├── network_server.go
    ├── response_handler.go
    ├── workheap.go
    └── g_db
        ├── db_client.go
        └── db_server.go

系统概述

MerkleDB 是使用 Merkle radix trie 持久化键值存储的实现，它是一种结合了 Merkle tree 和 radix trie 的结构。 它旨在提供安全、高效且可验证的键值存储，从而利用 Merkle tree 和 radix trie 的优势。 它对于需要高安全性和可验证性的应用程序（例如区块链技术）特别有用。

该数据库的基本优势来自于其对键值对的高效存储和检索，从而可以验证数据的完整性，并能够验证特定的键值对是否存在于数据库中。 Merkle tree 的使用使得数据库能够通过对叶子节点的数据进行哈希处理，然后递归地对子节点哈希的连接进行哈希处理，直到单个哈希（称为根哈希）代表整个数据集，从而创建整个数据集的指纹（哈希）。 该根哈希充当任何给定时间的数据状态的唯一标识符，因为对其底层键值对的任何修改都将导致不同的根哈希。

该 MerkleDB 实现还引入了视图的概念，这些视图本质上是数据库操作的提议。 视图是由一组键值操作（插入、更新、删除）创建的。 创建后，视图是不可变的并且可以链接在一起，从而可以在将任何更改永久提交到数据库之前实现复杂的数据操作和版本控制。

该数据库支持生成三种类型的加密证明，以确保其键值存储中数据的完整性和可验证性：简单证明、范围证明和变更证明。

• 简单证明： 用于证明特定的键值对在某个状态（如前所述，由特定的根哈希标识）下存在或不存在于数据库中。 这些证明依赖于从目标节点到树根的哈希路径。 对于包含证明，路径在包含键的节点处结束。 对于排除证明，路径在如果键存在则会位于的节点处结束，从而提供键不存在的证据。

• 范围证明： 简单证明的扩展，以覆盖指定键范围内的连续键值对集。 它们证明该范围内所有键值对存在于特定状态的数据库中，并且该范围内不存在其他键。 这些证明对于有效验证数据库的大部分内容特别有用，从而允许客户端在单个操作中同步或下载多个键值对。

• 变更证明： 显示数据库两个状态之间的数据差异，由它们各自的根哈希标识。 这些证明包含两个状态之间添加、修改或删除的键值对集。 变更证明使客户端能够通过应用证明中指示的更改，将其数据库的本地副本更新到新状态，而无需重新验证整个数据库。

通过使用这些证明，sync 包允许在客户端和服务器之间同步 MerkleDB 实例，其中服务器拥有数据库的最新版本，而客户端拥有过时或空版本。 这种同步机制非常适合区块链系统，并且旨在最终与 Firewood 兼容，Firewood 是一种最先进的数据库，专为存储 Merkleized 区块链状态而优化。

方法论

为了评估 MerkleDB 实现的正确性，我们在审计期间专注于以下几个方面：

• 检查节点序列化和反序列化，以确保该过程对于格式错误或恶意数据是安全的。
• 验证节点哈希和 ID 唯一性，以确保其可靠地生成唯一且抗冲突的节点 ID。
• 评估锁定机制和并发控制，以确保它们在不导致死锁或性能问题的情况下提供必要的原子性和一致性。
• 检查视图如何提交到 MerkleDB 以及如何跟踪和管理其有效性，尤其是在父视图和子视图的关系方面。
• 审查简单证明、范围证明和变更证明的生成和验证。
• 评估不同 MerkleDB 实例之间的同步的健壮性，同时确保数据完整性和客户端可用性。

评估

在审计 merkledb 和 sync 包期间，发现代码库质量非常高。 总的来说，代码干净整洁，遵循了最佳 Golang 实践，并具有全面的文档、单元测试、广泛的模糊测试和出色的测试策略，这些共同确保了数据库的正确实现。 但是，重要的是要注意，尽管 MerkleDB 实现质量很高，但尚未经过广泛的实际测试。 鉴于分布式系统中固有的复杂性和潜在的不可预见的故障，仅通过代码审计以及传统的测试方法不太可能发现所有现有问题。

因此，强烈建议开发模拟软件，该软件可以在各种条件下仔细测试数据库及其同步协议，从而确保其在现实场景中的稳健性和可靠性。 值得注意的是，AVA Labs 团队在这方面也取得了重大进展，因为在审计期间，他们提供了对专门为测试 MerkleDB 及其同步协议而设计的代码库的访问权限。

尽管如此，我们建议扩大模拟软件的范围，以涵盖更多样化的测试场景，例如硬件故障、波动的网络延迟和数据损坏场景，以确保 MerkleDB 在各种具有挑战性的环境中的健壮性和可靠性。

高危

能够生成Trie中存在的键的有效排除证明

MerkleDB 允许创建包含和排除证明。包含证明验证在指定根下的 trie 中是否存在特定的 key-value 对，而排除证明确认在同一根下的 trie 中不存在特定的 key-value 对。这两种证明的构造方式类似，都使用Proof struct。对于排除证明，此结构的 Key 字段被分配给旨在证明不存在于 trie 中的键，而 Value 字段则留空。Path 表示从 trie 的根到 (如果它是 trie 的一部分，则可能存在的) 节点（的父节点）的位置的一系列节点。

在验证排除证明时，验证器构造一个空的 trie，并用 Path 中的所有节点填充它。如果这个构造的 trie 的根 ID 与预期的根 ID 匹配，则验证器可以确定 Path 中的所有节点都是正确的，从而确认指定的 key-value 对不存在于 trie 中。

但是，一个恶意的证明者可以伪造一个有效的 key-value 对的排除证明，而该 key-value 对实际上存在于 trie 中。这可以通过从证明中删除 Value 并通过不包括 key-value 对可能所在的节点的父节点来减少证明路径的长度来实现。考虑到 ID 表示节点 哈希，并且每个节点 保存其子节点的 ID，只要它的父节点之一包含在证明路径中，证明路径实际上不需要到达该节点。因此，验证器创建的 trie 将与原始 trie 的上半部分相同，并产生相同的根 ID，并错误地通过验证过程。

请考虑审查证明验证机制，以防止接受现有 key-value 对的伪造的排除证明。

更新： 已在 pull request #2789 中解决。

低危

RecordKeyChange 忽略 ErrorNotFound

当 view.go 中的 recordKeyChange 函数被调用，并将布尔参数 newNode 设置为 false 时，该函数将调用 v.getParentTrie().getEditableNode(key, hadValue)。但是，如果出现 database.ErrNotFound 类型的错误，则该 错误将被忽略。

如果发生这种情况，则调用 v.getParentTrie().getEditableNode(key, hadValue) 产生的 before 值将为 nil，这将 在 v.changes.nodes 映射中注册。这将是不一致的，因为如果这不是一个新节点，则不应该没有 before。因此，虽然理论上，只要 recordKeyChange 的调用者正确使用 newNode 参数，就不会发生此错误，但如果调用者滥用它，该函数仍应失败。

考虑不要忽略返回错误 database.ErrNotFound 并让该函数返回一个错误。

更新： 已在 pull request #2743 中解决。

如果没有现有的子节点，函数 addPathInfo 将使用先前的 compressedKey

在addPathInfo函数中，验证器将证明路径中的每个节点添加到新的trie中。 对于每个节点，如果它们小于下限或大于所证明的键的上限，则添加子节点。 在添加子节点时，该函数将获取相应的compressedKey，然后再创建子条目。

但是，由于compressedKey变量在for循环之外声明，如果在构造trie中没有现有的子节点，则函数n.setChildEntry将使用找到的最后一个子节点的compressedKey，而不是传递一个空的Key。 这将导致trie中的节点为其子节点存储错误的compressedKey。 但是，由于只有ID对于计算哈希值是必要的，因此这不应该影响证明验证过程。

请考虑在addPathInfo函数中设置compressedKey是否绝对必要。 如果是，请确保它每个子节都有正确的值。

更新： 已在 pull request #2777 中解决。

删除节点时，recordKeyChange 函数的不正确参数值

recordKeyChange 函数 具有一个 hadValue 布尔参数，在调用 getEditableNode 函数时会传递该参数。 这是必要的，以便选择在底层数据库中查找节点时应使用的底层数据库（valueNodeDB 或 intermediateNodeDB）。

但是，在view.remove函数中，节点值设置为maybe.Nothing，然后调用recordNodeDeleted，这会调用recordKeyChange。 因此，在这种情况下，当删除的节点之前确实有一个现有值时，hadValue 将设置为 false。 这将导致无法从父trie中获取先前的值，因为它将选择错误的数据库。

考虑审查如何设置 hadValue 参数，而不是始终使用 after.hasValue()，以确保它正确识别节点是否确实具有先前的值。

更新： 已在 pull request #2779 中解决。

注释和补充信息

验证证明时，Trie构建的可能优化

当验证一个证明时，函数 addPathInfo 从证明路径中的 最后一个元素 len(proofPath) - 1 开始迭代，然后向后进行到第一个元素。 这个逆序表明 trie 是通过处理从叶子开始到根的节点来构建的，这是一种自下而上的方法。 然而，从上到下构建 trie 可能更有效，因为它会最大限度地减少必须创建然后删除节点（以便被拆分替换）的次数。

考虑评估在处理 addPathInfo 中的节点时，自上而下的方法是否会更有效。

更新： 已确认，未解决。

ViewNodeCacheMiss 从未使用

当从缓存成功检索节点时，将调用 ViewNodeCacheHit 函数。 但是，ViewNodeCacheMiss 函数从未使用。

考虑在未能从缓存中检索节点时调用 ViewNodeCacheMiss 函数。

更新： 已在 pull request #2781 和 pull request #2844 中解决。

代码风格不一致

在整个代码库中，有一些代码风格不一致的地方：

• 在 provenKey 的 赋值 中，可以重用 lastNode 变量。
• 范围指令 可以迭代键值对而不是仅迭代键。 这样，不应该 单独声明 childEntry。

考虑查看整个代码库以提高一致性并在可能的情况下重构代码。

更新： 已在 pull request #2783 中解决。

误导性注释

以下误导性和不一致的注释已在代码库中被识别：

• 根据这个 注释，visitPathToKey 应该返回沿路径的节点。 相反，在沿路径的每个节点上调用 visitNode 函数，并且 visitPathToKey 要么返回 err，要么返回 nil。
• getValue 中的 注释 指的是本地“键的副本”，但它应该指的是“键处的值的副本”。
• 根据这个 注释，compressNodePath 以递归方式合并没有值和单个子节点的节点。 但是，它仅将单个节点与其父节点合并。
• getProof 的 文档 提到了一个不存在的 bytesPath 变量。
• verifyProofPath 中的这个 注释 说“应该存储一个值”。 但是，它应该是“不应该存储一个值”。

考虑修改注释以提高一致性并更准确地反映已实现的逻辑。

更新： 已在 pull request #2780 中解决。

变量遮蔽

在整个代码库中，存在一个变量采用现有函数名称的多个变量遮蔽实例：

• NewView 中的 newView 变量 正在遮蔽 newView 函数。
• newView 中的 newView 变量 正在遮蔽 newView 函数。
• newViewWithChanges 中的 newView 变量 正在遮蔽 newView 函数。

虽然这不会影响代码，因为遮蔽仅发生在函数范围内，但请考虑遵循最佳实践并使用不同的变量名。

更新： 已在 pull request #2784 中解决。

结论

MerkleDB 是一个键值数据库，它继承了 Merkle 树和 radix trie 的属性，以提供安全高效的数据存储和验证的创新解决方案。 这种组合使数据库能够有效地管理数据，同时通过加密证明确保其完整性，使其特别适合安全性和数据可验证性至关重要的区块链应用程序。

在整个审计过程中，除了几个低严重性问题外，还发现了一个高严重性问题。 尽管如此，代码库的质量非常高，具有广泛的文档和全面的测试套件，涵盖了代码库的大部分内容。

但是，由于分布式系统中固有的复杂性，我们强烈建议开发模拟软件来测试和确保数据库在各种条件下的可靠性和稳健性。 该模拟软件应允许在各种具有挑战性的环境中测试 MerkleDB 的运行，确保 MerkleDB 能够满足实际场景的需求。

• 原文链接： blog.openzeppelin.com/me...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～