来源：贝壳手表CCT

哈希函数

Hash函数是一个散列函数，任意长度的数据通过散列算法都会得到固定长度的输出。

特点：

1、哈希函数可以起到压缩丝信息的作用；

2、它具有不可逆性；

3、 对输入敏感，两个非常相似但有细微差别的输入通过运算得到的数值差距很大；

4、抗碰撞性很强。

基于哈希函数以上特点，它在区块链中有很多应用。比如，数据完整性校验。将数据进行哈希运算得到长度固定的哈希值，然后把这个哈希值传播到网络中，用户在下载数据时，同样对数据进行哈希计算，将计算结果与网络中传播的哈希值是否一样，以此来判断数据有没有被损坏。

哈希列表

点对点网络中数据的传输会从很多计算机上下载数据，其中会出现很多机器不稳定或者不可信的问题，一旦数据源不稳定，数据损坏，就需要从新下载，效率很低。因此，一个大的文件通常被分割成好多小数据块进行传输是很可行的，如果在传输过程中某个小数据块被损坏，只要重新下载这一块就可以了，这样就大大提高了效率。

哈希列表，就是将整个数据分成若干小数据块，对每个小数据块进行哈希计算得到若干哈希值，探后再将这些哈希值拼成一个长串字符，在对长串字符进行哈希计算，得到一个哈希值，这样就构成了一个哈希列表，这个哈希值被称为根哈希。数据校验的时候，先验证根哈希，如果根哈希一致，数据就是正确的。

Merkle 树

Merkle树是泛化的哈希列表。我们具体了解一下。

首先将整个数据分成多个小数据块（L1、L2、L3、L4），分别计算出对应的哈希值（Hash0-0、Hash0-1、Hash1-0、Hash1-1）。这些哈希值构成了Merkle树的最底层，然后将两个相邻的哈希值（Hash0-0、Hash0-1）合并成一串字符，再进行哈希计算得到一个新的哈希值（Hash0），它被称为两个哈希的“子哈希”，然后循环这个操作，层层计算，每次计算哈希值的数量都减少二倍，直到最后只有一个哈希，这个哈希叫做“根哈希”。

Markle树的特点：

1. 是一棵倒挂的树，具有树结构的特点，大多是二叉树；

2. 最底层是叶子节点，叶子节点是小数据块的哈希值；

3. 非叶子节点是由它下面的两个叶子节点结合的字符串的哈希值。

Markle树的验证

在点对点网络下载数据之前，需要先从可信信息源获得该文件Markle树的根哈希，整个Markle树可以从任意信息源获取。以可信信息源获得的Markle树为标杆，检验获取的Markle树是否受损或虚假即可。

如果两台计算机（A、B）的Markle树进行检验，其中HASH0-0是不一致的，校验过程：

首先对比根哈希，发现不一致；

分别对比Hash1和Hash2，发现Hash1不一致，Hash2一致；

检查Hash这支下面的Hash0-0和Hash0-1，发现Hash0-0不一致，Hash0-1一致；

Hash0-0为叶子节点，获取其目录信息；

检索完毕。

这个过程采用的是二分法，这样就可以减少检查的工作量，提高效率。

文章声明：本文为MarsBit专栏作者作品，版权归作者所有，不代表MarsBit观点。