一文读懂Filecoin自认证存储设计

本文由IPFS原力区 Taosheng shi 原创

Filecoin项目的发起人胡安于2019/10/22，在‘slack’讨论群中公开了filecoin数据存储格式的细节，供团队讨论和审阅。

众所周知，filecoin是基于存储（IPFS）的区块链项目，数据存储设计，特别是区块链与数据存储的配合就至关重要。据笔者观察，协议实验室一直善于在借鉴和研究已有的成熟技术之上，进行基础性的创新。本文不仅对胡安公布的ppt进行解读，也会梳理其借鉴的设计思想。

思想来源

目前主流的服务器都安装类Unix的操作系统，其中文件存储都是基于POSXI 的IO语义。POSIX I/O API 是我们最熟悉的，因为它就是应用程序读写数据调用的接口，包括open()/close()/read()/write()/lseek()等等。POSIX I/O API 是当今应用程序和程序库的一个必要组成部分。一个典型的 POSXI  IO 程序的流程如下：

使用open()打开文件；

然后read()文件数据；

接着seek()到文件中的新位置；

在该位置write()一些数据；

最后close()文件。

伴随着类Unix系统的流行，文件组织的目录树结构也深入人心：

POSXI 抽象的语义在很长的时间里成为类Unix环境下的事实标准，但随着技术的发展，也逐渐无法满足新的业务需求，POSXI 开始被业内所诟病，详细请参阅《糟糕的 POSIX IO》一文。

filecoin数据存储借鉴了传统的POSIX语义，在IPFS的设计中，文件可能太大而无法容纳在单个数据块中，因此需要元数据来将其所有数据块链接在一起。也可能是符号链接或目录，因此它需要元数据才能链接到其他文件。因此，IPFS中的UnixFS是一种数据格式，用于表示IPFS中的文件及其所有链接和元数据，并且宽松地遵循POSIX语义。将文件添加到IPFS时，您将以UnixFS格式创建一个块（或块树）。

Textile 网络

Textile的线程（Thread）抽象也是协议实验室借鉴来源。线程是Textile的加密，可恢复，基于模式和跨应用程序数据存储的基础。每个线程的核心都是一个密钥。只有拥有密钥的对等方才能解密线程内容或跟随链接。与区块链不同，线程不是基于共识的思想。相反，他们遵循类似于全息链的以代理为中心的方法。每个对等方都具有线程访问控制和存储的权限。

因为线程只是更新消息或块的哈希链，所以它们可以表示任何类型的数据集。一些块指向存储在IPFS上的链下数据。例如，一组照片，PDF甚至整个网站。应用程序开发人员能够通过使用schmea在线程中添加结构并使它们与其他应用程序互操作。

添加到线程的所有数据最终都将作为文件。大多数情况下，schema用于在线程中定义一种或多种数据类型，以便其他用户和应用程序可以理解它。目前支持以下输入类型：原始数据Blob，图像，EXIF数据和JSON文档。

一个个线程只能有一个模式。它具有两个主要功能：

定义线程的数据DAG结构

定义从输入生成此结构所需的转换顺序

如上图所示：通过定义一个数据工厂，就可以转换任意格式的数据：

Cryptree 也是filecoin数据存储的借鉴来源，由《Cryptree: A Folder Tree Structure for Cryptographic File Systems》一文详细介绍。Cryptree是一种加密树结构，它有助于在不可信存储上实现文件系统的访问控制。Cryptree利用文件系统的文件夹层次结构实现高效、直观、简单的访问控制。最突出的是Cryptree可以递归地在固定时间内访问一个文件夹及其所有子文件夹，并且访问权的动态继承从本质上防止了访问权的分散，另外Cryptree允许某人访问文件或文件夹而不暴露其他访问者身份。为了推理和形象化加密树，论文引入了加密链接的概念。我们描述了在我们自己的文件系统中用来强制读写访问的加密树。

加密链接是一个重要基本抽象，也是协议实验室的重要借鉴之处。加密链接原理上很简单，从一个密钥K1到另一个密钥K2的加密链接使每个拥有K1的人都能推导出K2。连接多个链接可以构建加密数据结构。注意，当K1变脏时，K2也变脏。论文区分了两种类型的密码链路：对称链路和非对称链路。更多内容参阅《Cryptree: A Folder Tree Structure for Cryptographic File Systems》。

Filecoin数据存储借鉴的Git分支的原理。要真正理解Git管理分支的原理，需要打开Git的引擎盖，了解Git如何存储数据。

假设你的目录下面有三个文件，然后执行第一步add（stage）第二步commit。

$ git add README test.rb LICENSE

$ git commit -m ‘initial commit of my project’

add操作计算文件的校验和（SHA-1 ），存储这个版本的文件到Git仓库中（blob）。

