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

『 创业，是个非常苦逼的过程，是打散自己，重新连接资源的过程。在公司打工，凭的是连接公司资源，整合公司资源的能力。创业，连接的社会资源，开放性的资源。不确定性，自我否定，自我肯定，交错。如何快速的确定资源，连接资源，也有方法论。上周末，和好朋友夜游香山，上了一堂创业理论课，醍醐灌顶，先给大家分享一些名词：阶级错层，心理动力，项目管理。好朋友给别人讲课，一个小时1万块。以后有机会，我再慢慢讲讲我的体会和理解。 』

几个星期前，我看了看Filecoin的代码，整理了Filecoin的一些概念，架构以及协议 - Filecoin逻辑梳理及源代码导读。

PoRep以及PoSt的数据存储证明是通过FPS模块实现。整个FPS模块是通过Rust语言实现。技术人总是想打破沙锅问到底，究竟PoRep/PoSt的证明过程如何？我就从源代码的角度，讲述一遍数据证明的逻辑调用部分。方便其他小伙伴理解或者优化相关的逻辑。有关零知识证明的推导代码，后续文章详细介绍。

01 Filecoin代码模块依赖关系

从PoRep以及PoSt存储证明的角度来看，Filecoin代码模块由如下三层组成：

rust-fil-proofs是存储证明的具体实现，通过Rust语言实现。rust-fil-proofs模块依赖bellman项目（零知识证明）。bellman项目是ZCash项目使用的零知识证明模块。bellman项目也是用Rust语言实现。在go-filecoin的rustverifier.go文件实现go到rust语言的调用。

在该导读中，go-filecoin代码的最后一个commit信息如下：

commit b716be02c0e15436141a5c20274a38aec749490e (HEAD -> master, tag: nightly-13394-b716be, origin/master, origin/HEAD)

Author: Sidney Keese sidke.z@gmail.com

Date:   Wed Mar 27 14:06:13 2019 -0700

   use precompiled bls-signatures library (#2368)

rust-fil-proofs代码的最后一个commit信息如下：

commit 808dc884642acbf7b78b282eb7d933c7cc2cc3a7 (HEAD -> master, origin/master, origin/HEAD)

Author: wayne yang wayne.w.yang@foxmail.com

Date:   Mon Mar 25 21:12:40 2019 +0800

    docs: delete the outdated link

02 rust-fil-proofs的框架

rust-fil-proofs功能主要由四个子模块组成：

filecoin-proofs实现了filecoin存储证明的接口，依赖其他两个模块：storage-proofs（存储证明的逻辑）和 sector-base （数据存储的接口）。这两个模块又依赖于storage-backend模块实现数据的存储。

相关代码就在这四个目录中：

03 PoRep的生成和验证逻辑

PoRep就是Proof of Replicate，数据存储证明。模块之间的调用关系如下：

node.go代码在启动挖矿时，每120个区块调用一次SealAllStagedSectors函数（将所有的Staged的Sector数据进行Seal）。顺便说一句，用户的数据存储时分成一个个的Sector（目前设置为256M）。Sector有三个状态：Staging（数据还未写满，并且未超时），Staged（数据已经写满或者超时），Sealed（数据已经Seal并存储）。

在filecoin-proof模块接收到请求后，确认目前所有的Staged的Sector，并对每个Sector进行Seal。

核心逻辑在rust-fil-proofs/filecoin-proofs/src/api/internal.rs代码的seal函数。seal函数原型如下：

seal函数对in_path的原始数据，进行复制并存储到out_path。在seal的过程中，提供Sector的属性，证明人的id以及Sector的id。

01 Replica ID

对每一个Seal过的Sector，设置一个Replica ID。Replica ID是一个Hash值，计算过程如下：

相应实现是rust-fil-proofs/storage-proofs/src/porep.rs的replica_id函数。

02 整体逻辑

PoRep的生成逻辑包括两部分：1/数据的复制（replicate）2/数据的复制证明。Step1/Step3实现复制的证明，Step2实现数据的复制。

贴一段代码，方便小伙伴比对和理解：

03 数据复制逻辑

PoRep算法的全称是ZigZag-DRG-PoRep。整体流程示意如下：

Sector中未Seal的原始数据首先依次分成一个个小数据，每个小数据32个字节。这些小数据之间按照DRG（Depth Robust Graph）建立连接关系。按照每个小数据的依赖关系，通过VDE（Verifiable Delay Encode）函数，计算出下一层的所有小数据。整个PoRep的计算过程分为若干层（目前代码设置为4层），仔细观察每一层的DRG关系的箭头方向，上一层向右，下一层就向左，因此得名ZigZag（Z字型）。

VDE以及ZigZag设置的参数查看rust-fil-proofs/filecoin-proofs/src/api/internal.rs：

每一层的计算逻辑示意如下：

每一层的输入称为d（data），每一层的VDE的结果称为r（replica）。对每一层的输入，建构默克尔树，树根为comm_d, 整个树的数据结构称为tree_d。对每一层的输出，建构默克尔树，树根为comm_r，整个树的数据结构称为tree_r。

再介绍两个术语：TAU，AUX。

TAU: 希腊字母，一棵或者多棵Merkle树的树根都称为TAU。

$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Tau \tau$

AUX: Auxiliary的简称，一棵或者多棵Merkle树的结构称为AUX。

对于一层replica来说，TAU包括comm_d和comm_r，AUX包括tree_d和tree_r。

对于整个PoRep来说，也就是多层replica来说，TAU以及AUX示意如下：

其中的comm_r_star是每层comm_r的数据和replica id数据Hash的结果。

具体实现的源代码请看两个函数：

1、rust-fil-proofs/storage-proofs/src/layered_drgporep.rs中的Layers的replicate函数

2、rust-fil-proofs/storage-proofs/src/drgporep.rs中的PoRep的replicate函数

04 复制证明逻辑

复制数据完成后，需要提供零知识的证明。该证明逻辑需要花很多篇幅仔细介绍，涉及到QAP，KCA，Groth16，同态隐藏，双线性映射。后续的文章会详细讲解相关逻辑。本文先有些概念：需要生成证明（Proof）需要有两步：setup以及prove。

setup：设置证明的参数

prove：提供需要证明的内容，包括公共数据(public inputs)，私有数据（private inputs)以及Groth的参数。在2.b中的代码中可以看出，

