IPFS＆FileCoin-PoRep和PoSt算法

区块链在2017年爆发，很多项目都在用去中心化的思路去重塑。存储是很多人想去重塑的一个方向，用去中心化的存储代替中心化的存储。2015年，IPFS设计提出了一个点对点的分布式媒体发布协议。IPFS被认为是最有可能取代HTTP的新一代互联网协议。FileCoin在IPFS协议基础上，设计自己的区块链，激励更多的存储服务以及用户参与IPFS协议。

IPFS以及FileCoin的白皮书相对来说，知识量很大，读懂需要花一点时间。我总结一下FileCoin中设计的PoRep以及PoSt算法的原理，方便理解。

1）PoRep算法

PoRep 算法是用来证明一个存储系统确实存储了某一份数据的拷贝，而且每一份拷贝使用不同的物理存储。

PoRep 需要抵抗的三种攻击：

1） 女巫攻击（多份数据使用同一物理存储）

2） 外包攻击（用其他存储，而不是自己的存储进行数据存储）

3） 生成攻击（及时生成检验数据）

*) 解决女巫攻击的方法是数据编码，引入混淆因子：

RDek = Encode(D, ek)

RDek 是编码后的数据，D 是原数据，ek是混淆因子。

*)解决外包攻击或者生成攻击的方法是：Encode 的时间要足够长

(a) T honest = RTTVPV + Time(PoRep.Prove(SP, RD ek, c))

(b) T attack = RTTVPV + Time(PoRep.Prove(SP, Encode(D, ek), c))

保证 T Encode = 10 × T honest or 100 × T honest。也就是攻击者需要花10倍，甚至百倍的时间进行编码，从而可以区分出攻击者和诚实的矿工。

Encode 的方法必须具备以下几个特征：

1） 足够慢，保证 T honest

2） 可以 Decode

3） 必须有混淆因子

4） 输出不能压缩

5） Decode 足够快

6） Encode 的速度可调

7） Encode 的结果，所有人都能验证

8） Encode 必须和数据中的所有 bit 相关

9） …

Filecoin 选择的 Encode（ Seal）的方法是多轮的 AES-256的CBC加密。

数据编码以及验证过程的几个小概念：

1） 散列函数： CRH 以及 MerkleCRH（把一段数据切成一段段的，组成一个 Merkle 树，针对每个节点，算 CRH，输出是根上的 CRH）

2） zk-SNARKs： 零知识验证算法，在生成和验证数据之前，需要生成一对生成/验证密钥。

整个PoRep的生成以及验证的计算过程如下图所示：

值得强调的是，最终存储在硬盘的是Seal之后的数据，也就是AES的加密结果。

整个过程中有几种计算：

1） 散列 CRH 以及 MerkleCRH

2） 零知识 Prove 以及 Verify

3） Seal （ AES-256 CBC）

具体的计算公式可以查看FileCoin的白皮书第15 页。

2）PoSt算法

PoSt算法是在 PoRep算法的基础上，循环做一定次数的 PoRep 的证明。因为整个循环计算需要一定的时间，从而证明数据确实在物理存储上存储了一定的时间。 这也就是 Proof-of-SpaceTime 的由来。

可以参看白皮书上的图来理解：

整个计算会重复PoRep计算t次。每次PoRep的计算结果，会作为输入再次计算新的PoRep结果。最后一次PoRep的计算结果，作为PoSt的结果。