区块链中VRF的应用及原理解析

黄祺
Tarax Network 联合创始人 & CTO 资深全栈工程师,计算机科学硕士学位,主要研究方向为分布式系统、P2P 自组织网络,曾先后在中科院计算所智能科学组、索尼中国研究院、百度、今日头条从事分布式数据共享方面的技术研究。

演讲视频 https://www.bilibili.com/video/av27728568

今天给大家带来的这个分享叫做《区块链中VRF的应用及原理解析》,起因是来自我们团队在做的一条叫 Tarax Network 的公链。因为场景定位的缘故,我们想找到一种低功耗的方式来进行共识。那么 POW 肯定是没办法考虑的,很容就会想到 POS。继而考虑到,无论是 POW 或是 POS,都是想不被预测的随机找到一个节点进行区块打包,并让这个区块能被全网承认。 那么在随机选点这件事上,VRF基于可验证随机选点的抽签,是做的最直接的。

当然,POW 并不只是有随机选点打包的功能,还有一些博弈和人性上的考量,目前的 POS 方案中,也并不是随机选点完就OK了,替代了随机选点的方案,自然也会去从其他方面重新对博弈和人性上的问题进行设计。

不过我们先一个一个问题解决,抛开博弈的这块内容不谈,先研究研究VRF。 我们带着两个问题来看待这件事:

什么是可验证随机函数?

现在的一些链的方案是如何使用可验证随机函数的?

什么是可验证随机函数 可验证随机函数可以看作是一个随机预言机,意思是说我可以通过任意的一个输入,获得一个随机数输出:

对于不同的 Input,Output 的值是随机的,并且均匀分布在值域范围内。

对于相同的 Input,它得到的 Output 一定是相同的。

但是可验证随机函数比随机预言机多了一个非交互的零知识证明,可以用来该随机数输出的正确性,表明这个随机数的确是某个人生成的。

可验证随机函数它包含四个函数。

  1. 生成密钥,生成一个公钥私钥对,这个后面就不详细讲了

  2. 生成随机数输出

  3. 计算零知识证明

  4. 验证随机数输出

生成随机数和其证明的过程在本机执行,输入是私钥和一个值。输出就是随机数本数以及它的零知识证明。 其他节点收到该输入和证明之后,结合生成该随机数的节点的公钥,和即可对该随机数处进行验证。

那么通过这四个函数,以及他们的输出,我们如何来进行随机选点呢?

可验证随机函数抽签 最简单的方法,上面我们通过VRF生成了这个随机数value之后,可以通过设置一个全网公认阈值来判断是否被抽中,比如我们都认同了一个值100为阈值,假设某轮我随机到101那么,我就被允许进行下一步。 然而这种最简单的方案没有办法防止女巫攻击。所以现在大部分的VRF抽签方案都将基于权益来进行票数分配,然后进行抽签算法的设计。 我们来看下现在最普遍的一种方案,通过二项分布来进行抽签结果的计算。 首先我们已经通过私钥生成了value了,这个value实际上可以看作是大的正整数,假设是256bit的,那么它的取值范围应该处于0到2的256次方之间。相应的它与2的256次方相除,可以得到一个0到1之间的值。 将这个值放到二项分布的累积分布中进行比对,可以得到相应的值(详见PPT)。 如果这个值大于零,就相当于抽到了可以进行下一步的签。 将这个值和之前VRF生成的和一起,广播给其他人,其他任何收到的用户结合广播者的公钥以及全网都知道的值,则可以验证以下两个条件是否成立:

利用验证是否正确

利用通过二项分布函数得到j'是否与j相等

假设两个条件均成立,那么就证明这个抽签结果是正确的,是可信的。 到此为止,从抽签生成到验证的过程就完成了。

通过上面这个过程的描述,不难看出基于VRF的抽签机制有几个优点:

  1. 首先它的抽签过程不需要与其他通信,直接在本机就能够的到这个抽签结果,而且这个x输入是大家公认的,针对同一个x的输出value是固定的,因此无法通过多次尝试来改变抽签结果

  2. 某个节点收到其他节点的抽签信息之后,可以用附带的证明,来证明这个随机数的正确性,保证它的确是由私钥的拥有者计算出来的。因此这个抽签结果是无法被伪造的。

  3. VRF主要用来的得出一个伪随机数,抽签的部分主要是由一个二项分布函数负责,而通过构建二项分布的参数,我们可以很方便的控制需要被得出的中签权益的个数,适配不同的需要抽签的场景。

说完基于VRF的抽签算法,我们再来看看这个抽签算法给区块链共识带来了些什么。

VRF抽签给共识带来的变化

这个我们从一个具体的例子展开讲。 Ouroboros 是 Cardano 的共识算法,它很有意思,一开始它提出的是一种共识的流程方案,不过这种方案是可证实安全的,而并没有涉及到每一部分的实现。而之后它会在论文版本的更新中,以及具体的实现方案中,逐渐加上实现的细节。 到目前为止,他的理论版本已经迭代了三个版本了,分别是 Ouroboros、Praos和Genesis。而在第二个版本Praos中,引入了VRF的部分作为区块提出节点的抽取。

