随着以太坊将可验证延迟函数（Verifiable Random Function, VDF）列入研究计划并打算在以太坊 2.0 使用之后，VDF 得到了广泛的关注。VDF 这个概念最初由斯坦福大学密码学教授 Dan Boneh 等人在其论文 Verifiable Delay Function 中给出。该篇文章于 2018 年发表在密码学顶级会议之一的 CRYPTO 上。

目前网络上有一些英文和中文的文章介绍了 VDF 的概念和原理，但是它们要么无法给出全面直观的友们，要么只是粗浅地谈论应用。本文试图通过浅显的语言和具体的例子来让对密码学和群论不够了解的读者能够全面而直观地理解它的定义和原理。同时，本文还给出了它的可能的应用场景以及目前的研究和应用状况。

原文标题：《一文搞懂可验证延迟函数 VDF》 作者：邱飞旸 链闻经公众号「NPC 源计划」授权转载

VDF 是一类数学函数，能够使得该函数的计算需要至少一段已知的时间，即使是在同时使用少量 CPU 进行并行计算的情况下（这与比特币的 Proof-of-Work (PoW) 不同，后文会详细友们）。

对于未精心设计过的算法，并行计算有可能极大地缩减其计算时间。以比特币的挖矿算法为例，设 0?nonce?232?10?nonce?232?1，如果只有一个运算单元，那么可能需要耗费多达 232 次 SHA-256 计算的时间。如果有两个运算单元，就可以将任务对半分摊，让他们并行地计算哈希值。最多只需要耗费 231 次 SHA-256 计算的时间。

同时满足性质：

1、VDF 的结果的检验应当是非常有效率的； 2、唯一性（Uniqueness）：对于任意一个 VDF 的输入，应当有唯一的输出结果能够通过检验。也就是说，不存在两个不同的输出，他们有相同的输入。如果输出结果包含「结果」和关于结果的「证明」两部分，那么证明部分可以不具有唯一性，但需要保证「验证者因为证明而验证通过，但是输出结果却不是正确的结果」这件事发生的概率小到可以忽略不计； 2、串行性（Sequentiality）：攻击者即使能够提前计算很长时间（但不是任意长的时间），并且拥有很多并行处理器（但不是任意多的处理器），利用各种计算方法（确定地计算或是连蒙带猜），能够以少于 t 的时间计算出 VDF 结果的概率可以小到忽略不计（并不是 0，因为也许攻击者真的就运气好到猜中了呢？）。

VDF 能够抵抗并行计算加速，这意味着为了计算 VDF，应当完成一系列串行才能完成的任务，后一个任务必须依赖于前一个任务。这时，对哈希函数有所了解的读者可能会想到一种方案：连续将一个输入哈希 tt 次。这样的方案的确是无法通过并行算法显著地加速的，但是这样得到的结果，其验证将会非常没有效率：验证者需要重复哈希 T 次的计算，即使保留一些中间结果，验证的工作量和计算的工作量也是常数级别的差距。从这个例子我们可以看出，在这样的定义下，可验证延迟函数的构造并没有想象中的那么简单。

事实上，对于上面并不严谨的定义，去掉任何一个性质都会导致我们能够非常轻易地构造出可验证延迟函数：

1、如果不要求验证结果是高效的，也就是说没有显著地比计算结果更快，那么我们可以通过刚才提到的连续哈希的方案进行构造； 2、如果我们不需要它保证唯一性，那么早在 2013 年 Mahmoody 等人的工作 Publicly Verifiable Proofs of Sequential Work 就已经实现了这一点； 3、如果它不保证串行性，那么显然构造方法就更多了。

或许有读者会感觉 VDF 和 PoW 是一类东西，实际上，虽然他们计算起来都不是很容易，但是他们之间有很多关键的区别。

1、PoW 不抵抗并行计算加速而 VDF 抵抗。实际上，PoW 不抵抗并行计算加速是符合中本聪的「一 CPU 一票」的设想的，而抗并行加速的性质只会与这个目的背道而驰。VDF 会使得多 CPU 的计算者和单 CPU 的计算者相比几乎没有什么优势； 2、对于固定的难度设定 d，PoW 可以有很多合法的解，这也是保证 PoW 共识网络拥有稳定的吞吐量以及刺激矿工进行竞争的前提。而对于给定输入 x，VDF 拥有唯一的输出（这也是为什么它被称作函数）。

