黄祺
Tarax Network 联合创始人 CTO
资深全栈工程师，计算机科学硕士学位，主要研究方向为分布式系统、P2P 自组织网络。
曾先后在中科院计算所智能科学组、索尼中国研究院、百度、今日头条从事分布式数据共享方面的技术研究。
今天给大家带来的这个分享叫做《区块链中VRF的应用及原理解析》，起因是来自我们团队在做的一条叫 Tarax Network 的公链。因为场景定位的缘故，我们想找到一种低功耗的方式来进行共识。那么 POW 肯定是没办法考虑的，很容就会想到 POS。继而考虑到，无论是 POW 或是 POS，都是想不被预测的随机找到一个节点进行区块打包，并让这个区块能被全网承认。
那么在随机选点这件事上，VRF基于可验证随机选点的抽签，是做的最直接的。
当然，POW 并不只是有随机选点打包的功能，还有一些博弈和人性上的考量，目前的 POS 方案中，也并不是随机选点完就OK了，替代了随机选点的方案，自然也会去从其他方面重新对博弈和人性上的问题进行设计。
不过我们先一个一个问题解决，抛开博弈的这块内容不谈，先研究研究VRF。
我们带着两个问题来看待这件事：
1、什么是可验证随机函数？
2、现在的一些链的方案是如何使用可验证随机函数的？
什么是可验证随机函数
可验证随机函数可以看作是一个随机预言机，意思是说我可以通过任意的一个输入，获得一个随机数输出：
1、对于不同的 Input，Output 的值是随机的，并且均匀分布在值域范围内。
2、对于相同的 Input，它得到的 Output 一定是相同的。
但是可验证随机函数比随机预言机多了一个非交互的零知识证明，可以用来该随机数输出的正确性，表明这个随机数的确是某个人生成的。
可验证随机函数它包含四个函数。
1、生成密钥，生成一个公钥私钥对，这个后面就不详细讲了
2、生成随机数输出
3、计算零知识证明
4、验证随机数输出
生成随机数和其证明的过程在本机执行，输入是私钥和一个值。输出就是随机数本数以及它的零知识证明。
其他节点收到该输入和证明之后，结合生成该随机数的节点的公钥，和即可对该随机数处进行验证。
那么通过这四个函数，以及他们的输出，我们如何来进行随机选点呢？
可验证随机函数抽签
最简单的方法，上面我们通过VRF生成了这个随机数value之后，可以通过设置一个全网公认阈值来判断是否被抽中，比如我们都认同了一个值100为阈值，假设某轮我随机到101那么，我就被允许进行下一步。
然而这种最简单的方案没有办法防止女巫攻击。所以现在大部分的VRF抽签方案都将基于权益来进行票数分配，然后进行抽签算法的设计。
我们来看下现在最普遍的一种方案，通过二项分布来进行抽签结果的计算。
首先我们已经通过私钥生成了value了，这个value实际上可以看作是大的正整数，假设是256bit的，那么它的取值范围应该处于0到2的256次方之间。相应的它与2的256次方相除，可以得到一个0到1之间的值。
将这个值放到二项分布的累积分布中进行比对，可以得到相应的值（详见PPT）。
如果这个值大于零，就相当于抽到了可以进行下一步的签。
将这个值和之前VRF生成的和一起，广播给其他人，其他任何收到的用户结合广播者的公钥以及全网都知道的值，则可以验证以下两个条件是否成立：
1、利用验证是否正确
2、利用通过二项分布函数得到j是否与j相等
与随机预言机相比怎样？
与过程与它相似的非对称加密方案相比怎样？
是否可以参考现在VRF在工业界的使用案例？
是否在智能合约中有更广泛的使用？
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
假设两个条件均成立，那么就证明这个抽签结果是正确的，是可信的。
到此为止，从抽签生成到验证的过程就完成了。
通过上面这个过程的描述，不难看出基于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的实现
https://github.com/pinqy520/vrf.js
目前已在Tarax共识算法的实现中使用
参考文献—————————————————————————————————————————————————————
另附演讲视频地址：
https://v.qq.com/x/page/e0735yg5l7t.html
Blockchain Funds-Technology Federation
BFTF协办方:
LWY Labs是一家服务于全球区块链创新项目的孵化器，旨在帮助优秀的项目加速落地及可持续发展。
