前沿技术 | VRF与VDF

（图片来源于网络，如有侵权，请联系我们删除）

VRF(Verifiable Random Functions)

要解决的问题

传统的随机数方案存在的问题：

随机预言机RO(Random Oracle)，对于不同的输入，可以产生均匀分布的随机数，对于相同的输入，得到的输出一定是相同的。但接收者必须简单的相信随机数是从输入计算得来的。

带密钥的哈希函数，也可在有限数值区间内生成均匀分布的随机数。但如果要验证，必须暴露种子，一旦种子暴露给了敌手，敌手就可以计算出所有其它点对应的值，而不只是你想公布出去的某个点的值。

可验证随机函数VRF就可以解决以上两种随机方案存在的问题：

给定一个密钥，对于不同的输入值，可生成均匀分布的随机数；在不暴露密钥的情况下，敌手无法预测其它输入值对应的随机值；并且能够被验证此随机值的真实性，即该随机值确实是由该密钥和输入产生的。

简单来讲，VRF可生成均匀分布的随机数，生成的随机数可被验证但不可被预测。

相比非对称加密

相同点：非对称加密也可通过不同的输入消息产生不同的签名值，并且可以被验证。

不同点：

o 非对称加密得到的签名值不是均匀分布的，如RSA。

o 非对称加密对于相同的输入消息和密钥，得到的签名值不是固定的。可以对同一个消息不断的签名，产生不同的签名值，可将输出偏置到其期望范围内。而VRF对于相同的输入和密钥，产生的输出一定是相同的。

模型和定义

G：生成一对公私钥：

随机数生产方生成一对公私钥：(PK、SK) = G (k)；k为安全参数。

?F：生成随机数和证明：

随机数生产方生成随机数和证明：(vrfout, proof) = F (SK, input)。

input为公开的输入，生产方将PK、proof和随机数递交给接收方。

V：接收方验证随机数：

YES or NO = V (PK, input, vrfout, proof)

算法实现

?algorand

草案：https://tools.ietf.org/html/draft-irtf-cfrg-vrf-03.html

开源C库：基于libsodium开源密码库，添加了crypto_vrf模块https://github.com/algorand/libsodium.git

性能：

o?通过私钥生成证明

o?通过公钥验证

google

golang：

https://github.com/google/keytransparency/tree/master/core/crypto/vrf其它

JavaScript：https://github.com/pinqy520/vrf.js

区块链应用

选取功能性节点，打包节点或验证节点。

通常的选取方式：

ChainSQL联盟链新共识：(区块高度?+ view)?% 验证节点个数。

Zilliqa：前区块(FB或DSB)的hash % 节点 (分片节点或委员会节点) 个数。

以上两种方案如果应用在公链上的话，攻击者均可推测出将来的leader集中攻击， 需要额外的安全措施。使用区块hash的方案从逻辑上来讲还有一个弊端，当前区块的生产者可能有能力控制当前生产的区块hash，使区块hash偏置在其期望内，影响下一个leader的选举。当然，Zilliqa当前整体的共识方案是没有这个问题的。

在选取功能性节点中引入VRF后，所有节点可以同时出块，在打包的区块中公布自己的proof和随机数，其它节点验证proof和随机数，并且根据随机数选举出优先级最高的区块成为这一轮的候选区块，进行共识。

首先说明一点，algorand源码对VRF的封装与上面提到的模型稍微有点差别，但整体流程是一致的，不影响我们对VRF的理解。这里不展示代码，只简要说明下使用流程。

节点中每个能参与投票的账户为区块生成提案。提案包含区块hash和新的种子。新的种子供下N(N为可配置的种子回看参数，下同)轮的共识使用，新的种子的生成就是利用VRF来生成的，账户的私钥和前N轮的种子作为输入。这样一个节点在一轮中可以产生多个提案，这些提案包含的区块hash相同，新的种子不同。其它节点也可以产生与本节点区块hash不同，新的种子也不同的提案。

那么哪个提案能成为有效的提案呢？下面又需要使用VRF来做决定了。

每个账户为自己的提案投票(Vote)。在投票时，使用VRF来生成随机数和证明，使用前N个轮次的种子和当前轮次高度以及账户私钥生成随机数和证明。

节点对收到的所有投票进行VRF验证，并根据随机数、抽签因子和账户的token比例运算抽签。

计算出每个vote的权重后，再根据hash（随机数和权重），选出最小的vote作为最终的vote，进行共识。

VDF(Verifiable Delay Functions)

VDF可以抽象的理解为：可证延迟函数y=f(x)，对于给定的x，要计算出x对应的结果y，具有一定的难度(需要花费较长的时间t)。同时，需要满足以下性质：

1. 串行性：只能顺序运算，无法通过增加计算设备而使运算时间变短。

2. 唯一性：对于同一个输入x，仅存在唯一的结果y。

3. 快速验证：在得到结果y后，可以快速的验证x对应的结果就是y。

模型和定义

通常包含有三个算法：配置、计算和验证。

Setup(λ, t) -> pp = (ek, vk)

Setup接受一个安全参数λ以及时间参数t，时间参数t用于控制第二步串行运算须满足的运行时长。

同时Setup生成一个公共参数pp，pp包含用于计算的参数ek和用于验证的参数vk。

?Eval(ek, x) -> (y, π)

Eval接受计算参数ek和函数输入x，计算出结果y和证明π。

