LOADING...
LOADING...
LOADING...
当前位置: 玩币族首页 > 新闻观点 > 前沿技术 | VRF与VDF

前沿技术 | VRF与VDF

2019-12-11 众享比特 来源:区块链网络
本文主要通过VRF与VDF论文及相关代码和资料对这两个技术和其应用进行简要分析。文中不会展示具体代码部分,只对相关代码做一些文字性说明。

640?wx_fmt=jpeg

(图片来源于网络,如有侵权,请联系我们删除)

VRF(Verifiable Random Functions)

要解决的问题

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

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

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

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

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

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

相比非对称加密

640?wx_fmt=gif相同点:非对称加密也可通过不同的输入消息产生不同的签名值,并且可以被验证。

640?wx_fmt=gif不同点:

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

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

模型和定义

640?wx_fmt=gifG:生成一对公私钥:

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

640?wx_fmt=gif?F:生成随机数和证明:

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

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

640?wx_fmt=gifV:接收方验证随机数:

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

算法实现

640?wx_fmt=gif?algorand

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

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

性能:

o?通过私钥生成证明

640?wx_fmt=png

o?通过公钥验证

640?wx_fmt=png

640?wx_fmt=gifgoogle

golang:

https://github.com/google/keytransparency/tree/master/core/crypto/vrf640?wx_fmt=gif其它

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

区块链应用

应用场景

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

通常的选取方式:

640?wx_fmt=gifChainSQL联盟链新共识:(区块高度?+ view)?% 验证节点个数。

640?wx_fmt=gifZilliqa:前区块(FB或DSB)的hash % 节点 (分片节点或委员会节点) 个数。

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

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

Algorand对VRF的应用(抽签)

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

1.?设置初始种子为创世信息的哈希(种子就是VRF的输入)2.?每个账户生成一对vrf公私钥3.?节点生成区块后,账户为区块提案

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

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

4.?投票提案

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

5.?验证投票,并抽签

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

6.?确定唯一投票

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

VDF(Verifiable Delay Functions)

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

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

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

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

模型和定义

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

640?wx_fmt=gifSetup(λ, t) -> pp = (ek, vk)

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

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

640?wx_fmt=gif?Eval(ek, x) -> (y, π)

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

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

串行运算时间满足t。

640?wx_fmt=gifVerify(vk, x, y, π) -> (accept, reject)

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

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

640?wx_fmt=png

流程图

应用领域

产生随机数

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

RANDAO

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

640?wx_fmt=gif第一阶段:收集有效sha3(s)

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

640?wx_fmt=gif第二阶段:收集有效s

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

640?wx_fmt=gif第三阶段:计算随机数、退还押金及奖金

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的其他参与者。订阅随机数支付的费用予以退还。

安全风险:

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

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

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

RANDAO与VDF结合

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

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

具体方案:

640?wx_fmt=gif出块间隔为6s。

640?wx_fmt=gif一个epoch为6.4分钟,也就是一个epoch中产生64个区块。

640?wx_fmt=gif每一个epoch通过RANDAO合约产生一个随机数作为VDF的输入,并启动一个VDF。

640?wx_fmt=gifVDF的延迟时间t设置为102.4分钟,也就是每一个最终随机数的生成都需要经过102.4分钟。

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

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

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

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

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

复制证明(Proof of Replication)

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

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

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

具体方案:

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

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

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

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

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

与POW对比

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

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

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

—-

编译者/作者:众享比特

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

LOADING...
LOADING...