【Filecoin源码仓库全解析】第七章：了解PoRep与PoSt并参与复制证明游戏

        我们将在本章介绍目前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-project/rust-fil-proofs/blob/41d7fe97b2d98e79eaf52959590a86c4d1749843/storage-proofs/src/vdf_sloth.rs）

        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-project/go-filecoin/blob/a45c0f1a70c2e8a61d6d5b4e01e641bedb344a06/actor/builtin/miner/miner.go）

四、Filecoin Proving Subsystem（FPS）

        Filecoin Proving Subsystem（FPS）是Filecoin体系中所有证明算法的工程实现，由于底层依赖Bellman库的原因，完全由Rust编写，源码仓库地址:https://github.com/filecoin-project/rust-fil-proofs

        FPS在设计之时，十分注重解耦性：filecoin-proofs实现了为go-filecoin提供存储证明的接口，并依赖其他两个模块：storage-proofs（存储证明生成与验证的模块）和 sector-base （扇区控制模块）。

        这两个模块又依赖于storage-backend中间件实现存储控制和消息转发。

        关于FPS的其他细节导读，这里推荐李星前辈的一篇文章：

星想法：Filecoin - PoRep和PoSt算法源代码导读

        之后，可以配合官方的rust-fil-proofs源码仓库进行阅读和获取最新的变动：

• github：rust-fil-proofs（https://github.com/filecoin-project/rust-fil-proofs）

关于PoRep和PoSt的推演论证过程，想深入了解的童靴可以对照这两篇论文进行剖析：

• PoReps: Proofs of Space on Useful Data

  （https://eprint.iacr.org/2018/678.pdf）

• Ben Fisch：Tight Proofs of Space and Replication

        （https://eprint.iacr.org/2018/702.pdf）

五、参与复制证明游戏

        复制游戏是一项复制竞赛，参与者挑战 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.herokuapp.com/，来查看排行。

        小编的机型配置：

• 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/