文档章节

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

怎当她临去时秋波那一转
 怎当她临去时秋波那一转
发布于 2019/04/04 01:28
字数 2218
阅读 118
收藏 0

几个星期前,我看了看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_d。

再介绍两个术语:TAU,AUX。

TAU: 希腊字母,一棵或者多棵Merkle树的树根都称为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项目。

本文转载自:https://mp.weixin.qq.com/s/Sd6Y0gSX6HB4BFRKPV_0dQ

怎当她临去时秋波那一转
粉丝 12
博文 84
码字总数 39065
作品 0
其它
CTO(技术副总裁)
私信 提问
加载中

评论(0)

Filecoin逻辑梳理及源代码导读

Filecoin的源代码可以从Github下载:https://github.com/filecoin-project/go-filecoin。 在阅读源代码之前,强烈建议看两份对阅读代码有益的文档: Filecoin的设计文档 https://github.com...

怎当她临去时秋波那一转
2019/04/04
51
0
IPFS & FileCoin - PoRep和PoSt算法

区块链在2017年爆发,很多项目都在用去中心化的思路去重塑。存储是很多人想去重塑的一个方向,用去中心化的存储代替中心化的存储。2015年,IPFS设计提出了一个点对点的分布式媒体发布协议。I...

怎当她临去时秋波那一转
2019/04/04
73
0
技术工坊44期 - Filecoin区块链以及存储协议解析

【区块链技术工坊44期】Filecoin区块链以及存储协议解析 1. 活动基本信息 1)题目: 【区块链技术工坊44期】Filecoin区块链以及存储协议解析 2)议题: IPFS(InterPlanetary File System)是一...

深入浅出区块链
2019/05/24
0
0
区块链 - Filecoin为什么需要GPU?

今天IPFS/Filecoin的各种群炸开了锅,原因是Filecoin内部开发人员透露,下一个Filecoin的测试网络需要搭配GPU。而且Filecoin内部测试使用的是2080ti的显卡。 同时,聊天记录表明,下一个测试...

深入浅出区块链
2019/11/28
0
0
filecoin技术架构分析二:filecoin通用语言理解

我是先河系统CTO杨尉,欢迎大加关注的的Github: waynewyang,本文是filecoin技术架构分析系列文章第二章filecoin通用语言理解。 为什么要把filecoin通用语言单独列为一讲 笔者认为一位优秀的...

深入浅出区块链
2019/02/20
0
0

没有更多内容

加载失败,请刷新页面

加载更多

[ASP.NET Core MVC] 如何实现运行时动态定义Controller类型?

昨天有个朋友在微信上问我一个问题:他希望通过动态脚本的形式实现对ASP.NET Core MVC应用的扩展,比如在程序运行过程中上传一段C#脚本将其中定义的Controller类型注册到应用中,问我是否有好...

osc_n0c6719w
28分钟前
26
0
团队作业第三次—项目需求分析

这个作业属于哪个课程 2020春|S班 (福州大学) 这个作业要求在哪里 团队作业第三次—项目需求分析 团队名称 如果有一天我变得很有钱 这个作业的目标 1.原型设计、2.类图设计、3.需求规格说明书...

osc_bcvwusz2
29分钟前
23
0
流媒体服务器、海康威视 大华摄像头实现视频监控、直播解决方案

  随着互联网+物联网进程的加快,视频监控应用领域变得越来越广泛,其中海康威视 大华等品牌的摄像头频繁出现在视野中。由于去年也实现过智慧工地项目上的视频监控方案,加上当今直播趋势不...

osc_47qtuhkb
31分钟前
18
0
流媒体服务器、海康威视 大华摄像头实现视频监控、直播解决方案

  随着互联网+物联网进程的加快,视频监控应用领域变得越来越广泛,其中海康威视 大华等品牌的摄像头频繁出现在视野中。由于去年也实现过智慧工地项目上的视频监控方案,加上当今直播趋势不...

osc_1qix3fyb
32分钟前
35
0
thymeleaf中使用javascript中的[[]]的3种处理方式

thymeleaf中使用javascript中的[[]]的处理方式 1: 使用 CDATA 模式 /* <![CDATA[ */ 和 /* ]]> */就OK了 <script th:inline='javascript'>/* <![CDATA[ *//* ]]> */</script> 2:......

独钓渔
33分钟前
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部