+-
Filecoin密码中的Merkle Tree理解起来并不难

在之前的文章中我们有浅析过哈希加密是什么,也知道了使用哈希加密后文件的安全性得到了保障。单个文件或小文件在传输时通过哈希加密、解密就好,操作也比较简单,只需要获取一个哈希值。但若是大文件或者被切片成n份的文件,我们在获取时难道要用n个哈希值来挨个解密获取吗?有没有什么“偷懒”的方法,一次搞定呢?答案是肯定,这时候我们就需要认识一个新的概念——Merkle Tree(默克尔树)了。

Merkle Tree是什么?

Merkle Tree中文名是默克尔树,顾名思义是一个姓Merkle的人发明的,又因为逻辑图梳理出来像树的结构,所以叫默克尔树。

... 图1 Merkle Tree示意图

当我们想验证区块内交易时,如果数据不稳定或损坏,如果只是单纯的使用hash,就需要全部重新下载,即浪费时间又占用空间,若是使用了Merkle Tree,则仅需定位到损坏位置,只需下载验证这一个分支就可,Merkle树会大大减少数据的传输量以及计算的复杂度。

Merkle Tree的计算逻辑是什么?

merkle tree通常是一个hash二叉树,最下面一层是交易数据,每一个交易数据L都可以计算出一个Hash得到H,每两个H继续向上计算就会得到一个新的Hash值N,向上层层计算就会得到Merkle root。Merkle root就是每一个区块中的头部哈希值,每一个区块都是通过这个ROOT值来连接的,它包含了所有块内交易的哈希值。

由于blockchain里面都merkle运算要求叶子节点是偶数,所以,当一个区块内包含交易数量为奇数时,最后一个交易会复制一份,凑成偶数。

Merkle tree是基于Hash的密码学来确保数据传输的完整性,已经用在许多分布式文件系统,P2P网络、证书验证、可信计算、NoSQL等方面。比如一些游戏下载,会将大文件分割为小文件,每份文件都有一个hasa,每块从不同的网络节点下载,最后组成一个完整的文件,最后使用 Merkle来进行完整性验证。这样不仅避免计算整棵Hash树,而且提升了检索效率与空间。