共计 1692 个字符，预计需要花费 5 分钟才能阅读完成。
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 证实本人领有某个房间的钥匙，假如该房间只能用钥匙关上锁，而其余任何办法都打不开。这时有两个办法：
- A 把钥匙出示给 B, B 用这把钥匙关上该房间的锁，从而证实 A 领有该房间的正确钥匙。
- 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 树结构
