可验证随机函数 VRF：从数学原理到区块链共识的密码学抽签

密码学概念 · 2026-07-06

概述

可验证随机函数 (Verifiable Random Function, VRF) 是一种公钥密码学原语，允许持有私钥的证明者对输入生成伪随机输出，同时附上可供任何验证者检验正确性但不泄露私钥的证明。VRF 的核心价值在于输出的可验证性（verifiability）与伪随机性（pseudorandomness）在公钥体系下的统一。

VRF 最早由 Silvio Micali (2013 年图灵奖得主)、Michael Rabin 和 Salil Vadhan 于 1999 年提出 [MRV99]。在之后的二十余年中，VRF 从理论构造发展为实际可用的密码学工具，在以下场景中产生深远影响：

区块链共识：Algorand 使用 VRF 实现"密码学抽签"，无偏地选举区块提议者和验证委员会
去中心化随机数：drand 网络使用基于 BLS 签名的 VRF 为智能合约提供可验证随机性
DNS 安全：DNSSEC 的 NSEC3 使用 VRF 防止区域遍历
零知识证明：某些 ZKP 方案利用 VRF 实现高效的承诺和开放机制

本文将从安全定义、构造方法、标准协议和实践应用四个层次，系统解析 VRF 的设计思想与工程实现。

安全定义

VRF 必须满足以下安全特性，使其区别于普通数字签名和普通随机函数。

唯一性 (Uniqueness)

对任意固定的公钥 PK 和任意输入 $\alpha$，至多存在一个有效的 VRF 输出 $\beta$，使得存在证明 $\pi$ 通过 $\text{Verify}(PK, \alpha, \pi) = (\text{VALID}, \beta)$。

完全唯一 (Full Uniqueness)：即使对手可以恶意生成密钥，也无法找到冲突。 可信唯一 (Trusted Uniqueness)：仅在密钥以可信方式生成时成立。

多数应用仅需可信唯一。其意义在于：VRF 输出是"唯一可验证的"——不存在"一个输入对应两个同样有效输出"的情况，这与数字签名有本质区别（同一消息可产生多个有效签名）。

抗碰撞性 (Collision Resistance)

在不知道私钥的情况下，找到两个不同输入 $\alpha_1 \neq \alpha_2$ 使得 $\text{VRF}(SK, \alpha_1) = \text{VRF}(SK, \alpha_2)$ 在计算上不可行。

伪随机性 (Pseudorandomness)

对于不知道私钥的敌手，只要证明 $\pi$ 未知，VRF 输出在计算上与均匀随机串不可区分。

选择性伪随机 (Selective Pseudorandomness)：敌手在观察到公钥之前选定目标输入。 完全伪随机 (Full Pseudorandomness)：敌手在观察到公钥之后仍可（但必须在生成密钥对之后选定输入）。

这一性质确保 VRF 输出不会泄漏关于私钥的任何信息。

不可预测性 (Unpredictability)

即使密钥对以非可信方式（甚至恶意）生成，只要输入本身具有足够熵，输出仍不可预测。这一性质被称为"类随机预言机"性质（random oracle-like property），在 IETF ECVRF 标准中有形式化处理。

与数字签名的区别

初学者常混淆 VRF 与数字签名。核心区别在于：

特性	数字签名 (ECDSA/EdDSA)	VRF
输出唯一性	非唯一（同一消息可产多个有效签名）	唯一（一输入一输出）
输出伪随机性	分布可能不均匀（如 ECDSA 的 s 值）	保证伪随机
验证需要消息	验证需要原始消息	验证需要输入和证明
签名长度	64 字节 (Ed25519)	32 字节（输出）+ 证明

EdDSA (Ed25519/Ed448) 虽然具有确定性签名（满足唯一性），但仍然不是 VRF，因为其输出不保证伪随机性。

构造方法

基于 RSA 的 VRF (Shoup 构造)

2002年 Thomas Shoup 提出第一个实用的 RSA-VRF：

选择 RSA 参数 $(N, e)$ 和私钥 $d$
对输入 $x$：$\beta = \text{SHA256}(x)^d \bmod N$
证明 $\pi$：利用中国剩余定理和哈希证明系统构造

RSA-VRF 满足可信唯一和完全伪随机性，但 2048 位 RSA 导致效率低下，现代实践中基本不被采用。

基于椭圆曲线的 VRF (ECVRF)

IETF RFC 9381 标准化了 ECVRF，作为现代 VRF 的事实标准。其核心步骤：

#### 1. 密钥生成

选择椭圆曲线 $E$（如 P-256, secp256k1），基点 $G$：

私钥 $x \in_R [1, n-1]$
公钥 $Y = x \cdot G$

#### 2. VRF 计算 (证明者)

输入：私钥 $x$，消息 $\alpha$

CODE

