可验证随机函数(Verifiable Random Function)用于生成一个可以进行验证的随机数，生成随机数的生成者通过自己的掌握的私钥来生成一个随机数和一个验证参数(proof)，接收到随机数的验证者可以通过该随机数和验证参数来对随机数进行验证。可验证随机函数的三个特性：可验证性、唯一性和随机性。

这样一种存在公私钥对用于进行验证的函数，需要通过非对称加密来实现，下面以RSA和ECC为例。

该函数传入消息，经过生成者处理后输出一个随机数和验证参数

RSA-VRF

基于RSA算法的VRF感觉和RSA算法的签名过程一样，只要生成的结果随机且可确认即可

如RSA算法一样，首先选取两个大素数$p$和$q$，$n=p \times q$，$n$作为进行运算的整数群$Z_n^*$的阶，生成元为$g$

将消息通过编码的方式映射到群上，如果消息编码后过大需要考虑其他的编码方式，编码映射后的消息为$m$

在VRF其实并不需要解密得到结果，所以对消息进行编码也可以通过哈希函数缩短输入，保证可以进行验证即可

生成者选取$e \in (1, \phi(n))$以及生成私钥$d = e^{-1} mod\ n$

计算$c=m^d\ mod \ n$即可得到随机数，验证方可以使用生成者的公钥进行验证，这里其实就是一个签名的过程

ECC-VRF

基于椭圆加密算法的VRF的流程较为复杂，而且和椭圆加密的方法也有一定的差别

设选定的椭圆曲线的基点为$O$,阶为$n$，生成者选择$k \in [1,\ n-1]$作为私钥，计算公钥$Y=kO$

将消息映射到椭圆曲线上的一个点$M$，选取随机数$r\in[1, \ n-1]$，计算$rM， rO$

这里映射的方式也是使用时自定义的映射方式，比如直接将消息编码后计算得到在曲线上点，在不需要解密结果的时候也可以直接进行哈希

我在自己的代码实现中直接哈希得到一个整数$x$，然后计算$y=xO$，得到曲线上的点，这里是拿ecdsa的包来进行改造

https://github.com/Decision2016/python-ecdsa/blob/master/src/ecdsa/keys.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
number = _truncate_and_convert_digest(
    digest,
    self.curve,
    allow_truncate
)
hashfunc = hashfunc or self.default_hashfunc

order = self.curve.order
generator = self.curve.generator

message_point: ecdsa.ellipticcurve.PointJacobi
rH: ecdsa.ellipticcurve.PointJacobi
rO: ecdsa.ellipticcurve.PointJacobi
message_point = generator * number