可验证随机函数VRF

VRF是一种将输入映射到可验证的伪随机输出的加密方案。

VRF 的目的就是要生成一个真正随机、无法被预测而且还可以被验证的随机数。

在区块链中，被用于随机选择出块节点和验证节点，并提供验证节点的功能。

定义

可验证随机函数可以看作是一个随机预言机（Random Oracle），可以通过任意的一个输入，获得一个随机数输出。可验证随机函数比随机预言机多了一个非交互的零知识证明，可以用来证明这个随机数的确是某个人生成的。

随机预言机有两个特征：

对于不同的 Input，Output 的值是随机的，并且均匀分布在值域范围内。
对于相同的 Input，它得到的 Output 一定是相同的。

首先讲一个简单的哈希函数，比如结合了secret的哈希函数：

1	result = SHA256(secret,info)

上面的函数，要想得到结果result，需要secret和info；要验证result，也需要secret和info，也就是说需要知道secret才能验证info和result是否对应匹配。

有没有可能在不出示secret的情况下，验证result和info是否对应匹配。这就是可验证随机函数VRF可以做到的。

1	result = VRF_HASH(SK,info)

其中SK表示secret key，是私钥，不对外公开的，自己保存即可。与SK配对的PK表示public key，是公钥，需要公开给验证者的。有了上面这些基本的元素，具体的VRF操作流程就非常简单清晰了：

1.证明者生成一对秘钥，PK和SK；
2.证明者计算result = VRF_HASH(SK,info)；
3.证明者计算proof = VRF_Proof(SK,info);
4.证明者把result和proof递交给验证者;
5.验证者计算result = VRF_P2H(proof)是否成立，若成立，继续，否则中止；
6.证明者把PK，info递交给验证者；
7.验证者计算True/False = VRF_Verify(PK,info,proof),True表示验证通过，False表示验证未通过。

验证通过，指proof是否是通过info生成的，通过proof是否可以计算出result，从而推导出info和result是对应匹配的。从上面可以看出，验证者并没有获得证明者的私钥SK，验证者同样可以推导出info和result是否对应匹配，这就是VRF的妙用。

对哈希函数的不断演化，可以简单用如下的路径来表示：

原始的哈希函数: info -> result

带密钥的哈希函数： info,secret -> result

公钥版本的VRF： info,SK -> proof,PK -> result

算法流程

可验证随机函数一共包含四个函数：

生成密钥，生成一个公钥私钥对；
生成随机数输出；
计算零知识证明；
验证随机数输出。

其大概流程如上，下面是基于椭圆曲线加密算法实现VRF的具体算法流程：

可验证随机函数的设计

更对实现的细节，参考：Goldberg S, Vcelak J, Papadopoulos D, et al. Verifiable random functions (VRFs)[J]. 2018.

基于GO中对该流程实现的demo

package main

import (
	"fmt"
	"github.com/r2ishiguro/vrf/go/vrf_ed25519"
	"golang.org/x/crypto/ed25519"
)

func main() {
	const message = "message"
	pk, sk, err := ed25519.GenerateKey(nil)
	if err != nil {
		fmt.Println("errors")
	}
	c := vrf_ed25519.ECVRF_hash_to_curve([]byte(message), pk)
	fmt.Println("Hash:")
	fmt.Println(c)
	pi, err := vrf_ed25519.ECVRF_prove(pk, sk, []byte(message))
	if err != nil {
		fmt.Println("errors")
	} else {
		fmt.Println()
		fmt.Println("Proof:")
		fmt.Println(pi)
	}
	res, err := vrf_ed25519.ECVRF_verify(pk, pi, []byte(message))
	if err != nil {
		fmt.Println("errors")
	} else {
		fmt.Println()
		fmt.Println("Result:")
		fmt.Println(res)
	}
}

在区块链中的应用

VRF在 Algorand 和 Dfinity 的共识机制中都被使用到。

举例说明

假设全网有 100 个节点，我想生成下一轮一个节点谁打包，我以某一轮的轮次作为输入，然后随机输出的值必须要是在 1-100 之间的自然数（因为网络中只有 100 个节点）。这就每一轮都选出了一个打包节点的人。

VRF 的方式是，让各个节点自己抽签，如果抽中了之后，大家可以很容易地验证这个结果确实是你生成的。具体过程有可能是这样的：假设现在是 round 10（第 10 轮），节点们可能会轮流抽签，以节点自己的私钥 + 一个全网都知道的随机数（比如是这轮的轮次 10）作为输入，生成了一个随机数（0-100）和零知识证明；设置一个条件：100 个节点轮流抽签，谁先抽出来的随机数大于 10，就是这一轮的打包者。假设 5 号节点抽到了 11，可是只有 5 号知道其他人不知道，因此他在广播这个随机的同时还需要广播一个零知识证明。通过零知识证明，全网只需要通过 5 号的公钥就可以验证，接受 5 号为这轮打包者。

总结

VRF其实和Pow的hash探索过程类似，都是为了随机安全的选出出块节点，Pow主要问题在于功耗和性能。而VRF利用本地随机抽签（类似pow挖矿，不过是生成随机数），大家可验证的方式（类似pow中验证hash）。

但是VRF自身容易受到女巫攻击，所以结合Pos或者设置用户注册准入门槛，可以比较完备的解决区块链中共识的问题。

实际应用

VRF 已经在 Cardano 、Dfinity 和 Algorand等项目中得到使用：

VBFT

VBFT 的每轮共识中：

根据 VRF 从共识网络中选择备选提案节点，各个备选节点将独立提出备选区块；
根据 VRF 从共识网络中选择多个验证节点，每个验证节点将从网络中收集备选的区块，进行验证，然后对最高优先级的备选区块进行投票；
根据 VRF 从共识网络中选择多个确认节点，对上述验证节点的投票结果进行统计验证，并确定出最终的共识结果。
所有节点都将接收确认节点的共识结果，并在一轮共识确认后开启新的共识。

Algorand 和 Dfinity

大体流程都是利用VRF选择打包者，选择验证者，排序选择区块。但是VRF算法的细节实现不同。

输入值由前一个随机数（最初的随机数却是协议给定的）和某种代表高度、轮次的变量进行组合
然后用私钥对之进行签名（或者是先签名再组合）
最后哈希一下得出最新的随机数

值得注意的两点：

签名算法应当具有唯一性，也就是用同一把私钥对同样的信息进行签名，只有一个合法签名可以通过验证
- 如果不存在这个性质，如：SM2。会存在反复尝试多次签名，以挑选最优随机数的可能。
避免在生成新随机数时将当前块的数据作为随机性来源之一，比如引用本块交易列表的 merkle root 值等
- 出块者可能会尝试打包不同的出块顺序、交易以达到更有利的随机数的可能。

当然Dfinity中除了使用到VRF进行节点选择，验证。还有用到BLS阈值签名算法，出块或验证需要在VRF选出的M个出块节点和验证节点中持有其中N个节点的签名才能通过。

参考：

https://blog.csdn.net/shangsongwww/article/details/88813116

https://www.jianshu.com/p/c3f239a6c858

Goldberg S, Vcelak J, Papadopoulos D, et al. Verifiable random functions (VRFs)[J]. 2018.

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