欢迎大家来到第七章，经过前章《【Filecoin 源码仓库全解析】第六章：如何单机部署多节点集群及矿池设计思路》的介绍，我们分享了如何在单机部署多节点集群的知识以及矿池设计的一些思路。
我们将在本章介绍 目前 Filecoin 工程实现中所采用的复制证明（PoRep）方式与时空证明（PoSt）方式，以及如何参与协议实验室发起的复制证明游戏（Replication-Game）。
一、Filecoin 所设计的证明类型
Filecoin 是一个利用区块链技术来实现的去中心化存储系统，我们都知道，在一个区块链系统中，需要保证每个节点公平有序地按照规则自行运转，能抵制恶意攻击，确保整个体系的可信安全。
为此，Filecoin 体系下也需要一个严谨的证明手段来确保矿工不会在没有存储数据的情况下谎称自己存储了用户的数据，需要矿工凭借他们的存储能力争夺出块资格。
Filecoin 系统中的证明算法最初源于存储证明（PoS）、数据持有性证（PDP）和可检索证明（PoRet），后面逐渐迭代、增强约束条件，才完善为如今工程中所采用的复制证明（PoRep）与时空证明（PoSt），这里分别详细介绍一下它们的含义：
- 存储证明（Proof-of-Storage, PoS）：为存储空间提供的证明机制。
- 数据持有性证明（Provable Data Possession，PDP)：用户发送数据给矿工进行存储，矿工证明数据已经被自己存储，用户可以重复检查矿工是否还在存储自己的数据。
- 可检索证明（Proof-of-Retrievability，PoRet）：和 PDP 过程比较类似，证明矿工存储的数据是可以用来查询的。
- 复制证明（Proof-of-Replication，PoRep）：存储证明 PoS 的一个实际方案，用以证明数据被矿工独立地保存，可以防止女巫攻击，外源攻击和生成攻击。
- 空间证明（Proof-of-Space，PoSpace）：存储量的证明，PoSpace 是 PoW 的一种，不同的是 PoW 使用的计算资源，而 PoSpace 使用的是存储资源。
- 时空证明（Proof-of-Spacetime，PoSt）：证明在一段时间内，矿工在自己的存储设备上实际的存储了特定的数据。
如下图所示，这 6 种证明的定义并不是互斥独立的，PoS 包括 PDP, PoRet, PoRep, PoSpace；而 PoRep 和 PoSt 是 PoSpace 的两种实例，他们之间的定义相互有交叉：
复制证明和时空证明的实现方式决定了 Filecoin 矿机的配置。间接决定 Filecoin 系统的整体成本。Filecoin 提供了存储和数据下载服务两种服务，系统成本最终决定用户的使用成本。
如果复制证明和时空证明消耗的资源过多，那么会系统性的提升整个 Filecoin 成本，这会让 Filecoin 系统的价值大打折扣。
目前所开源的第一版 go-filecoin0.1.x 系列所采用的是 ZigZagDrg 和 StackedDrg 的 VDF 方式来作为 PoRep 的实现，官方对此认为仍有改进空间，协议实验室也为此设立了 RFPs 基金，专门研究该课题，而复制游戏的诞生也是为了更好地让社区爱好者提前参与测试和协助官方优化这个部分。
二、复制证明 PoRep
2.1 PoRep 职能
PoRep 算法的职能是用来证明一个存储系统确实存储了某一份数据的拷贝，而且每一份拷贝使用不同的物理存储，并用来抵御去中心化系统中三种常见的攻击：
2.2 PoRep 本质
PoRep 本质是一个加密时间长，解密时间短且证明与验证过程高效的算法， 这个过程在学术圈，被称为可验证时延加密（Verifiable Time-Delay Encoding Function）：
如上图，我们假设这一加密算法的验证时长是一倍，解密时间大约 2 - 5 倍，挑战有效时间算作 10 倍，那么这一加密时间大约要 1000 倍才能在概率上达到 99.9% 的相对安全。
2.3 挑战及证明模型
Filecoin 证明机制的角色和过程可以抽象成如下，挑战者、证明者、检验者。他们可以是矿工、用户或者任何网络内其他角色。涉及的定义包括如下：
- 挑战（challenge）：系统对矿工发起提问，可能是一个问题或者一系列问题，矿工正确的答复，则挑战成功，否则失败。
- 证明者（prover）：一般只矿工。向系统提供证明了完成系统发起的挑战。
- 检验者（verifier）：向矿工发起挑战（challenge）一方，来检测是否矿工完成了数据存储任务。
- 数据（data）：用户向矿工提交的需要存储或者矿工已经存储的数据。
- 证明（proof）：矿工完成挑战（challenge）时候的回答。
如上图，验证过程可以表述为: 验证者会按照一定的规则向矿工提起挑战，挑战是随机生成的，矿工不能提前获知。矿工作为证明者相应向检验者提交证明，证明的生成需要原始数据与随机挑战信息。证明生成后，证明者会交给验证者，并由验证者判定该证明是否有效，如果有效，则挑战成功。
2.4 可验证时延加密函数（VDF）
对于 VDF，Filecoin 最初受到了类似 Cipher Block Chaining 分组块加密链的启发，从而改进和优化属于自己的 VDF 方式。
我们先看一下 CBC 的原理: 大文件分块成 d1-d4…
除了 c1 初始化向量比较特殊，后续所有文件块编码都需要做 XOR 运算和 AES 加密，例如 c2 由 c1 与 d2 共同生成，以此类推。这样在编码过程就无法并行，从而速度变慢。
再看右边的过程，是对 CBC 算法的进一步优化，采用的深度鲁棒链(Depth Robust Chaining)，在分块上使用了有向无环图来做，进一步压缩了解码验证的复杂度，也提高了随机性。
Filecoin 目前工程上的实现是基于前面两个算法的改进版：ZigZagDRG 算法，如下图所示：
原始数据 data 首先依次分成一个个小数据（d1-d5），每个小数据将被计算出一个散列值（32 个字节），小数据本身也将散列值作为加密种子来进行编解码。这些小数据的散列值按照 DRG（Depth Robust Graph）建立连接关系。
数据块的散列关系将构成 Merkle Tree 结构（类 MySql 数据库的索引使用 B + 树实现）。
这样是为了在进行挑战与检验的时候，无需针对所有数据块解码，即可以快速验证，也更好地抵御了攻击性。
例如：树根即为副本的哈希，系统或者用户随机发起挑战，位置 d5，矿工只需计算 d5 到根节点 root 的路径，输出一个证明给发起挑战的验证节点。
至于 VDF 中每个数据块的单元加密，如下图所示，应用到了 BLS12-381 来进行单元编码与解码：
（源码路径：https://github.com/filecoin-p…）
BLS12-381 是一种 Zcash 中所用的新型 zk-SNARK 椭圆曲线的构造加密算法，隶属于 Bellman 库，由 Rust 语言所实现，它的特点是小巧易用，能快速验证。Bellman 的目标是让普通程序员更加简单地使用 zk-SNARKs。
散列函数由于需要适应于 SNARKS，目前沿用了 Zcash 中的 Pedersen（Blake2、SHA256 也在做实现和选择）：
整个 PoRep 的计算过程分为若干层 （目前在 Filecoin 中设置为 4 层，在复制游戏项目中设置为 10 层），每一层的 DRG 关系的箭头方向是互斥的，上一层向右，下一层就向左，因此得名 ZigZag（Z 字型），数据解码过程中，每一层之间互不依赖，即可并行执行，相对于串行编码要更为快速。
综上，这样就实现了 PoRep 的本质：编码快，而解码和验证证明快的效果，从而防范各种攻击。
三、时空证明 PoSt
如图所示，PoSt 可以理解为矿工一定时间内持续地生成复制证明和接受挑战和验证的过程，并通过这个过程，更新全网存储算力。
挑战者在 PoRep 循环重复执行的 i 轮，输入一个随机挑战参数 c，之后，挑战参数 C 会被链式递归计算，即上一次的输出作为下一次的输入，直到 T 时间内，最后一次的结果作为 PoSt 的证明，接受反向验证。
很明显，不正当的矿工如果没有老老实实执行 PoSt，是无法反推出 C 的。
如下图所示，目前，go-filecoin 中所定义的阈值是：每隔 20000 个区块（平均 6 天左右），存储矿工必须提供一次 PoSt（Proof of Space Time)的证明，表明仍存有用户数据的证明。与此同时，存储市场（上帝）会每隔 100 个区块（平均 50 分钟），去对 PoSt 发起证明验证，以判断是否需要下发惩罚。
（源码路径：https://github.com/filecoin-p…）
四、Filecoin Proving Subsystem（FPS）
Filecoin Proving Subsystem（FPS）是 Filecoin 体系中所有证明算法的工程实现，由于底层依赖 Bellman 库的原因，完全由 Rust 编写，源码仓库地址:https://github.com/filecoin-p…
FPS 在设计之时，十分注重解耦性：filecoin-proofs 实现了为 go-filecoin 提供存储证明的接口，并依赖其他两个模块：storage-proofs（存储证明生成与验证的模块）和 sector-base（扇区控制模块）。
这两个模块又依赖于 storage-backend 中间件实现存储控制和消息转发。
关于 FPS 的其他细节导读，这里推荐李星前辈的一篇文章：
- 星想法：Filecoin – PoRep 和 PoSt 算法源代码导读
之后，可以配合官方的 rust-fil-proofs 源码仓库进行阅读和获取最新的变动：
- github：rust-fil-proofs
关于 PoRep 和 PoSt 的推演论证过程，想深入了解的童靴可以对照这两篇论文进行剖析：
- PoReps: Proofs of Space on Useful Data
- Ben Fisch：Tight Proofs of Space and Replication
五、参与复制证明游戏
复制游戏是一项复制竞赛，参与者挑战 Filecoin 官方提供的默认的复制证明算法（前文提到的 VDF），看是否能够提供更优 (相对于默认算法) 的算法或执行结果。
参与游戏的方法是：通过当前 Filecoin 提供的复制算法(运行或重构 FPS)，并将执行结果发送到 Filecoin 服务器。
5.1 编译游戏客户端
如下准备环境依赖，小编采用的是 linux 系统，macOS 环境类似，可使用 brew 包管理工具代替 apt。
// 安装 Rust
curl https://sh.rustup.rs -sSf | sh
重启 terminal
// 切换 rust 到 nightly 版
rustup install nightly
// 若想自行部署游戏服务端，需安装 PostgreSQL 数据库
brew install postgresql@10
apt-get install postgresql
// 安装 clang 和 libclang
apt-get install clang
// 安装 pq 库
apt-get install libpq-dev
// 下载 replication-game 源码
git clone https://github.com/filecoin-project/replication-game.git
cd replication-game
// 执行编译
cargo +nightly build --release --bin replication-game
编译完成后，可在 bin/ 目录下看到 play 可执行文件：
5.2 启动游戏
# 启动指令：# bin/play NAME SIZE TYPE
# E.g.
# Zigzag 10MiB
bin/play NAME 10240 zigzag
# Zigzag 1GiB
bin/play NAME 1048576 zigzag
# DrgPoRep 10MiB
bin/play NAME 10240 drgporep
# DrgPoRep 1GiB
bin/play NAME 1048576 drgporep
- NAME: 你的游戏玩家名称
- SIZE: 你打算要复制的文件的大小，单位是 KB
- TYPE: 你想要运行的算法名称(目前可选值有：zigzag 和 drgporep)
Play 脚本将自动从游戏服务器下载种子，复制数据，生成证据，然后将该证据发布到游戏服务器。
5.3 发送游戏结果至 Rank 服务器
Play 脚本将通过 curl 提交游戏结果：
curl -X POST -H "Content-Type: application/json" -d @./proof.json https://replication-game.herokuapp.com/api/proof
我们可以通过访问 Rank 页面：http://replication-game.herok…，来查看排行。
小编的机型配置：
- Processor Name: Intel Core i5
- Processor Speed: 3.1 GHz
- Number of Processors: 1
- Total Number of Cores: 2
- L2 Cache (per Core): 256 KB
- L3 Cache: 4 MB
- Memory: 8 GB
Drg 复制证明耗时 2.1s/MiB：
ZigZag 复制证明耗时 11.2s/MiB：
我们的游戏结果将记录在 proof.json 中，可以手动打开 proof.json，分析一下证明的数据结构：
- prover：验证人。
- seed：游戏种子，加密 Key。
- proof_params：证明配置项。
- proof：证明数据块关系。
- tau：一棵或者多棵 Merkle 树的树根都称为 tau，每一层的输入称为 d（data），每一层的 VDE 的结果称为 r（replica）。
- comm_d：每一层的输入构建的默克尔树根为 comm_d。
- comm_r：每一层的输出构建的默克尔树根为 comm_r。
- comm_r_star：每层 comm_r 的数据和 replica id 数据散列计算后的结果。
通过查阅 Proof.json 的数据结构，也可以帮助大家更好地理解 2.4 所述内容。
5.4 如何提升 Rank 位置？
- 从硬件和软件方面优化：增加硬件配置，更快的 CPU 更大的内存(RAM)，或者使用其他的替换方案比如使用 FPGA, GPU, ASICs 等更擅长进行深度计算的硬件。另外你可以优化你操作系统的一些参数设置，比如 IO 参数等。
- 从算法方面优化：你可以不使用 Filecoin 给你提供的默认实现算法，自己设计一种新的能够更快生成存储证明的算法，比如打破顺序假设，生成存储更少数据的证明，打破 Pedersen 哈希等。
当然，光追求 Rank 数据是无意义的，PoRep 和 PoSt 的时延在 Filecoin 体系下，只是影响存储效率的一个因子而已，对于矿工来说，需要追求的是综合性价比。
参考文献
- https://github.com/filecoin-project/replication-game
- https://z.cash/blog/bellman-zksnarks-in-rust/
往期系列文章回顾：
【Filecoin 源码仓库全解析】第一章：搭建 Filecoin 测试节点
【Filecoin 源码仓库全解析】第二章：如何创建账户钱包并获取 FIL Mock 代币
【Filecoin 源码仓库全解析】第三章（上）：存储提供方（矿工）的配置操作
【Filecoin 源码仓库全解析】第三章（下）：存储提供方（矿工）的配置操作
【Filecoin 源码仓库全解析】第四章：存储需求方（用户）的配置操作
【Filecoin 源码仓库全解析】第五章：检索市场及检索矿工
【Filecoin 源码仓库全解析】第六章：如何单机部署多节点集群
本章赞助品牌：
广东星蓝区块链技术有限公司 聚集了一批志向于 IPFS 生态建设的“先锋”，也是中国最早、最专业的 IPFS 生态布道、交流社区，公司拥有最成熟完整的产业供应链，包括矿机、矿场、矿池、合作托管、数据支持、专业运维、应用开发、知识服务等在内的全方位立体化服务的企业，为 IPFS 生态提供最全面、专业的支持。作为国内 IPFS 生态的第一批布道者，“星蓝”的团队十分看好 IPFS 未来的价值，也会全力推动 IPFS 的发展及应用落地。我们团队置身于区块链革命的第一线，投身 IPFS 生态建设，坚信 IPFS 将为世界带来更好的体验，为商业创造更大的价值。星蓝核心价值观：共建、共赢、共担，块链有框，星蓝无界，星蓝产品“TimeBook”期待您的关注！
感谢广东星蓝区块链技术有限公司 (www.xlipfs.com) 对 嘉乐 SOHO的原创内容提供支持。
联系作者：
本人从业经验有限，不免有不足之处，欢迎指正和更多讨论，可私信 微信公众号：jialesoho，或者加我 微信：daijiale6239，如果觉得对您有帮助，可以 帮点击好看推广 和打赏支持 噢，感激不尽！
（识别图中二维码，关注嘉乐 SOHO 微信公众号)