关于go:默克尔树Merkle-Tree

默克尔树（又叫哈希树）是一种典型的二叉树构造，有 一个根节点 、 一组两头节点 和一组叶节点 组成。默克尔树最早由 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 树结构

关于go:默克尔树Merkle-Tree

Merkle 树结构

利用场景

证实某个汇合中存在或不存在某个元素

疾速比拟大量数据

疾速定位批改

零常识证实

代码示例