Merkle Tree和Merkle DAG(默克尔树和默克尔有向无环图)
阿牛哥 Lv4

Merkle Tree和Merkle DAG看名字挺玄乎,其实非常简单,仅仅是哈希(HASH)和Tree(树)和DAG(有向无环图)的综合运用。

Merkle Tree

Merkle Tree在之前的文章《到底什么是区块链?区块链结构简述》中已经讲过,这里只讲一下Merkle Tree的特点和应用。

Merkle Tree的所有叶子节点都用于存储数据,而其他节点(非叶子节点)所存储的都是对该节点之下子节点哈希,只要知道最顶层的节点(Merkle Root)的值,就能验证其下所有节点的值是否正确,方法是计算每个节点的子节点的哈希,将子节点哈希合并再计算一次哈希就能得到当前节点的哈希,一旦树中的任何一个节点被篡改都会导致与上一级节点计算的哈希值不相符。可见,Merkle Tree自带验证能力,只要能确定Merkle Root是可信的,那么这棵树下的所有数据都是可信的。

另一方面,当我们只需要某个叶子节点的数据时,只需要下载这一条路径上的哈希值就能确信下载的叶子节点数据是否可信。这正是Merkle Proof(默克尔证明)的核心思想。

Merkle Tree

Merkle DAG

理解了Merkle Tree和Merkle Proof后,我们来看Merkle DAG。按照What is a Merkle DAG? 的解释,Merkle DAG相比Merkle Tree有以下不同:

  1. Merkle DAG可以不是平衡树,也就是说每一层有深有浅,比如有的叶子在第3层,有的在第4层,等等。
  2. 非叶子节点可以包含数据。
  3. 我觉得还应该再加一点,就是Tree只能有一个根节点,而DAG没有这个限制,这样才是一张有向无环图。

Merkle Tree有以下特点:

  • Merkle Tree上的所有非叶子节点的哈希值都是从其子节点计算而来。
  • Merkle Tree的结构是递归的,任何一个节点及其子节点拎出来都会构成一个新的Merkle Tree。
  • Merkle DAG的节点是不可更改的。任何子节点的变化都会重新计算出新的父节点,DAG由此产生。
  • 某个节点变化产生新的父节点,而其他部分并没有变化,此时将会有部分节点同时属于两个根节点。换言之,一个节点可以有多个父节点。

Merkle DAG

基于以上特点,Merkle DAG非常适合用来存储分布式文件,IPFS正是利用了这一点。关于存储细节,请看下一期文章。

参考:Merkle Directed Acyclic Graphs (DAGs)