本期Annchain深度系列将关注可验证随机函数（VFR）在区块链中的运用。Annchain.OG在DAG（Directed Acyclic Graph, 有向无环图）的账本构型和BFT（拜占庭容错）的确认机制组合而成的混合共识中，引入了VFR，以公平、随机选出一部分节点作为共识节点参与共识。
作者介绍
Shor，Annchain核心开发成员，毕业于中科大。负责Annchain高性能p2p网络、通信与编码、基于DAG的高效交易同步、交易执行逻辑、wasm虚拟机智能合约平台、rpc等模块的研发以及系统优化。
VFR 简介
可验证随机函数（Verifiable Random Function） 简称VRF，由Micali、Rabin 和Vadhan提出。VRF作为伪随机函数，给定一个输入X,以及一个私钥Sk, 可以算出一个随机输出Y=F(Sk,X) 以及证明P。任何人使用该私钥对应的公钥Pk, 以及输入X, 证明P, 可以验证随机输出Y确实通过私钥Sk和输入X计算出来的， 而且无法推导出私钥Sk。
VRF算法
VRF算法由秘钥生成函数Key_Gen、VRF计算函数VRF_Hash、VRF证明函数VRF_Proof与VRF验证函数VRF_Verify等密码学函数组成。VRF是公钥版本的密码学哈希函数。
秘钥生成函数：
Sk,Pk = Key_Gen(r), 对任意的随机输入、产生VRF私钥Sk、和私钥Sk对应的公钥Pk。 在基于RSA的VRF中生成一对RSA公私钥对，在基于椭圆曲线密码学的VRF(ECVRF)中生成一对椭圆曲线公私钥对。
VRF计算函数：
Y = VRF_Hash(Sk,X) , 对输入消息X， 使用VRF 私钥Sk计算VRF哈希输出Y。由于理想的哈希函数值域是离散的，给定不同的输入、哈希函数的输出随机分布在值域区间内，VRF计算过程中使用哈希方法，计算出来的值是随机的。
VRF证明的计算：
P = VRF_Prove(Sk, X),对输入消息X，以及私钥Sk, 计算VRF证明。
由vrf证明推导出vrf输出：Y = VRF_Proof_To_Hash(P) 由VRF证明直接算出VRF输出Y。
证明者计算完成之后，需要将输入数据X、VRF输出Y、VRF公钥Pk、VRF证明P发送给验证者。
VRF验证：
True/False = VRF_Verify(Pk,X,Y,P)，验证者输入验证的VRF公钥Pk, 消息X,以及VRF输出的随机值Y和证明P进行验证，输出为False/True。 如果证明P是根据X产生的、且由P可以推导出Y,则验证通过输出为True, 否则验证失败、输出为FALSE。
目前VRF的开源实现主要有基于RAS的VRF RSA_VRF与基于椭圆曲线密码学的VRF ECVRF等两种。
VRF 特性
VRF具有唯一性、抗碰撞性与随机性等特性。
唯一性：对相同私钥Sk与相同的输入X,输出Y是唯一的，具有不可抵赖性。
随机性： 输出Y是随机的，对于不知道证明P的旁观者来说是不可预测的、随机的。
抗碰撞性：私钥Sk由证明方秘密保存，VRF可以理解为带公钥版本的哈希函数，基于哈希函数的抗碰撞性、无法根据输入X与输出Y推导出私钥Sk。
VRF在区块链中的应用
VRF在区块链中用于加密抽签和选举出块节点。
在区块链中，大部分共识算法需要选择一个或者多个节点参与共识打包区块。在POW中拼算力，谁算力强谁大概率有记账权；在POS、DPOS中根据持有资产情况等因素选择出块节点。传统的POW、POS、DPOS、BFT等共识算法不能保证出块节点的完全随机性。
引入了VRF之后，可以公平、随机选择出一个或者多个点作为共识节点参与共识。一般通过VRF选择共识节点过程如下：
区块链网络中每个节点使用自己的私钥Sk、将网络中共有的一个数据X（前一个随机数、代表高度、轮次等变量进行组合）作为输入， 算出VRF输出Y与证明P， 由于Y 是随机的、不可预测的，可以根据Y是否满足一定的条件来选择出块节点。比如VRF输出小于某个阈值、则该节点被选择为出块节点。
目前在共识算法中使用VRF的有Algorand、Dfinity、Ontology的VBFT等共识算法。
在ALgorand共识算法中，通过VRF、结合账户的余额比例随机选择出块节点、再通过BA*（一种拜占庭一致性协议）共识算法进行共识出块。
在Dfinity共识中，节点需要交一定数量的stake作为押金，再通过VRF选择出块节点再选公证人进行出块。
在VBFT共识算法中， 通过VRF选择一轮共识的备选出块提案节点，区块验证节点与区块确认节点、然后又选出的节点集完成共识。VBFT是对BFT算法在随机性的一个改进。
参考文献
1. Micali, Silvio; Rabin, Michael O.; Vadhan, Salil P. (1999). “Verifiable random functions”. Proceedings of the 40th IEEE Symposium on Foundations of Computer Science. pp. 120–130.
2. https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/?include_text=1
