Arweave第17版白皮书解读（三）：SPoRes游戏的论证

作者：Arweave Oasis，来源：PermaDAO

本文有些硬核，因为会有很多数学推导论证过程，各位朋友要作好准备。但笔者认为数学作为基础学科，在从逻辑上解释一个事物有着极强的精准性，所以不妨让笔者试试用简单的语言来展示 @ArweaveEco 机制中的数学之美。

在白皮书解读（二）文章中，我们描述了简洁访问证明（ #SPoA ）游戏可以被任何参与者用来证明他们在数据集的特定位置确实存储了一些数据。这个模式还可以用来创建第二个游戏，我们称其为简洁的复制证明（Succinct Proofs of Replications #SPoRes ），这将允许证明者无论数据集大小如何，都能以极小的数据传输和验证成本，来向验证者证明自己存储了一定数量的数据副本。

SPoRes 游戏

简洁的复制证明（SPoRes）游戏是这样进行的。Alice 声称她存储了 n 份默克尔化数据集的唯一副本。Bob 想要验证 Alice 有没有说谎。为了做到这一点，他给 Alice 一个难度参数 d 和一个随机产生的种子 Seed。Alice 使用这个 Seed 生成一个每秒钟发出一个检查点的 VDF 哈希链，这个检查点可以用来解锁数据集内最多 k 个 SPoA 挑战。每当她有对应于这些挑战的打包数据块时，Alice 可以构建相应的 SPoA 证明。然后将这些证明进行哈希处理，并与 Bob 的难度参数 d 进行对比。如果证明哈希值大于 d，则 Alice 找到了一个有效解决方案，并将相应的证明发送给 Bob。Bob 则记录下发送随机种子到收到 Alice 有效证明之间的时间。

基于难度 d，单次尝试找到有效解决方案的概率 p 的表达式为：

公式注解：由于基于 SHA 256 的算法是一个 256 位字符串，所以就有 2^256 (这里「^」表示的是次方的意思) 个最大哈希数量，如果要找到大于 d 的有效解决方案，那只有 2^256-d 个哈希数量，以此可以计算出单次尝试成功的概率。

如果 Alice 有 n 个副本，并且每秒每个副本可以进行 k 次尝试，那么她在任何给定的一秒时间内找到解决方案的概率是：

公式注解：kN 的意思为 Alice 在一秒内总共可以进行的哈希解决方案尝试次数，这个尝试次数与 Alice 存储的唯一副本数量成正比，具体解释可以阅读此前文章 《Arweave 2.6 也许更符合中本聪的愿景》的内容。1-p 是单次尝试失败的概率。p2 的概率值就是 1 减去 kN 次尝试失败的概率的差。

通过上述两个公式的代入推导，我们可以得到：

公式注解：将 p 代入至 P2 的公式中所得结果

Alice 提交证明所需的时间可以用一个几何随机变量 X ~ geom(p2) 来模拟，p2 为成功的概率。这个随机变量 X 取决于 d，k 和 n。为了验证 Alice 是否说谎，Bob 发送一个难度 d，使 Alice 以有 n 个副本的前提下，可以每 120 秒向 Bob 提交一次证明。这相当于 Alice 在 120 秒的成功概率为：

公式注解：1/120 为 120 秒内成功提交一次证明的概率

如果 Alice 可以在要求的时间内提交证明，那她很可能拥有正确数量的唯一副本。但一次证明是不足以让 Bob 确信 Alice 没有说谎，如果 Alice 能在很长一段时间内平均每 120 秒一直提交证明，Bob 才可以合理地确信 Alice 存储了符合期望的数据量。

接下来我们尝试去量化 Bob 对 Alice 存储的确定性。

假设 Alice 声称存储了 20 个副本，并且在 2 周的时间内以平均 120 秒的速度一致地提交了证明（总共提交了 10,080 个证明）。此时，Bob 在想如果 Alice 只存储了 19 个（或更少）的副本，她依然能提交这些证明的概率是多少。这对应于在不同的一秒钟内提供证明的概率：

公式注解：这里出现的 19k，就是 Alice 存了 19 个副本，每个副本拥有 k 次尝试寻找解决方案的次数。

过简化:

这个概率可以使用 Bob 为诚实的 Alice 生成的 d 值来计算。如果她存储了 19 个或更少的副本，她一秒钟内提供证明的概率可以通过下面给出的一系列推导得到。其中， p2 代表了 Alice 诚实存储了 20 个副本时，一秒内生成证明的概率，而 p2* 则代表如果她在说谎（存储≤ 19 个副本）时，一秒内提供证明的概率：