什么是默克尔树

  • R4y 
  • 未分类

许多区块链或是散列链都是基于一种叫做默克尔树的结构。与相对概念比较新的区块链技术相比,默克尔树最早诞生于1979年,由Ralph Merkle发明。

Hash

hash(散列算法),使我们生活中极为常用。其定义就是对任意长度的数据输入经过该算法后得到一个定长的输出。这样的一个映射具有唯一性,和单向性。

  • 唯一性 是指, 输入和输出是唯一对应的,不存在输入到输出的多个映射
  • 单向性 是指, 由输入很容易计算出输出,但是输出很难得到输入。(实际上使用大量计算数学(碰撞)上是可能找到,所以说是很难)。

    MD5 (“hellowolrd”) = 78932c6b96a60237f48407558e91cb23
    MD5 (“helloworlD”) = 9f7599f32fcd536ccfb8c668f735a588
    MD5 (“hellowor1d”) = 9063e763e70bea4fc4052ed7ac933428

这里可见,输入数据的小变化进行Hash之后的输出是天壤之别了已经,这个也是哈希技术的一个核心点叫做输入敏感性。所以散列技术也是用作数据指纹(FingerPoint)
常用的散列算法有 MD5,sha1,sha256等。

Hash Table

哈希表,现在就说BT下载了。(下的人越多,越快)要是究其原因就很简单,因为是P2P从大家哪里获取资源呀。

可是现在问题来了,我们从这么多的匿名用户地方获取我们的资源,我们怎么能保证这些提供资源的节点不作恶呢?万一我的100G的小姐姐,被突然换成了新闻联播怎么办???!!!

这里很自然就要用到上面的数据指纹技术了!我们先把这个小姐姐的MD5(指纹)接受过来,然后我们对下载的东西进行校验。一眼就看出了,这不是新闻联播,这样就不用傻傻的下上一天了。


其实上面我们设想的情景看似可以,可是我们忽略了一个问题,我在完成整个文件的下载前如果计算它的hash呢??? 实际上BT下载是把整个文件分散的存储到各个节点上,具体的结构看图。

hash
对每个小块先做一边hash校验,确保每个块的内容是正确的,日狗hash对不上就舍弃这个错误块,当整个文件下载完成之后,再进行一边整体的hash,用于确保我们整个文件的完整性。

DHT

如果在使用迅雷下载小电影的时候,有点开下载详情, 那么对DHT这个词汇一定不会太陌生。

DHT的全称是Distributed Hash Table, 直译过来的是分布式哈希表。哈希表(hash table)是一种很常见的数据结构。我们常用的数据结构Map就是哈希表的一直实现。实际上就是建立了一个键到散列的映射(Key-Value)键值对。

Merkle Tree

Merkle Tree可以看做Hash List的泛化(Hash List可以看作一种特殊的Merkle Tree,即树高为2的多叉Merkle Tree)。

不同于Hashlist,默克尔树是二叉结构,所有的根节点两两进行hash,得到其父节点,父节点再次进行两两hash,最终会得到一个根节点(Merkle Root)。

默克尔树在使用时,从根节点出发,同步下一个高度(D1)的数据(D2的hash),得到(D1)的两个hash值之后,自己进行hash校验。如果正确继续进行下一级的Hash的获取(这次将会有4个Hash),得到之后再次进行校验。正确则继续获取下一层的Hash,这样递归下去,直到得到存放在根节点的数据。

拓扑图如下,整体结构是一个倒挂的二叉树。
merkle

Merkle Tree的特点

  • MT是一种树,大多数是二叉树,也可以多叉树,无论是几叉树,它都具有树结构的所有特点;
  • Merkle Tree的叶子节点的value是数据集合的单元数据或者单元数据HASH。
  • 非叶子节点的value是根据它下面所有的叶子节点值,然后按照Hash算法计算而得出的。

留下点什么吧