Filecoin的SDR算法（一）

最近，在我的分享中反复出现了这个词“SDR算法”，之所以这个词会反复出现是因为它有可能事关Filecoin是否会再次延期的问题。

SDR算法是目前用在Filecoin的共识机制复制证明（PoRep）中的算法，那么这个算法的细节到底是什么样的呢？接下来的几天我就和大家分享一下SDR算法的细节。

SDR算法的全称是“Stacked DRG PoRep”，是Filecoin中用到的一种特殊的复制证明算法。在这个算法中，证明的构造者要将原有的数据编码成一个replica然后提交这个replica。这是一种离线的复制证明，它能证明如果replica有效则replica所源自的原始数据就有效。

具体说来，这个算法表示如下：证明构造者P向证明验证者V证明P确实存储了replica R，R代表一份数据D。

在数学上，我们可以将之定义为一个在多项式时间内完成的算法（Setup、Replication、Prove、Verify），并假设一个replica很难产生。这其中的Setup、Replication、Prove、Verify分别为算法进行过程中的每个阶段，分别表述如下：

Setup：在此阶段，系统设置好一些公共参数。

Replicate：在此阶段，任何一方或多方（完全视系统的构造情况而定，在我们的系统中，仅有一方，那就是证明的构造者）根据原始数据D计算产生一个唯一的序列数，我们称之为replica R。

Prove：证明构造者会接到挑战，并必须产生一个证明，证明他拥有一个replica，且该replica源自原始数据D。证明构造者当且仅当他已经拥有这个replica时，才能成功应对这个挑战。也就是说当证明构造者接到挑战时几乎不可能马上产生一个replica。

Verify：在接到证明后，验证者检验该证明的有效性，并判断接受或拒绝该证明。

在这四个阶段，有下面几个概念要和大家解释下：

-耗时：当我们构造复制证明时，在时间方面要假设产生replica是需要耗费一定时间的。我们定义耗费的时间为t，且该时间要大大多余在Prove阶段证明构造者产生一个证明（证明他拥有此replica）所需要的时间+接到挑战和发出证明的时间。

-区别恶意的证明构造者：一个恶意的证明构造者并没有replica R，但为了欺骗系统，必须想办法在接到挑战前伪造一个R。因为恶意的证明构造者事先并没有这个R，所以当他接到挑战时需要花比诚实的证明构造者多的时间来伪造R然后提交。

因此，如果一个证明构造者在超过提交时间后才提交证明，则验证者可以据此判断他是一个恶意的证明构造者而拒绝承认他提交的证明。

SDR算法是Filecoin中用到的一种特殊的复制证明算法。这个算法保证了在Replicate阶段，计算replica的过程无法并行进行。它使用了一种特殊的数据结构---深度健壮图（Depth Robust Graph简称DRG）。

在DRG结构中，每一个节点会被按顺序标号，且每个节点标号的产生都依赖它的父节点标号。

这就保证了要给系统中每个节点标号只能以串行的方式进行而无法以并行的方式进行。当系统对图中的每一个节点都标完号后，最后一个标号即是系统所得到的结果。

我是IPFS/Filecoin社区发起人晓熙（加入社区，联系v号： liandaoxixi），IPFS/Filecoin是全球共识最大的去中心化存储项目，我会定期在社区分享专业的资讯，为IPFS/Filecoin爱好者建设一个共赢的学习社区。

参考链接：https://filecoin-project.github.io/specs/#algorithms__porep

—-

编译者/作者：FIL社区

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。