【他山之石】大话密码学·默克尔树·章三 扬前帆
前帆(Jib)：主桅杆前面使用的帆
基本定义
Merkle Tree 是由计算机科学家 Ralph Merkle 在很多年前提出的，并以他本人的名字来命名，中文翻译过来叫默克尔树，也叫哈希树。
哈希树
主要用途
Merkle Tree 常用来做完整性校验的，所谓的完整性校验，就是检查一下数据有没有损坏或者被恶意篡改。
Merkle Tree 的最大的应用场合就是在点对点网络上，早期的 BT ，电驴，快播等各种下载器，以及目前用的磁力下载，Git 版本控制系统，NMP包管理，GoLang 包管理，IPFS 协议以及比特币以太坊等等项目都用到了它。例子太多了……欢迎补充……
Merkle Tree
Merkle Tree 如果直接去看定义，会看到一张比较复杂的图，可能会把你一下子吓到，然后就不想学了。但是别忘了，Merkle Tree 还有另外一个名字，叫哈希树。
花开两朵 各表一枝
上一章已经讲过哈希，接下来讨论一下哈希列表，最后说一下哈希树，其实每一步都很好理解，我保证你能一下子就掌握 Merkle Tree 的概念。信不信？
还不是你笨哦！
哈希
要实现完整性校验，目前最简单的方法就是对要校验的整个的数据文件做个哈希运算，把得到的哈希值公布在网上，这样我们把数据下载到手之后，再次运算一下哈希值，如果运算结果相等，就表示我们下载过程中文件没有任何的损坏。因为哈希的最大特点是，如果数据稍微变了一点点，那么经过哈希运算，得到的哈希值将会变得面目全非。没有人可以把数据篡改了，同时还能保证数据的哈希不变。
md5sum
这种简单的采用哈希的方式做数据运算，比较适合数据本身不做分割，同时是放在一台服务器上的情况。例如，如果去某个公司网站上去下载他们的一个软件，就会看到公司网站上公布了这个下载包的哈希值，这个哈希值非常重要，因为有了这串数，我们就可以放心的去下载这个软件，下载完做一下完整性校验，就知道这个软件没有损坏。甚至可以放心从其他的不可信网站上去下载这个软件包，因为有了校验机制，也一样可以保证这个包是跟官方的包丝毫不差的。
哈希列表 Hash List
但是在去中心化网络，或者叫点对点网络上，数据往往都是拆分成很多小碎片去下载的，而且其中很多网络节点可以认为是不稳定或者是不可信的，这时需要有更加巧妙的做法。最简单的方式就是用 Hash List ，也就是哈希列表。
image
实际中，点对点网络在传输数据的时候，其实都是把比较大的一个文件，切成小的数据块。这样的好处是，如果有一个小块数据在传输过程中损坏了，那我只要重新下载这一个数据块就行了，不用重新下载整个文件。当然这就要求对每个数据块计算哈希值，所有这些小数据块的哈希值都是兄弟关系，这样大家就组成了一个哈希列表。BT 下载的时候，在下载真正的数据之前，会先下载一个哈希列表的，这个就是所谓的种子文件。有了各个 hash 之后，数据本身就可以从任意的节点上下载了，不用管那些节点是否是安全可信的。
这时有一个问题就出现了，那么多的哈希，我们怎么保证它们本身都是正确地呢？
image
答案是我们需要一个根哈希，根就是树根的根。把每个小块的哈希值拼到一起，然后对整个这个长长的字符串再做一次哈希运算，最终的结果就是哈希列表的根哈希。于是，如果我们能够保证从一个绝对可信的网站，或者从我们的朋友手里拿到一个正确的根哈希，就可以用它来校验哈希列表中的每一个哈希都是正确的，进而可以保证下载的每一个数据块的正确性了。
Hash List 也就是哈希列表形式，就非常适合在点对点网络上存储的大型数据了。
Merkle Tree 哈希树
其实 Merkle Tree 本身也算是一个哈希列表，只不过是在这个基础上又引入了树形结构，从而获得了更高的灵活性。
我们先说计算机科学中的树的概念，树跟自然界一棵树有着类似的结构，只不过计算机科学中的树通常都是倒着画，根在上面，然后一路往下开枝散叶。举一个最简单的例子，所有的文件都存放在一个文件夹中，这个文件夹就叫根文件夹，根就是树根的意思，这个文件夹又会包含其他文件夹，子文件夹中又会包含孙子辈的文件夹。这样层层的包含或者说从属关系，画成图就是一棵倒挂的树，而这个结构就是计算机科学中随处可见的树的概念，怎么样，简单吧？
然后就说到主角 Merkle Tree 了。在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root 。需要补充一下的是，根哈希有时候也叫主哈希 Master Hash ，也有人叫它顶哈希 Top Hash ，因为画图的时候通常都是倒着画这根树，反正不管叫什么，说的都是一个东西。
image
于是我们看到 Merkle Tree 比普通的哈希列表稍微复杂了一点点，那么优点是什么呢？相对于 Hash List，Merkle Tree 的明显的一个好处是可以单独拿出一个分支来（作为一个小树）对部分数据进行校验，这给很多使用场合就带来了哈希列表所不能比拟的灵活和高性能。
image
总结
- Merkle Tree 是三个概念的叠加，一个是哈希，第二个是哈希列表，第三个是树。
- 哈希和树都是计算机科学中最基础最重要的两个概念，可以用在很多不同场合。单个哈希不能担当大文件在分布式点对点网络上的校验工作，于是我们有了哈希列表的概念。
- Merkle Tree 可以认为是哈希列表的一个变体，让哈希列表变得更加灵活高效，因为每次校验都可以单纯拿出树的一个分支来操作。
参考：
