MerkleDAG：IPFS与Filecoin的数据结构解析

数据结构是一种数据组织、管理和存储格式，可实现高效访问和修改。在不同的系统中，使用不同的数据结构。比如一台电脑中，都会使用一种称之为“链表”的数据结构，你可以高度信任这种在孤立环境中、中心化的数据结构。

然而，在去中心化的系统中，信任度肯定远远低于中心化系统，那么为了适应这种环境，需要一种有效的方法将数据结构连接在一起，同时仍然保持我们验证其完整性的能力。因此，这里就需要了解这种去中心化专用的数据结构，MerkleDAG。

我们先来了解一些基础概念。一般来说，我们常见的存储结构是这样的：如果需要找一个文件，我们会先从根目录pics开始，逐步深入层次结构，以到达所需文件。这种模式就叫做有向图（Directed Graphs），每条边都有某种固定方向，即一个目录包含一个文件，但一个文件不包含它的目录，该方向由单向箭头指示。就像家中的族谱图。

在这张图中，一般称有子节点的中间节点为“父节点”，没有父节点的节点（如上图的pics）则被称为根节点，没有子节点的（如freshwater）为叶节点。如果图中没有循环，那么该图又被称为无环图（Acyclic Graphs）。即图中的任何节点，无法沿着图的边缘从该节点导航回其自身。在像上图这样文件层次结构这样的有向图中，只能从父节点移动到子节点。符合上述两种特征的结构图，则被称为有向无环图（Directed Acyclic Graphs），简称为DAG。

如果不用画图的方式，要如何表示DAG呢？我们知道，CID可以唯一的标识一个节点，那么也可以使用它来表示从一个节点到另一个节点的边。这样，就创建了一种特殊的DAG，即MerkleDAG，任何以这种方式利用内容寻址的图形表示都必然是一个DAG。

现在来了解如何构建MerkleDAG。继续以上图的文件目录为例，第一步是对图的叶节点进行编码，并为每个叶节点提供一个CID。将这些节点的表示简化为两个属性：文件名，以及与文件内容对应的数据。这些属性捆绑在一起，构成了我们节点的数据，如下图橙色框所示。

节点上方的标签“baf…1”是CID的简化表示，它是通过加密哈希算法根据数据本身得出的，要注意，这个标签不是节点的一部分。

可以通过首先创建叶节点来开始构建MerkleDAG——层次结构中的每个文件都有一个节点，然后用其CID标记每个节点。中间节点与叶节点有些不同，这些节点中的每一个还将包含目录，目录节点的“内容”是它包含的文件和目录的列表，而不是任何特定文件的内容。可以将其表示为CID列表，每个CID都链接到图中的另一个节点。这样一来，上图DAG使用MerkleDAG构建，就会变成这样：

在MerkleDAG中，每个节点的CID取决于它的下一层，因此只要有任何一个内容有一点不同，标签CID的哈希值也会随之改变。这是MerkleDAG最精髓的部分。但在一个分支中进行的更改不会强制更改其他分支中节点的CID，节点的CID仅响应于其自身数据或随着其后代数据的变化而变化。例如，更改“blowfish.png”不需要更改baf...1、baf...2、baf...4、baf...5或baf...7。

看完上文的内容，想必你已经大致了解MerkleDAG到底是什么，那它又有什么属性呢？

1. 可验证性：在MerkleDAG中，每个节点的CID依次取决于其每个子节点的CID。根节点的CID不仅唯一标识该节点，还唯一标识它可以将CID的安全性、完整性和持久性保证扩展到我们的数据结构本身，而不仅仅是它包含的数据。

2. 任何节点都可以是根节点：DAG可以看作是递归数据结构，每个DAG由较小的DAG组成。在上文示例中，CID“baf...8”标识了一个DAG，但CID“baf...6”也是如此——它只是标识了一个较小的DAG，即由“baf...8”标识的DAG的子图”。给定正确的上下文，相应的节点都是根节点。这一点有什么用呢？如果我们要检索结构为DAG的内容，不必检索整个DAG，只需可以选择检索一个子图，由其自己的顶部节点的CID标识（此子图的顶部节点将成为其根节点）。如果想与其他人共享该子图，不必包含我们最初从中检索数据的较大图的上下文——只需发送子图CID。因为DAG的CID，即其根节点的CID，取决于根节点的后代而不是其祖先。

3. 可分配性：MerkleDAG还继承CID的可分配性。该DAG的所有者是任何拥有DAG的人都能够充当该DAG的提供者。当我们检索编码为DAG的数据时，比如文件目录，可以利用这一事实并行检索节点的所有子节点。文件服务器不仅限于集中式数据中心，这让数据覆盖范围更广。

最后，因为DAG中的每个节点都有自己的CID，所以它所代表的DAG可以独立于它本身嵌入的任何DAG进行共享和检索。因此DAG十分适用于内容寻址。MerkleDAG为人们提供了一种在分布式网络上建模和共享数据的灵活方式。因此，它也是许多