可验证延迟函数(VDF)入门指南
区块链随机性的挑战
在区块链上获取随机数非常困难。开发者常犯的典型错误是使用未来区块哈希、区块难度或时间戳等链上数据作为随机源。这类方案的共同问题是容易被矿工操纵。例如：
- 假设我们运行一个链上彩票游戏，用户猜测下一个区块哈希的奇偶性
- 矿工可以押注"偶数"，如果挖出的区块哈希为奇数就丢弃该区块
- 这种策略能轻微提高矿工的中奖概率
权益证明(PoS)协议中的验证者选举也存在类似问题。攻击者可以轻易观察不同输入如何影响伪随机数生成器的输出结果。
VDF的核心定义
给定延迟时间t，可验证延迟函数f必须满足：
- 顺序性：任何人都能用t个顺序步骤计算f(x)，但拥有大量处理器的攻击者无法显著更快地辨别f(x)的输出
- 高效可验证性：给定输出y，任何观察者都能在极短时间内(具体为log(t))验证y = f(x)
VDF的关键特性在于：
- 计算时间呈指数级高于验证时间
- 在最终结果产生前，输出不可区分于随机数
- 验证者接受错误输出的概率必须极低(由安全参数λ控制)
VDF候选构造方案
目前有三种满足要求的VDF构造方案，各具特点：
Pietrzak方案(基于未知阶群的重复平方)
- 设置阶段：
- 选择时间参数T
- 选择未知阶的有限阿贝尔群G
- 选择哈希函数H: bytes → G
- 计算过程：
- 输入x，计算g = H(x)
- 输出y = g^(2^T)
- 验证协议(可通过Fiat-Shamir启发式转为非交互式)：
- 证明者计算v = g^(2^(T/2))并发送给验证者
- 验证者发送随机数r ∈ {1,…,2^λ}
- 双方计算g₁ = gʳv，z₁ = vʳz
- 递归证明z₁ = g₁^(2^(T/2))
Pietrzak方案的安全分析
该方案的安全性依赖于低阶假设：攻击者难以在VDF使用的群中找到低阶元素。如果发现阶为d的低阶元素m：
- 恶意证明者发送zm给验证者
- 无效输出被接受的概率为1/d
群选择问题
- RSA群：需要可信第三方生成(因需知道模数分解)
- 类群：无需信任设置，但低阶元素安全性研究不足
VDF现状与开放问题
实现挑战
- 无信任的RSA群生成仍是开放问题
- Wesolowski方案依赖的"自适应根假设"缺乏数学研究
- 抗量子VDF构造
- ASIC对实际安全性的影响
行业应用
- Chia：采用重复平方技术，举办实现竞赛
- 以太坊基金会：开发结合RANDAO与VDF的伪随机数生成器
警告：该领域研究仍处于早期阶段，所有安全性声明都应谨慎看待。