Filecoin - Snark as a Service数据量分析

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左右。

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