1. 将消息映射到曲线点 H = HashToCurve(α)
2. 计算 Gamma = x * H
3. 证明 pi = Prove(x, H, Y, Gamma)

证明 $pi$ 使用 Chaum-Pedersen 协议的非交互式变体，证明离散对数 $\log_H(\Gamma) = \log_G(Y) = x$：

CODE

k = 随机标量
U = k * H
V = k * G
c = HashToScalar(G, H, Y, Gamma, U, V)
s = (k - c * x) mod n
pi = (c, s, Gamma)

#### 3. VRF 验证 (验证者)

输入：公钥 $Y$，消息 $\alpha$，证明 $pi = (c, s, \Gamma)$

CODE

1. H = HashToCurve(α)
2. 验证 c, s 在 [1, n-1] 范围内
3. U = s * H + c * Gamma  (验证对 H 的关系)
4. V = s * G + c * Y      (验证对 G 的关系)
5. c' = HashToScalar(G, H, Y, Gamma, U, V)
6. 验证 c == c'
7. 输出 beta = HashToField(Gamma)

#### 正确性证明

验证的等式成立是因为：

$$U = s \cdot H + c \cdot \Gamma = (k - cx) \cdot H + c \cdot x \cdot H = k \cdot H$$

$$V = s \cdot G + c \cdot Y = (k - cx) \cdot G + c \cdot x \cdot G = k \cdot G$$

因此验证者计算出的 $U, V$ 与证明者相同，哈希输出 $c'$ 必定匹配。

HashToCurve 函数

RFC 9381 中的 HashToCurve 使用简化 SWU (Shallue-van de Woestijne-Ulas) 方法，将任意比特串映射到曲线上的非零点。该过程是确定性的，确保证明者和验证者计算相同的 $H$。

常见曲线映射：

P-256: hash_to_field + map_to_curve (simplified SWU)
secp256k1: 专用 Secp256k1Encode
Curve25519: 使用 Elligator2 映射

ECVRF-Ed25519-SHA512 (RFC 9381)

最广泛部署的 ECVRF 实例化方案：

曲线：Ed25519 (Edwards25519)
哈希：SHA-512
HashToCurve：SHA-512 → 约化 → Ed25519 压缩点 → 反压缩 → Edwards 坐标
安全强度：约 256 位（抗 2^128 次操作碰撞）
证明长度：129 字节 (Gamma 32 + c 16 + s 64 + nonce 17)
输出长度：32 字节

PYTHON

# ECVRF 代码结构示意（概念性，非完整 RFC 9381 实现）
def vrf_prove(private_key: bytes, alpha: bytes) -> (bytes, bytes):
    Y = derive_public_key(private_key)  # 公钥
    x = private_key                     # 私钥标量

    # 1. Hash to curve
    H = hash_to_curve_ed25519(alpha)

    # 2. Compute VRF output point
    Gamma = scalar_multiply(x, H)

    # 3. Generate proof using Chaum-Pedersen
    k = random_scalar()
    U = scalar_multiply(k, H)
    V = scalar_multiply(k, Y)

    c = hash_to_scalar([G_bytes, H_bytes, Y_bytes, Gamma_bytes, U_bytes, V_bytes])
    s = (k - c * x) % ORDER

    pi = bytes([Gamma_bytes + encode_scalar(c) + encode_scalar(s)])
    beta = hash_to_field_ed25519(Gamma_bytes)  # 确定性输出

    return beta, pi

应用：Algorand 密码学抽签

最能体现 VRF 价值的应用是 Algorand 区块链的共识机制。

问题定义

拜占庭共识要求从网络中选择委员会（验证者子集），在存在 $f$ 个拜占庭节点的系统中保证安全性（活性 + 一致性）。传统方法（轮次随机、PoW）受通信复杂度和能源消耗限制。

VRF 抽签算法

每个 VRF 私钥持有者 $i$ 根据当前"种子" $seed$ 独立计算：

确定输入：$x = \text{Hash}(seed \| round \| role)$
VRF 计算：$\langle hash, \pi \rangle = \text{VRF}_{sk_i}(x)$
概率判定：将 $hash$ 归一化为小数 $d = hash / 2^{256}$
基于二项分布确定 $j = $ 被抽中的"子用户"数：

- 若 $\sum_{k=0}^{j} \binom{w_i}{k} p^k (1-p)^{w_i-k} \leq d < \sum_{k=0}^{j+1}$，则用户抽中 $j$ 次

为什么不能直接用 ECDSA/EdDSA

同一输入 + 同一私钥在每次签名时可产生多个有效签名（$k$ 的随机性）。但 $hash$ 在投票和传播过程中必须是确定且唯一的，否则：

不同节点看到同一用户的"不同签名结果"，无法验证一致性
恶意用户可选择对自己最有利的 $hash$ 广播（对抗公平性）

