4.4 PoRep和PoSt实际应用

我们感兴趣的是PoRep和PoSt的应用构建,可以应用于现存系统而不是依赖于可信任的第三方或者硬件。我们给出了PoRep的一个构建(请参见基于密封的复制证明[5]),它在Setup过程中需要一个非常慢的顺序计算密封的执行来生成副本。PoRep和PoSt的协议草图在图4给出,Post的底层体系的证明步骤在图3中。

4.4.1 构建加密区块

1.防碰撞散列: 我们使用一个防碰撞的散列函数:CRH : {0, 1}^* → {0, 1}^O(λ) 。我们还使用了一个防碰撞散列函数MerkleCRH,它将字符串分割成多个碎片,构造出二叉树并递归应用CRH,然后输出树根。

2.zk-SNARKs(零知识证明): 我们的PoRep和PoSt的实际实现依赖于零知识证明(zk-SNARKs)[6,7,8]。因为zk-SNARKs是简洁的,所以证明信息简短并且很容易验证。更正式地,定义L为NP语言,C为L的决策回路。一个可信任的参与方执行一次setup时会产生两个公共密钥:证明密钥pk和验证密钥vk。证明密钥pk使任何(不可信)的证明者都能产生证明π,对于她选择的实例x,x∈L。非交互式证明π是零知识和知识证明。任何人都可以使用验证密钥vk验证证明π。特别是zk-SNARK的证明可公开验证:任何人都可以验证π,而不与产生π的证明者进行交互。证明π具有恒定的大小,并且可以被及时验证,即验证π在|x|中是线性的。

一个zk-SNARKs要满足C的多项式时间算法的元组是: (KeyGen, Prove, Verify)

我们建议感兴趣的读者参看[6,7,8]对zk-SNARK系统的正式介绍和实现。

通常而言这些系统要求KeyGen是由可信任参与方来运行。关于可扩展的计算完整性和私密性(SCIP)系统的新工作[9]显示了避免这个初始步骤的有希望的方向,因此才做出上面的信任假设。

4.4.2 封装操作(Seal)

封装操作的作用是(1)通过要求证明者存储其公钥唯一的D的伪随机置换,来强制副本是物理上独立的副本,从而执行存储n个副本时,n个独立副本将被存储于磁盘空间中(因此是副本存储大小的n倍)和(2)在执行PoRep.Setup的时候,强制生成副本的时间要大大的长于预计响应挑战的预期时间。有关密封操作的更正式定义,请参见[5]。上述的操作可以用Seal^τ τAES−256 来实现,并且τ使得Seal^τ τAES−256 需要花费比诚实的“挑战-证明-验证”顺序多10-100倍的时间。请注意,对τ的选择是重要的,这使得运行Seal^τ τAES−256 比证明人随机访问R花费更多时间显得更加明显。

4.4.3 PoRep构建实践

本节描述PoRep协议的构建,并总结了一个已在图4包括了的简单协议草图。实现和优化的细节略过了。

1.创建副本 Setup算法通过封装Seal算法生成一个副本并提供证明。证明人生成副本并将输出(不包括副本R)发送给验证者。

2.证明存储 Prove算法生成副本的存储证明。证明人收到来自验证者的随机挑战c,c指定了一个在根哈希为rt的默克树R中的叶子数据Rc 。证明人生成关于从树根rt到叶子Rc的路径的知识证明。

3.验证证明 Verify算法检查所给的源数据的哈希和副本的Merkle树根的存储证明的有效性。证明是公开可验证的:分布式系统的节点维护账本和对特定数据感兴趣的可以验证这些证明。

4.4.4 PoSt构建实践

本节描述PoSt协议的构建并已在图4中包含了一个简单协议草图。实现和优化的细节略过了。

Setup和Verify算法和上面的PoRep构建是一样的。所以我们这里值描述Prove。

1.空间和时间的证明 Prove算法为副本生成“时空证明”。证明人接收到来自于验证者的随机挑战,并顺序生成”复制证明“,然后使用证明的输出作为另一个输入做指定t次迭代(见图3)。

Figure 3: 演示PoSt.Prove的底层机制,展示用于演示随时间变化的存储的迭代证明.