共识中的可验证随机函数

共识协议需要随机性来进行领导者选举、委员会选择和分片分配。这种随机性必须满足三个属性：不可预测性（在输出揭示前任何人都无法预测结果）、不可偏置性（任何参与者都无法操纵结果来使自己获利）以及公开可验证性（任何人无需信任生成者即可验证输出是否正确）。简单方法都会失败：单个节点的随机数可以被操纵，而提交-揭示方案会受到最后揭示者偏置的影响。可验证随机函数（VRF）解决了全部三个要求。

可验证随机函数（VRF）由 Micali、Rabin 和 Vadhan 于 1999 年提出，是一种能够提供正确性证明的伪随机函数。VRF 包含三个算法：KeyGen 生成密钥对（SK、PK）；Prove(SK, alpha) 生成（beta、pi），其中 beta 是输出，pi 是证明；Verify(PK, alpha, beta, pi) 返回有效或无效。对于不知道 SK 的任何人而言，输出 beta 都与随机值不可区分（VRF 伪随机性），而证明 pi 不可伪造（VRF 唯一性）。证明大小为 O(1)，无论输入是什么，始终保持不变。

目前部署最广泛的 VRF 构造是 ECVRF（IETF RFC 9381），其安全性基于椭圆曲线离散对数问题的困难性。给定私钥 x 和输入 alpha，证明者先计算 H = hash-to-curve(PK, alpha)（将 alpha 映射为曲线上的点），然后计算 gamma = x * H（标量乘法）。VRF 输出 beta = keccak(gamma)。证明 pi 使用类似 Schnorr 的零知识论证：证明者选取随机 k，计算挑战 c = hash(H, gamma, k*G, k*H)，计算响应 s = k - c*x，并输出 pi = (gamma, c, s)。验证过程会检查 Schnorr 方程，并重新计算 beta。

Algorand（Silvio Micali 等人，2017 年）率先将 VRF 应用于区块链共识。在每个轮次中，每个验证者都会私下计算 VRF(SK, round || seed)，以获得随机输出。随后将该输出与阈值进行比较：如果 VRF_output < stake_fraction * threshold，则该验证者会被选为委员会成员或区块提议者。直到验证者连同 VRF 证明广播其区块或投票之前，只有该验证者自己知道是否入选。这种密码学自我选择机制消除了公开领导者选举的需要，使 Algorand 能够抵御针对已知即将担任领导者的定向拒绝服务攻击。

Cardano 的 Ouroboros Praos（当前部署的版本）使用 VRF 进行时隙领导者选举。每个纪元都会从区块链中导出一个新的随机种子。每个质押池运营者（SPO）都会针对该纪元中的每个时隙计算 VRF(SK, slot || epoch_seed)。如果输出低于与其质押量成比例的阈值，该运营者就会成为该时隙的领导者，并可以生成区块。VRF 证明会包含在区块头中，因此任何人都可以验证该 SPO 是否经过合法选举。这使 Cardano 能够针对在纪元中途获知领导者计划的自适应对手，提供可证明的安全性。

Ethereum 使用 RANDAO（累积的 BLS 签名）而不是 VRF 作为随机性信标。RANDAO 更简单——除 BLS 之外不需要额外的密码学原语——但容易受到最后揭示者偏差的影响：如果区块提议者能够预测自己的 RANDAO 贡献会产生不利结果，就可以选择不发布区块（代价是损失区块奖励）。基于 VRF 的选举会隐藏入选者的身份，直到其主动揭示身份，从而彻底消除这一攻击路径。权衡在于：VRF 会增加密码学复杂性（哈希到曲线、证明生成），而 RANDAO 可以复用现有的 BLS 基础设施。

Chainlink VRF 为智能合约提供可验证的随机性服务。使用方合约通过支付 LINK 代币来请求随机性。Chainlink 预言机节点持有一对 VRF 密钥。该节点计算 ECVRF(SK, seed)，其中 seed 由区块哈希和用户提供的随机数导出，然后将 (beta, pi) 提交到链上。VRF 协调器合约会先验证证明，再将随机输出转发给使用方。这样，智能合约无需区块链实现原生 VRF 信标，就能获得抗操纵的随机性，可用于 NFT 铸造、彩票和游戏。

Signal Protocol 使用 VXEdDSA（可验证的 X25519 EdDSA），这是一种基于 Curve25519 的 VRF 构造。当发送方生成一次性预密钥签名时，VRF 会根据消息和发送方密钥生成确定性但不可预测的随机数。这可以防止随机数重复使用（否则会破坏 EdDSA 的安全性），同时保持签名可验证。VRF 证明允许接收方验证随机数是否经过正确派生，从而防止发送方选择可能导致密钥恢复攻击的恶意随机数。VXEdDSA 展示了 VRF 作为通用密码学工具在共识领域之外的应用。

可验证延迟函数（VDF）有时会与 VRF 混淆。VDF 要求至少进行 T 个步骤的顺序计算（时间锁属性），并生成一个带有简短正确性证明的输出。VDF 可用于缓解 RANDAO 的最后揭示者偏差：Ethereum 计划中的 VDF 层会使任何操纵尝试都必须提前运行 VDF，而运行时间会超过攻击窗口。VRF 提供即时的私下计算；VDF 提供公开但缓慢的计算。二者相互补充：VDF 防止最后揭示者偏差，VRF 防止领导者预测。

VRF 选举针对自适应对手提供了重要的安全性改进。在 PBFT 和 Tendermint 中，领导者身份会预先确定（采用轮询调度），因此对手可以在下一位领导者提出区块之前对其发起分布式拒绝服务攻击。基于 VRF 的选举（Algorand、Cardano）会将领导者身份保密，直到区块被广播；到那时区块已经提出，拒绝服务攻击为时已晚。这称为自适应安全性或不可预测的领导者选举。实现这一点的密码学性质是：对于不持有私钥的任何人而言，VRF 输出都呈现伪随机性。

正确实现 VRF 需要注意几个方面。哈希到曲线必须使用常数时间且均匀的算法（IETF RFC 9380 定义了标准化方法，以防止时序泄漏）。证明中的 VRF 随机数 k 必须使用 RFC 6979，根据 (SK, alpha) 确定性地派生——重复使用 k 或使用弱随机的 k 会泄露私钥（与 ECDSA 随机数重复使用时的漏洞相同）。ECVRF-P256-SHA256-TAI 的证明大小为 80 字节；ECVRF-ED25519-SHA512-ELL2 的证明大小也是 80 字节，二者都适合包含在链上。VRF 的唯一性保证对于同一个 (SK, alpha) 对，不会存在两个有效证明。

为什么基于 VRF 的领导者选举比轮流领导者调度提供更强的安全性？

VRF 会生成带有正确性密码学证明的伪随机输出，从而满足不可预测性、不可偏置性和公开可验证性。ECVRF（RFC 9381）是基于椭圆曲线的标准构造。Algorand 使用 VRF 密码学自我选择机制来抵抗自适应对手。Cardano Ouroboros Praos 使用 VRF 进行逐时隙的领导者选举。Chainlink VRF 为智能合约提供可验证的随机性。VRF 与 VDF 互为补充（VDF 用于解决最后揭示者偏差），并且不同于 RANDAO（RANDAO 使用累积的 BLS 签名，但存在已知的最后揭示者弱点）。