可验证延迟函数（VDFs）简介
区块链随机性的挑战
在区块链上获取随机数十分困难。开发者常犯的一个经典错误是使用未来区块哈希、区块难度或时间戳等量作为随机值。这些方案的问题在于它们容易受到矿工的操纵。例如，假设我们试图运行一个链上彩票，用户猜测下一个区块的哈希是偶数还是奇数。矿工可以押注结果为偶数，如果他们挖出的下一个区块是奇数，就丢弃它。在这里，丢弃奇数区块会略微增加矿工赢得彩票的概率。
现实中有许多通过区块变量生成“随机性”的例子，但它们都面临一个不可避免的问题：观察者很容易通过计算确定他们的选择将如何影响链上生成的随机性。
另一个相关的问题是在权益证明协议中选举领导者和验证者。在这种情况下，能够影响或预测随机性使得矿工可以影响他们被选中挖块的时间。虽然有多种技术可以克服这个问题，例如 Ouroboros 的可验证秘密共享方案，但它们都面临同样的缺陷：必须存在一个不串通的诚实多数。
可验证延迟函数的定义
在上述两种场景中，攻击者很容易看到不同输入如何影响伪随机数生成器的结果。这促使 Boneh 等人定义了可验证延迟函数（VDFs）。VDFs 是需要中等量顺序计算来评估的函数，但一旦找到解决方案，任何人都可以轻松验证其正确性。将 VDFs 视为对某些伪随机生成器输出施加的时间延迟。这种延迟可以防止恶意行为者影响伪随机生成器的输出，因为所有输入将在任何人完成计算 VDF 之前最终确定。
当用于领导者选择时，VDFs 相比可验证随机函数提供了显著改进。VDF 基于的领导者选择不需要不串通的诚实多数，只需要存在任何诚实参与者。这种增加的鲁棒性是由于无论多少并行性都无法加速 VDF，并且任何非恶意行为者都可以轻松验证其他人声称的 VDF 输出是否准确。
VDF 定义
给定延迟时间 t，可验证延迟函数 f 必须满足：
- 顺序性：任何人都可以在 t 个顺序步骤中计算 f(x)，但拥有大量处理器的对手无法在显著更少的步骤中将 f(x) 的输出与随机数区分开。
- 高效可验证性：给定输出 y，任何观察者都可以在短时间内（具体为 log(t)）验证 y = f(x)。
换句话说，VDF 是一种函数，其计算时间（即使在高并行处理器上）比在单处理器上验证的时间呈指数级增长。此外，验证者接受错误 VDF 输出的概率必须非常小（在初始化时由安全参数 λ 选择）。在达到最终结果之前，没有人能够将 f(x) 的输出与随机数区分开，这一条件至关重要。
假设我们正在运行一个彩票，用户提交 16 位整数，获胜数字通过将种子提供给需要 20 分钟计算的 VDF 来确定。如果对手在仅进行 1 分钟的 VDF 计算后就能了解到 VDF 输出的 4 位，那么他们可能会改变提交内容，并将成功机会提高 16 倍！
VDF 候选方案
目前有三种满足 VDF 要求的候选构造。每种都有其潜在的缺点。第一种在 Boneh 等人的原始 VDF 论文中概述，使用单射有理映射。然而，评估此 VDF 需要相当大量的并行处理，导致作者将其称为“弱 VDF”。后来，Pietrzak 和 Wesolowski 独立地提出了基于未知阶群中重复平方的极其相似的构造。
Pietrzak 方案
高层次上，Pietrzak 方案的工作原理如下：
设置 VDF，选择时间参数 T、未知阶的有限阿贝尔群 G，以及从字节到 G 元素的哈希函数 H。
给定输入 x，令 g = H(x)，通过计算 y = g^(2^T) 来评估 VDF。
重复平方计算不可并行化，并且在最后一次平方之前不会揭示最终结果。这些特性都是由于我们不知道 G 的阶。了解阶会让攻击者使用基于群论的攻击来加速计算。
现在，假设有人断言 VDF 的输出是某个数字 z（可能等于 y，也可能不等于）。这等价于显示 z = v^(2^(T/2)) 且 v = g^(2^(T/2))。由于前两个方程具有相同的指数，可以通过检查随机线性组合来同时验证它们，例如，对于随机 r 在 {1, … , 2^λ} 中（其中 λ 是安全参数），验证 v^r z = (g^r v)^(2^(T/2))。更正式地，证明者和验证者执行以下交互式证明方案：
- 证明者计算 v = g^(2^(T/2)) 并将 v 发送给验证者。
- 验证者向证明者发送随机 r 在 {1, … , 2^λ} 中。
- 证明者和验证者都计算 g1 = g^r v 和 z1 = v^r z。
- 证明者和验证者递归证明 z1 = g1^(2^(T/2))。
上述方案可以使用称为 Fiat-Shamir 启发式的技术变为非交互式。在这里，证明者通过哈希 (G, g, z, T, v) 并在每个递归级别生成挑战 r，并将 v 附加到证明中。在这种情况下，证明包含 log2 T 个元素，并且需要大约 (1 + 2/√T) T 的计算。
Pietrzak 方案的安全分析
Pietrzak 方案的安全性依赖于低阶假设的安全性：对手在计算上不可行地在 VDF 使用的群中找到低阶元素。要了解为什么找到低阶元素会破坏方案，首先假设恶意证明者 Eve 找到了某个小阶 d 的元素 m。然后 Eve 向验证者发送 z m（其中 z 是有效输出）。无效输出将以概率 1/d 被接受，因为：
在计算递归的第二步时，我们将有基元素 g1 = g^r v，其中 v = g^(2^T/2) m，并且需要显示 g1^(T/2) = v^r (z m)。
左边的 m 项是 m^(T/2)。
右边的 m 项是 m^(r+1)。
由于 m 的阶为 d，当 r+1 = T/2 mod d 时，这两项相等，这种情况以概率 1/d 发生。
要查看低阶假设为什么是必要且充分的条件以显示 Pietrzak 方案是健全的完整证明，请参阅 Boneh 对最近 VDF 构造的综述。
安全分析假设可以轻松生成满足低阶假设的未知阶群。我们将在下面看到，目前已知的满足这些约束的群并不适合无信任设置，即没有一方可以破坏 VDF 协议的设置。
例如，尝试使用每个人最喜欢的群族：两个大素数乘积的整数模（RSA 群）。这些群具有未知阶，因为找到阶需要分解大整数。然而，它们不满足低阶假设。确实，元素 -1 总是阶为 2。这种情况可以通过将 RSA 群 G 除以子群 {1,-1} 来补救。事实上，如果 G 的模是强素数的乘积（即 p-1/2 也是素数的素数），那么在取上述商之后，除了 1 之外没有低阶元素。
这一分析表明 RSA 群对 Pietrzak 的 VDF 是安全的，但有一个问题。要生成 RSA 群，必须有人知道模数 N 的因式分解。设计一个无信任的 RSA 群选择协议——没有人知道模数 N 的因式分解——因此是该领域一个有趣且重要的开放问题。
实例化 Pietrzak 方案的另一个工作途径涉及使用虚二次数域的类群。该群族不受上述选择需要可信第三方的问题影响。简单地选择一个大的负素数（带有几个注意事项）将生成一个群，其阶在计算上不可行确定，即使对于选择素数的人也是如此。然而，与 RSA 群不同，二次数域类群中寻找低阶元素的困难尚未得到充分研究，在任何此类方案使用之前需要更多调查。
VDF 的现状和开放问题
如前一节所述，Pietrzak 和 Wesolowski 方案都依赖于生成未知阶的群。在 RSA 群的情况下，没有可信方这样做是困难的，但类群似乎是一个有希望的工作途径。此外，Wesolowski 方案假设存在满足所谓自适应根假设的群，这在数学文献中尚未得到充分研究。该领域还有许多其他开放问题，包括构建抗量子 VDF，以及 ASIC 在实践中破坏 VDF 构造安全保证的潜力。
至于行业对 VDF 的采用，区块链领域的几家公司正在尝试将 VDF 用于共识算法。例如，Chia 使用上述重复平方技术，并且目前正在举办该方案最快实现的竞赛。以太坊基金会似乎也在开发一种将 RANDAO 与 VDF 结合的伪随机数生成器。虽然这两个都是非常令人兴奋的项目，对区块链社区将大有裨益，但这仍然是一个非常年轻的研究领域。对任何安全声明持保留态度。