加密货币背后的密码学之 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 可以认为是哈希列表的一个变体,让哈希列表变得更加灵活高效,因为每次校验都可以单纯拿出树的一个小树来操作。