域名频道资讯站 
在章节1.3中，我们已经深入浅出地探讨过“Hash值”，这一章来讨论Merkle Tree。Merkle Tree又称Hash树（Hash tree），因其概念由瑞夫·墨克（(Ralph C. Merkle)）于1979年申请专利，故亦称墨克树（Merkle tree），这也是我在Hash值之后编写这一章的原因。
上一章我们提到Hash算法接收一段明文后，会以一种不可逆的方式将其转化为一段长度较短、位数固定的散列数据，输入的明文与输出的散列数据一一对应，这样可以检测接受的文件是否完好，密码是否有误等等问题。
如果数据庞大，需要同时在多个机器上下载或者验证数据，有些数据损坏或者不稳定，这时采取单一Hash函数就会重新对整一个庞大文件重复验证下载，效率十分低下。打个比方，就像解一道复杂的数学题，数学题中应用到多个定理公式，你只是其中一个定理不熟悉，那么你整道题都解不出来。你唯一能做的，就是把会的定理列出来，然后解答相关的部分。这其实就是Hash list——把大的文件分割成小的数据块，对每一个数据块做Hash函数。在下载数据之前，先下载这个Hash列表，以此来比对数据，这样一来，如果小的数据块损坏了，则只需要处理这一小块数据就行了。你可以拿到正确部分的步骤分数，而计算机也能验证成功没有损坏和错误的部分，提高效率。此外，再对这个Hash list作一次Hash运算，确保Hash列表的正确性，运算能够得出的Hash值即Hash list的Root Hash。在校验Root Hash的准确性之后，即可用其对应的Hash list来校验所需的数据块了。
理解Hash list就能很好地理解Merkle tree，类似于特殊性与普遍性，Hash list是一种特殊的Merkle tree——即树高为二的多叉Merkle tree（见上图）。两者的区别主要在于，Merkle tree可以下载完一个分支后即时进行验证，而不必像Hash list那样只有下载完整个list才能进行验证，类比寻常的电影下载情况的话，Merkle tree不必下载完所以就可以观看已经下载好的部分，而Hash list需要你下载完整部电影。
在最底层，和Hash list一样，我们把数据分成小的数据块，有相应地Hash和它对应。但是往上走，并不是直接去运算根Hash，而是把相邻的两个Hash合并成一个字符串，然后运算这个字符串的Hash，这样每两个Hash就孕育出一个”子Hash“。如果最底层的Hash总数是单数，那到最后必然出现一个单身Hash，这种情况就直接对它进行Hash运算，所以也能得到它的子Hash。于是往上推，依然是一样的方式，可以得到数目更少的新一级Hash，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root。
Merkle Tree的特点
*具有树结构；
*Merkle Tree叶子节点的value是数据集合的单元数据或者单元数据Hash；
*非叶子节点的value是根据它下面所有的叶子节点值，按照Hash算法计算得出。
Merkle Tree的应用
1. 数字签名
最初Merkle Tree目的是高效的处理Lamport one-time signatures。 每一个Lamport key只能被用来签名一个消息，但是与Merkle tree结合可以来签名多条Merkle。这种方法成为了一种高效的数字签名框架，即Merkle Signature Scheme。
2. P2P网络
在P2P网络中，Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换，甚至检查其他节点不会欺骗或者发布虚假的块。大家所熟悉的BT下载就是采用了P2P技术来让客户端之间进行数据传输，一来可以加快数据下载速度，二来减轻下载服务器的负担。BT即BitTorrent，是一种中心索引式的P2P文件分分析通信协议。
这篇文以感性的理解为主，如果还想探讨具体的算法操作，可以在文章下面留言。
本文素材来自互联网
