首页 > Filecoin > 正文

知识干货 | Filecoin - PoRep和PoSt算法源代码导读

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

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

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

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


rust-fil-proofs的框架

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

  

  filecoin-proofs实现了filecoin存储证明的接口,依赖其他两个模块:STOrage-proofs(存储证明的逻辑)和 sector-base (数据存储的接口)。这两个模块又依赖于storage-backend模块实现数据的存储。

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

  

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。

Replica ID

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

  

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

整体逻辑

  PoRep的生成逻辑包括两部分:1/数据的复制(replicate)2/数据的复制证明。Step1/Step3实现复制的证明,Step2实现数据的复制。

  

  贴一段代码,方便小伙伴比对和理解:

  

 
数据复制逻辑

  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的结果。

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

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

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

复制证明逻辑

  复制数据完成后,需要提供零知识的证明。该证明逻辑需要花很多篇幅仔细介绍,涉及到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分钟。


复制验证逻辑

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

  

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

PoSt的生成和验证逻辑

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


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的框架图:

  


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项目。

   

  

  目前100000 人已关注加入我们

    

  

版权信息
作者:Star Li
来源:IPFS海神社区

关于我们

联系我们

作者进驻

手机版

Copyright © 2013 比特巴 www.btb8.com
始建于2013年,提供比特币 区块链及数字货币新闻、技术教程、测评、项目周报、人物等资讯
本页面提供的是IPFS教程资讯,星际文件系统IPFS(Filecoin)目标是为了补充甚至是取代目前统治互联网的超文本传输协议(HTTP)。