VRF 的唯一性保证：对任意输入，唯有一个合法 $hash$ 可通过验证。

安全与公平性证明

敌手无法：

知道他人被抽中结果（$V$ 的伪随机性）
操纵种子以偏袒自身（种子通常来自区块链历史）
作为同一用户被抽中多次（$j$ 的权重比例控制）

Algorand 分析表明：网络诚实权重 $h = 80\%$，$t = 26$ 时，活性违背概率 $< 10^{-18}$，与比特币 6 个确认的安全性相当。

应用：drand 可验证随机信标

drand (distributed randomness) 是一个去中心化随机数生成网络，为智能合约和 dApp 提供公共可验证的随机数。

架构

由数十个独立运营节点组成联盟（如 Cloudflare、EPFL、University of Geneva）
使用基于 BLS 门限签名的 VRF (t-of-n BLS VRF)
每个时间周期（如 30 秒）生成一个随机数
随机数包含前一周期值、签名和证明

BLS VRF 构造

BLS 签名基于配对友好的椭圆曲线（如 BLS12-381）：

私钥 $sk$，公钥 $pk = sk \cdot G_1$
对消息 $m$：签名 $\sigma = sk \cdot G_2(m)$（其中 $G_2(m)$ 是到 $G_2$ 的映射）
验证：$e(G_1, \sigma) == e(pk, G_2(m))$

VRF 输出 = Hash($\sigma$)。由于 BLS 签名具有唯一性和确定性（无 $k$），天然满足 VRF 要求。

VRF 输出 = Hash($\sigma$) = Hash(sk · H(m))

其中 $H(m)$ 是消息映射到 $G_2$ 的点。

阈值化 (CSP)

为了保证安全性，使用门限签名：

总节点 $n$，门限 $t = \lceil (n+1)/2 \rceil$
每个节点 $i$ 持有份额 $sk_i$（Shamir 秘密共享）
至少 $t$ 个节点合作才能生成有效签名
任何少于 $t$ 节点的联盟无法恢复主私钥

这提供了容错能力：即使有 $t-1$ 个节点离线或故障，仍可生成随机数。

实现标准与进展

IETF RFC 9381 (2024)

IETF 在 2024 年发布了 RFC 9381，标准化了 ECVRF：

定义 $\text{ECVRFProve}(), \text{ECVRFVerify}()$ 等核心函数
提供三种曲线实例化方案：

- ECVRF-P256-SHA256 - ECVRF-secp256k1-SHA256 - ECVRF-Ed25519-SHA512-TAI

包括完整的 ASN.1 编码和测试向量

NIST SP 800-185 (2023)

NIST 在 SP 800-185 (Derived Function Functions) 中定义了基于 KMAC 的 VRF (KMAC-VRF)：

CODE

KVRF(key, message) = KMAC(SHA-3, key, message)

利用 SHA-3 的密钥化哈希特性隐含证明关系，提供更灵活的构造。

Draft-cfrg-vrf-decentralized-randomness (IETF)

当前标准化中的去中心化随机信令:

基于 ECVRF 或 BLS-VRF
定义 Verifiable Random Beacon (VRB) 应用层协议
关注安全治理：如何在不信任环境中设置和维护随机数生成器

安全注意事项

1. 输入熵不足

如果 VRF 输入可预测或有偏，即使输出伪随机，攻击者也可能枚举攻击。

解决方案：

输入应包含随机源（如区块哈希、时间戳、前一个 VRF 输出）
使用 commit-reveal 模式：先提交再开放
使用不可预测种子机制（reveal-commit 协议）

2. 侧信道攻击

定时攻击：暴露 Gamma 计算时间或模乘的时序差异
能量分析：密钥 $x$ 的汉明重量可能通过功耗侧信道泄露

解决方案：

恒定时间标量乘法（如 Montgomery 阶梯）
对 $x$ 进行盲化（random blinding）
物理侧信道防护（智能卡、TEE）

3. 协议层攻击

自适应输入敌手：在观察到多个 VRF 输出后，尝试推断私钥
中毒攻击：攻击者参与系统设置阶段，产生“有毒”密钥对

解决方案：

使用可信初始化（NIZK 的公共参考字符串）
对公钥执行可验证随机检查（如验证 $Y$ 是正确子群的点）
防御后门的参数生成（nothing-up-my-sleeve numbers）

4. 区块链环境中的 MEV

在去中心化激励环境下（如 L2 排序器选举），VRF 输出可能被用于：

猜测未来排序器（如果 seed 可预测）
MEV 竞拍中的闪电贷操纵

工程实现

Python 实现 (evrf 库)

PYTHON

from ecvrf import vrf_ed25519_sha512  # 示意性库

# 1. 密钥生成
private_key, public_key = vrf_ed25519_sha512.generate_key_pair()

