数据结构是一种数据组织、管理和存储格式,可实现高效访问和修改。在不同的系统中,使用不同的数据结构。比如一台电脑中,都会使用一种称之为“链表”的数据结构,你可以高度信任这种在孤立环境中、中心化的数据结构。
然而,在去中心化的系统中,信任度肯定远远低于中心化系统,那么为了适应这种环境,需要一种有效的方法将数据结构连接在一起,同时仍然保持我们验证其完整性的能力。因此,这里就需要了解这种去中心化专用的数据结构,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为人们提供了一种在分布式网络上建模和共享数据的灵活方式。因此,它也是许多