commit操作计算所有目录和文件的校验和（SHA-1 ），然后存储到tree对象中。commit操作还会创建一个 commit 对象存储元数据和指向tree对象的指针。

现在，Git仓库包含五个对象，对应于每个文件的三个blob对象，包含目录内容和文件映射的tree对象，包含元数据信息和指向tree指针的commit对象。

区块链基于时间戳的链式存储也是filecoin数据存储借鉴来源。如下图所示，区块链存储结构众所周知，这里不再赘言。

总体设计

基于以上思想来源，包含了一下关键要点：

文件存储的目录结构

链式加密

链式存储

元数据设计

分支管理

Merkle tree

这些为filecoin数据存储的Dags + Pieces 设计奠定了基础。filecoin把其数据存储更为自认证归档存储（ Certified ARchives）。filecoin自认证归档存储分为三部分：证明树（Proving Tree）、真实数据载荷（payload）和填充数据（padding）。

其中，证明树是一个merkle tree，其root id为PieceCID，真实数据载荷的merkle root为PayloadCID。

需要padding数据的原因是，merkle tree是一个平衡二叉树，对于无能满足约束的数据填充一些数据来补齐。

显然，证明树需要真实数据之外的额外存储空间，为了优化带宽占用，可以不存储证明树部分，只存储证明树的root id（证明树的内容可以临时从真实数据中构建）。然后证明树的merkle root id（CommD） 和真实数据的merkle root id一起构成自认证归档格式的元数据部分，然后这部分元数据和真实数据一起，序列化为filecoin数据存储格式的CAR文件（Certified ARchives）。

所谓自认证归档存储，其实就是把IPLD 数据序列化为顺序字节，然后把证明树内容和真实数据内容一起序列化存储，就是自认证归档存储。如下图所示。

filecoin既支持原始数据的自认证归档存储，也支持数据副本的自认证归档存储。

下图是原始数据分片的自认证归档存储过程，上面已经解释，不在赘述。

对于数据副本的自认证归档存储，需要引入filecoin 的sector的概念。sector是一个数据结构，用于存储和证明一个或多个数据分片。从原始数据构建副本的过程被成为seal，这个过程同样是构建自认证归档存储的过程，其证明树的merkle root id 是CommR。

IPFS unixfs 设计

由于filecoin的自认证归档存储基于IPFS的数据存储格式，传统posix 语义的文件需要转换为IPFS unixfs的文件格式，才能比较方便地参与filecoin区块链的复制证明和时空证明。

IPFS unixfs 使用可插拔的数据分片算法对传统posix 语义的文件进行分片。传统posix 语义的文件是顺序存储的字节，IPFS unixfs 是基于分片的有向无环图。IPFS unixfs的最小单位是分片，这些分片（leaves）被称为叶子或者数据片（pieces），为了构建有向无环图，必然需要引入中间文件对象（File objects），这些中间对象通过一定拓扑hash为一个root CID。IPFS unixfs 这种构建图式数据存储的方式被称为IPLD，即是星际链式数据，这也是IPFS 内容寻址的基础。

如下图所示，ipfs文件系统存储一只猫的图片形象表示：

IPFS unixfs的这种设计代表了文件存储范式的一种转变，即从posix 语义（单机顺序字节存储、文件名检索）向网络化链式存储的转变（全网链式存储，内容寻址）。

IPFS unixfs 目录设计

目录设计，或者是元数据设计，是所有文件系统设计的重中之重。对比传统posix 语义的目录设计和IPFS unixfs的目录设计，

可以更好的理解IPFS unixfs是如何把传统类unix文件系统中文件转化为链式文件存储的。

传统文件系统组织成树形的目录和文件，要么存储在本地，要么存储在云中。这种树形结构已经成为人们认知数据存储的基本方式。类似于这种组织方式，IPFS unixfs使用IPLD graph来表示目录，来指向其他目录或文件。

由于IPLD graph的这种递归指向方式，IPFS unixfs可以存储超大文件。

当然，IPFS unixfs也可以单机存储，把IPLD目录对象单独存储一部分，和数据文件一起序列化存储。

IPFS unixfs 应用

Textile本身就是基于ipfs的，非常适合存储在filecoin中。

Peergos cryptree 内置了IPFS unixfs 能力，可以输出加密的IPLD graph。

Git 也是基于DAG的方式存储。

一些区块链的数据存储格式本身就是IPLD 组织方式。可以通过修改代码存储为IPLD存储方式。

参考资料：

《糟糕的 POSIX IO》

《Cryptree: A Folder Tree Structure for Cryptographic File Systems》

—END—

【IPFS原力区】

价值观：价值 共建 共享 荣耀

总部位于上海，聚集基于分布式网络&存储的众多技术大咖和爱好者，深耕基于 IPFS 的商业生态建设和社区发展。

（作者：IPFS原力区，内容来自链得得内容开放平台“得得号”；本文仅代表作者观点，不代表链得得官方立场）