查看原文

Merkle Tree, 也叫 Hash Tree，是一种基于 Tree， Hash 这两种算法的数据结构，主要用于验证数量众多的数据。它的叶子结点存储数据的Hash，非叶子结点存储所有子节点 hash concat 后的数据的 hash。它被应用于 Git, Mercurial, BitCoin, Ethereum, Dynamo, ZFS, Cassandra 等等。我们可以在中本聪的 BitCoin 那篇论文里面找到 merkle tree( 第 8 章节 Simplified Payment Verification )；在 P2P 网络中，我们也可以通过简单校验 top hash 来看这个源靠不靠谱。

一般我们会推荐使用 SHA-2 家族的哈希函数。

Merkle tree 有一个缺陷是 root 无法说明树的深度。小改进是把树的深度添加到 hash 里面去。