用 Rust 从零实现 Merkle Tree:把"两边数据一致吗"变成 O(log n)
两台机器要同步一个目录,怎么找出哪些文件不一样?
朴素做法是把所有文件的哈希列表传过来逐个比对——100 万个文件就要传 100 万个哈希(约 32MB),即使两边完全一致也要传。
Merkle Tree 的解法很漂亮:把哈希组织成树,比较根就相当于比较全部。
- 根哈希相同 → 两份数据完全一致,一个字节都不用传
- 根哈希不同 → 往下走,只比较不同的分支
这就是 O(n) 变成 O(log n) 的来源。
结构:一层层往上哈希
root = H(AB + CD)
/ \
AB = H(A+B) CD = H(C+D)
/ \ / \
A = H(f1) B = H(f2) C = H(f3) D = H(f4)
| | | |
文件1 文件2 文件3 文件4规则只有两条:
- 叶子节点是数据块的哈希
- 内部节点是两个子节点哈希拼起来再哈希
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Hash([u8; 32]);
impl Hash {
pub fn of_bytes(data: &[u8]) -> Self {
Hash(sha256(data))
}
/// 内部节点:把两个子哈希连起来再哈希
pub fn combine(left: &Hash, right: &Hash) -> Self {
let mut buf = [0u8; 64];
buf[..32].copy_from_slice(&left.0);
buf[32..].copy_from_slice(&right.0);
Hash(sha256(&buf))
}
}combine 里"先拼再哈希"这一步有一个重要的安全细节:不能简单地 H(left) + H(right) 或者 H(left xor right)。
用"拼接再哈希"的原因是防止第二原像攻击——如果不做拼接,攻击者可能构造出不同的树得到相同的根。具体做法是给叶子哈希和内部哈希加不同的前缀(这是 RFC 6962 里的做法):
const LEAF_PREFIX: u8 = 0x00;
const NODE_PREFIX: u8 = 0x01;
impl Hash {
pub fn leaf(data: &[u8]) -> Self {
let mut buf = Vec::with_capacity(1 + data.len());
buf.push(LEAF_PREFIX);
buf.extend_from_slice(data);
Hash(sha256(&buf))
}
pub fn node(left: &Hash, right: &Hash) -> Self {
let mut buf = [0u8; 65];
buf[0] = NODE_PREFIX;
buf[1..33].copy_from_slice(&left.0);
buf[33..].copy_from_slice(&right.0);
Hash(sha256(&buf))
}
}没有前缀区分的话,一棵"两层树"和一棵"一层树"可能算出同一个哈希,这会让"用根哈希代表整棵树"这个前提失效。
任何"用哈希表达结构"的场景,都要给不同层级的哈希加域分隔符(domain separation)。 这是密码学里一个反复出现的模式。
树结构:用扁平数组而不是指针
pub struct MerkleTree {
/// 用完全二叉树的数组表示:下标 i 的左右孩子是 2i+1 和 2i+2
nodes: Vec<Hash>,
/// 叶子数量(补齐到 2 的幂之前)
leaf_count: usize,
/// 补齐后的叶子数量
padded_count: usize,
}
impl MerkleTree {
pub fn build(data_blocks: &[Vec<u8>]) -> Self {
let leaf_count = data_blocks.len();
// 补齐到 2 的幂,让树是"完全二叉树"
let padded_count = leaf_count.next_power_of_two().max(1);
// 数组大小 = 2 * padded_count - 1
let mut nodes = vec![Hash::zero(); 2 * padded_count - 1];
// 1. 填叶子
for (i, block) in data_blocks.iter().enumerate() {
nodes[padded_count - 1 + i] = Hash::leaf(block);
}
// 2. 自底向上算内部节点
for i in (0..padded_count - 1).rev() {
nodes[i] = Hash::node(&nodes[2 * i + 1], &nodes[2 * i + 2]);
}
Self { nodes, leaf_count, padded_count }
}
pub fn root(&self) -> &Hash {
&self.nodes[0]
}
}为什么要"补齐到 2 的幂"? 因为这样树就是完全二叉树,可以用 2i+1 / 2i+2 的公式定位孩子,不需要存指针。内存连续,缓存友好。
代价:如果叶子数不是 2 的幂(比如 3 个),最后会多出一个"空叶子"。这不是问题——空叶子用全零哈希表示即可,两边算法一致就行。
一致性验证:只走不同的分支
这是 Merkle Tree 最有价值的操作:
#[derive(Debug)]
pub enum DiffNode {
/// 这个子树两边一致
Same,
/// 这个子树有差异,需要继续往下
Different { left: Option<Box<DiffNode>>, right: Option<Box<DiffNode>> },
/// 到了叶子,这个位置的数据不同
Leaf { index: usize },
}
impl MerkleTree {
/// 比较两棵树,返回差异位置
pub fn diff(&self, other: &MerkleTree, index: usize) -> DiffNode {
// 1. 位置超出范围:一边有数据一边没有
if index >= self.nodes.len() || index >= other.nodes.len() {
return DiffNode::Leaf { index };
}
// 2. 哈希相同 -> 整个子树一致,直接返回
if self.nodes[index] == other.nodes[index] {
return DiffNode::Same;
}
// 3. 是叶子 -> 这个位置确实不同
if index >= self.padded_count - 1 {
return DiffNode::Leaf { index: index - (self.padded_count - 1) };
}
// 4. 内部节点 -> 递归比较两个孩子
DiffNode::Different {
left: Some(Box::new(self.diff(other, 2 * index + 1))),
right: Some(Box::new(self.diff(other, 2 * index + 2))),
}
}
}关键在第 2 步:哈希相同就整棵子树跳过。
如果两边只有 1 个文件不同(100 万个文件里),比较路径是这样的:
第 0 层: 根不同 -> 往下 2 个分支
第 1 层: 1 个不同 -> 往下 2 个分支(另一个分支哈希相同,直接停)
第 2 层: 1 个不同 -> ...
...
第 20 层: 找到叶子只走了 20 层 × 2 个分支 = 40 次哈希比较,而不是 100 万次。而且两边实际需要传输的只是"路径上的节点哈希",大约 20 × 32 = 640 字节。
从 32MB 降到 640 字节——这就是 Merkle Tree 的价值。
增量更新:只重算路径上的节点
数据变化时,不需要重建整棵树:
impl MerkleTree {
/// 更新第 i 个叶子,只重算从它到根的路径
pub fn update_leaf(&mut self, i: usize, data: &[u8]) {
let mut index = self.padded_count - 1 + i;
self.nodes[index] = Hash::leaf(data);
// 自底向上重算到根
while index > 0 {
let parent = (index - 1) / 2;
let left = 2 * parent + 1;
let right = 2 * parent + 2;
self.nodes[parent] = Hash::node(&self.nodes[left], &self.nodes[right]);
index = parent;
}
}
}复杂度是 O(log n) 次哈希,而不是 O(n)。
这个性质是它被用在这些地方的原因:
| 场景 | 用 Merkle Tree 做什么 |
|---|---|
| Git | 每次 commit 只需要重算变了的目录 |
| Cassandra / DynamoDB | 副本间反熵(anti-entropy)同步 |
| IPFS / BitTorrent | 分块校验,只重传坏块 |
| 区块链 | 轻节点只需下载区块头(含根哈希)验证交易 |
| ZFS / Btrfs | 数据块完整性校验 |
稀疏 Merkle Tree:固定高度
上面是"按数据量构建树"。还有另一种常见变体:固定高度,叶子数量固定(比如 2^256)。
pub struct SparseMerkleTree {
/// 固定高度
depth: usize,
/// 只有非默认值的节点才存
nodes: std::collections::HashMap<(usize, usize), Hash>,
/// 默认(空)子树每层的哈希
default_hashes: Vec<Hash>,
}默认哈希是它的关键:每一层的"空子树"哈希是固定的,可以预计算。
impl SparseMerkleTree {
pub fn new(depth: usize) -> Self {
let mut default_hashes = vec![Hash::zero()];
for i in 1..=depth {
default_hashes.push(Hash::node(&default_hashes[i - 1], &default_hashes[i - 1]));
}
Self {
depth,
nodes: std::collections::HashMap::new(),
default_hashes,
}
}
}好处是"地址就是路径"——要更新 key = 0b1011... 的叶子,就沿着这个位序列往下走。
稀疏 Merkle Tree 的典型用途是"证明某个 key 的存在/不存在":
证明 key 存在:提供从叶子到根的兄弟节点哈希(depth 个)
验证者:用这些哈希重算根,看是否和已知根一致这个证明叫 Merkle Proof,大小是 O(log n)。 轻钱包验证"这笔交易在区块里"用的就是这个。
顺便说一个重要的应用:以太坊的状态树就是稀疏 Merkle Tree 的变体(Merkle Patricia Trie)。它的根哈希是整个网络状态的"指纹",任何状态变化都会改变根哈希——这也是为什么全节点必须一步步同步状态,不能跳过。
Merkle Proof 的实现
#[derive(Debug, Clone)]
pub struct Proof {
/// 从叶子到根,每层的兄弟哈希
pub siblings: Vec<Hash>,
/// 叶子的方向(在左还是在右)
pub directions: Vec<bool>,
}
impl MerkleTree {
/// 生成第 i 个叶子的存在证明
pub fn prove(&self, i: usize) -> Proof {
let mut siblings = Vec::new();
let mut directions = Vec::new();
let mut index = self.padded_count - 1 + i;
while index > 0 {
let parent = (index - 1) / 2;
let is_left = index == 2 * parent + 1;
let sibling = if is_left { 2 * parent + 2 } else { 2 * parent + 1 };
siblings.push(self.nodes[sibling].clone());
directions.push(is_left);
index = parent;
}
Proof { siblings, directions }
}
}
/// 验证:只用叶子和证明,重算出根
pub fn verify_proof(leaf_data: &[u8], proof: &Proof, expected_root: &Hash) -> bool {
let mut current = Hash::leaf(leaf_data);
for (sibling, is_left) in proof.siblings.iter().zip(proof.directions.iter()) {
current = if *is_left {
Hash::node(¤t, sibling)
} else {
Hash::node(sibling, ¤t)
};
}
¤t == expected_root
}验证方完全不需要知道整棵树——只要有一个可信的根哈希(比如从区块头拿到的),就能验证任意叶子。
注意 verify_proof 里的 is_left 判断必须精确。 如果方向搞反了,Hash::node(left, right) 的参数顺序就错了,验证会失败。这个 bug 在测试中很容易漏掉,因为两个方向各占一半,随机测试有 50% 通过率。
实际应用中的三个工程问题
1. 数据块大小怎么定。
叶子不一定是"一个文件"。常见选择:
| 粒度 | 适用 |
|---|---|
| 整个文件 | 目录级同步(找出哪些文件变了) |
| 固定大小块(如 4KB) | 只重传坏块(BitTorrent、IPFS) |
| 按内容切分(CDC) | 内容定义分块,增删不移动块边界 |
内容定义分块(Content-Defined Chunking) 值得单独提:它用滚动哈希在数据里找"自然边界",使得"在文件中间插入一段"只影响少数几个块。
固定分块的问题:在开头插入 1 个字节,后面所有块的内容都变了——Merkle Tree 的所有叶子哈希都变,增量同步完全失效。
CDC 解决了这个问题,代价是计算量更大。rsync、Borg、restic 都用它。
2. 树的高度 vs 宽度。
- 树矮而宽 → 每次比较要传更多哈希
- 树高而窄 → 比较路径更长
对"文件级别"的同步,树的扇出(fanout)增大到 16 或 32 能显著减少比较次数——因为每层能排除更多分支。很多实现(如 Dat/Hypercore)用的是 2 路,但"flat tree"(单层)在文件数量少时反而更好。
3. 传输的是"哈希路径",不是"树"。
两个节点同步的正确姿势不是"互相传树",而是:
1. A 把根哈希发给 B
2. 不同 -> A 把根的两个孩子哈希发给 B
3. B 找出相同的那个分支,丢弃
4. B 请求不同的那个分支的孩子
5. 递归直到找到叶子每一轮交互只传一层。 这叫"懒惰同步"(lazy sync),网络往返次数是 O(log n),但每轮数据量很小。
Cassandra 的 anti-entropy repair 就是这个流程:两个副本互相比较 Merkle Tree,只修复不同的部分,而不是全量对比。
结论
Merkle Tree 把"比较两份数据"这件事的结构性优势发挥到了极致:
根哈希是整体指纹;比较时遇到相同哈希就整棵子树跳过;更新只重算到根的路径;用 Merkle Proof 可以只凭根验证任意叶子。
三个实现要点:
- 叶子哈希和内部哈希必须加不同的前缀,防止结构歧义
- 用扁平数组 + 2 的幂补齐,避免指针,缓存友好
- 传输按层交互,不要传整棵树
理解了这些,你会明白 Git 为什么能"只传变化的部分"、区块链轻节点为什么能只凭区块头验证交易、以及分布式数据库的副本修复为什么能做到增量——它们都在用同一棵树,只是叶子上挂的东西不同。