证明π不是必须的，如果算法构造仅仅通过y就能验证的话。

串行运算时间满足t。

Verify(vk, x, y, π) -> (accept, reject)

Veriry接受输入、输出、验证参数及证明，返回验证通过或者失败。

验证的时间要比t小的多。

流程图

应用领域

产生随机数

同VRF一样，VDF同样可以用来产生随机数。首先看下目前以太坊RANDAO生成随机数机制。

以太坊1.x中的随机数生成器，生成随机数的基本过程可以分为三个阶段：

第一阶段：收集有效sha3(s)

首先需要在RANDAO合约(以下用C指代)中创建一轮随机数竞选活动，然后想要参与生成随机数的人需要在指定时间段内向合约C发送m个ETH做抵押并附上sha3(s)的结果，s为参与者自选的秘密数字。

第二阶段：收集有效s

第一阶段后，成功提交sha3(s)的人要在第一阶段指定时间内向合约C发送一笔带有秘密数字s的交易。合约C会对s运行sha3运算并将结果与先前提交的数据进行比较，检查s是否有效。有效s将被保存到种子集合中，最终生成随机数。

第三阶段：计算随机数、退还押金及奖金

1. 成功收集全部秘密数字后，合约C根据函数f(s1，s2，...，sn)计算出随机数，计算结果会被写入C的存储并发送给订阅者，需要随机数的人也可以自提。

2. 合约C将第一阶段的押金返还给参与者，并将利润分成相等份作为额外奖励发给全部参与者。收益指需要随机数的其他人所支付的费用。

附加规则：

为确保RNG不受操纵，合约C有以下附加规则：

1. 第一阶段中，超过两个相同sha3(s)按顺序提交时，接受第一个。

2. 参与者提交sha3(s)被合约C接受时，须在第二阶段中披露该s。

> 参与者未能在第二阶段披露s时，第一阶段发送的m个ETH被没收且不提供任何回报。> 第二阶段有一个或多个s未披露时，随机数生成失败。没收的ETH被均分成等份发予在第二阶段中披露s的其他参与者。订阅随机数支付的费用予以退还。

安全风险：

最后一个披露自己秘密数字的人，可以先计算出最终的随机数，如果对自己有利则披露，否则不披露(放弃保证金)。

如果需要高级别安全性的话，可以大大增加第一阶段的押金数量。

但是在某些涉及大量利益的场景下，参与者仍有动机和能力去操控随机数的生成与否。

随机数参与者可以通过预测、操控生成对自己有利的随机数。那如果无法预测，他们就无法作弊。VDF通过延迟生成随机数来防止参与者作弊。

以太坊2.0将RANDAO和VDF结合，RANDAO合约产生的随机数作为VDF的输入，计算出最终的随机数，从而提高作弊的难度。

具体方案：

出块间隔为6s。

一个epoch为6.4分钟，也就是一个epoch中产生64个区块。

每一个epoch通过RANDAO合约产生一个随机数作为VDF的输入，并启动一个VDF。

VDF的延迟时间t设置为102.4分钟，也就是每一个最终随机数的生成都需要经过102.4分钟。

为了保证每隔一个epoch(6.4分钟)能够产生一个随机数，系统中总是有16个(102.4/6.4)VDF在同时运行。

每个随机数在区块链中都能被任何人用于任何功能。

目前VDF函数结构和硬件设施还在研究中：

协议实验室（Protocol Labs）宣布将和以太坊基金会进行合作，共同研发最少一类可以满足“安全、高效、可用”要求的可验证延时函数（Verifiable Delay Function，简称VDF）结构。

协议实验室将和以太坊基金会就构建针对VDF运行优化的ASIC的可行性进行合作与初步研究，并对其进行评估和投资。

在VDF的论文中提到了一种VDF变种：可解码VDF(Decodable VDF)。

除了上面的性质外，还满足，对于结果y可以反向计算出x。在这种情况下，证明π是不需要的。

可以把VDF函数理解成一个编码函数，并且它还对应一个解码函数。这一对编解码函数在时间上是不对称的，编码耗时长，解码迅速。

具体方案：

服务器存储文件的形式为(B1, B2, B3, ..., Bn)，将一份文件分割成大小为b bit的n个数据块，将第i个数据块记作Bi。

每一个数据块对应的Xi = Bi xor HASH(id, i)，其中id为服务器的id，i为数据块id，HASH是输出长度与数据块大小(b bit)一致的防碰撞哈希函数。

每台服务器在存储每个数据块的同时，计算好Xi对应的编码数据Yi = VDF_ENCODE(Xi)后，并且存储每个数据块对应的Yi。

客户端向某个服务器请求Yi，以验证其是否存储有文件副本。服务器无法作弊，因为每个存储服务器存储的Yi不一样，并且通过向其它服务器请求文件块Bi后，再生成Yi的过程很长，验证会超时。

服务器可以只存储所有数据块编码后的Yi，因为根据Yi可以很快的解码出Xi，然后得到文件块i。Xi = DECODE(Yi), Bi = Xi xor HASH(id, i)。

与POW对比

1. 计算和验证都是非对称的。

2. pow可以并行运算，VDF只能串行计算。

3. 而对于给定输入x，VDF拥有唯一的输出(这也是为什么它被称作函数)，而POW的解可以有多个。

—-

编译者/作者：众享比特

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。