可验证延迟函数（VDFs）简介
在区块链上获取随机性非常困难。开发者在链上获取随机值时常犯的一个经典错误是使用未来区块哈希、区块难度或时间戳等量。这些方案的问题在于它们容易受到矿工的操纵。例如，假设我们正在运行一个链上彩票，用户猜测下一个区块的哈希是偶数还是奇数。矿工可以赌结果为偶数，如果他们挖出的下一个区块是奇数，就丢弃它。在这里，丢弃奇数区块会略微增加矿工赢得彩票的概率。现实世界中有许多通过区块变量生成“随机性”的例子，但它们都存在一个不可避免的问题：观察者很容易通过计算确定他们的选择将如何影响链上生成的随机性。
另一个相关的问题是在权益证明协议中选举领导者和验证者。在这种情况下，能够影响或预测随机性使矿工能够影响他们被选中挖块的时间。有多种技术可以克服这个问题，例如Ouroboros的可验证秘密共享方案。然而，它们都存在同样的缺陷：必须存在一个不串通的诚实多数。
在上述两种场景中，攻击者很容易看到不同输入如何影响伪随机数生成器的结果。这导致Boneh等人定义了可验证延迟函数（VDFs）。VDFs是需要中等量顺序计算来评估的函数，但一旦找到解决方案，任何人都可以轻松验证其正确性。将VDFs视为对某些伪随机生成器输出施加的时间延迟。这种延迟防止恶意行为者影响伪随机生成器的输出，因为所有输入将在任何人完成计算VDF之前最终确定。
当用于领导者选择时，VDFs比可验证随机函数有显著改进。VDF-based领导者选择不需要不串通的诚实多数，只需要任何诚实参与者的存在。这种增加的鲁棒性是由于无论多少并行性都不会加速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构造之前，让我们检查为什么一个“明显”但不正确的方法会失败。一种这样的方法是重复哈希。如果某个哈希函数h的计算需要t步，那么使用f = h(h(…h(x)))作为VDF肯定会满足上述顺序要求。确实，无法通过并行性加速此计算，因为哈希的每次应用完全依赖于前一次的输出。然而，这不能满足VDF的高效可验证要求。任何试图验证f(x) = y的人都必须重新计算整个哈希链。我们需要VDF的评估计算时间比验证时间指数级更长。
VDF 候选方案
目前有三种满足VDF要求的候选构造。每种都有其潜在的缺点。第一种在Boneh等人的原始VDF论文中概述，并使用单射有理映射。然而，评估此VDF需要相当大量的并行处理，导致作者将其称为“弱VDF”。后来，Pietrzak和Wesolowski独立地得出了基于未知阶群中重复平方的极其相似的构造。在高层次上，Pietrzak方案的工作原理如下。
设置VDF，选择时间参数T，一个未知阶的有限阿贝尔群G，以及一个从字节到G元素的哈希函数H。
给定输入x，令g = H(x)，通过计算y = g2T评估VDF。
重复平方计算不可并行化，并且在最后一次平方之前不揭示最终结果。这些特性都是由于我们不知道G的阶。这些知识将允许攻击者使用基于群论的攻击来加速计算。
现在，假设有人断言VDF的输出是某个数字z（可能等于y，也可能不等于）。这等价于显示z = v2(T/2)且v = g2(T/2)。由于前两个方程具有相同的指数，它们可以通过检查随机线性组合同时验证，例如，对于{1, … , 2λ}中的随机r（其中λ是安全参数），验证vr z = (gr v)2(T/2)。更正式地，证明者和验证者执行以下交互式证明方案：
- 证明者计算v = g2(T/2)并将v发送给验证者
- 验证者向证明者发送{1, … , 2l}中的随机r
- 证明者和验证者都计算g1 = gr v和z1 = vr z
- 证明者和验证者递归证明z1 = g12(T/2)
上述方案可以使用称为Fiat-Shamir启发式的技术变得非交互。在这里，证明者通过哈希(G,g,z,T,v)并在每个递归级别生成挑战r，并将v附加到证明中。在这种情况下，证明包含log2 T个元素，并需要大约(1 + 2/√T) T。
Pietrzak 方案的安全分析
Pietrzak方案的安全性依赖于低阶假设的安全性：对手在计算上不可能在VDF使用的群中找到低阶元素。要了解为什么找到低阶元素会破坏方案，首先假设恶意证明者Eve找到了某个小阶d的元素m。然后Eve向验证者发送zm（其中z是有效输出）。无效输出将以概率1/d被接受，因为：
- 在计算递归的第二步时，我们将有基本元素g1 = gr v，其中v = g2T/2 m，并且需要显示g1T/2 = vr(zm)
- 左侧的m项是mT/2
- 右侧的m项是mr+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结合的伪随机数生成器。虽然这两个都是非常令人兴奋的项目，对区块链社区将非常有益，但这仍然是一个非常年轻的研究领域。对任何安全声明持保留态度。
如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News
页面内容 VDF 定义 VDF 候选方案 Pietrzak 方案的安全分析 VDF 的现状和开放问题 最近的帖子 使用Deptective调查您的依赖项 系好安全带，Buttercup，AIxCC的评分回合正在进行中！ 使您的智能合约超越私钥风险 Go解析器中意外的安全陷阱 我们从审查首批DKLs23库中学到了什么 来自Silence Laboratories的23个库 © 2025 Trail of Bits。 使用Hugo和Mainroad主题生成。