默克尔树（Merkle Tree）

Merkle 树结构

默克尔树（又叫哈希树）是一种典型的二叉树结构，有一个根节点、一组中间节点和一组叶节点组成。默克尔树最早由 Merkle Ralf 在 1980 年提出，曾广泛用于文件系统和P2P系统中。比如 git、区块链、IPFS 等。

主要特点：

• 最下面的叶节点包含存储数据或其哈希值；
• 非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值

默克尔树可以推广到多叉树的情形，此时非叶子节点的内容为它所有的孩子节点的内容的哈希值。

默克尔树逐层记录哈希值的特点，让它具有了一些独特的性质。例如，底层数据的任何变动，都会传递到其父节点，一层层沿着路径一直到树根。这意味着根的值实际上代表了对底层所有数据的“数字摘要”。

应用场景

目前，默克尔树的典型应用场景包括以下几种。

证明某个集合中存在或不存在某个元素

通过构建集合的默克尔树，并提供该元素各级兄弟节点中的 hash 值，可以不暴露集合完整内容而证明某元素存在。

另外，对于可以进行排序的集合，可以将不存在元素的位置用空值代替，以此构建稀疏默克尔树（Sparse Merkle Tree）。该结构可以证明某个集合中不包括指定元素。

快速比较大量数据

对每组数据排序后构建默克尔树结构。当两个默克尔树根相同时，则意味着所代表的两组数据必然相同。否则，必然不同。

由于 hash 计算的过程可以十分快速，预处理可以在短时间内完成。利用默克尔树结构能带来巨大的比较性能优势

快速定位修改

以下图为例，基于数据 D0……D3 构造默克尔树，如果 D1 中数据被修改，会影响到 N1，N4 和 Root。

因此，一旦发现某个节点如 Root 的数值发生变化，沿着 Root –> N4 –> N1，最多通过 O(lgN) 时间即可快速定位到实际发生改变的数据块 D1。

零知识证明

它指的是证明者能够在不向验证者提供任何有用的信息的情况下（没有泄露信息），使验证者相信某个论断是正确的。

有个很简单的例子：A 要向 B 证明自己拥有某个房间的钥匙，假设该房间只能用钥匙打开锁，而其他任何方法都打不开。这时有两个方法：

1. A 把钥匙出示给 B, B 用这把钥匙打开该房间的锁，从而证明 A 拥有该房间的正确钥匙。
2. B 确定该房间内有某一物体，A 用自己拥有的钥匙打开该房间的门，然后把物体拿出来出示给 B，从而证明自己确实拥有该房间的钥匙。

后面的第二种方法属于零知识证明。它的好处在于，整个证明的过程中，B 始终不能看到钥匙的样子，从而避免了钥匙的泄漏。

在默克尔树中，我们仍旧以上图为例，如何向他人证明我拥有 D0 这个数据，而不用暴露更多系统的信息呢？模仿上面的例子，验证者随机提供数据 D1、D2 和 D3，证明者构造如图的默克尔树，并公布 N1 、N5 和 Root。验证者自行计算 Root 值，看是否一致，从而检验 D0 是否存在，因为如果存在，N0 一定相同，那么 N4(N0-N1) 也一定相同、Root(N4-N5)也一定相同。整个过程中验证着没有得到任何除了 D0 外的敏感信息(其他的 D)。

代码示例

以下展示部分代码，完整代码

// Content 代表一个数据块
type Content interface {
    CalculateHash() ([]byte, error)
    Equals(other Content) (bool, error)
}

// MerkleTree 默克尔树
type MerkleTree struct {
    Root         *Node            // 根节点
    merkleRoot   []byte           // 根节点的哈希值
    Leafs        []*Node          // 所有的叶子节点
    hashStrategy func() hash.Hash // 计算哈希的方法
}

// Node 表示默克尔树中的叶节点、非叶节点或 Root
type Node struct {
    Tree   *MerkleTree // 所在的 Merkle Tree
    Parent *Node       // 父节点
    Left   *Node       // 左孩子
    Right  *Node       // 右孩子
    leaf   bool        // 是否叶子节点
    dup    bool        // 是否复制节点
    Hash   []byte      // 如果是叶子节点，则为叶子节点数据的哈希值；如果非叶子节点，则为左右孩子哈希值组合后的哈希值
    C      Content     // 叶子节点存储的数据块
}

引用：Merkle 树结构

本作品采用《CC 协议》，转载必须注明作者和本文链接