Merkle 树在 Fuchsia 生态系统的各个位置都有使用，包括 FAR 归档格式、Blob Storage 文件系统以及 ffx 中包含的软件包管理工具。
在 Zircon 中，zx-verity 提供了一个 API，供应用组件从本地存储空间读取数据。检索数据时，系统会验证数据的完整性，并在数据被修改或损坏时导致读取失败。zx-verity 基于 Merkle 树，源自 ChromeOS 中的类似系统。
所有这些实现都使用本文档中记录的算法。
Merkle 树的参数
- 块大小：8kb，填充 0。
- 根摘要大小：32 字节。
- 哈希算法：SHA-256。
- 分块摘要计算：SHA-256(u64(offset | level) + u32(length) + data)
定义
Merkle 树包含多个层级。层级是树的一行，从 0 开始向上计数。级别 0 表示包含输入数据流分块哈希的级别。
每个级别都包含上一个级别的多个哈希值。某个层级内的哈希是根据上一层级中的 8kb 区块（如果是第 0 层级，则为数据）计算得出的，并附加区块标识。
区块标识是当前级别中区块的起始字节索引与当前级别索引的二进制 OR 运算结果，后跟区块的长度。对于第 0 层，块的长度为 8kb，但最后一个块的长度可能小于 8kb。所有其他级别均使用 8kb 的长度，即使最后一个分块填充了 0 也是如此。
计算等级
- 使用索引、从 0 开始的偏移量和空哈希列表初始化该层级。
- 对于每个 8kb（或其余部分）的输入，请通过对级别索引和当前偏移量进行二进制 OR 运算来计算下一个块标识符，后跟输入的长度。
- 初始化 SHA-256 摘要，将身份、输入附加到该摘要，如果输入短于 8kb，则附加一个长度不超过 8kb 的 0 填充。
- 将摘要的输出附加到该级别的哈希列表。将偏移量按输入长度递增。
- 重复 1-4 步，直到使用完所有输入。
- 如果哈希的长度为 32，则完成。
- 如果哈希的长度不是 8kb 对齐，则用 0 填充到 8kb 对齐，并计算更多层级，直到根级别包含单个 32 字节的摘要。
计算根摘要
使用输入数据计算第 0 层级。使用上一个级别的哈希作为输入数据构建和计算后续级别，直到级别哈希恰好包含 32 个字节。这最后一级包含 Merkle 树的根摘要。
关于空摘要的说明
作为一种特殊情况，如果没有输入数据，实现可能需要独立处理计算。空输入的摘要只是 12 个 0 字节的 SHA-256，即单个长度为 0 的块的块标识。
示例值
- 空摘要：
15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b - 8192 字节的
0xff-“oneblock”68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737 - 65536 字节的
0xff-“小”f75f59a944d2433bc6830ec243bfefa457704d2aed12f30539cd4f18bf1d62cf - 2105344 字节的
0xff-“large”7d75dfb18bfd48e03b5be4e8e9aeea2f89880cb81c1551df855e0d0a0cc59a67 - 2109440 字节的
0xff-“未对齐”7577266aa98ce587922fdc668c186e27f3c742fb1b732737153b70ae46973e43 0xff0080字节，填充了重复的0xff0080-“fuchsia”2feb488cffc976061998ac90ce7292241dfa86883c0edc279433b5c4370d0f30