可验证延迟函数（VDF）：从重复平方构造到区块链共识应用

1. 引言：为什么需要"可验证的延迟"？

在分布式系统中，"时间"是一个难以信任的概念。如果协议要求"等待 T 时间后才能获得结果"，恶意节点可以通过并行计算加速，破坏公平性。

可验证延迟函数（Verifiable Delay Function, VDF）正是为了解决这一问题而设计。VDF 是一种函数 f(x)，具有以下核心特征：

• 顺序性（Sequentiality）：计算 f(x) 必须消耗至少 T 步顺序计算，无法通过并行计算加速
• 高效可验证性（Efficient Verifiability）：给定输入 x 和输出 y，任何人可以在远少于 T 的时间内验证 y 是否正确
• 确定性（Determinism）：相同的输入总是产生相同的输出

2. 形式化定义与 VDF 家族

一个 VDF 由三个算法组成：

Setup(λ, T) → pp：输入安全参数 λ 和时间参数 T，输出公共参数 pp。Setup 可以是公开可验证的（通过公开随机字符串）或可信设置的。

Evaluate(pp, x) → (y, π)：输入 pp 和 x，输出评估结果 y 和证明 π。该算法必须执行至少 T 步顺序计算。

Verify(pp, x, y, π) → {0, 1}：输入 pp、x、y 和证明 π，输出接受或拒绝。该算法必须在多项式时间内完成，且远快于 Evaluate。

VDF 的安全属性

• 正确性：如果 y 和 π 由 Evaluate 正确生成，Verify 必须接受
• 稳健性（Soundness）：任何多项式时间敌手无法生成能通过 Verify 的错误 y
• 顺序性：任何拥有多项式数量处理器的敌手，无法在显著少于 T 的时间内计算出 y
• 唯一性：对于给定输入 x，只有一个 y 能通过 Verify

VDF 家族

3. 数学基础：重复平方与未知阶群

3.1 重复平方问题

VDF 的核心数学技巧是重复平方（Repeated Squaring）。给定一个群 G 中的元素 g 和一个大整数 T，计算：

g^(2^T) = g^(2·2·2·...·2) （共 T 次平方）

这个计算本质上是顺序的：要计算第 i 次平方，必须先完成第 i-1 次平方。无论有多少处理器，都无法将 T 次平方压缩到少于 T 步。

如果群的阶未知（如 RSA 群 Z_N^* 的二次剩余子群），就无法利用欧拉定理将指数 2^T mod φ(N) 化简，从而强制计算必须执行完整的 T 次平方。

3.2 RSA 群

RSA 群是 Z_N^* 的二次剩余子群，其中 N = p·q 是两个大素数的乘积。群的阶 φ(N) = (p-1)(q-1)，但只有在分解 N 的情况下才能计算。

在 RSA 群中，重复平方 VDF 的 Evaluate 为：

• 输入：g ∈ G，时间参数 T
• 输出：y = g^(2^T) mod N

3.3 类群（Class Groups）

类群是二次域的等价类群，其阶与二次域的判别式相关。类群的优势在于无需可信设置：可以通过选择一个随机判别式来生成类群，而无需生成隐藏的阶。

类群的元素表示和运算比 RSA 群更复杂，但其无需可信设置的特性使其在去中心化应用中更具吸引力。

4. Wesolowski 2019 构造

4.1 算法描述

Setup(λ, T) → pp：

• 生成 RSA 模数 N = p·q（p, q 为大素数）
• 选择哈希函数 H（如 SHA-256）
• 公共参数 pp = (N, H, T)

• 将输入 x 映射到群元素：g = H(x) mod N
• 计算 y = g^(2^T) mod N（执行 T 次模平方）
• 生成证明：

• 输出 (y, π)

• 重构群元素：g = H(x) mod N
• 计算挑战：l = H(y, g, T)
• 计算 r = 2^T mod l
• 验证：π^l · g^r ≡ y (mod N)

4.2 验证正确性证明

验证等式 π^l · g^r ≡ y 的正确性源于：