PoRep证明的公共数据包括原始数据的comm_d，最后一层的comm_r和comm_r_star。

PoRep证明的私有数据包括所有层的comm_r/comm_d和每一层的tree_r/tree_d。

值得特别提出的是，PoRep提交到Filecoin区块链上的数据是：PoRep的公共数据和复制证明数据。

整个数据复制的过程时间比较长，目前1G的数据需要消耗40～50分钟。

05 复制验证逻辑

在某个存储矿工生成PoRep后，通过CommitSector接口向区块链提交证明信息。在Filecoin区块链的所有矿工接收到CommitSector的Message交易时，调用VerifySeal进行复制验证，大体流程如下：

具体实现的源代码请查看rust-fil-proofs/storage-proofs/src/api/internal.rs的verify_seal函数。

04 PoSt的生成和验证逻辑

在一个存储矿工存储（Seal）用户数据后，每隔20000个区块，必须提供一次PoSt（Proof of Space Time)的证明，也就是说，某个存储矿工还存有用户数据的证明。20000个区块，一个区块30秒，也就说每6天提交一次证明。

01 PoSt生成逻辑

PoSt的生成是基于最近的存储状态，所以提交PoSt的证明最好能在一个区块之内（30秒）完成。PoSt生成逻辑的调用关系如下：

在新的区块生成时（OnNewHeaviestTipSet函数），每个提供存储的矿工会检查是否需要提供PoSt的证明。如果需要，则调用generatePoSt函数生成证明。

generatePoSt函数提供两个参数：所有提交到区块链上的comm_r信息以及随机挑战信息 （ChallengeSeed)。所有提交到区块链上的comm_r信息通过区块链查询可以获取。ChallengeSeed通过currentProvingPeriodPoStChallengeSeed函数生成，生成逻辑如下：

简单的说，就是从当前区块高度往前看几个TipSet，找出某一个TipSet中众多区块中的最小Ticket。该Ticket就是ChallengeSeed。

在最新的代码逻辑中，PoSt每两个Sector会生成一个Proof，也就是post_adapter实现的逻辑。提交到区块链上的是众多Proof的列表。

VDFPostCompound::setup函数设置验证相关参数。VDFPostCompound::prove函数需要四个参数：

a. setup函数设置的参数 b. Public数据（comm_r的数据列表，随机挑战信息） c. 私有数据（Seal数据构成的Merkle树的结构信息） d. Groth相关的参数信息

具体实现的源代码请查看rust-fil-proofs/storage-proofs/src/api/internal.rs的generate_post_fixed_sectors_count函数。

prove函数实现的逻辑就是白皮书中的PoSt的框架图：

02 PoSt验证逻辑

在某个存储矿工生成PoSt证明后，通过SubmitPoSt接口向区块链提交证明信息。在Filecoin区块链的所有矿工接收到SubmitPoSt的Message交易时，调用VerifyPoST进行复制验证，大体流程如下：

具体实现的源代码请查看rust-fil-proofs/storage-proofs/src/api/internal.rs的verify_post_fixed_sectors_count函数。

总结：PoRep是对某个Sector数据存储的证明，每个Sector一次。PoSt是一系列已经Seal过的Sector的存储证明，每隔一段时间一次。两个证明的核心是Groth16零知识验证算法，基于Bellman项目。