收藏本站 网站导航 开放平台 Sunday, June 26, 2022 星期日

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

来源 中金网 06-21 14:24
摘要: 在之前介绍Filecoin技术概念的文章中,我们介绍了CID,它由加密哈希组成,相当于数据本身独一无二的指纹。这些数据又是如何分类的?我们今天就来了解另一个概念:Merkle DAG。数据结构是一种数据组织、管理和存储格式,可实现高效访问和修改。在不同的系统中,使用着不同的数据结构。比如一台电脑中,都会使用一种称之为“链表”的数据结构,你可以高度信任这种在孤立环境中、中心化的数据结构。而在IPFS或Filecoin这种去中心化系统中,信任度肯定是远远低于中心化系统的,那么为了适应这种环境,就需要

  区块天眼APP讯 : 一文了解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的数据格式及其正式描述的生态系统,以支持广泛的数据交换。

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

更多区块链消息,请关注下载区块天眼APP,全球区块链监管查询APP 。

免责声明:中金网发布此信息目的在于传播更多信息,与本网站立场无关。中金网不保证该信息的准确性、真实性、完整性、有效性等。相关信息并未经过本网站证实,不构成任何投资建议,据此操作,风险自担。
天眼经纪商 更多
天眼交易所 更多
猜你喜欢