区块链 | IPFS：Merkle DAG

🦊原文：IPFS: Merkle DAG 数据结构 - 知乎
🦊写在前面：本文属于搬运博客，自己留存学习。

1 Merkle DAG 的简介

Merkle DAG 是 IPFS 系统的核心概念之一。虽然 Merkle DAG 并不是由 IPFS 团队发明的，它来自于 Git 数据结构，但是 IPFS 团队对其进行了改造。可以肯定的是，IPFS 团队并非直接拿来使用，而是在原有基础上进行修改以更适合项目的使用。

Merkle DAG 的全称是 Merkle Directed Acyclic Graph，即默克有向无环图。它是在 Merkle Tree 基础上构建的，Merkle Tree 是由美国计算机学家 Merkle 于 1979 年申请的专利。Merkle DAG 跟 Merkle Tree 很相似，但不完全一样，比如：Merkle DAG 不需要进行树的平衡操作，非叶子节点允许包含数据等。

2 Merkle DAG 的功能

Merkle DAG 拥有如下的功能：

• 内容寻址：使用多重哈希来唯一标识一个数据块的内容；
• 防篡改：通过检查哈希值来确认数据块的内容是否被篡改；
• 去重：由于内容相同的数据块哈希值是相同的，因此很容易去除重复的数据，以节省存储空间；

3 IPFS 的数据对象格式

IPFS 的数据对象格式如下：

type IPFSLink struct {
	name string 		// Link的名字
	hash Multihash 		// 数据的加密哈希
	size int 			// 数据大小
}

type IPFSObject struct {
	links []IPFSLink 	// Link数组
	data []byte 		// 数据内容
}

这段代码是用 Go 语言写的，Go 语言又称为 Golang 语言。

在 IPFS 网络中，大的文件通常会被分割成多个小片。每个碎片拥有自己的哈希值，再根据碎片的哈希值生成对应的「链接」。按照每个碎片在文件中出现的顺序，使用它们的链接生成「链接数组」，再使用「链接数组」生成最终的顶层「对象」，以此来表示文件。

除此之外，IPFS 赋予应用完全的数据字段控制权，允许应用自由定义数据类型和结构，包括那些 IPFS 系统无法直接识别的复杂数据结构，从而提供了极大的灵活性。

4 IPFS 的数据对象如何工作

第一步：准备数据

一张图片，文件名为 rainy_day.jpg，文件大小为 1MB，如下图所示：

说明：我没有采用原博的图片，因为图片上的水印导致图片内容改变了。如果你想自己测试的话，那么建议使用一个超过 256K 的数据文件，因为 IPFS 当前的数据分片标准是 256K 一个。

第二步：添加文件

执行 ipfs add 命令以添加文件：

$ ipfs add rainy_day.jpg
added QmQhSvoNcYCXk7JAjXzkQN8TmQaA8wP4oZxB9EmDNXiUzd rainy_day.jpg

说明：在本文中，以 $ 开头的是命令，不以 $ 开头的是输出结果。

第三步：查看文件分片

执行 ipfs ls -v 命令以查看文件分片：

$ ipfs ls -v QmQhSvoNcYCXk7JAjXzkQN8TmQaA8wP4oZxB9EmDNXiUzd

输入的就是刚才得到的哈希值。

如下所示，可以看到文件被分成了 5 个区块（block），每个区块的大小为 256K，除了最后一个。

Hash Size Name
QmTKqvEAgEaWfJVZjq7drgQUBLxwWzyrCTBVzZ9dcBc3Cq 262158
QmQCxXC4EUqw9gRmiRStNfYSr15oyPTV6yVJ7G9KBzecVt 262158
QmT4vb3Ujn6RpLijb8z4jFooCWmNqgvPbSagQf1WgdJjZe 262158
QmZ4UtPdZ5aBL4g55Yb7erWVtJGEBwhyGd5dCwYx28CafK 262158
QmcbpccHVURapPiKPn37yG14ar1myeFvTdqm215RRKcKqW 3071

由此可见，当执行 ipfs add 命令时，文件 first.JPG 的数据被分割成多个相等大小的区块，同时构建一个 Merkle DAG 来将这些数据区块整合成一个有序的结构。如下图所示：

上图源自 IPFS 官方在线测试网站：https://dag.ipfs.tech/

5 IPFS 的查询命令

我们还可以使用 IPFS 提供的命令来查看数据块（block）的信息，数据块下面还允许链接子数据块（sub-block），本文的例子中没有涉及。

相关的查询命令如下：

• ipfs block stat：查询数据块的大小，不包含子块；
• ipfs refs：列出数据块的子块信息；
• ipfs ls or ipfs object links：显示所有的块和子块的大小；

例如：

$ ipfs block stat QmTKqvEAgEaWfJVZjq7drgQUBLxwWzyrCTBVzZ9dcBc3Cq
Key: QmTKqvEAgEaWfJVZjq7drgQUBLxwWzyrCTBVzZ9dcBc3Cq
Size: 262158

既然每个数据块都能被我们查询到，那么我们可以手动将这些数据块重新组合起来。

比如刚才那张图片，就可以使用命令：

$ ipfs cat hash1 hash2 hash3 ... hashn > rainy_day.jpg

从而得到上面的那张照片，有兴趣的读者可以自己动手试试。

6 直接操作 Merkle DAG

IPFS 可以让我们直接操作 Merkle DAG 的数据，举个例子：

$ echo "hello world" | ipfs block put
QmZjTnYw2TFhn9Nn7tjmPSoTBoY7YRkwPzwSrSbabY24Kp

$ ipfs block get QmZjTnYw2TFhn9Nn7tjmPSoTBoY7YRkwPzwSrSbabY24Kp
hello world

上述命令的意思应该是：将 “hello world” 编码为一个 IPFS 块，IPFS 返回该数据块的哈希值。然后，可以通过该哈希值访问到数据内容是 “hello world”。

怎么样？很魔性吧，我们完全控制了数据块中的数据内容和结构，IPFS 把 Merkle DAG 的操作权限几乎全部下放给了开发者，开发者可以很容易构造出来自己的数据结构。

IPFS 在论文里面提出了可以自己一些潜在的数据结构：

• 键值对存储（Key-value Stores）
• 关系型数据库（Traditional Relatioinal Databases）
• 三元组存储（Linked Data Triple Stores）
• 文档发布系统（Linked Document Publishing Systems）
• 通信平台（Linked Communications Platforms）
• 加密货币区块链（Cryptocurrency Blockchains）

在此基础上开发者还可以完全自定义自己的数据结构。看到最后一条了吧，IPFS 为所有的区块链准备好了数据存储结构，IPFS 将作为区块链的基础设施存在。