星球日报
搜索
手机客户端
iPhone · Android
微信公众号
微信公众号

iPhone · Android

微信公众号

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

2018-08-02

VRF 的基本原理是什么?如何利用 VRF 来实现共识?VRF 还可以用在哪些场景?

推广

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

黄祺

Tarax Network 联合创始人 & CTO

资深全栈工程师,计算机科学硕士学位,主要研究方向为分布式系统、P2P 自组织网络。

曾先后在中科院计算所智能科学组、索尼中国研究院、百度、今日头条从事分布式数据共享方面的技术研究。

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

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

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

         那么在随机选点这件事上,VRF基于可验证随机选点的抽签,是做的最直接的。

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

         不过我们先一个一个问题解决,抛开博弈的这块内容不谈,先研究研究VRF。

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

             我们带着两个问题来看待这件事:

             1、什么是可验证随机函数?

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


             什么是可验证随机函数

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

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

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

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

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


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

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

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

             2、生成随机数输出

             3、计算零知识证明

             4、验证随机数输出

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


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

          可验证随机函数抽签

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

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

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

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

          区块链中VRF的应用及原理解析最简单的方法,上面我们通过VRF生成了这个随机数value之后,可以通过设置一个全网公认阈值来判断是否被抽中,比如我们都认同了一个值100为阈值,假设某轮我随机到101那么,我就被允许进行下一步。

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

              1、利用验证是否正确

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

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

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

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

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

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

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

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

          VRF抽签给共识带来的变化

          这个我们从一个具体的例子展开讲。

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

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

          首先大概讲一下Ouroboros 的共识流程:

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

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

          而在每个 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 开始之前,每个节点都知道的,它们可以自己算出来。


          这样就会有一个问题:我可以提前知道某个区块的打包节点,那么攻击者就可以提前攻击这个打包节点,来达到它攻击的目的。

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

          区块链中VRF的应用及原理解析之后在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的一些共识算法。
          思路大体上是用可验证随机函数抽签,来降低参与共识节点或者某种角色的数量的数量。

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

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

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

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

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


          几个问题

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

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

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

           

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

        • 与随机预言机相比怎样?

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

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

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

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

        • 谢谢大家。

          开源了一个VRF的实现 

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

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

          目前已在Tarax共识算法的实现中使用

          参考文献—————————————————————————————————————————————————————

        • Verifiable Random Functions [1999]

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

        • Scaling Byzantine Agreements for Cryptocurrencies [2017]

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

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

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

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

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



        • 另附演讲视频地址:

          https://v.qq.com/x/page/e0735yg5l7t.html

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

          Blockchain Funds-Technology Federation 


          BFTF协办方:

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

          LWY Labs是一家服务于全球区块链创新项目的孵化器,旨在帮助优秀的项目加速落地及可持续发展。

        原创文章,作者:BFTF技术社区联盟。转载/内容合作/寻求报道请联系 report@odaily.com ;违规转载法律必究。

        推广

        参与讨论

        登录后参与讨论

        BFTF技术社区联盟

        特邀作者

        BFTF技术社区联盟

        定期组织区块链技术的 meetup,一起探讨学习区块链技术。

        总文章数: 10


        分享至

        微信扫一扫分享

        0
        前沿科技比特币区块链