IPFS 背后的数据结构 | 深入浅出区块链技术博客 - JOYK Joy of Geek, Geek News, Link all geek

本文翻译自： https://proto.school/#data-structures IPFS去中心化网络依赖于唯一的数据结构和链接策略。了解哈希(Hashing)、内容寻址(content addressing)、DAG和Merkle树让我们更深...

本文翻译自： https://proto.school/#data-structures

IPFS 去中心化网络依赖于唯一的数据结构和链接策略。了解哈希(Hashing)、内容寻址(content addressing)、DAG 和 Merkle 树让我们更深刻理解 IPFS.

1. 数据结构

在进入具体代码之前，让我们先花点时间看看去中心化 Web 的概念。暂时不会涉及代码，让你可以可以更快熟悉一些关键术语和概念。

让我们开始吧！

什么是数据结构？

无论你是否是程序员，你每天都被数据结构所包围。列表、词典和目录都有助于我们组织信息并考虑各种数据之间的关系。

来自 Wikipedia：

在计算机科学中，数据结构是一种数据组织，管理和存储格式，可以实现高效的访问和修改。更确切地说，数据结构是数据值的集合，描述它们之间的关系，以及可以应用于数据的功能或操作。

在编程中，数据结构无处不在。将数据组织成变量以便在程序中使用它们的方式涉及数十到数百万个数据结构。如果你是开发人员，你可能熟悉常见的数据结构：如数组、对象，图等。

去中心化的数据结构

在去中心化的的 Web 上，我们是从对等节点（Peers）而不是某个中央节点访问数据，所以我们需要专门的一些数据结构，来让我们验证和链接各种各样的数据。

去中心化系统中的数据结构必须是可验证的。在单一系统上，你会比较信任你机器内存或磁盘上使用的数据结构。但在去中心化的系统中，对等节点的信任度较低，甚至可能为零。

此外，大型数据结构需要能够在对等节点之间传播并链接在一起以便实现去中心化。与任何网页可以链接到不同位置的另一个网页的形式类似，去中心化的数据结构实现了可互连的数据网络。

2.中心化的 Web:基于位置寻址

在我们深入研究去中心化 Web 的共享工作方式之前，让我们先花点时间来研究一下传统方式是如何访问数据的。

通过 URL 寻址

URLs (统一资源定位符，Uniform Resource Locators) 是我们在中心化 Web 上分享数据的主要方式（这种方式我们都习惯）。URL 使我们能够在网络上创建链接和连接数据，因此它们有助于实现有价值的目的。（没有链接的话网络会非常糟糕！）但是，URL 基于存储数据的位置** ，而不是基于存储在那里的资源内容。我们称这种方式为位置寻址（location addressing），它会带来一些问题。

大多数人都有使用 URL 的体验，我们根据经验对它做了一些假设。例如当我们看到 https://www.puppies.com/beagle.jpg 时，我们可能会从文件名和扩展名猜测存储在该位置的数据是小猎犬的照片（JPEG 格式），但是我们无法仅通过 URL 验证这一点。很可能有一张藏在 beagle.jpg 的吉娃娃的照片，甚至更糟糕的是它居然是一只可爱的小猫！

通过域名、URL 描述了表示我们所请求数据的中央机构。即使网络是去中心化的，任何人都可以连接到其他任何人，但基于位置的引用要求了数据本身必须是中心化的，以便我们可以从中央机构获取到。除了上面提到的文件名假设，我们也会对这些权威或域名做出假设。例如我们假设在 puppies.com 上托管的文件比在 evilhacker.com 上托管的文件更安全，但我们无法确定是否真的如此。

所有这些不确定性也反之亦然。如果我们看到一张可爱的小狗的照片并被告知它被存储在网络上，但我们是无法猜出该图片 URL 的。我们不能确定域名，不能确定由谁托管（hosting），不能确定文件名。

中心化 Web 上的信任和效率

正如你所看到的，由于我们无法验证 URL 上的特定内容并且依赖于中心化机构（和人们的善良）来标记事物的真实情况，因此我们很容易被欺骗。

42000 人很可能存储完全相同的可爱小猎犬的照片，它们使用了不同的域名和不同的文件名。让我们面对现实吧，即使在我们自己的笔记本电脑上，大多数人都保存了与 download.pdf 相同的文档 download(01).pdf，或者使用 v1 或 2018-12-18 来命名相同的文档。Web 非常令人困惑，不同的 URL 上多次保存了非常混乱的数据，而且没有简单的方法来判断哪些数据项彼此相同。

必须要有更好的办法！

3. 去中心化的 Web:基于内容寻址

正如我们之前说的，中心化的 Web 依赖于权威机构来托管我们的数据，并使用 URL 作为地址来进行访问。但位置寻址不是唯一的选择。在去中心化的 Web 上，我们可以托管彼此的数据，并且通过一种特殊的链接方式让我们彼此间访问数据更可信和安全。

加密哈希是去中心化数据结构中最重要的工具函数。它打开了新链接形式的大门，我们称之为内容寻址，这样我们才能在没有中央机构的去中心化环境中链接数据。

哈希可以用于任何大小的数据，并为该数据返回单个固定大小的“哈希值”。哈希值是一个看起来像 gobbledygook 的字符串，你可以将其视为数据的名称。它可能是这样的：

zdpuAsHkamdCQgrDrNSwJVgjMkQWoLxdrccxV6qe9htipNein

说实话，由内容衍生的名字目前对人类来说并不友好（beagle.jpg 更具描述性！），但哈希值更加安全。原因如下：