上述两条性质决定了 PoW 直接作为随机数的来源是有缺陷的，同时，VDF 也无法直接替代 PoW。但是这并不能说明 VDF 不可以被用到共识协议里，这一点会在下一个章节详谈。

上一章节我们介绍了 VDF 是什么，以及它具有怎样的性质，这一章节我们关注它的用途。

增强公共可验证随机数的安全性

区块链上的随机数一直是一个热门话题。无论是在一些权益证明（Proof-of-Stake,PoS）共识协议的设计里，还是在智能合约平台，譬如 Ethereum 和 EOS，上一些非常火爆的游戏类应用，随机数都占据了核心的地位。同时，很多这些应用中，实际设计的随机数获取方案还非常不成熟，以至经常会有应用因为不安全的随机数而被黑客攻击 [6] 的新闻出现。

VDF 对于一些从公共来源获取随机数的方法非常有用。比如从股票市场或者是从 PoW 区块链上获取。这些随机源拥有足够的随机性（更严格地讲，是最小熵）。但是高频交易者可以影响股价，同时，PoW 区块链的矿工也可以通过不广播自己挖出的区块来降低自己不想要的随机数结果的出现概率。但是这样的攻击方式成立的前提条件是攻击者有时间在其他诚实参与者之前预测出随机数结果。VDF 恰好能阻止这一点。如果将 VDF 的时间参数 tt 设置到足够长（比如 10 个块的间隔），将最新的区块头

作为输入扔进 VDF 中，输出作为随机数结果。那么攻击者只能在 10 个块之后才能知道随机数的结果是什么，那个时候想要再改变结果已经很难了（需要 fork 10 个区块）。

此外，VDF 也可以增强一些多方参与的随机数方案。比如 Commit-and-Reveal 方案中，攻击者可以拖到 Reveal 阶段的最后再决定是否揭示自己的承诺。如果我们去掉 Commit 阶段，并且协议的最后整合所有人的输入之后不直接作为随机数结果，而是放入 VDF 中，并且将 VDF 的时间参数 tt 设置到足够长（晚于最后提交期限），那么即使是最后一刻提交的人也无法知道随机数的结果，操纵结果也就无从谈起。与之相比较，其他的多方参与方案通常最多容忍小于一半的恶意节点，并且交互的开销要比上述方案更大。

解决 Nothing-at-stake Attack

正如上一节所述，VDF 可以用于增强随机数生成方案的安全性，因此，在一些使用了随机数来选取 Leader 的共识协议中也可以使用 VDF 在增强其安全性。一些节约能源的共识协议，例如 PoS，空间证明（Proof-of-Space）以及存储证明（Proof-of-Storage），为了防止 Nothing-at-stake attack，需要使用随机选举每隔一段时间选举出一个 Leader。这些协议使用的随机数方案大多只在诚实参与者占据大多数时保持安全。利用 VDF 可以降低这样的限制到至少存在一个诚实参与者。

什么是 Nothing-at-stake Attack？PoS 区块链发生分叉时，共识参与者为了自己的利益会选择在不同的分叉链上同时进行抵押资产参与出块，这样分叉链有可能会一直存在并且分叉越来越多，严重危害系统的一致性，这样的攻击被叫做 Nothing-at-stakeattack。在 PoW 链上进行这样的攻击需要分散算力，因此这样的攻击只适用于「节约能源」的共识协议。

除了随机选举之外，还有一种叫做 Proofs of Space and Time[7] 的方案可以防止这种攻击。实际上该方案模拟了 PoW 的挖矿过程：挖出区块的时间是不确定的，并且每个矿工都在互相竞争成为最早挖出区块的人。不一样的地方在于，模拟挖矿过程实际上并不需要消耗大量的并行计算资源（Proof-of-Time），只有在进入挖矿时有一定的门槛（Proof-of-Space）。具体来讲，整个挖矿过程按照时间顺序被分成不同的区间，每一个区间都有一个公共随机的挑战 c （举个例子，可以是前一个区间挖出的块的哈希值）。假设某个矿工拥有的空间单位为 N，他需要生成一个证明 π 来证明他拥有这 N 单位的空间，并且专门用于该区块链的挖矿，这一点由 Proof-of-Space 保证。矿工的目标为找到最小的 τ=H(c,π,i),1?i?N，然后将 c 作为输入计算一个 VDF （事实上是增量 VDF），该 VDF 的时间参数与 τ 正相关。这样的设计中，拥有空间越多的矿工找到更小的 τ 的可能性更大，同时，VDF 保证了一段时间的流逝，使矿工大量分叉需要消耗大量的时间。

