Filecoin - Snark as a Service数据量分析

Snark as a Service是个比较有意思的服务,在Filecoin生态中专门提供零知识证明的计算服务。在Sector大小为32G的情况下,证明需要的数据量在8M左右。

Filecoin又延期了,其实也在预料之中。看代码的小伙伴可能会发现,现在lotus以及rust-fil-proof项目每天还在大量的更新代码。大型的项目开发,在上线之前都会code freeze,进行一定时间的压测,没有严重bug的情况下,就可以上线。目前看项目还是在开发阶段,没有code freeze的意味。

从上次AMA,Filecoin团队就引入了Snark as a Service的想法。可以说,在整个Filecoin的生态中引入新的角色,专门提供零知识证明的生成服务。一般的矿工,可以将零知识证明的计算外包给这个服务。Filecoin团队也对外开放这种服务的提案。

我们Trapdoor Tech团队,对这种服务比较感兴趣。零知识证明的计算涉及到电路的生成,FFT以及Multiexp的计算。在目前官方版本的基础上,可以有2.5倍~3倍的性能提升。

Snark as a Service,最基本的事情是弄清楚矿工需要传输给服务的数据量。本文详细分析一下数据量的大小。本文中涉及到一些专业的术语,labeling/column hash/encoding等等。对这些术语还不熟悉的小伙伴,可以看看SDR的算法介绍的文章:

Filecoin - 深入理解SDR算法

Filecoin - PoREP电路介绍

Vanilla Proof是整个数据量对应的数据结构,就从这个结构分析开始。

01 Overview

Vanilla Proof是PoREP证明所需数据的结构。具体的定义在storage-proofs/src/porep/stacked/vanilla/params.rs的Proof结构。

pub struct Proof {
 pub comm_d_proofs: MerkleProof,
 pub comm_r_last_proof: MerkleProof,
 pub replica_column_proofs: ReplicaColumnProof,
 pub labeling_proofs: HashMap>,
 pub encoding_proof: EncodingProof,
}

可以看出,整个Proof由2个MerkleProof,1个ReplicaColumnProof, 1个LabelingProof的HashMap和1个EncodingProof组成。在整个PoREP的计算中,用到两种Hash函数:Poseidon和Sha256。这两种的Hash函数的Domain的大小都是256bit,也就是32个字节。

02 MerkleProof

MerkleProof包括了叶子节点在一个Merkle树上的证明所需要的数据,包括叶子节点(leaf),路径(path)和树根(root)。具体的定义在storage-proofs/src/merkle.rs的MerkleProof的结构。

pub struct MerkleProof {
 pub root: H::Domain,
 path: Vec, usize)>,
 leaf: H::Domain,
}

其中,root和leaf是32bytes。Path由一个tuple的Vec实现。每个tuple,指定了兄弟节点的信息以及兄弟节点的位置(左边还是右边)。对于二叉树来说,tuple由一个兄弟节点以及位置组成。对于八叉树来说,tuple由7个兄弟节点以及位置组成。MerkleProof结构中的U代表Merkle树的叉数,U2代表二叉树,U8代表8叉树。

也就是说,一个MerkleProof的大小可由如下公式计算:

MerkleProof = 32 * 2 + (树高-1)* (兄弟节点个数*32 + 4)

03 ReplicaColumnProof

PoREP中的SDR算法,需要对原始数据计算11层。如果Sector为32G,每一层都是分成了1^30个节点。同样节点位置的所有层的数据,组成一个Column,也就是一列。

所有证明所有的列的数据整合在ReplicaColumnProof结构中。具体的定义在storage-proofs/src/porep/stacked/vanilla/params.rs中的ReplicaColumnProof结构。

pub struct ReplicaColumnProof {
 pub c_x: ColumnProof,
 pub drg_parents: Vec>,
 pub exp_parents: Vec>,
}

其中c_x是某个challenge的节点位置的列信息,drg_parents是该challenge节点的base依赖的节点相应的列信息,exp_parents是该challenge节点的exp依赖的节点相应的列信息。

3.1 Column

每一列的信息用Column结构表示:

pub struct Column {
 pub(crate) index: u32,
 pub(crate) rows: Vec,
}

其中index代表列的编号,rows代表某列的具体的每一行的信息。

3.2 ColumnProof

单个列的证明数据信息用ColumnProof结构表示,具体定义在storage-proofs/src/porep/stacked/vanilla/column_proof.rs的ColumnProof结构。

pub struct ColumnProof {
 pub(crate) column: Column,
 pub(crate) inclusion_proof: MerkleProof,
}

因为某个列的最后一层节点数据也构成了Merkle树,所以每一列的提供的证明信息会包括一个MerkleProof的信息。

所以,ReplicaColumnProof大小的计算如下:

Column = 4 + 32*11 = 356
ColumnProof = Column + MerkleProof
ReplicaColumnProof = (1+6+8)*ColumnProof

04 LabelingProof

PoREP的SDR的计算成为Labeling。所谓的Labeling,就是根据base和exp的依赖节点信息计算出新的节点信息。

LabelingProof用来表示一个节点进行Labeling计算证明需要的信息,具体定义在storage-proofs/src/porep/stacked/vanilla/labeling_proof.rs中的LabelingProof结构中。

pub struct LabelingProof {
 pub(crate) parents: Vec,
 pub(crate) node: u64,
}

其中的node就是节点编号,parents就是该节点依赖的base和exp的依赖节点信息。在实际Labeling计算中,parents的信息会被计算多次,所以LabelingProof中的Parents也会从14个节点信息扩展为37个节点信息(base和exp依赖节点的信息复制)。

单个LabelingProof的长度计算公式为:

LabelingProof = 32 * 37 + 8 = 1192

注意,在Proof中的labeling_proofs会包含每一层的LabelingProof证明信息。

05 EncodingProof

EncodingProof是SDR计算的最后一层数据和原始数据Encoding的证明所需数据。具体的定义在storage-proofs/src/porep/stacked/vanilla/encoding_proof.rs的EncodingProof结构。

pub struct EncodingProof {
 pub(crate) parents: Vec,
 pub(crate) node: u64,
}

和LabelingProof类似,需要证明Encoding的计算结果正确,需要节点依赖的所有节点信息。

单个EncodingProof的长度计算公式为:

EncodingProof = 32 * 37 + 8 = 1192

06 Proof大小计算

以32G的Sector为例,统计所有证明需要的数据,包括:9 partitions,11 layers,16 challenges。也就是说,整个证明需要的数据包括9*16 = 144个Proof。

comm_d_proof = 32 * 2 + 30 * (32 + 4)= 1144
comm_r_last_proof = 32 * 2 + 10 * (32*7 + 4)= 2344
replica_column_proofs = 15*(356+2344) = 40500
labeling_proofs = 11*1192 = 13112
encoding_proof = 1192
Proof = 1144 + 2344 + 40500 + 13112 + 1192 = 58292

总共的数据为:144*58292 = 8394048 = 8M

总结:

Snark as a Service是个比较有意思的服务,在Filecoin生态中专门提供零知识证明的计算服务。在Sector大小为32G的情况下,证明需要的数据量在8M左右。

公众号星想法有很多原创高质量文章,欢迎大家扫码关注。

公众号-星想法

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-04-20 11:03
  • 阅读 ( 353 )
  • 学分 ( 44 )
  • 分类:FileCoin

0 条评论

请先 登录 后评论
Star Li
Star Li

43 篇文章, 1286 学分