自从以太坊将可验证延迟函数（Verifiable Delay Function, VDF） 列入研究计划并打算在以太坊 2.0 使用之后，VDF 得到了广泛的关注。VDF 这个概念最初由斯坦福大学密码学教授 Dan Boneh 等人在其论文 Verifiable Delay Function 中给出。该篇文章于 2018 年发表在密码学顶级会议之一的 CRYPTO 上。
目前网络上有一些英文和中文的文章介绍了 VDF 的概念和原理，但是它们要么无法给出全面直观的解释，要么只是粗浅地谈论应用。本文试图通过浅显的语言和具体的例子来让对密码学和群论不够了解的读者能够全面而直观地理解它的定义和原理。同时，本文还给出了它的可能的应用场景以及目前的研究和应用状况。
VDF 是一类数学函数，能够使得该函数的计算需要至少一段已知的时间，即使是在同时使用少量 CPU 进行并行计算的情况下（这与比特币的 Proof-of-Work (PoW) 不同，后文会详细解释）。VDF 通常会接受一个输入以及一些参数（安全参数、时间参数等），输出一个结果以及相应的证明（可以为空，如果结果能够自带证明）。验证者会依据输入、参数、输出以及结果来判断 VDF 的结果是否正确。
对于未精心设计过的算法，并行计算有可能极大地缩减其计算时间。以比特币的挖矿算法为例，设 0⩽nonce⩽232−10⩽nonce⩽232−1，如果只有一个运算单元，那么可能需要耗费多达 232232 次 SHA-256 计算的时间。如果有两个运算单元，就可以将任务对半分摊，让他们并行地计算哈希值。最多只需要耗费 231231 次 SHA-256 计算的时间。
同时，VDF 满足以下性质：
VDF 能够抵抗并行计算加速，这意味着为了计算 VDF，应当完成一系列串行才能完成的任务，后一个任务必须依赖于前一个任务。这时，对哈希函数有所了解的读者可能会想到一种方案：连续将一个输入哈希 tt 次。这样的方案的确是无法通过并行算法显著地加速的，但是这样得到的结果，其验证将会非常没有效率：验证者需要重复哈希 tt 次的计算，即使保留一些中间结果，验证的工作量和计算的工作量也是常数级别的差距。从这个例子我们可以看出，在这样的定义下，可验证延迟函数的构造并没有想象中的那么简单。
事实上，对于上面并不严谨的定义，去掉任何一个性质都会导致我们能够非常轻易地构造出可验证延迟函数：
或许有读者会感觉 VDF 和 PoW 是一类东西，实际上，虽然他们计算起来都不是很容易，但是他们之间有很多关键的区别。
上述两条性质决定了 PoW 直接作为随机数的来源是有缺陷的，同时，VDF 也无法直接替代 PoW。但是这并不能说明 VDF 不可以被用到共识协议里，这一点会在下一个章节详谈。
上一章节我们介绍了 VDF 是什么，以及它具有怎样的性质，这一章节我们关注它的用途。
区块链上的随机数一直是一个热门话题。无论是在一些权益证明（Proof-of-Stake, PoS）共识协议的设计里，还是在智能合约平台，譬如 Ethereum 和 EOS，上一些非常火爆的游戏类应用，随机数都占据了核心的地位。同时，很多这些应用中，实际设计的随机数获取方案还非常不成熟，以至经常会有应用因为不安全的随机数而被黑客攻击的新闻出现。
VDF 对于一些从公共来源获取随机数的方法非常有用。比如从股票市场或者是从 PoW 区块链上获取。这些随机源拥有足够的随机性（更严格地讲，是最小熵）。但是高频交易者可以影响股价，同时，PoW 区块链的矿工也可以通过不广播自己挖出的区块来降低自己不想要的随机数结果的出现概率。但是这样的攻击方式成立的前提条件是攻击者有时间在其他诚实参与者之前预测出随机数结果。VDF 恰好能阻止这一点。如果将 VDF 的时间参数 tt 设置到足够长（比如 10 个块的间隔），将最新的区块头作为输入扔进 VDF 中，输出作为随机数结果。那么攻击者只能在 10 个块之后才能知道随机数的结果是什么，那个时候想要再改变结果已经很难了（需要 fork 10 个区块）。
此外，VDF 也可以增强一些多方参与的随机数方案。比如 Commit-and-Reveal 方案中，攻击者可以拖到 Reveal 阶段的最后再决定是否揭示自己的承诺。如果我们去掉 Commit 阶段，并且协议的最后整合所有人的输入之后不直接作为随机数结果，而是放入 VDF 中，并且将 VDF 的时间参数 tt 设置到足够长（晚于最后提交期限），那么即使是最后一刻提交的人也无法知道随机数的结果，操纵结果也就无从谈起。与之相比较，其他的多方参与方案通常最多容忍小于一半的恶意节点，并且交互的开销要比上述方案更大。
正如上一节所述，VDF 可以用于增强随机数生成方案的安全性，因此，在一些使用了随机数来选取 Leader 的共识协议中也可以使用 VDF 在增强其安全性。一些节约能源的共识协议，例如 PoS，空间证明（Proof-of-Space）以及存储证明（Proof-of-Storage），为了防止 Nothing-at-stake attack，需要使用随机选举每隔一段时间选举出一个 Leader。这些协议使用的随机数方案大多只在诚实参与者占据大多数时保持安全。利用 VDF 可以降低这样的限制到至少存在一个诚实参与者。
Nothing-at-stake Attack
PoS 区块链发生分叉时，共识参与者为了自己的利益会选择在不同的分叉链上同时进行抵押资产参与出块，这样分叉链有可能会一直存在并且分叉越来越多，严重危害系统的一致性，这样的攻击被叫做 Nothing-at-stake attack。在 PoW 链上进行这样的攻击需要分散算力，因此这样的攻击只适用于“节约能源”的共识协议。
除了随机选举之外，还有一种叫做 Proofs of Space and Time 的方案可以防止这种攻击。实际上该方案模拟了 PoW 的挖矿过程：挖出区块的时间是不确定的，并且每个矿工都在互相竞争成为最早挖出区块的人。不一样的地方在于，模拟挖矿过程实际上并不需要消耗大量的并行计算资源（Proof-of-Time），只有在进入挖矿时有一定的门槛（Proof-of-Space）。具体来讲，整个挖矿过程按照时间顺序被分成不同的区间，每一个区间都有一个公共随机的挑战 cc（举个例子，可以是前一个区间挖出的块的哈希值）。假设某个矿工拥有的空间单位为 NN，他需要生成一个证明 ππ 来证明他拥有这 NN 单位的空间，并且专门用于该区块链的挖矿，这一点由 Proof-of-Space 保证。矿工的目标为找到最小的 τ=H(c,π,i),1⩽i⩽Nτ=H(c,π,i),1⩽i⩽N，然后将 cc 作为输入计算一个 VDF（事实上是增量 VDF），该 VDF 的时间参数与 ττ 正相关。这样的设计中，拥有空间越多的矿工找到更小的 ττ 的可能性更大，同时，VDF 保证了一段时间的流逝，使矿工大量分叉需要消耗大量的时间。
几乎所有的 PoS 方案都面临 Long-range attack 的问题。目前 PoS 协议依赖于外部的时间戳服务来帮助他们解决这个问题——只要能判断哪一条链更老，就能阻止这样的攻击发生。VDF 能够帮助 PoS 解决这样的问题。VDF 相当于一种时间流逝的证明，对于给定的 VDF，该 VDF 至少需要多久才能得出结果是一个公共知识。因此，只需要在 PoS 链上包含 VDF 的输入与输出即可证明给定区块的历史。
Long-range Attack
在 PoS 协议中，任意时刻都有一组权益相关者拥有按照权益多少分配的投票权。PoS 假设大多数权益相关者并没有理由对系统造成破坏，因为这样反而会损害自己的权益。但是如果这些权益相关者在某一个时间点出售了自己的权益，这样的激励对他们来讲是无效的。这些已经出售了自己权益的曾经的权益相关者仍然可以在曾经某一个时间点轻易对（那时他们占据大多数权益） PoS 链分叉达到原有链的的长度，从中攫取额外的利益，这样的攻击被称作 Long-range attack。它在 PoW 上不太可能发生，因为对于 PoW 来讲，无论从哪一个时间点进行分叉，都必须要付出相应的算力才能追上原有的链，想要分叉的区块越多，付出的算力也就越多。
但是必须要指出的是，这样的方法并不是完美的，因为 VDF 仍然是可以被特殊硬件加速的（尽管是常数级的）。如果攻击者获得了诚实节点 10 倍的计算速度，那么攻击者可以用 1 年的时间伪造出 10 年以前的区块，从而用 1 年的时间获得一条有 10 年历史的链。这样的加速对于使用 VDF 作证明的 PoS 链是不可接受的。
10 倍的加速对于随机数生成的场景无所谓，因为该场景下，不需要保证“攻击者算得没有诚实节点快”，只需要保证攻击者无法在某个时间点（随机数来源再也无法更改的时间点，例如股市闭市）之前无法计算出结果即可。从而在随机数生成的场景，我们可以选取一个足够长的时间参数，使得攻击者即使加速也无法操纵随机数。
副本证明所需要解决的问题是，服务器如何向客户端证明自己在某一专门的存储介质上存储了指定的数据，即使这样的数据是可以从别的存储来源轻易获得的。注意副本证明是为了证明服务器拥有一份数据的副本，而不是证明它有这样的数据。举个例子，云存储服务提供商声称自己为客户的数据做了额外的两份冗余备份来保证用户数据的 availability，因此客户需要为这样的冗余备份交更多的钱。但是怎么证明云服务提供商有一共三份副本而不是两份或者只有一份呢？这就需要用到副本证明。一种思路是利用在时间上不对称的编码方案（也就是编码很慢，但是解码很快），VDF 可以做到这一点（事实上是可解码 VDF）。身份为 idid 的服务器首先将文件分成 bb-bit 大小的文件块 Bi,1⩽i⩽nBi,1⩽i⩽n，然后计算 Bi⊕H(id||i)Bi⊕H(id||i) 并将结果作为输入放进 VDF 计算得到 yi,1⩽i⩽nyi,1⩽i⩽n，其中 HH 是输出长度为 bb-bit 的防碰撞哈希函数。服务器存储所有的 yiyi，客户端不断随机挑选 ii 进行轮询要求服务器返回 yiyi，服务器在规定时间内需要响应给客户端相应的结果，而客户端可以在很短的时间内通过解码 yiyi 得到 BiBi 完成验证。如果服务器没有存储 yiyi ，那么想要正确响应客户端必须计算 yiyi，然而这样的计算无法在规定的时间内完成。服务器也可以只存储一部分 yiyi（比例为 ρρ），由于客户端是随机轮询，每一次服务器成功欺骗客户端的概率为 ρρ。只要客户端重复 kk 次这样的轮询，就可以将服务器欺骗成功的概率降到 ρkρk。需要补充的一点是，服务器可以不存储 BiBi，由于 yiyi 解码很快，即使只存储 yiyi 也不会太影响性能。
既然 VDF 是一个函数，那么它就必然具有这样的形式：f:X→Yf:X→Y。为了实现前文所述的功能，即“抵抗并行计算的延迟”以及“可验证的结果”，VDF 中必然包含一个用于计算结果的算法以及一个用于验证结果的算法。同时，这样的密码学工具通常还包含一个配置阶段，用来确定后续需要使用的参数。因此，VDF 被描述为三个算法的一个三元组 (Setup,Eval,Verify)(Setup,Eval,Verify)。
每个算法的定义如下：
如图 1 所示我们可以看到 VDF 通常的运行流程。
图 1：可验证延迟函数
以上几个算法有一些需要补充说明的地方：
基于上述定义，VDF 还有一些拥有特殊性质的变种：
上文提到了使用连续的哈希操作是一种防止并行的计算加速的手段，但是这样的手段非常低效，不符合 VDF 的定义。我们希望能够找到一种验证更加迅速的防并行的构造方式。考虑这样的一个例子：
首先选择一个数 λ=161λ=161 ，然后然后对于任意的输入 xx，我们执行下面的操作 tt 次：
假设我们的输入 x=11x=11，t=8t=8，那么结果为 9595，事实上，如果我们让 tt 取不同的值，把结果都记录下来，可以得到下述表格
| tt | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| yy | 121 | 151 | 100 | 18 | 2 | 4 | 16 | 95 |
更一般地讲，如果 a≡bmodma≡bmodm 代表 aa 和 bb 分别除以 mm 的余数相同的话，那么上述操作实际上就是计算
y≡x2tmodλy≡x2tmodλ
如果我们知道 λλ 的因式分解，例如 161=7×23161=7×23，那么我们可以通过两次指数运算来快速计算出 yy 的值。首先计算函数 ϕ(161)=(7−1)×(23−1)=132ϕ(161)=(7−1)×(23−1)=132，然后计算 2t2t 除以 ϕ(161)ϕ(161) 的余数
28≡124mod13228≡124mod132
然后计算 x124x124 除以 λλ 的余数
11124≡1126+25+24+23+22≡4×2×18×100×151≡95mod16111124≡1126+25+24+23+22≡4×2×18×100×151≡95mod161
上述过程比起连续平方 8 次看似没有减轻多少工作量，但实际上当 tt 和 λλ 非常大（t≈230t≈230）时，远比连续平方快得多。一般地，函数 ϕ(n)=∏ri=1pki−1i(pi−1)ϕ(n)=∏i=1rpiki−1(pi−1)，如果 n=pk11pk22⋯pkrrn=p1k1p2k2⋯prkr。这个函数被称之为欧拉函数（Euler’s Totient Function）。上述例子可以一般化为
e≡2tmodϕ(λ),y≡xemodλe≡2tmodϕ(λ),y≡xemodλ.
因此，如果没有任何人知道 λλ 的因式分解，也就无法快速计算出 ϕ(λ)ϕ(λ)，从而只能重复 tt 次平方操作使用
x→x2→x22→⋯→x2tmodλx→x2→x22→⋯→x2tmodλ
计算出 yy。
事实上，这个构造可以使用群论得到更加本质的解释。我们发现，由于模运算 yy 的值是小于 λλ 的，而所有小于 λλ 且与 λλ 互素的数一起组成了一个群（Group），这个群被称作整数模 λλ 乘法群，记作 (Z/λZ)∗(Z/λZ)∗。这个群的阶（Order），也就是元素个数就等于欧拉函数 ϕ(λ)ϕ(λ) 的值。因此，关键问题落在了如何生成这样的不知道阶的群。
目前主要有两种方法：
RSA 群的生成与 RSA 加密算法类似，选取大素数 pp 和 qq，其中 p=2m+1p=2m+1，q=2n+1q=2n+1 且 mm，nn 均为素数。令 N=pqN=pq，则 (Z/NZ)∗(Z/NZ)∗ 即为所需群。然而一个很显然的问题是，这其中涉及到了 trusted setup，我们必须相信生成 NN 的参与者不会泄露 pp 和 qq。我们也可以使得群生成算法使用公共随机数来直接选取足够大的 NN 使得因式分解 NN 非常困难，但是这样的 NN 需要非常大以至于这样的方法非常不现实。第二种方法解决了第一种方法的问题，但是由于第二种方法解释起来涉及概念较多，本篇文章不会涉及。同时，对于结果 yy 的快速验证需要用到证明系统，有兴趣的读者可以参考 Boneh 的一篇综述。
学术界第一次正式提出 VDF 的概念是在 Boneh 的论文中，他在论文中给出了 VDF 的应用场景以及形式化的模型，安全分析和一般构造方法。之后出现了分别出现了两篇 VDF 的构造论文，分别是 Wesolowski 的 Efficient VDF 以及 Pietrzak 的 Simple VDF。两者都利用在不知道阶的群中连续做平方运算的方法来构造 VDF，不同的是，他们生成证明的构造有所区别。简单来讲，Wesolowski 的证明更短，验证更快；但是 Pietrzak 的构造中，生成证明的速度更快，同时证明系统依赖的安全假设更弱。2019 年 Feo 等人使用超奇异同源 (Supersingular Isogenies) 以及双线性对（Bilinear Pairings）构造 VDF。相比于 Wesolowski 和 Pietrzak 的工作，他们的构造本身就是非交互的，不需要经过转换，同时不需要证明 ππ 即可完成验证，但是他们的构造中 SetupSetup 耗费的时间更长，更为主要的是，目前还只能进行 trusted setup。
在应用领域，Chia Network 计划使用 VDF 来支持他们的 Proof-of-Space；以太坊研究团队也打算在以太坊 2.0 中引入 VDF，以期在以太坊 2.0 信标链中使用 RANDAO + VDF 随机选取出块人。最初以太坊计划使用 RANDAO + VDF 的方案。但由于以太坊 2.0 的计划瞬息万变，截至文章最后修改前，以太坊信标链计划将区块间隔限制到 6 秒，64 个区块为一个 epoch，因此一个 epoch 为 6.4 分钟，每一个 epoch 需要进行一次出块人切换，因此 VDF 的时间参数最少应设置为 6.4 分钟，但是目前以太坊计划将其设置为 102.4 分钟，目的是防止潜在的攻击者利用特殊硬件加速 VDF。
