自从以太坊将可验证延迟函数列入研究计划并打算在以太坊2.0使用之后，VDF得到了广泛的关注。VDF这个概念最初由斯坦福大学密码学教授DanBoneh等人在其论文VerifiableDelayFunction中给出。该篇文章于2018年发表在密码学顶级会议之一的CRYPTO上。
目前网络上有一些英文和中文的文章介绍了VDF的概念和原理，但是它们要么无法给出全面直观的解释，要么只是粗浅地谈论应用。本文试图通过浅显的语言和具体的例子来让对密码学和群论不够了解的读者能够全面而直观地理解它的定义和原理。同时，本文还给出了它的可能的应用场景以及目前的研究和应用状况。
简介
VDF是一类数学函数，能够使得该函数的计算需要至少一段已知的时间，即使是在同时使用少量CPU进行并行计算的情况下。
对于未精心设计过的算法，并行计算有可能极大地缩减其计算时间。以比特币的挖矿算法为例，设0?nonce?232?10?nonce?232?1，如果只有一个运算单元，那么可能需要耗费多达232次SHA-256计算的时间。如果有两个运算单元，就可以将任务对半分摊，让他们并行地计算哈希值。最多只需要耗费231次SHA-256计算的时间。同时满足以下性质：
VDF的结果的检验应当是非常有效率的。
唯一性：对于任意一个VDF的输入，应当有唯一的输出结果能够通过检验。也就是说，不存在两个不同的输出，他们有相同的输入。如果输出结果包含“结果”和关于结果的“证明”两部分，那么证明部分可以不具有唯一性，但需要保证“验证者因为证明而验证通过，但是输出结果却不是正确的结果”这件事发生的概率小到可以忽略不计。
串行性：攻击者即使能够提前计算很长时间，并且拥有很多并行处理器，利用各种计算方法，能够以少于t的时间计算出VDF结果的概率可以小到忽略不计。
VDF能够抵抗并行计算加速，这意味着为了计算VDF，应当完成一系列串行才能完成的任务，后一个任务必须依赖于前一个任务。这时，对哈希函数有所了解的读者可能会想到一种方案：连续将一个输入哈希tt次。这样的方案的确是无法通过并行算法显著地加速的，但是这样得到的结果，其验证将会非常没有效率：验证者需要重复哈希T次的计算，即使保留一些中间结果，验证的工作量和计算的工作量也是常数级别的差距。从这个例子我们可以看出，在这样的定义下，可验证延迟函数的构造并没有想象中的那么简单。
事实上，对于上面并不严谨的定义，去掉任何一个性质都会导致我们能够非常轻易地构造出可验证延迟函数：
BTC五分钟内上涨1.21%:BTC五分钟内上涨1.2%，上涨金额为78美元，其中火币PRO上现价为$6531.05。[2018/6/19]
如果不要求验证结果是高效的，也就是说没有显著地比计算结果更快，那么我们可以通过刚才提到的连续哈希的方案进行构造。
如果我们不需要它保证唯一性，那么早在2013年Mahmoody等人的工作PubliclyVerifiableProofsofSequentialWork就已经实现了这一点。
如果它不保证串行性，那么显然构造方法就更多了。
PoW或许有读者会感觉VDF和PoW是一类东西，实际上，虽然他们计算起来都不是很容易，但是他们之间有很多关键的区别。PoW不抵抗并行计算加速而VDF抵抗。实际上，PoW不抵抗并行计算加速是符合中本聪的“一CPU一票”的设想的，而抗并行加速的性质只会与这个目的背道而驰。VDF会使得多CPU的计算者和单CPU的计算者相比几乎没有什么优势。
对于固定的难度设定d，PoW可以有很多合法的解，这也是保证PoW共识网络拥有稳定的吞吐量以及刺激矿工进行竞争的前提。而对于给定输入x，VDF拥有唯一的输出。
上述两条性质决定了PoW直接作为随机数的来源是有缺陷的，同时，VDF也无法直接替代PoW。但是这并不能说明VDF不可以被用到共识协议里，这一点会在下一个章节详谈。
用途
上一章节我们介绍了VDF是什么，以及它具有怎样的性质，这一章节我们关注它的用途。
增强公共可验证随机数的安全性
区块链上的随机数一直是一个热门话题。无论是在一些权益证明共识协议的设计里，还是在智能合约平台，譬如Ethereum和EOS，上一些非常火爆的游戏类应用，随机数都占据了核心的地位。同时，很多这些应用中，实际设计的随机数获取方案还非常不成熟，以至经常会有应用因为不安全的随机数而被黑客攻击的新闻出现。
VDF对于一些从公共来源获取随机数的方法非常有用。比如从股票市场或者是从PoW区块链上获取。这些随机源拥有足够的随机性。但是高频交易者可以影响股价，同时，PoW区块链的矿工也可以通过不广播自己挖出的区块来降低自己不想要的随机数结果的出现概率。但是这样的攻击方式成立的前提条件是攻击者有时间在其他诚实参与者之前预测出随机数结果。VDF恰好能阻止这一点。如果将VDF的时间参数tt设置到足够长，将最新的区块头作为输入扔进VDF中，输出作为随机数结果。那么攻击者只能在10个块之后才能知道随机数的结果是什么，那个时候想要再改变结果已经很难了。
BTC五分钟内上涨1.07%:BTC五分钟内上涨1.07%，上涨金额为76美元，其中火币Pro上现价为$7236.09。[2018/5/28]
此外，VDF也可以增强一些多方参与的随机数方案。比如Commit-and-Reveal方案中，攻击者可以拖到Reveal阶段的最后再决定是否揭示自己的承诺。如果我们去掉Commit阶段，并且协议的最后整合所有人的输入之后不直接作为随机数结果，而是放入VDF中，并且将VDF的时间参数tt设置到足够长，那么即使是最后一刻提交的人也无法知道随机数的结果，操纵结果也就无从谈起。与之相比较，其他的多方参与方案通常最多容忍小于一半的恶意节点，并且交互的开销要比上述方案更大。
Nothing-at-stakeAttack
正如上一节所述，VDF可以用于增强随机数生成方案的安全性，因此，在一些使用了随机数来选取Leader的共识协议中也可以使用VDF在增强其安全性。一些节约能源的共识协议，例如PoS，空间证明以及存储证明，为了防止Nothing-at-stakeattack，需要使用随机选举每隔一段时间选举出一个Leader。这些协议使用的随机数方案大多只在诚实参与者占据大多数时保持安全。利用VDF可以降低这样的限制到至少存在一个诚实参与者。
什么是Nothing-at-stakeAttack？PoS区块链发生分叉时，共识参与者为了自己的利益会选择在不同的分叉链上同时进行抵押资产参与出块，这样分叉链有可能会一直存在并且分叉越来越多，严重危害系统的一致性，这样的攻击被叫做Nothing-at-stakeattack。在PoW链上进行这样的攻击需要分散算力，因此这样的攻击只适用于“节约能源”的共识协议。除了随机选举之外，还有一种叫做ProofsofSpaceandTime的方案可以防止这种攻击。实际上该方案模拟了PoW的挖矿过程：挖出区块的时间是不确定的，并且每个矿工都在互相竞争成为最早挖出区块的人。不一样的地方在于，模拟挖矿过程实际上并不需要消耗大量的并行计算资源，只有在进入挖矿时有一定的门槛。具体来讲，整个挖矿过程按照时间顺序被分成不同的区间，每一个区间都有一个公共随机的挑战c。假设某个矿工拥有的空间单位为N，他需要生成一个证明π来证明他拥有这N单位的空间，并且专门用于该区块链的挖矿，这一点由Proof-of-Space保证。矿工的目标为找到最小的τ=H(c,π,i),1?i?N，然后将c作为输入计算一个VDF，该VDF的时间参数与τ正相关。这样的设计中，拥有空间越多的矿工找到更小的τ的可能性更大，同时，VDF保证了一段时间的流逝，使矿工大量分叉需要消耗大量的时间。
BTC五分钟内下跌1.01%:据huobiPro平台数据，BTC五分钟内下跌1.01%，下跌金额为75美元，目前收于7381.43美元，请密切关注行情走向，注意控制风险。[2018/5/27]
Long-rangeAttack
几乎所有的PoS方案都面临Long-rangeattack的问题。目前PoS协议依赖于外部的时间戳服务来帮助他们解决这个问题——只要能判断哪一条链更老，就能阻止这样的攻击发生。VDF能够帮助PoS解决这样的问题。VDF相当于一种时间流逝的证明，对于给定的VDF，该VDF至少需要多久才能得出结果是一个公共知识。因此，只需要在PoS链上包含VDF的输入与输出即可证明给定区块的历史。
什么是Long-rangeAttack？在PoS协议中，任意时刻都有一组权益相关者拥有按照权益多少分配的投票权。PoS假设大多数权益相关者并没有理由对系统造成破坏，因为这样反而会损害自己的权益。但是如果这些权益相关者在某一个时间点出售了自己的权益，这样的激励对他们来讲是无效的。这些已经出售了自己权益的曾经的权益相关者仍然可以在曾经某一个时间点轻易对PoS链分叉达到原有链的的长度，从中攫取额外的利益，这样的攻击被称作Long-rangeattack。它在PoW上不太可能发生，因为对于PoW来讲，无论从哪一个时间点进行分叉，都必须要付出相应的算力才能追上原有的链，想要分叉的区块越多，付出的算力也就越多。但是必须要指出的是，这样的方法并不是完美的，因为VDF仍然是可以被特殊硬件加速的。如果攻击者获得了诚实节点10倍的计算速度，那么这样的加速对于使用VDF作证明的PoS链是不可接受的。
10倍的加速对于随机数生成的场景无所谓，因为该场景下，不需要保证“攻击者算得没有诚实节点快”，只需要保证攻击者无法在某个时间点之前无法计算出结果即可。从而在随机数生成的场景，我们可以选取一个足够长的时间参数，使得攻击者即使加速也无法操纵随机数。ProofofReplication副本证明所需要解决的问题是，服务器如何向客户端证明自己在某一专门的存储介质上存储了指定的数据，即使这样的数据是可以从别的存储来源轻易获得的。注意副本证明是为了证明服务器拥有一份数据的副本，而不是证明它有这样的数据。举个例子，云存储服务提供商声称自己为客户的数据做了额外的两份冗余备份来保证用户数据的availability，因此客户需要为这样的冗余备份交更多的钱。但是怎么证明云服务提供商有一共三份副本而不是两份或者只有一份呢？这就需要用到副本证明。一种思路是利用在时间上不对称的编码方案，VDF可以做到这一点。身份为id的服务器首先将文件分成b-bit大小的文件块Bi,1?i?n，然后计算Bi⊕H(id||i)并将结果作为输入放进VDF计算得到yi,1?i?n，其中H是输出长度为b-bit的防碰撞哈希函数。服务器存储所有的yi，客户端不断随机挑选iyi，服务器在规定时间内需要响应给客户端相应的结果，而客户端可以在很短的时间内通过解码yi得到Bi完成验证。如果服务器没有存储yi，那么想要正确响应客户端必须计算yi，然而这样的计算无法在规定的时间内完成。服务器也可以只存储一部分yi，由于客户端是随机轮询，每一次服务器成功客户端的概率为ρ。只要客户端重复k次这样的轮询，就可以将服务器成功的概率降到ρk。需要补充的一点是，服务器可以不存储Bi，由于yi解码很快，即使只存储yi也不会太影响性能。基本原理
BTC五分钟内上涨1.04%:BTC五分钟内上涨1.04%，上涨金额为91美元，其中火币Pro上现价为$8879.16，请密切关注行情走向，注意控制风险。[2018/4/26]
既然VDF是一个函数，那么它就必然具有这样的形式：f:X→Y。为了实现前文所述的功能，即“抵抗并行计算的延迟”以及“可验证的结果”，VDF中必然包含一个用于计算结果的算法以及一个用于验证结果的算法。同时，这样的密码学工具通常还包含一个配置阶段，用来确定后续需要使用的参数。因此，VDF被描述为三个算法的一个三元组(SetupEvalVerify)每个算法的定义如下：
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λ所限制。
Setup这个阶段通常会需要随机数作为参数以保证安全性，如果随机数是私下选择的，也就是不可公开的，那么这个阶段就会需要一个可被信任的一方来进行随机数的选择，称之为trustedsetup。相反，如果随机数可以是公共随机数，那么这个阶段就不需要这样的trustedsetup。显然，我们希望尽量避免trustedsetup。
关于Eval
证明π不是必须的，如果仅仅通过y就能验证的话。在y的计算中，不允许有随机数的引入，但是在π的生成过程中可以引入。
为了保证串行性，Eval在拥有不超过关于t的多项式对数(Poly-log)个并行处理器时，运行时间必须为t。
为什么Eval要允许一定程度的并行计算达到时间t呢？因为可能并没有构造能够完美地让并行和串行计算时间完全相同，所以我们需要容忍一定量的不太显著的并行加速。
关于Verify
Verify中不引入随机数，也就是说，它是确定性算法。Verify的运行时间要比t小得多，具体来讲，他们在运行时间上拥有指数级别的差距。
基于上述定义，VDF还有一些拥有特殊性质的变种：
可解码VDF：如果对于一个VDF方案，存在一个算法对于任意x∈X能够从y∈Y反向计算出x，那么这个VDF就是可解码VDF。在这样的情况下，证明π是不需要的。当然，一个平凡的构造是，将π放进y里面。
增量VDF：如果在Setup算法中，参数t没有被唯一确定，而是允许在Eval的输出之一π中指定，这样的VDF被称作增量VDF。一种效果类似的构造是，在Setup中设定t为一个单位的时间，如果想要在计算阶段达到不同的延迟时间，例如T=nt，只需要串行n次Eval即可。但是这样的构造会导致n倍的证明长度，增量VDF不会产生额外的证明。
陷门VDF：如果某个VDF方案存在一个算法，使得知道某一秘密值sk的人能够通过这个算法迅速由Eval的输入得到Eval的输出，那么这个VDF是陷门VDF。更直观的理解是，陷门VDF有一个后门可以让人绕过延迟限制迅速算出结果。
弱VDF：如果我们放宽限制，允许“即使在Eval中使用多项式个并行处理器才能在t时间算出结果”这样的情况出现，这样的VDF被称作弱VDF。弱VDF在实际应用中会更加消耗诚实参与者的算力。但如果将VDF用于生成公共可验证的随机数，可以将计算任务交给一个诚实参与者，其他参与者等着验证。这时，这样的唯一计算者是可能拥有足够多的处理器的。
一种简单的构造方式
上文提到了使用连续的哈希操作是一种防止并行的计算加速的手段，但是这样的手段非常低效，不符合VDF的定义。我们希望能够找到一种验证更加迅速的防并行的构造方式。考虑这样的一个例子：
首先选择一个数λ=161，然后然后对于任意的输入x，我们执行下面的操作t次：
计算k=2
取k除以λ的余数得到l
令k取l，返回第一步，如果是最后一次操作，输出结果y
假设我们的输入x=11，t=8那么结果为95，事实上，如果我们让t取不同的值，把结果都记录下来，可以得到下述表格：
更一般地讲，如果a≡bmodm代表a和b分别除以m的余数相同的话，那么上述操作实际上就是计算：
如果我们知道λ的因式分解，例如161=7×23，那么我们可以通过两次指数运算来快速计算出y的值。首先计算函数?(161)=(7?1)×(23?1)=132，然后计算2t除以?(161)的余数：
然后计算x124除以λ的余数：
上述过程比起连续平方8次看似没有减轻多少工作量，但实际上当t和λ非常大时，远比连续平方快得多。一般地，函数
如果
这个函数被称之为欧拉函数。上述例子可以一般化为：
因此，如果没有任何人知道λλ的因式分解，也就无法快速计算出?(λ)，从而只能重复t次平方操作使用
计算出y。
事实上，这个构造可以使用群论得到更加本质的解释。我们发现，由于模运算y的值是小于λ的，而所有小于λ且与λ互素的数一起组成了一个群，这个群被称作整数模λ乘法群，记作(Z/λZ)*。这个群的阶，也就是元素个数就等于欧拉函数?(λ)的值。因此，关键问题落在了如何生成这样的知道阶的群。
目前主要有两种方法：
使用RSA群
使用虚二次域的类群
RSA群的生成与RSA加密算法类似，选取大素数p和q，其中p=2m1，q=2n1且m，n均为素数。令N=pq，则(Z/NZ)*即为所需群。然而一个很显然的问题是，这其中涉及到了trustedsetup，我们必须相信生成N的参与者不会泄露p和q。我们也可以使得群生成算法使用公共随机数来直接选取足够大的N使得因式分解N非常困难，但是这样的N需要非常大以至于这样的方法非常不现实。第二种方法解决了第一种方法的问题，但是由于第二种方法解释起来涉及概念较多，本篇文章不会涉及。同时，对于结果y综述。
研究与应用现状
学术界第一次正式提出VDF的概念是在Boneh的论文中，他在论文中给出了VDF的应用场景以及形式化的模型，安全分析和一般构造方法。之后出现了分别出现了两篇VDF的构造论文，分别是Wesolowski的EfficientVDF以及Pietrzak的SimpleVDF。两者都利用在不知道阶的群中连续做平方运算的方法来构造VDF，不同的是，他们生成证明的构造有所区别。简单来讲，Wesolowski的证明更短，验证更快；但是Pietrzak的构造中，生成证明的速度更快，同时证明系统依赖的安全假设更弱。2019年Feo等人使用超奇异同源(SupersingularIsogenies)以及双线性对构造VDF。相比于Wesolowski和Pietrzak的工作，他们的构造本身就是非交互的，不需要经过转换，同时不需要证明π即可完成验证，但是他们的构造中Setup耗费的时间更长，更为主要的是，目前还只能进行trustedsetup。
在应用领域，ChiaNetwork计划使用VDF来支持他们的Proof-of-Space；以太坊研究团队也打算在以太坊2.0中引入VDF，以期在以太坊2.0信标链中使用RANDAOVDF随机选取出块人。最初以太坊计划使用RANDAOVDF的方案。但由于以太坊2.0的计划瞬息万变，截至文章最后修改前，以太坊信标链计划将区块间隔限制到6秒，64个区块为一个epoch，因此一个epoch为6.4分钟，每一个epoch需要进行一次出块人切换，因此VDF的时间参数最少应设置为6.4分钟，但是目前以太坊计划将其设置为102.4分钟，目的是防止潜在的攻击者利用特殊硬件加速VDF。
附录
https://vdfresearch.org/
https://eprint.iacr.org/2018/601
https://blog.trailofbits.com/2018/10/12/introduction-to-verifiable-delay-functions-vdfs/
https://ethfans.org/posts/vdf-faq-part-1
https://eprint.iacr.org/2011/553
https://www.huoxing24.com/newsdetail/20181122150016435403.html
[7https://cyber.stanford.edu/sites/g/files/sbiybj9936/f/bramcohen.pdf
https://zh.wikipedia.org/wiki/群
https://zh.wikipedia.org/wiki/整数模n乘法群
https://eprint.iacr.org/2018/712
https://eprint.iacr.org/2018/623
https://eprint.iacr.org/2018/627
https://eprint.iacr.org/2019/166
https://www.chia.net/
https://ethresear.ch/t/minimal-vdf-randomness-beacon/3566
作者:PRIEWIENV
本文首发于公众号NPC源计划，EthFans经授权转载。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。