# 2. 计算 VRF 输出
alpha = b"block-height-#12345 | round=2"
beta, pi = vrf_ed25519_sha512.prove(private_key, alpha)

# 3. VRF 验证
is_valid, beta_prime = vrf_ed25519_sha512.verify(public_key, alpha, pi)
assert is_valid
assert beta == beta_prime

# 4. 获取伪random数
import hashlib
random_number = int.from_bytes(hashlib.sha256(beta).digest(), 'big')

Rust 实现 (ark-vrf)

Arkworks 提供了 ark-ec-vrf 库，支持多种曲线实例化：

RUST

use ark_ec_vrf::ecvrf;
use ark_ec::ProjectiveCurve;

let params = ecvrf::ecvrf_edwards25519::VRFParams::new();
let (private_key, public_key) = ecvrf::ecvrf_edwards25519::keygen();
let (beta, pi) = ecvrf::ecvrf_edwards25519::prove(&private_key, &params, alpha);
let (valid, beta_prime) = ecvrf::ecvrf_edwards25519::verify(&public_key, &params, alpha, &pi);

部署建议

曲线选择：Ed25519 在性能和安全性间有最佳平衡，Grover 攻击复杂度约 2^128
哈希至曲线：使用标准化简化 SWU，避免实现差异导致分叉
恒定时间：所有代码路径必须恒定时间，以防侧信道
新鲜度：VRF 输入必须包含不可预测的熵源（如链上随机性）

未来展望

1. 标准化的推进

NIST 正在评估后量子 VRF 候选方案（基于格和基于哈希），以应对量子威胁：

基于 LWE 问题的 VRF: 利用 Regev 方案的可验证性
基于哈希的 VRF: 利用 XMSS 等哈希签名方案的唯一性

2. 模块化原语集成

VRF 作为原语被更广泛地集成到协议栈：

Filecoin 的 Leader Election using VDF+VRF
DFINITY (Internet Computer) 的随机信标 (VRF + BLS 门限签名)
Polkadot 的 BABE 共识（VRF-Slot leader 选举）

3. 可验证计算的未来

VRF 与同态加密、零知识证明结合：

在 ZK-Rollup 中生成可验证随机序列
隐私保护的领导者选举（VRF 输出作为选票混淆基础）
多方计算协议中的无偏硬币投掷

总结

VRF 填补了"可验证性"与"伪随机性"在传统公钥密码学中的空白。其通过私钥持有者的唯一输出能力，为分布式系统中的随机信标、共识抽签、公平选举等关键需求提供了数学上可证明的密码学保证。

从 Shoup 的 RSA 构造到 IETF RFC 9381 的 ECVRF 标准化，从 Algorand 的密码学抽签到 drand 的去中心化随机信标，VRF 的发展证明：密码学创新不仅需要数学严谨，更需要工程可用和对现实需求（如 MEV 保护）的深刻理解。

理解和掌握 VRF，是构建下一代去中心化系统的必要基础。

参考来源

RFC 9381: ECVRF (Elliptic Curve Verifiable Random Functions) — 当前 IETF 标准
Algorand Whitepaper VRF Sortition — Algorand 抽签原理解析
drand: Distributed Randomness Beacon — drand 官方文档
NIST SP 800-185: DFFs and KMAC-VRF — NIST SP 800-185 派生函数标准
Micali-Rabin-Vadhan 1999 — VRF 原始论文
Google's Verifiable Random Functions Project — 可验证透明性中的 VRF 应用

可验证随机函数 VRF：从数学原理到区块链共识的密码学抽签

概述

安全定义

唯一性 (Uniqueness)

抗碰撞性 (Collision Resistance)

伪随机性 (Pseudorandomness)

不可预测性 (Unpredictability)

与数字签名的区别

构造方法

基于 RSA 的 VRF (Shoup 构造)

基于椭圆曲线的 VRF (ECVRF)

HashToCurve 函数

ECVRF-Ed25519-SHA512 (RFC 9381)

应用：Algorand 密码学抽签

问题定义

VRF 抽签算法

为什么不能直接用 ECDSA/EdDSA

安全与公平性证明

应用：drand 可验证随机信标

架构

BLS VRF 构造

VRF 输出 = Hash($\sigma$) = Hash(sk · H(m))

阈值化 (CSP)

实现标准与进展

IETF RFC 9381 (2024)

NIST SP 800-185 (2023)

Draft-cfrg-vrf-decentralized-randomness (IETF)

安全注意事项

1. 输入熵不足

2. 侧信道攻击

3. 协议层攻击

4. 区块链环境中的 MEV

工程实现

Python 实现 (evrf 库)

Rust 实现 (ark-vrf)

部署建议

未来展望

1. 标准化的推进

2. 模块化原语集成

3. 可验证计算的未来

总结

参考来源

相关实践