"本文翻译自 IPFS 社区教程 ProtoSchool。ProtoSchool 是一个可以交互式学习 IPFS 编程的网站,涉及代码的部分大家可到该网站上直接运行测试! 本文接上篇 IPFS 去中心化数据结构(三)。 LESSION 5 - 默克尔树和有向无环图(DAG) 正如我们所讨论的,去中心化的 Web 依赖于链 .."

IPFS 去中心化数据结构(四)

本文翻译自 IPFS 社区教程 ProtoSchool。ProtoSchool 是一个可以交互式学习 IPFS 编程的网站,涉及代码的部分大家可到该网站上直接运行测试!

本文接上篇 IPFS 去中心化数据结构(三)

LESSION 5 - 默克尔树和有向无环图(DAG)

正如我们所讨论的,去中心化的 Web 依赖于链接的数据结构。让我们来探索一下它们的样子。

默克尔树

默克尔树即“哈希树”,是一种树形数据结构,其中每个节点都是哈希值。

               +--------+
               |        |
     +---------+  root  +---------+
     |         |        |         |
     |         +----+---+         |
     |              |             |
+----v-----+  +-----v----+  +-----v----+
|          |  |          |  |          |
|  node A  |  |  node B  |  |  node C  |
|          |  |          |  |          |
+----------+  +-----+----+  +-----+----+
                    |             |
              +-----v----+  +-----v----+
              |          |  |          |
              |  node D  |  |  node E  +-------+
              |          |  |          |       |
              +----------+  +-----+----+       |
                                  |            |
                            +-----v----+  +----v-----+
                            |          |  |          |
                            |  node F  |  |  node G  |
                            |          |  |          |
                            +----------+  +----------+

在默克尔树中,节点通过内容地址(哈希值)指向其他节点。当我们通过加密哈希运算数据后,我们会得到一个“哈希值”或“内容地址”,我们可以将其视为一个链接,因此一颗默克尔树是链接节点的集合。

如前所述,所有内容地址都是唯一的。在上图中,节点 E 包含对节点 F节点 G 的哈希引用。这意味着节点 E 的内容地址(哈希值)对于包含这些地址的节点是唯一的。

有点晕么?让我们把它想象成一组文件夹。如果我们通过哈希算法运行文件夹 E,同时它包含子文件夹 F 和 G,我们获取的内容生成哈希值对其当前内容是唯一的。如果我们删除文件夹 G,就像 Grace 从她的小猫照片中删除那个胡须,则以前称为 E 的文件夹不再具有相同的内容,因此它会得到新的哈希值。

在构建上面的树时,根节点的最终内容地址(哈希值)对于包含该树一直向下的每个节点的树是唯一的。 如果任何节点中的数据即使是单个字节发生改变,则改变的节点的哈希值也将改变,其所有父节点的哈希值都会被改变。

你可能注意到了,程序员将始终需要从底部向上来构建这棵树,从叶节点到根节点。

有向无环图(DAG)

dag.png

DAG 是“Directed Acyclic Graph”的首字母缩写。这是一种描述特定类型的默克尔树(哈希树)的独特方式,其中树中的不同分支可以在单个前向方向上指向树中的其他分支,如上图所示。


(完)

  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    20 引用 • 209 回帖 • 221 关注
  • 去中心化
    14 引用 • 90 回帖 • 2 关注
  • 数据结构
    51 引用 • 99 回帖 • 1 关注
  • dag
    1 引用 • 7 回帖
7 回帖   
请输入回帖内容...
  • pangwen  

    感觉这种牵一发而动全身,会不会影响性能啥的😳

    1 回复
  • 88250      

    哈希算法速度很快的,并且文件是分片存取的,所以对性能影响不大。性能取决于网络中节点的个数,节点越多速度越快。

    1 回复
  • qiankunpingtai        

    所有节点的地址随着内容的改变处于不断改变中,只有组织内的节点才能实时寻路到其他节点,组织外的人持有节点地址随时可能失效!是这样吗?感觉一个节点树就和 linux 的目录结构一样,对系统内透明,对系统外完全就是屏蔽呀。

    1 回复
  • 88250      

    文件根节点也是“组织内的节点”,所以其实都在变化,解决这个问题是通过网络全局的命名系统 IPNS

    1 回复
  • qiankunpingtai        

    才发现你这个是译文呀,你的英文可以呀!我也就能看懂一部分,没有看中文爽快!

    1 回复
  • 88250      

    机翻 + 人工微调 😄

    1 回复
  • qiankunpingtai        

    国内都是以应用为主,比较先进的理念都是外国人先提出来的,要想往比较前沿的方向跑就得翻译老外的文章!

请输入回帖内容 ...