默克尔树

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

主要特点：

• 最下面的叶节点包含存储数据或其哈希值；
• 非叶子节点（包括中间节点和根节点）都是它的两个孩子节点内容的哈希值
• 默克尔树可以推广到多叉树的情形，此时非叶子节点的内容为它所有的孩子节点的内容的哈希值。

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

生成过程

将一个大数据块拆分成更多小的数据块，然后对每个数据块进行哈希运算，得到所有数据块的哈希值之后，获得一个哈希列表。接下来根据列表元素个数的奇偶特性重新再计算出哈希值，如果是偶数，则两两合并再计算哈希值，获得新的列表；如果是奇数，则前面两两计算哈希值，最后一个单独计算哈希值。重复上面的过程最终得到一个哈希值，被称为跟哈希。

应用场景

1、快比较大量数据。叶子节点数据的细微改动，都会导致根节点发生变化，可以用根节点来判断数据是否发生修改。
2、快速定位数据块的修改。如果Data1的数据发生修改，那么就会影响H1、H4、Root。根据树的特性，从根节点到叶子节点，只需要通过O(logn)便定位到实际发生改变的数据块是Data1。
3、零知识证明。为了证明某个论断是否正确，通常我们需要将数据发送给验证者。默克尔树提供了一种方法，可以证明某方拥有数据，而不需要将原始数据发给对方。 例如，我们只需要将Data0、H1、H5、Root对外公布，任何拥有Data0的用户，经过计算可以获得同样的Root值，说明该公开用户拥有数据Data1、Data2、Data3。

在区块链中的应用

在区块链中，我们只需要保留对自己有用的交易信息，删除或者在其它设备备份其余交易信息。如果需要验证交易内容，只需要验证默克尔树即可。若根哈希验证不通过，则验证两个叶子节点，再验证其中哈希验证不通过的节点的叶子节点，最终可以准确识别被篡改的交易。