Merkle山脉树（MMR）：Herodotus案例 - Chainsecurity

Merkle Mountain Range (MMR)：以 Herodotus 为例

Merkle Proof 是一种密码学认证数据结构，广泛用于最小化链上数据存储。例如，针对 Merkle root 的 Merkle proof 可以支持智能合约的空投认领。类似地，Merkle Patricia Trie proof 可以验证以太坊状态 Trie 中键值对的存在性。

在这篇博客中，我们将讨论在构建 Merkle Mountain Range (MMR) 时遇到的一些挑战，这是我们最近对一个项目进行审查时观察到的。这些见解也可能适用于其他 Merkle 相关算法。

Merkle Mountain Range 简介

MMR (Merkle Mountain Range) 是 Merkle 家族中一种独特的数据结构。它类似于一个完美平衡二叉树的列表，其中最高的树位于左侧，高度向右逐渐降低。每棵树的顶部节点被称为 peak。

MMR 严格只允许追加。除了叶子节点，每个节点都有两个子节点。一旦存在一对子节点，就会创建新的父节点。MMR 的根由其大小和所有 peaks 的“bagging”决定。

 // root = H(size, H(P0, H(P1, H(P2, ... H(Pn-1, Pn)))))
fn compute_root(mmr_size: felt252, peaks: Peaks) -> felt252 {
    let bag = peaks.bag();
        // bag = PoseidonHasher::hash_double(peaks[0],
        //           PoseidonHasher::hash_double(peaks[1], ...
        //               PoseidonHasher::hash_double(peaks[n-1], peaks[n])
    //           )
        //       )
    PoseidonHasher::hash_double(mmr_size, bag)
}

Herodotus：使用 MMR 的存储证明

我们最近审查了 Herodotus，这是一个利用 MMR 效率存储区块哈希和区块时间戳的存储证明系统。Herodotus 实现了一个无状态的 MMR 结构，只存储最终的根及其大小。存储证明的运作方式如下：

1. MMR 证明验证历史区块哈希是否包含在 MMR 中。
2. Merkle Patricia Trie 证明确认给定区块哈希的账户或 slot 在状态 Trie 中的存在性。

这种方法允许对任何历史状态进行无需许可的证明。有关以太坊状态和存储证明的更多详细信息，请参阅“延伸阅读”部分。

在 Herodotus 的 MMR 中插入区块哈希也需要提交所有 peaks。MMR 大小的哈希以及提交的 peaks 的 bagging 结果必须与存储的 MMR root 匹配，这一点至关重要。

 fn append(ref self: MMR, hash: felt252, peaks: Peaks) -> Result<(felt252, Peaks), felt252> {
        if !peaks.valid(self.last_pos, self.root) {
            return Result::Err('Invalid peaks');
        }
    ...
}

fn valid(self: Peaks, last_pos: usize, root: felt252) -> bool {
        let computed_root = compute_root(last_pos.into(), self);
        computed_root == root
}

peaks 验证不足会破坏 MMR 更新

用存储的大小对提交的 peaks 进行哈希并将其与存储的根进行比较，似乎可以确保用户提交的 peaks 的完整性。然而，这种检查是不够的。由于独特的哈希构造方法，右侧 peaks 的 bagging 的中间结果也可以作为有效的 peak，从而规避检查。

1. 当插入 N9 时，诚实用户提交实际的 peaks (N7, N8)。
2. 恶意用户可以提交 Hash(N7, N8) 作为 peak，这也通过了检查。

这个漏洞允许 MMR 异常增长和根的不正确更新。因此，合法的 Merkle proof 可能会在被操纵的 MMR 上失败。

此外，这个缺陷可能允许验证中间节点。鉴于 N10 预期是右侧树的 peak，可以错误地验证 X 作为叶子的存在。这尤其危险，因为它将中间节点视为叶子，可能滥用其大的哈希值作为合法的据点。有关此攻击的更多信息，请参阅我们的 审计报告。

如何缓解 MMR 的滥用和操纵？

Herodotus 已通过明确验证 peak 哈希与 MMR root 以及 peak 计数与 MMR 大小来解决此漏洞。此外，现在使用树深度来验证和限制 proof 长度。这些措施有效地限制了潜在的 MMR 操纵和滥用。

仔细验证 Merkle proof 的所有输入至关重要。任何未经验证的属性都可能对项目构成威胁。请考虑以下内容作为进一步检查的起点：

• 叶子节点和中间节点之间是否有明确的区别？是否可以验证中间节点，如果可以，它的值是否可能被利用？
• 叶子节点中存储了什么数据？它是否经过哈希处理？如果没有，恶意数据（例如，一个子树）是否可以插入到叶子中？
• 是否彻底检查了 proof 输入，例如 proof 长度和节点索引？每个 proof 是否是唯一的，数据是否可以在 proof 中被非法注入或更改？

延伸阅读：

Merkle Mountain Range

Herodotus storage Proof

Herodotus security audit reports

Herodotus on Starknet

Herodotus Cairo Libs

外部链接

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