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团队也对外开放这种服务的提案。 ![](https://img.learnblockchain.cn/2020/04/20_/705744981.png) 我们Trapdoor Tech团队,对这种服务比较感兴趣。零知识证明的计算涉及到电路的生成,FFT以及Multiexp的计算。在目前官方版本的基础上,可以有**2.5倍~3倍**的性能提升。 Snark as a Service,最基本的事情是弄清楚矿工需要传输给服务的数据量。本文详细分析一下数据量的大小。本文中涉及到一些专业的术语,labeling/column hash/encoding等等。对这些术语还不熟悉的小伙伴,可以看看SDR的算法介绍的文章: [Filecoin - 深入理解SDR算法](http://mp.weixin.qq.com/s?__biz=MzU5MzMxNTk2Nw==&mid=2247486980&idx=1&sn=d525f288bd1305191a7cd7a4d26acb8c&chksm=fe131f14c9649602fdb874443a0b09ead774208e3fa1ca6dc4bb35322390299aa7eeeffe2141&scene=21#wechat_redirect) [Filecoin - PoREP电路介绍](https://learnblockchain.cn/article/890) 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左右。 *公众号**星想法**有很多原创高质量文章,欢迎大家扫码关注。* ![公众号-星想法](https://img.learnblockchain.cn/2019/15572190575887.jpg!/scale/20)
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
- 阅读 ( 1155 )
- 学分 ( 44 )
- 分类:FileCoin
评论