一文了解IPFS与Filecoin都在使用的去中心化数据结构——Merkle DAG - 哔哩哔哩

　　一文了解IPFS与Filecoin都在使用的去中心化数据结构——Merkle DAG

　　我们先来了解一些基础概念。一般来说，我们常见的存储结构是这样的：

　　如果需要找一个文件，我们会先从根目录pics开始，逐步深入层次结构，以到达所需文件。

　　这种模式就叫做有向图（Directed Graphs），每条边都有某种固定方向，即一个目录包含一个文件，但一个文件不包含它的目录，该方向由单向箭头指示。就像家中的族谱图。

　　在这张图中，一般称有子节点的中间节点为“父节点”，没有父节点的节点（如上图的pics）则被称为根节点，没有子节点的（如freshwater）为叶节点。

　　如果图中没有循环，那么该图又被称为无环图（Acyclic Graphs）。即图中的任何节点，无法沿着图的边缘从该节点导航回其自身。在像上图这样文件层次结构这样的有向图中，只能从父节点移动到子节点。

　　符合上述两种特征的结构图，则被称为有向无环图（Directed Acyclic Graphs），简称为DAG。

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

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

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

　　可以通过首先创建叶节点来开始构建Merkle DAG——层次结构中的每个文件都有一个节点，然后用其CID 标记每个节点：

　　中间节点与叶节点有些不同，这些节点中的每一个还将包含目录，目录节点的“内容”是它包含的文件和目录的列表，而不是任何特定文件的内容。可以将其表示为CID列表，每个CID都链接到图中的另一个节点。这样一来，上图DAG使用Merkle DAG构建，就会变成这样：

　　在Merkle DAG中，每个节点的CID取决于它的下一层，因此只要有任何一个内容有一点不同，标签CID的哈希值也会随之改变。这是Merkle DAG最精髓的部分。

　　但在一个分支中进行的更改不会强制更改其他分支中节点的CID，节点的CID仅响应于其自身数据或随着其后代数据的变化而变化。例如，更改“blowfish.png”不需要更改 baf...1、baf...2、baf...4、baf...5 或 baf...7。

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

　　1 可验证性

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

　　2 任何节点都可以是根节点

　　DAG可以看作是递归数据结构，每个DAG由较小的DAG组成。在上文示例中，CID“baf...8”标识了一个DAG，但 CID“baf...6”也是如此——它只是标识了一个较小的DAG，即由“baf...8”标识的 DAG 的子图。给定正确的上下文，相应的节点都是根节点。

　　这一点有什么用呢？如果我们要检索结构为DAG的内容，不必检索整个DAG，只需可以选择检索一个子图，由其自己的顶部节点的CID标识（此子图的顶部节点将成为其根节点）。如果想与其他人共享该子图，不必包含我们最初从中检索数据的较大图的上下文——只需发送子图CID。因为DAG的CID，即其根节点的CID，取决于根节点的后代而不是其祖先。

　　3 可分配性

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

　　最后，因为DAG中的每个节点都有自己的CID，所以它所代表的DAG可以独立于它本身嵌入的任何DAG进行共享和检索。因此DAG十分适用于内容寻址。

　　IPFS等分布式Web 协议以及Filecoin等去中心化存储网络都使用Merkle DAG用于存储和通信数据。

　　这种广泛使用说明Merkle DAG有在不同项目之间通信的潜在能力。为了实现这一点，IPLD项目正在开发一个基于Merkle-DAG的数据格式及其正式描述的生态系统，以支持广泛的数据交换。

　　这些技术为人们提供了一种遍历和理解数据结构的方法，而也正是它们构成了以相互关联和相互理解为主的数据生态系统，在未来，这将会成为全球网络的基础。