IPFS 数据结构 Merkle DAG

本文大纲：

1.散列（Hash）

二、Hash List（散列表）

3.默克尔树

4. Merkle DAG（Merkle directed acyclic graph以太坊dag计算器，默克尔有向无环图）

1.散列（Hash）

哈希是一种函数，它可以将任意长度的数据作为输入并将其映射到固定长度的输出。 例如，对于数据的完整性验证，最简单的方法就是对整个数据进行Hash运算，得到一个固定长度的Hash值，然后将得到的Hash值发布到互联网上，这样用户下载数据后，就可以再次对数据进行Hash运算，将比较运算的结果与网上公布的Hash值进行比较，如果两个Hash值相等，则说明下载的数据没有损坏。 之所以能做到这一点，是因为散列函数有两个重要的特点：一是输入数据的微小变化都会引起散列运算结果的重大变化，二是推导难度很大基于哈希输出的原始输入数据。

二、Hash List（散列表）

在点对点网络中传输数据时，会同时从多台机器下载数据，许多机器可以被认为是不稳定或不可信的。 为了验证数据的完整性，比较好的方法是将大文件分成小的数据块（比如分成256K的数据块）。 这样做的好处是，如果在传输过程中有一小块数据损坏了，只需要重新下载这块快数据，而不用重新下载整个文件。

如何保证小数据块没有损坏？ 只需要对每个数据块做Hash。 下载BT时，在下载真正完整的数据之前，我们会先下载一个Hash列表。 那么问题又来了，如何保证Hash列表本身是正确的呢？ 答案是把每一小块数据的Hash值放在一起，然后对这个长串进行Hash运算，从而得到Hash列表的根Hash（Top Hash或Root Hash）。 下载数据时，首先从可信数据源获取正确的根哈希，然后用它来验证哈希列表，再通过验证后的哈希列表来验证数据块。 下图中的第一行和第二行组成了一个Hash List。

3.默克尔树

Merkle树是美国计算机科学家Merkle在1979年申请的专利，可以看作是Hash List的推广（Hash List可以看作是一种特殊的Merkle Tree，即一棵树高为多叉的Merkle Tree 2).

在最底层，就像哈希表一样，我们将数据分成小块，并有相应的哈希与之对应。 但是往上走，并不是直接计算根哈希，而是将相邻的两个哈希组合成一个字符串，然后计算这个字符串的哈希，这样每两个哈希结婚生子以太坊dag计算器，就得到了一个“子” -哈希”。 如果底层的哈希总数是奇异的，那么末尾一定只有一个哈希。 此时直接对其进行哈希运算，因此也可以得到其子哈希。 所以往上推，还是老样子，可以用更少的数得到新一级的哈希，最终必然形成一棵倒树。 在树根的这个位置，这一代只剩下一个根哈希。 我们称之为默克尔根。

在 p2p 网络上下载数据之前，首先从可信来源获取文件的默克尔树根。 一旦获得根，就可以从其他不受信任的来源获得 Merkle 树。 根据可信根检查收到的默克尔树。 如果 Merkle Tree 损坏或伪造，则从其他来源获得另一棵 Merkle Tree，直到获得与可信树根匹配的 Merkle Tree。

Merkle Tree 和 Hash List 的主要区别在于 Merkle Tree 的一个分支可以直接下载并立即验证。 因为文件可以分成小的数据块，所以如果某个数据块损坏了，只要重新下载这个数据块即可。 如果文件很大，Merkle树和Hash链表都很大，但是Merkle树可以一次下载一个分支，然后立即对分支进行验证。 如果分支验证通过，则可以下载数据。 只有在下载了整个哈希列表后才能验证哈希列表。

4. Merkle DAG（Merkle directed acyclic graph，默克尔有向无环图）

Merkle DAG是ipfs开发团队在Merkle树的基础上构建的，是ipfs中的一种数据结构。 它类似于默克尔树，但又不完全相同。 例如：首先，Merkle DAG不需要进行树平衡操作，DAG可以有单节点； 第二，允许非叶子节点包含数据，有时小数据直接存在于非叶子节点中。 在叶节点上。

DAG的格式如下：

type IPFSLink struct {

  Name string             // link 的名字
  Hash Multihash        // 数据的加密哈希
  Size int                    // 数据大小
}

type IPFSObject struct {
  links []IPFSLink             // link数组
  data []byte        // 数据内容
}

这样，开发者就可以完全控制对象的数据字段，也就是说应用程序可以随意定义自己的数据类型和结构。 理论上任何数据结构都是可以的，比如我们的以太坊等公链数据，这里很有想象力。 . .

我们可以使用ipfs object命令来操作DAG对象，详见