本节中, 我们将展示和概括在 Filecoin 中所使用的复制证明 (Proof-of-Replication,PoRep) 和时空证明 (Proof-of-Spacetime,PoSt) 实现方案
3. 复制证明与时空证明
在 Filecoin 协议中, 存储供应商必须让客户相信, 他们的数据已经被完好存储在实际操作中, 存储供应商会生成存储证明 (Proofs-of-Storage,POS) 给区块链网络 (或客户本身) 进行验证
本节中, 我们将展示和概括在 Filecoin 中所使用的复制证明 (Proof-of-Replication,PoRep) 和时空证明 (Proof-of-Spacetime,PoSt) 实现方案
3.1 动机
存储证明 (POS) 方案, 例如可证明数据拥有 (PDP) 以及可恢复性证明 (PoR) 方案, 它允许用户 (即审核人 V) 将数据外包给服务器 (既证明人 P) 以检查服务器是否依然存储数据 D 用户可以用比下载数据还便捷的方式, 来验证外包给服务器数据的完整性服务器通过对一组区块进行随机采样和传送少量数据, 来生成概率性的拥有证明, 以此作为给用户的怀疑 / 响应协议
PDP 和 PoR 方案只允许证明人在怀疑 / 响应的时候拥有某些数据在 Filecoin 中, 我们需要更强大的保障, 来阻止恶意矿工通过攻击获得不应得的奖励常见的三种攻击类型有: 女巫攻击 (Sybil attack) 外包攻击 (outsourcing attacks) 生成攻击(generation attacks)
3.2 复制证明
复制证明 (PoRep) 是一个新型的存储证明, 它允许服务器 (证明人 P) 向用户 (审核人 V) 证明: 数据 D 已被复制到它专有的物理存储上了我们的方案是一种交互式协议, 证明人 P:(a)承诺存储数据 D 的 n 个不同的拷贝 (独立物理拷贝), 然后(b) 通过怀疑 / 响应协议来使审核人 V 相信 P 确实已经存储了每个拷贝我们目前已经知道, PoRep 在 PDP 和 PoR 方案中, 阻止女巫攻击外包攻击生成攻击的能力会有所提高
注意, 想要 PoRep 正式的定义, 以及了解它的属性和深入研究的, 我们推荐参考[5]
定义六 PoRep 方案允许有效的证明人 P 来说服审核人 V: 数据 D 的独立物理副本 R 已被 p 存储 PoRep 协议是多项式时间算法的元组:
(Setup, Prove, Verify)
Setup(1λ, D) R, SP , SV, 其中 SP 和 SV 是为方案专门设定的 P 和 V 变量,λ是一个安全参数 PoRep.Setup 用来生成副本 R, 以及给予 P 和 V 必要的信息来运行 PoRep.Prove 和 PoRep.Verify 一些方案可能会要求证明人或者第三方交互来运算 PoRep.Setup
Prove(SP, R, c) πc, 其中 c 是审核人 V 发出的随机质疑, πc 是证明人产生的访问 R 的证明, R 是 D 的特定副本 PoRep.Prove 由 P 运行, 为 V 生成πc
Verify(Sv, c, πc) {0, 1}, 用来检测证明是否正确 PoRep.Verify 由 V 运行, 并使 V 相信 P 已经存储了 R
3.3 时空证明
存储证明方案允许用户检查存储提供商当时是否存储了外包数据我们如何使用 PoS 方案来证明在一段时间内数据被存储了? 一个非常自然的答案是要求用户重复 (例如, 每分钟) 对存储提供商发送请求然而这样的交互所需要的通信复杂度会成为一些系统的瓶颈像 Filecoin 这样, 存储提供商会被要求提交证明到区块链网络
为了解决这个问题, 我们介绍一个新的证明, 时空证明 (Proof-of-Spacetime), 它可以让审核人检查存储提供商是否在一段时间内存储了他的外包数据这就对证明人产生了直观的要求:(1) 生成连续的存储证明 (在本文中是复制证明) 来作为确定时间的一种方法 (2) 递归执行来生成简单的证明
定义七 (时空证明)Post 方案可使有效的证明人 P 能够说服一个审核人 V 相信 P 在一段时间内存储了数据 DPoSt 是多项式时间算法的元组:
(Setup, Prove, Verify)
Setup(1λ, D) R, SP , SV, 其中 SP 和 SV 是为方案专门设定的 P 和 V 变量,λ是一个安全参数 PoRep.Setup 用来生成副本 R, 以及给予 P 和 V 必要的信息来运行 PoRep.Prove 和 PoRep.Verify 一些方案可能会要求证明人或者第三方交互来运算 PoRep.Setup
Prove(SP, R, c) πc, 其中 c 是审核人 V 发出的随机质疑, πc 是证明人产生的访问 R 的证明, R 是 D 的特定副本 PoRep.Prove 由 P 运行, 为 V 生成πc
Verify(Sv, c, πc) {0, 1}, 用来检测证明是否正确 PoRep.Verify 由 V 运行, 并使 V 相信 P 已经存储了 R
3.4 PoRep 和 PoSt 实际应用
我们对 PoRep 和 PoSt 在现有系统上的应用很感兴趣, 希望能构建一个实用性系统, 但不依赖任何的中心式第三方或者硬件我们给出了一个 PoRep 架构(见密封的复制证明[5]), 它需要在 Setup 过程中执行缓慢的顺序计算密封来生成副本 PoRep 和 PoSt 的协议草图详见图 4,Post 证明步骤的底层机制的见图 3
3.4.1 构建加密区块
防碰撞散列我们使用一个防碰撞散列函数: CRH : {0, 1}* {0, 1}O(λ)以及另一个一个防碰撞散列函数 MerkleCRH, 它可以将字符串分割成多个部分, 构造二叉树并将递归应用到 CRH, 最后输出根
zk-SNARKs 我们对 PoRep 和 PoSt 的实现依赖于零知识的简洁非交互式知识论 (zero-knowledge Succinct Noninteractive ARguments of Knowledge,zk-SNARKs)[6,7,8] 因为 zk-SNARKs 非常简洁, 证明短并且容易验证形式上来说, 就是让 L 作为 NP 语言, 并用 C 做为 L 的判决电路中心式信任方执行一次设置会产生两个公共密钥: 证明密钥 pk 和验证密钥 vk 证明密钥 pk 可使任何 (非信任的) 的证明人都能生成证明π来证明 xL,x 是任一实例非交互式证明π是零知识的, 也是知识证明的任何人都可以使用验证密钥 vk 来验证π证明尤其 zk-SNARK 的证明是可公开验证的: 任何人都可以验证π, 而不需要与生成π的证明者进行交互π证明具有恒定的大小, 并且可以在 | x | 的线性时间内得到及时验证
zk-SNARKs 是一个三项式时间算法:
(KeyGen, Prove, Verify)
KeyGen(1λ,C)(pk, vk)输入安全参数为λ, 回路为 C,pk 和 vk 是 KeyGen 的概率样本这两个密匙是公共参数, 可用于证明 / 审核 Lc 上的成员
Prove(pk, x, w)π在输入 pk 输入 x 并看到 NP 声明 w 后, 如果 xLC, 证明人 Prove 会输出非交互式证明π
Verify(vk, x,π){0, 1}当输入 vk,x 和证明 π, 如果有 xLC, 审核人 verifier 输出 1
建议有兴趣的读者阅读 [6,7,8], 那里有对 zk-SNARK 系统的概念和实现更详细的介绍通常来说系统会要求 KeyGen 是由中心式可信任参与方来运行的新型可扩展计算的完整性和隐私性(SCIP) 系统 [9] 展示了一个很有前景的可以避免这个步骤的发展方向, 才有了上面的信任假设
3.4.2 密封操作
密封操作的作用是:(1)通过要求证明人存储公钥下数据 D 的伪随机序列, 强制副本成为成为相互独立的拷贝, 这样提交 n 个副本后就会产生 n 个独立的磁盘空间 (并占用副本大小 n 倍的储存空间)(2) 在运行 PoRep.Setup 的时候强制生成副本, 实质上会比预估的质疑响应花费更多的时间有关密封操作的更正式定义, 请参见 [5] 上述的操作可以用 SealτAES?256 实现, SealτAES?256 中的τ需要比常规的质疑 - 证明 - 审核序列多花费 10-100 倍的时间所以对τ的选择非常重要的, 因为运行 SealτBC 可能比证明人随机访问 R 要花费更多时间
3.4.3 PoRep 构建实践
本节将描述 PoRep 协议的组成, 并在图 4 展示简化的协议草图我们略过了具体实现方法和优化细节
创建副本 Setup 算法通过密封操作, 和正确生成副本的证明, 来实现副本的生成证明人生成副本, 并将输出 (不包括 R) 发送给审核人
证明存储 Prove 算法生成副本存储的证明证明人收到来自审核人的随机质疑 c 该审核人在树根为 rt 的 Merkle 树 R 中确定叶子节点 Rc 证明人生成关于 Rc, 和其延伸到叶子 Rc 的 Merkle 路径的知识证明
审核证明考虑到副本的 Merkle 树根, 和原始数据的散列, Verify 算法会审核存储证明的有效性证明是公开可验证的: 分布式系统的节点保持了账本和客户对特定数据的关注, 这样就能验证这些证明
3.4.4 PoSt 构建实践
本节将描述 Post 协议架构, 并在图 4 中给出一个简单协议草图本节忽略实现过程和优化细节 Setup 和 Verify 算法和前文的 PoRep 架构相同, 所以这里只描述 Prove
证明时空 Prove 算法为副本生成时空证明证明人接收来自于审核人的随机质疑, 并顺序生成复制证明, 证明输出后, 经过特定次数的迭代 t, 可作为其他的输入(见图 3)
Figure 3: Illustration of the underlying mechanism of PoSt.Prove showing the iterative proof to demonstrate storage over time.
3.5 在 Filecoin 中的应用
Filecoin 协议采用时空证明来审核矿工提供的存储因为没有指定的审核人, 并且我们希望网络中的任何成员都有审核权, 所以为了在 Filecoin 中使用 PoSt, 我们把方案改为了非交互式的我们的审核人在公开的代币模型中运行, 所以我们可以从区块链中随机地发出质疑
来源: http://stor.51cto.com/art/201803/569295.htm