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