23

【他山之石】大话密码学·默克尔树·章三 扬前帆

 5 years ago
source link: https://studygolang.com/articles/25140
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

前帆(Jib)：主桅杆前面使用的帆

基本定义

Merkle Tree 是由计算机科学家 Ralph Merkle 在很多年前提出的，并以他本人的名字来命名，中文翻译过来叫默克尔树，也叫哈希树。
7BJJVrm.jpg!web

哈希树

主要用途

Merkle Tree 常用来做完整性校验的，所谓的完整性校验，就是检查一下数据有没有损坏或者被恶意篡改。

Merkle Tree 的最大的应用场合就是在点对点网络上，早期的 BT ，电驴，快播等各种下载器，以及目前普遍使用的 Git 版本控制系统，NMP包管理，GoLang 包管理，IPFS 协议以及比特币以太坊等等项目都用到了它。例子太多了……欢迎补充……

Merkle Tree

Merkle Tree 如果直接去看定义，会看到一张比较复杂的图，可能会把你一下子吓到，然后就不想学了。但是别忘了，Merkle Tree 还有另外一个名字，叫哈希树。

花开两朵 各表一枝

上一章已经讲过哈希，接下来讨论一下哈希列表，最后说一下哈希树，其实每一步都很好理解，我保证你能一下子就掌握 Merkle Tree 的概念。信不信？

RvEJNri.png!web

还不是你笨哦！

哈希

要实现完整性校验，目前最简单的方法就是对要校验的整个的数据文件做个哈希运算，把得到的哈希值公布在网上，这样我们把数据下载到手之后，再次运算一下哈希值，如果运算结果相等，就表示我们下载过程中文件没有任何的损坏。因为哈希的最大特点是，如果数据稍微变了一点点，那么经过哈希运算，得到的哈希值将会变得面目全非。没有人可以把数据篡改了，同时还能保证数据的哈希不变。

IzYFn2E.png!web

md5sum

这种简单的采用哈希的方式做数据运算，比较适合数据本身不做分割，同时是放在一台服务器上的情况。例如，如果去某个公司网站上去下载他们的一个软件，就会看到公司网站上公布了这个下载包的哈希值，这个哈希值非常重要，因为有了这串数，我们就可以放心的去下载这个软件，下载完做一下完整性校验，就知道这个软件没有损坏。甚至可以放心从其他的不可信网站上去下载这个软件包，因为有了校验机制，也一样可以保证这个包是跟官方的包丝毫不差的。

哈希列表 Hash List

但是在去中心化网络，或者叫点对点网络上，数据往往都是拆分成很多小碎片去下载的，而且其中很多网络节点可以认为是不稳定或者是不可信的，这时需要有更加巧妙的做法。最简单的方式就是用 Hash List ，也就是哈希列表。

n6fENvB.jpg!web

image

实际中，点对点网络在传输数据的时候，其实都是把比较大的一个文件，切成小的数据块。这样的好处是，如果有一个小块数据在传输过程中损坏了，那我只要重新下载这一个数据块就行了，不用重新下载整个文件。当然这就要求对每个数据块计算哈希值，所有这些小数据块的哈希值都是兄弟关系，这样大家就组成了一个哈希列表。BT 下载的时候，在下载真正的数据之前，会先下载一个哈希列表的，这个就是所谓的种子文件。有了各个 hash 之后，数据本身就可以从任意的节点上下载了，不用管那些节点是否是安全可信的。

这时有一个问题就出现了，那么多的哈希，我们怎么保证它们本身都是正确地呢？

MZ3uimq.jpg!web

image

答案是我们需要一个根哈希，根就是树根的根。把每个小块的哈希值拼到一起，然后对整个这个长长的字符串再做一次哈希运算，最终的结果就是哈希列表的根哈希。于是，如果我们能够保证从一个绝对可信的网站，或者从我们的朋友手里拿到一个正确的根哈希，就可以用它来校验哈希列表中的每一个哈希都是正确的，进而可以保证下载的每一个数据块的正确性了。

Hash List 也就是哈希列表形式，就非常适合在点对点网络上存储的大型数据了。

Merkle Tree 哈希树

其实 Merkle Tree 本身也算是一个哈希列表，只不过是在这个基础上又引入了树形结构，从而获得了更高的灵活性。

我们先说计算机科学中的树的概念，树跟自然界一棵树有着类似的结构，只不过计算机科学中的树通常都是倒着画，根在上面，然后一路往下开枝散叶。举一个最简单的例子，所有的文件都存放在一个文件夹中，这个文件夹就叫根文件夹，根就是树根的意思，这个文件夹又会包含其他文件夹，子文件夹中又会包含孙子辈的文件夹。这样层层的包含或者说从属关系，画成图就是一棵倒挂的树，而这个结构就是计算机科学中随处可见的树的概念，怎么样，简单吧？

然后就说到主角 Merkle Tree 了。在最底层，和哈希列表一样，我们把数据分成小的数据块，有相应地哈希和它对应。但是往上走，并不是直接去运算根哈希，而是把相邻的两个哈希合并成一个字符串，然后运算这个字符串的哈希，这样每两个哈希就结婚生子，得到了一个”子哈希“。如果最底层的哈希总数是单数，那到最后必然出现一个单身哈希，这种情况就直接对它进行哈希运算，所以也能得到它的子哈希。于是往上推，依然是一样的方式，可以得到数目更少的新一级哈希，最终必然形成一棵倒挂的树，到了树根的这个位置，这一代就剩下一个根哈希了，我们把它叫做 Merkle Root 。需要补充一下的是，根哈希有时候也叫主哈希 Master Hash ，也有人叫它顶哈希 Top Hash ，因为画图的时候通常都是倒着画这根树，反正不管叫什么，说的都是一个东西。

ZZNN7vz.jpg!web

image

于是我们看到 Merkle Tree 比普通的哈希列表稍微复杂了一点点，那么优点是什么呢？相对于 Hash List，Merkle Tree 的明显的一个好处是可以单独拿出一个分支来（作为一个小树）对部分数据进行校验，这给很多使用场合就带来了哈希列表所不能比拟的灵活和高性能。

fQjiYrv.jpg!web

image

总结

  • Merkle Tree 是三个概念的叠加，一个是哈希，第二个是哈希列表，第三个是树。
  • 哈希和树都是计算机科学中最基础最重要的两个概念，可以用在很多不同场合。单个哈希不能担当大文件在分布式点对点网络上的校验工作，于是我们有了哈希列表的概念。
  • Merkle Tree 可以认为是哈希列表的一个变体，让哈希列表变得更加灵活高效，因为每次校验都可以单纯拿出树的一个分支来操作。

参考：


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK