首页 > GameFi > 一文了解IPFS与Filecoin都在使用的去中心化数据结构—Merkle DAG
一文了解IPFS与Filecoin都在使用的去中心化数据结构—Merkle DAG
  • 路安
  • 2022-06-07
  • 7788
  • GameFi
广告
摘要:GameFi在之前介绍Filecoin技术概念的文章中,我们介绍了CID,它由加密哈希组成,相当于数据本身独一无二的指纹。这些数据又是如何分类的?我们今天就来了解另一个概念:Merkle DAG。数据结构是一种数据组织、管理和存储格式,可实现高效访问和修改。在不同的系统中,使用着不同的数据结构。比如
一文了解IPFS与Filecoin都在使用的去中心化数据结构—Merkle DAG

在之前介绍Filecoin技术概念的文章中,我们介绍了CID,它由加密哈希组成,相当于数据本身独一无二的指纹。这些数据又是如何分类的?我们今天就来了解另一个概念:Merkle DAG。

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

而在IPFSFilecoin这种去中心化系统中,信任度肯定是远远低于中心化系统的,那么为了适应这种环境,就需要一种有效的方法将数据结构连接在一起,同时仍然保持我们验证其完整性的能力。因此,这里就需要了解这种去中心化专用的数据结构,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。将这些节点的表示简化为两个属性:文件名,以及与文件内容对应的数据。这些属性捆绑在一起,构成了我们节点的数据,如下图橙色框所示。

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

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

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

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

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

一文了解IPFS与Filecoin都在使用的去中心化数据结构—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十分适用于内容寻址。

Merkle DAG为人们提供了一种在分布式网络上建模和共享数据的灵活方式。因此,它也是许多不同项目的基本构建块,如Git等版本控制系统、以太坊区块链IPFS等分布式Web 协议以及Filecoin等去中心化存储网络都使用Merkle DAG用于存储和通信数据。

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

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

免责声明:世链财经作为开放的信息发布平台,所有资讯仅代表作者个人观点,与世链财经无关。如文章、图片、音频或视频出现侵权、违规及其他不当言论,请提供相关材料,发送到:2785592653@qq.com。
风险提示:本站所提供的资讯不代表任何投资暗示。投资有风险,入市须谨慎。
世链粉丝群:提供最新热点新闻,空投糖果、红包等福利,微信:rtt4322。