π^l · g^r = (g^(⌊2^T/l⌋))^l · g^(2^T mod l)
          = g^(l·⌊2^T/l⌋ + 2^T mod l)
          = g^(2^T)  （因为 l·⌊2^T/l⌋ + 2^T mod l = 2^T）
          = y

4.3 性能特征

• Evaluate：T 次模平方，每次模乘法 O(log² N)，总计 O(T · log² N)
• Verify：2 次模幂运算（指数大小约为 log(2^T) = T 和 log l），总计 O(T · log² N)，但常数远小于 Evaluate
• Proof 大小：1 个群元素，约 log N 位

5. Pietrzak 2019 构造

Pietrzak 构造与 Wesolowski 类似，但使用类群而非 RSA 群。核心区别在于：

• 无需可信设置：类群的判别式可以通过公开随机字符串生成
• 证明生成方式不同：Pietrzak 使用递归方式生成证明，验证也是递归的

5.1 递归验证

Pietrzak 的验证算法递归地将问题规模减半：

Verify(pp, x, y, π, T)：

• 如果 T = 1：直接验证 y = x²
• 否则：

递归深度为 O(log T)，每层需要一次模幂运算。

6. 应用场景

6.1 区块链共识：Filecoin 的 VDF

Filecoin 使用 VDF 来创建"可验证的随机信标"，用于领导者选举。通过要求矿工在出块前执行 VDF 计算，Filecoin 确保没有任何矿工可以通过并行计算获得不公平的优势。

6.2 空间时间证明：Chia

Chia 使用 VDF 作为其"空间时间证明"（Proof of Space and Time）的核心组件。农民先证明他们存储了空间（通过 Proof of Space），然后通过 VDF 证明时间已经流逝。

6.3 随机数信标：drand

drand 是一个去中心化的随机数信标服务，使用 VDF 来防止攻击者在随机数发布前预测或操纵结果。drand 联盟使用基于类群的 VDF，避免了对可信设置的依赖。

6.4 文件系统验证

VDF 可以用于创建"时间释放加密"（Time-release Encryption）：加密一个消息，只有在 VDF 计算完成后才能解密。这在密封投标拍卖、遗产分配等场景中有应用。

7. 国密对照：基于 SM3 的 VDF 可行性分析

7.1 SM3 哈希链作为简单 VDF

最简单的 VDF 构造是基于哈希链的迭代：

x_0 = H(input)
x_i = H(x_{i-1})  for i = 1..T

输出 y = x_T。这种构造具有顺序性（必须依次计算每次哈希），但缺乏高效的验证方法（验证也需要 T 次哈希）。

7.2 SM3 + Merkle Tree 验证

为了支持快速验证，可以结合 Merkle Tree：

• 计算哈希链 x_0 → x_1 → ... → x_T
• 每隔 √T 步创建一个 Merkle Tree 节点
• 验证时只需提供 √T 个中间值作为证明

7.3 SM3 在 RSA/类群 VDF 中的角色

在实际的 Wesolowski/Pietrzak VDF 中，哈希函数用于：

• 将输入映射到群元素：g = H(x) mod N
• 生成挑战值：l = H(y, g, T)

7.4 合规性考量

在密评场景下使用 VDF 时，需要注意：

• 如果 VDF 用于密钥派生或随机数生成，应优先使用国密算法
• SM3 作为国产密码算法，在 VDF 中替代 SHA-256 是合规的
• 但 VDF 本身不属于 GM/T 标准体系，实际应用中需要评估其安全性和合规性

8. 与相关概念对比

9. 总结

VDF 作为一种新兴的密码学原语，填补了"强制延迟"这一需求的技术空白。Wesolowski 和 Pietrzak 两大构造各有优势：前者依赖 RSA 群，实现简洁；后者使用类群，无需可信设置。

在区块链、随机信标、时间释放加密等场景中，VDF 已经展现出不可替代的价值。对于国密生态而言，SM3 可以无缝替代 VDF 中的哈希函数，但 VDF 整体框架尚未纳入国家标准体系，实际应用中需要结合具体场景评估合规性。

相关实践：

• 可验证随机函数 VRF 原理详解
• BLS 签名算法原理
• SM3 密码杂凑算法原理详解
• SM3-HMAC 消息认证码实战