减轻 Long-range Attack

几乎所有的 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 倍的计算速度，那么这样的加速对于使用 VDF 作证明的 PoS 链是不可接受的（攻击者可以在 10 年之后伪造出 1 年以前的区块）。

10 倍的加速对于随机数生成的场景无所谓，因为该场景下，不需要保证「攻击者算得没有诚实节点快」，只需要保证攻击者无法在某个时间点（随机数来源再也无法更改的时间点，例如股市闭市）之前无法计算出结果即可。从而在随机数生成的场景，我们可以选取一个足够长的时间参数，使得攻击者即使加速也无法操纵随机数。

副本证明（Proof of Replication）

副本证明所需要解决的问题是，服务器讲解向客户端证明自己在某一专门的存储介质上存储了指定的数据，即使这样的数据是可以从别的存储来源轻易获得的。注意副本证明是为了证明服务器拥有一份数据的副本，而不是证明它有这样的数据。举个例子，云存储服务提供商声称自己为客户的数据做了额外的两份冗余备份来保证用户数据的 availability，因此客户需要为这样的冗余备份交更多的钱。但是怎么证明云服务提供商有一共三份副本而不是两份或者只有一份呢？这就需要用到副本证明。一种思路是利用在时间上不对称的编码方案（也就是编码很慢，但是解码很快），VDF 可以做到这一点（事实上是可解码 VDF）。身份为 id 的服务器首先将文件分成 b-bit 大小的文件块 Bi\,1?i?n，然后计算 Bi⊕H(id||i) 并将结果作为输入放进 VDF 计算得到 yi\,1?i?n，其中 H 是输出长度为 b-bit 的防碰撞哈希函数。服务器存储所有的 yi，客户端不断随机挑选 ii 进行轮询要求服务器返回 yi，服务器在规定时间内需要响应给客户端相应的结果，而客户端可以在很短的时间内通过解码 yi 得到 Bi 完成验证。如果服务器没有存储 yi ，那么想要正确响应客户端必须计算 yi，然而这样的计算无法在规定的时间内完成。服务器也可以只存储一部分 yi （比例为 ρ），由于客户端是随机轮询，每一次服务器成功欺骗客户端的概率为 ρ。只要客户端重复 k 次这样的轮询，就可以将服务器欺骗成功的概率降到 ρk。需要补充的一点是，服务器可以不存储 Bi，由于 yi 解码很快，即使只存储 yi 也不会太影响性能。

既然 VDF 是一个函数，那么它就必然具有这样的形式：f:X→Y。为了实现前文所述的功能，即「抵抗并行计算的延迟」以及「可验证的结果」，VDF 中必然包含一个用于计算结果的算法以及一个用于验证结果的算法。同时，这样的密码学工具通常还包含一个配置阶段，用来确定后续需要使用的参数。因此，VDF 被描述为三个算法的一个三元组 (Setup(Setup, EvalEval, Verify)Verify)。

每个算法的定义如下：

• Setup(λ,t)→pp=(ek,vk) 接受安全参数 λ 以及时间参数 t，生成一个公共参数 pp，这个参数是所有人都可以看到的。公共参数 pp 包含了一个用于计算的参数 ek 和一个用于验证的参数 vk；
• Eval(ek,x)→(y,π) 接受计算参数 ek 和输入 x∈X，计算出输出 y∈Y 和证明 π；
• Verify(vk,x,y,π)→{accept,reject}接受 vk，x，y 以及 π，输出 accept （验证通过）或者 reject （验证失败）。

如图 1 所示我们可以看到 VDF 通常的运行流程。

图 1：可验证延迟函数

上面这些几个算法有一些需要补充说明的地方：

• 关于 SetupSetup

1、SetupSetup 的运行时间不能太久，它被安全参数 λ 所限制； 2、Setup 这个阶段通常会需要随机数作为参数以保证安全性，如果随机数是私下选择的，也就是不可公开的，那么这个阶段就会需要一个可被信任的一方来进行随机数的选择，称之为trusted setup。相反，如果随机数可以是公共随机数，那么这个阶段就不需要这样的 trusted setup。显然，我们希望尽量避免 trusted setup。

 1/2    1 2 下一页 尾页