首先大概讲一下Ouroboros 的共识流程: 而在每个 epoch 开始之前,上一轮 epoch 中,会确定一个 random seed,以及若干 Stake Holders,作为这一轮 epoch 的参与节点,根据 random seed,会得出这一轮的所有 slot 的 slot leader,由它们进行依次打包。 上一轮中,Random Seed 的交由一个交互式的 PVSS 方案产生。举一个简单的例子来说明一下就类似于,两个不能通过实时沟通进行猜拳的人,如果一个人收到另一个人的出拳结果,完全可以发出一个必胜的出拳来获胜,这样就不公平了,那么现在这样,我们先每个人用一张牌代替自己的出拳,然后将它盖上,大家都不知道出的是什么,但是都能保证大家都已经选好了这个出拳了。之后在依次公布结果。 产生了这个 Random Seed 之后,然后用 Follow the Satoshi 算法,得到每个 slot 的 slot leader,可以将 Follow the Satoshi 看作是一个随机预言机,可以利用 Random Seed 以及每个 StakeHolder 的权益值,给每个 slot 随机分配一个 stake holder 作为slot leader,而这个结果是在这一次 epoch 开始之前,每个节点都知道的,它们可以自己算出来。

这样就会有一个问题:我可以提前知道某个区块的打包节点,那么攻击者就可以提前攻击这个打包节点,来达到它攻击的目的。 之后在Praos中,也就是Ouroboros的第二个版本中,它引入VRF来代替了这种Follow the Satoshi的方案,刚刚我们了解过VRF抽签的过程以及特性之后,可以知道,引入了VRF之后,每一轮的slot的slot leader只有这个节点自己知道,他发布之后,其他节点可以验证他是不是真有这个角色,这样就可以避免上面所说的攻击。 但是这也带来了新问题,上面说到Follow the Satoshi能够随机的给每个slot都分配上slot leader,但是VRF这种基于概率的抽签方式,在这点上就没有办法做到一定。又可能出现某一轮slot没有抽出slot leader或者抽出了多个slot leader的情况。因此Praos中,新增了额外的方案来处理这种情况。 对比这两种方案,VRF在引入了slot leader不可预知的安全性升级之外,也引入了两种异常情况。但是这两种异常情况是否是VRF引入的新问题呢?我们来思考一下。 实际上,这个问题不论是Follow the Satoshi还是VRF的方案,都必须去解决,因为就算我能保证每个slot都有slot leader,我也没办法保证slot leader是否能在这个slot里打出包来。而验证分叉的方案,又是只要是链就一定会考虑的问题,假设某个slot leader被攻击,而在自己的slot里大量重复打包,也会造成分叉问题。

所以在没有新问题引人的情况下,增加了打包节点的匿名性,实际上是对系统有了一个安全性上的升级。

然后我们再来看看其他的有使用或者极大的依赖于VRF的一些共识算法。 思路大体上是用可验证随机函数抽签,来降低参与共识节点或者某种角色的数量的数量。

  1. Algorand先选打包者,选完打包者选委员会,委员会用BA*进行选区块。

  2. Dfinity中,交保证金提高门槛,并降低参与节点的数量,然后选打包者,选完打包者选公证人,对区块权重进行排序,选出区块。

  3. VBFT,本体的共识算法中,首先选打包者,打包之后,选投票者对这些包进行投票,之后选确认者,对这些票数进行统计,选出区块。

除了共识算法,其实在其他的方面也有一些项目使用了VRF,比如IOST的高效分布式分配片中,就使用了VRF来进行领头节点的选举。不过于上面所说的离线抽签方案不同,这里的选举通过VRF得到随机数之后,会将结果进行广播,然后其他节点会进行统计,得到随机数值最小的作为分片领头节点。是一种交互式的选举方式。

几个问题 分享完VRF以及它现在的一些应用之后,有几个问题需要我们共同思考一下:

1.抽签有没有必要用VRF?

与随机预言机相比怎样?

与过程与它相似的非对称加密方案相比怎样?

2.是否有其他的应用场景?

是否可以参考现在VRF在工业界的使用案例?

是否在智能合约中有更广泛的使用?

谢谢大家。


参考文献

  1. Verifiable Random Functions [1999]

  2. Ouroboros: A provably secure proof-of-stake blockchain protocol [2017] Algorand:

  3. Scaling Byzantine Agreements for Cryptocurrencies [2017]

  4. Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of- stake blockchain [2018]

  5. https://github.com/iost-official/Documents/blob/master/ Technical_White_Paper/EN/Tech_white_paper_EN.md

  6. https://tools.ietf.org/html/draft-irtf-cfrg-vrf-02

  7. https://github.com/Realiserad/fts-tree

  8. https://www.cs.bu.edu/~goldbe/projects/vrf

BFTF,可以理解成 Blockchain Funds-Technology Federation 或者 Byzantine Fault Tolerance Federation。

最初,高可用架构技术社区中对区块链感兴趣的技术人员组成了一个区块链学习小组,定时组织学习会,分享和探讨区块链技术。慢慢的小组规模扩大,有很多人想一起参与分享或者学习,但受限于场地原因,一直没有开放。经过一个多月的筹划,我们决定成立这个技术社区联盟 BFTF,定期组织区块链技术的 meetup,一起探讨学习区块链技术,未来会进一步发起或者支持一些社区项目建设。

BFTF 之所以称为联盟,我们是想实践一个去中心化的社区组织,可以联合更多的区块链开发者,媒体,以及基金,组织中的成员可以自发发起活动以及提案,寻求技术以及资本的支持。

BFTF 中的 FT,表示希望这个组织可以提供一个平台,桥接优良的 Funds 和 Technology,助力行业发展。

BFTF 的一个常规活动是定期的 BFTF 知享会(BFTF meetup),初步计划每个月举行一次,每期一个方向,大约包含四个主题演讲,每个主题五十分钟左右,若干个闪电演讲,每个十分钟左右。演讲都主要围绕当期方向,以技术干活为主。

-END-