什么是VRF,VRF全称是verifiable random function ,也就是可验证随机数. 他有两个特性, 他产生的是随机数,第二还是可验证的.
我直接引用维基百科上的VRF,就是说针对一个输入x,一个私钥SK的拥有者可以计算$y=FSK(x)$和证明$PSK(x)$. 依据证明(proof)和SK对应的公钥PK($PK=g^{SK}$),任何人都可以验证y是被正确计算的,但是不能知道SK是什么.
原文中提到了使用双线性映射来做这个事情,当然VRF可以有很多种不同的实现,只要满足上面提出的条件即可.一个是随机数,另一个是可验证.
简单解释一下:
首先我们常用的数字签名可否用作VRF呢?
假设私钥为k,那么公钥$K=kG$,其中G为G点(就是椭圆曲线的公共参数,可以忽略). 签名的过程如下:
为什么这样可以呢,来看一下简单的推导过程:
\(
\begin{eqnarray}
& \frac {mG} s + \frac {xK} s \\
=& \frac {mG} s + \frac {x(kG)} s \\
=& \frac {(m+xk)G} s \\
=& \frac {r(m+xk)G} {m+kx} \\
=& rG
\end{eqnarray}
\)
注意: $s=\frac {m+kx} r$
首先第一点,固定m以后,如果其他人不知道签名人对应的私钥是什么,那么他们确实不知道产生的随机数会是什么样子. 同时验证人如果知道私钥对应的公钥,也很容易确定私钥是否是对m签的名. 所以看起来签名是可以用作VRF的. 但是问题出在签名过程中的随机数r,因为r是随机的,所以每次签名的结果{rG,s}完全是随机的,那么这就给随机数生成方选择随机数的机会. 也就是说一开始定义的$y=FSK(x)$,这里的x到y的映射是不固定的,这不符合函数的定义.
这个问题答案肯定是和前一个一样的,不可以. 但是为什么还有此一问呢,那是因为很多人观察到的签名和我刚刚讲的并不一致. 什么意思呢? 就是对于相同的内容,如果私钥相同,那么无论你尝试签名多少次,其结果都是一样的,和我们刚刚讲的原理似乎并不一致. 感兴趣的小伙伴可以自行编码验证. 这又是为什么呢? 那是因为RFC6979在作怪,签名结果之所以每次都不一样,就是因为随机数r,如果r固定下来,那么自然签名就不会变了.这实际上就是RFC6979在做的事,他给出了一个固定计算r的方法. 至于为什么这么复杂的计算r,为什么不固定采用一个数字比如3,这主要是考虑到可能泄露私钥的安全性问题. 这些看起来没什么问题,关键是验证者无法验证私钥拥有者有没有按照RFC6979的规则来生成签名,这就导致了私钥拥有者可以选择随机数
前文给出了一个错误的思路,关键就在于他给出的随机数是受私钥持有者控制的,如果能把这个因素去掉,是否就可以行了呢?
思路也很简单,将Hash(m)(注意是256位hash)作为曲线上的X,然后带入上述椭圆曲线公式,求出相应的Y即可.
这个也很简答,就是Hash(...) mod q即可.
\( h=H_1(m) \\ v=VRF_k(m)=h^k \) 这里的v是完全确定的,就是$h^k$,满足了函数的确定性,但是怎么可验证呢?
随机生成一个r,然后计算:
\[ s=H_2(g,h,G,v,g^r,h^r) \\ t=r-sk (mod p) \]
然后把(v,s,t)一起打包发给验证方,
上述信息中已知的有:
\( g^r =g^{t+ks} =g^t \cdot g^{ks} =g^t \cdot {g^k}^s =g^t \cdot G^s \) \( h^r =h^{t+ks} =h^t \cdot h^{ks} =h^t \cdot {h^k}^s =h^t \cdot v^s \)
虽然验证人不知道k,也不知道r,但是知道h,g,G,v,s,t所以他可以计算出$s2=H_2(g , h ,G , v , g^t \cdot G^s , h^t \cdot v^s)$ . 然后验证s2是否和s相等,如果相等,那就是k持有人按照规则计算出的随机数
这里专门说的是比特币和以太坊上采用椭圆曲线S256,这根曲线.
// A VRF is a pseudorandom function f_k from a secret key k, such that that
// knowledge of k not only enables one to evaluate f_k at for any message m,
// but also to provide an NP-proof that the value f_k(m) is indeed correct
// without compromising the unpredictability of f_k for any m' != m.
// http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=814584
// PrivateKey supports evaluating the VRF function.
type PrivateKey interface {
// Evaluate returns the output of H(f_k(m)) and its proof.
Evaluate(m []byte) (index [32]byte, proof []byte)
// Public returns the corresponding public key.
Public() crypto.PublicKey
}
// PublicKey supports verifying output from the VRF function.
type PublicKey interface {
// ProofToHash verifies the NP-proof supplied by Proof and outputs Index.
ProofToHash(m, proof []byte) (index [32]byte, err error)
}
func TestVRFForS256(t *testing.T) {
//私钥持有人
key, err := crypto.GenerateKey()
if err != nil {
t.Error(err)
return
}
k, err := NewVRFSigner(key)
if err != nil {
t.Error(err)
return
}
//验证人,只知道公钥
pk, err := NewVRFVerifier(&key.PublicKey)
if err != nil {
t.Error(err)
return
}
msg := []byte("data1")
index, proof := k.Evaluate(msg)
index2, err := pk.ProofToHash(msg, proof)
if err != nil {
t.Error(err)
}
if index2 != index {
t.Error("index not equal")
}
}
google VRF 注意这里面使用的曲线是P256,不是比特币和以太坊使用的S256,实现语言是go语言
Spectrum VRF 这个项目是在参考项目1基础之上改进得来,他使用的是S256这根曲线,实现语言也是go语言,好处是直接可以在项目中集成.
witnet VRF 这个项目使用rust开发,同时支持P256,S256两根曲线.因为用rust开发,可以方便与其他语言集成,并且性能很高.