• 一篇文章搞懂VRF

• 一种错误的实现
  • 椭圆曲线签名算法原理
    • 那么椭圆曲线的签名可否当做VRF呢?
  • 比特币和以太坊中的数字签名可以做VRF么?
• 一种正确的实现
  • 公式推导
    • H1:把任意信息映射到曲线上的点
    • H2: 映射任意信息为(1,q)
    • 计算随机数
    • 随机数的proof
    • 如何验证
    • 生成$g^r$ , $h^r$
• 在椭圆曲线上的实现
  • 接口原型
  • 使用方法
• 推荐实现
  • 1. 谷歌的keytransparency项目
  • 2. Spectrum上使用的VRF
  • 3. witnet上的VRF

什么是VRF,VRF全称是verifiable random function ,也就是可验证随机数. 他有两个特性, 他产生的是随机数,第二还是可验证的.

我直接引用维基百科上的VRF,就是说针对一个输入x,一个私钥SK的拥有者可以计算$y=FSK(x)$和证明$PSK(x)$. 依据证明(proof)和SK对应的公钥PK($PK=g^{SK}$),任何人都可以验证y是被正确计算的,但是不能知道SK是什么.

原文中提到了使用双线性映射来做这个事情,当然VRF可以有很多种不同的实现,只要满足上面提出的条件即可.一个是随机数,另一个是可验证.

简单解释一下:

1. 验证人只知道x,在SK持有人没有广播之前不知道随机数是什么
2. SK持有人无法伪造随机数,一旦x确定,随机数也确定了. 这就是所谓的随机数(除了SK持有人之外,其他任何人事先不知道) 可验证(知道PK的任何人都知道SK生成的随机数是否合规)

一种错误的实现 ​

首先我们常用的数字签名可否用作VRF呢?

椭圆曲线签名算法原理 ​

假设私钥为k,那么公钥$K=kG$,其中G为G点(就是椭圆曲线的公共参数,可以忽略). 签名的过程如下:

1. 选择随机数r,计算$P=rG$,P实际上就是曲线上的一个点
2. 计算$s=\frac {m+kx} r$,其中m就是公共信息,比如是一个以太坊交易的Hash值. 这里的x是P的x坐标.
3. 将消息m和签名{rG,s}发送给接收方 接收方在事先知道公钥K的情况下,就很容易验证签名和m是否是对应关系. 验证签名的过程: 计算$\frac {mG} s + \frac {xK} s $,然后与rG比较,如果相等说明是对应关系.其中x是rG这个点的x坐标

为什么这样可以呢,来看一下简单的推导过程:

$\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$

注意: $s=\frac {m+kx} r$

那么椭圆曲线的签名可否当做VRF呢? ​

首先第一点,固定m以后,如果其他人不知道签名人对应的私钥是什么,那么他们确实不知道产生的随机数会是什么样子. 同时验证人如果知道私钥对应的公钥,也很容易确定私钥是否是对m签的名. 所以看起来签名是可以用作VRF的. 但是问题出在签名过程中的随机数r,因为r是随机的,所以每次签名的结果{rG,s}完全是随机的,那么这就给随机数生成方选择随机数的机会. 也就是说一开始定义的$y=FSK(x)$,这里的x到y的映射是不固定的,这不符合函数的定义.

比特币和以太坊中的数字签名可以做VRF么? ​

这个问题答案肯定是和前一个一样的,不可以. 但是为什么还有此一问呢,那是因为很多人观察到的签名和我刚刚讲的并不一致. 什么意思呢? 就是对于相同的内容,如果私钥相同,那么无论你尝试签名多少次,其结果都是一样的,和我们刚刚讲的原理似乎并不一致. 感兴趣的小伙伴可以自行编码验证. 这又是为什么呢? 那是因为RFC6979在作怪,签名结果之所以每次都不一样,就是因为随机数r,如果r固定下来,那么自然签名就不会变了.这实际上就是RFC6979在做的事,他给出了一个固定计算r的方法. 至于为什么这么复杂的计算r,为什么不固定采用一个数字比如3,这主要是考虑到可能泄露私钥的安全性问题. 这些看起来没什么问题,关键是验证者无法验证私钥拥有者有没有按照RFC6979的规则来生成签名,这就导致了私钥拥有者可以选择随机数

一种正确的实现 ​

前文给出了一个错误的思路,关键就在于他给出的随机数是受私钥持有者控制的,如果能把这个因素去掉,是否就可以行了呢?

公式推导 ​

H1:把任意信息映射到曲线上的点 ​

思路也很简单,将Hash(m)(注意是256位hash)作为曲线上的X,然后带入上述椭圆曲线公式,求出相应的Y即可.

H2: 映射任意信息为(1,q) ​

这个也很简答,就是Hash(...) mod q即可.

计算随机数 ​

这里的v是完全确定的,就是$h^k$,满足了函数的确定性,但是怎么可验证呢?

随机数的proof ​

随机生成一个r,然后计算:

然后把(v,s,t)一起打包发给验证方,

如何验证 ​

上述信息中已知的有:

1. g: 曲线公共参数
2. h: H1(m) ,因为m已知,Hash方法也是已知
3. G: 公钥
4. v: 随机数,验证方明文收到
5. t: 验证法明文收到
6. s: 验证法明文收到

生成$g^r$ , $h^r$ ​

$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")
	}

}

推荐实现 ​

1. 谷歌的keytransparency项目 ​

google VRF 注意这里面使用的曲线是P256,不是比特币和以太坊使用的S256,实现语言是go语言

2. Spectrum上使用的VRF ​

Spectrum VRF 这个项目是在参考项目1基础之上改进得来,他使用的是S256这根曲线,实现语言也是go语言,好处是直接可以在项目中集成.

3. witnet上的VRF ​

witnet VRF 这个项目使用rust开发,同时支持P256,S256两根曲线.因为用rust开发,可以方便与其他语言集成,并且性能很高.