资讯

【区块链那些事儿】1.4 Merkle Tree

在章节1.3中,我们已经深入浅出地探讨过“Hash值”,这一章来讨论Merkle Tree。Merkle Tree又称Hash树(Hash tree),因其概念由瑞夫·墨克((Ralph C. Merkle))于1979年申请专利,故亦称墨克树(Merkle tree),这也是我在Hash值之后编写这一章的原因。

上一章我们提到Hash算法接收一段明文后,会以一种不可逆的方式将其转化为一段长度较短、位数固定的散列数据,输入的明文与输出的散列数据一一对应,这样可以检测接受的文件是否完好,密码是否有误等等问题。

如果数据庞大,需要同时在多个机器上下载或者验证数据,有些数据损坏或者不稳定,这时采取单一Hash函数就会重新对整一个庞大文件重复验证下载,效率十分低下。打个比方,就像解一道复杂的数学题,数学题中应用到多个定理公式,你只是其中一个定理不熟悉,那么你整道题都解不出来。你唯一能做的,就是把会的定理列出来,然后解答相关的部分。这其实就是Hash list——把大的文件分割成小的数据块,对每一个数据块做Hash函数。在下载数据之前,先下载这个Hash列表,以此来比对数据,这样一来,如果小的数据块损坏了,则只需要处理这一小块数据就行了。你可以拿到正确部分的步骤分数,而计算机也能验证成功没有损坏和错误的部分,提高效率。此外,再对这个Hash list作一次Hash运算,确保Hash列表的正确性,运算能够得出的Hash值即Hash list的Root Hash。在校验Root Hash的准确性之后,即可用其对应的Hash list来校验所需的数据块了。

理解Hash list就能很好地理解Merkle tree,类似于特殊性与普遍性,Hash list是一种特殊的Merkle tree——即树高为二的多叉Merkle tree(见上图)。两者的区别主要在于,Merkle tree可以下载完一个分支后即时进行验证,而不必像Hash list那样只有下载完整个list才能进行验证,类比寻常的电影下载情况的话,Merkle tree不必下载完所以就可以观看已经下载好的部分,而Hash list需要你下载完整部电影。

在最底层,和Hash list一样,我们把数据分成小的数据块,有相应地Hash和它对应。但是往上走,并不是直接去运算根Hash,而是把相邻的两个Hash合并成一个字符串,然后运算这个字符串的Hash,这样每两个Hash就孕育出一个”子Hash“。如果最底层的Hash总数是单数,那到最后必然出现一个单身Hash,这种情况就直接对它进行Hash运算,所以也能得到它的子Hash。于是往上推,依然是一样的方式,可以得到数目更少的新一级Hash,最终必然形成一棵倒挂的树,到了树根的这个位置,这一代就剩下一个根哈希了,我们把它叫做 Merkle Root。

Merkle Tree的特点

*具有树结构;

*Merkle Tree叶子节点的value是数据集合的单元数据或者单元数据Hash;

*非叶子节点的value是根据它下面所有的叶子节点值,按照Hash算法计算得出。

Merkle Tree的应用

1. 数字签名

最初Merkle Tree目的是高效的处理Lamport one-time signatures。 每一个Lamport key只能被用来签名一个消息,但是与Merkle tree结合可以来签名多条Merkle。这种方法成为了一种高效的数字签名框架,即Merkle Signature Scheme。

2. P2P网络

在P2P网络中,Merkle Tree用来确保从其他节点接受的数据块没有损坏且没有被替换,甚至检查其他节点不会欺骗或者发布虚假的块。大家所熟悉的BT下载就是采用了P2P技术来让客户端之间进行数据传输,一来可以加快数据下载速度,二来减轻下载服务器的负担。BT即BitTorrent,是一种中心索引式的P2P文件分分析通信协议。

这篇文以感性的理解为主,如果还想探讨具体的算法操作,可以在文章下面留言。

编辑:valkrja

Previous ArticleNext Article

Leave a Reply

Your email address will not be published. Required fields are marked *

X