Merkle Tree- 哈希树证明的简单概念/原理/用途分析

昨天我们介绍了EOS 是使用merkle 哈希证明。为了更好地理解这背后的原理，让我们一起来了解一下什么是merkle 树或哈希树。它们的用处，原理以及为什么需要它。

根据wikipedia（维基百科） 上的解释：

在密码学及计算机科学中，哈希树（hash tree）是一种树形数据结构，每个叶节点均以数据块的哈希作为标签，而非叶节点则以其子节点标签的加密哈希作为标签 。哈希树能够高效、安全地验证大型数据结构的内容，是哈希链的推广形式。

哈希树的概念由瑞夫·墨克于 1979 年申请专利，故亦称墨克树（Merkle tree）。

Merkle 证明的用处：

• 证明数据是否归属于此merkle 树。
• 在不需要存储整个数据的情况下，就可以简明地证明数据是否属于资料组的一部分。
• 验证某些数据组是包含在更大的数据组中，而无须显示整个数据组或其子资料组。

Merkle 树的原理：

它使用的是单向哈希。哈希树的顶部为顶部哈希（top hash），亦称根哈希（root hash）或主哈希（master hash）。它是通过并联两个子哈希来往树上爬直到找到根哈希。
单向哈希可以避免碰撞，而且由于它是确定性算法，因此不会也不可能存在两个一样的文本哈希。

Merkle 证明如何运作？ 让我们通过以下的示例来更好地解释：

为了验证 数据[K] 的根哈希，我们可以使用单向函数哈希[K] 来取得H(K).
为了发现验证K 的包含性, K 不需要被显示，
当H(K) 和未知的数据组L 哈希时， 会产生H(KL).
H(KL)与H(IJ) 哈希得到H(IJKL).
H(IJKL) 与H(MNOP) 哈希得到H(IJKLMNOP)
H(IJKLMNOP) 与H(ABCDEFGH) 哈希得到H(ABCDEFHGIJKLMNOP) ，它正好是公共的merkle 根.

因此， 在不显示H 或任何数据的情况下，我们通过使用H(L), H(IJ), H(HMNOP) 和 H(ABCDEFGH)就证明了数据组H 确实在merkle 树里。

为了取得H 的merkle 证明，我们需要H(L), H(IJ), H(HMNOP) 和 H(ABCDEFGH) 以及通过它们得到的H(ABCDEFHGIJKLMNOP)来证明H(H) 是merkle 树的一部分。因此意味着 数据组H 确实是所有数据组 [A, B, C, … , N, O, P]中的一部分。

换一种简单的说法， merkle 树是一种类似二进制树结构。任何中间的叶节点数据都是它两个子数据的并联。如下图所示（暂时把哈希拿掉方便阅读）:

ABCD 是merkle的根. 要证明C 有效性，所需要的只是D , 只要证明C|D=CD , AB , 就可以证明AB|CD=ABCD ( | | 表示串联).

假如有人提出X , D , 和AB，并说X 是树节点的一部分，那么可以非常容易地证明他在说谎，因为X 不是merkle 根ABCD 的一部分。所有在数字货币交易中需要记住的只是自己的交易和区块头球。

在以上这个例子里，T 代表交易。如果只知道Tx3并需要核对Tx3 是在区块里，要证明这个，只要验证Hash01 和Hash2 看证明是否和Merkle 根一致。 这是因为Hash3, Hash23, 以及Merkle 根已经通过给出的证明和交易计算得出。而Hash01 和 Hash2 是不可能从天而降。它们必须是已经在树里才可以生成证明。

为什么需要merkle 证明？

1． Merkle 树被广泛地用来验证大数据组和大多数区块链应用的包含性。
2． 它使得说谎或作假根本不可能发生，保证了数据的真实和有效性。
3． 在上面的例子中，如果Tx01-2 已经花费并证明，在存储中它们可以被忽略，这不会影响到树的一致性。这样可以使得Merkle 证明很短。

备注：部分内容参阅-
https://www.quora.com/Cryptography-How-does-a-Merkle-proof-actually-work