加密哈希值是数据本身产生的，这意味着在相同数据上使用相同哈希算法将得到相同的哈希值。如果 Ada 和 Grace 都使用相同的去中心化 Web 协议（例如 IPFS）来共享完全相同的小猫照片，则两个图片文件会具有完全相同的哈希值。通过比较这些哈希值，我们可以保证这两张照片中的每个像素都是相同的。

加密哈希值也是独一无二的。这意味着如果 Grace 使用 Photoshop 从该小猫中删除了一些胡须，则更新后的图片会具有新的哈希值，并且很容易分辨 - 仅从哈希值，不用访问文件本身 - 它包含不同的数据。

去中心化 Web 上的信任

在中心化的网络上，我们信任某些机构，不信任其他机构。我们利用 URL 提供的线索尽力而为，但有些有恶意的人会使用位置寻址的缺点来欺骗我们。

在去中心化的网络上，我们能够传播并托管彼此的数据，我们可能不太了解托管数据的其他节点，但内容寻址为我们提供了一种信任他们所共享的数据的方法。通过内容寻址，我们不会被恶意行为者欺骗导致访问错误的数据。这就是加密哈希对去中心化网络如此重要的原因。

向对等节点查找内容

通过传统的位置寻址，我们知道需要访问域名 puppies.com 来查找 beagle.jpg 保存的数据内容。如果 puppies.com 域由于某种原因被破坏，我们将无法访问该图片。

去中心化网络的工作方式则是完全不同的。当我们想要一张可爱宠物的照片时，我们会通过其内容地址（哈希值）来进行查找。我们向谁查找呢？答案是整个网络！如果 Ada 在线，我们会看到她有我们正在寻找的内容，我们可以验证数据是否为我们正在寻找的内容，只要它具有匹配的哈希值。如果她下线，我们仍然可以从 Grace 或其他节点获得相同的照片。

由于我们使用哈希值来在去中心化的网络上请求数据，因此我们可以将哈希值视为链接，而不仅仅是数据名称。

4. 加密哈希与内容标识符（CID）

到目前为止，为了更有趣，我们一直在讨论可爱的图像，但是内容寻址可用于所有不同类型的文件和数据，从 JSON 对象到术语论文再到视频。为了使加密哈希工作，我们需要知道正在使用哪种数据格式并使用适当的工具。

解码数据结构

CID（内容标识符）是在去中心化　Web 上使用的一种特定形式的内容寻址。它是为 IPFS 开发的，但它具有广泛的含义。

CID 是包含加密哈希和编解码器（codec）的标识符，其中包含有关如何解释该数据的信息。编解码器(Codec)以某些格式对数据进行编码和解码。

+-------+------------------------------+
| Codec | Multihash                    |
+-------+------------------------------+

许多格式和协议已经使用了内容寻址。像 Git 以及以太坊和比特币协议，只是它们在解析数据以及加密哈希函数上有所不同。CID 让我们可以为任何系统机制创建通用标识符。

CID 是一种标识符，包含用于解释数据的编解码器和多重哈希值（multihash），它是一种自描述哈希值（标识了使用什么类型的哈希函数来创建该哈希值）。

+------------------------------+
| Codec                        |
+------------------------------+
|                              |
| Multihash                    |
| +----------+---------------+ |
| |Hash Type | Hash Value    | |
| +----------+---------------+ |
|                              |
+------------------------------+

不同数据结构之间的链接

CID 使我们能够构建链接了完全不同的格式数据的数据结构。想象一棵 JSON 对象树，这些树链接到 BSON 对象，而 BSON 对象也链接到 Git commits。（或者想象一个包含小狗图像和小猫视频的目录，以及一个包含有关长颈鹿文章的子目录。可能性无穷无尽！）沿着这棵树的内容都有加密 hash，这些 hash 允许我们分发和链接数据。

为什么在不同数据结构之间进行链接很重要？在中心化 Web 上，我们从文本调转到图像，从 logo 调转到主页，从电子邮件链到 PDF。链接将资源联系在一起，传达含义，并使网络互动性极强！

5. 默克尔树和有向无环图（DAG）

正如已经讨论的，去中心化 Web 依赖于链接的数据结构。看看它是怎样的？

默克尔树(Merkle trees)

Merkle 树（或简单的“哈希树”）是其中每个节点都被哈希化(hashed)的数据结构。

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

在 Merkle 树中，节点通过其内容地址（哈希值）指向其他节点。注意，当我们通过 hash 运算数据后，我们获得的是“hash”或“内容地址”（可以认为是一个链接），因此 Merkle 树是链接节点的集合。

如前所述，所有内容地址对于所表示的数据都是唯一的。在上图中，节点 E 包含对 节点F 和 节点G 的哈希的引用。这意味着 节点E 的内容地址（哈希）对于包含那些地址的节点是唯一的。

凌乱了么？让我们将其想象为一组目录或文件夹。如果我们在包含子目录 F 和 G 的情况下通过哈希算法运行目录 E，则返回的基于内容的哈希将包含对这两个目录的引用。如果我们删除目录 G，目录 E 不再具有相同的内容，因此将获得一个新的哈希。

当上面的树被构建时，根节点的最终内容地址（哈希）对于一棵树是唯一的，该树包含该树下所有的节点。如果任何节点中的数据甚至要更改一个字节，那么更改后的节点的哈希值就会更改，其所有父节点的哈希值也会更改。

现在了解了，我们将始终需要从叶节点到根节点去构建这颗树。