区块链中的数学 - 随机可验证函数（VRF）

写在前面

上一节讲了uniswap 中交易的几种情况算法流程,本文开始讲随机可验证函数（VRF）的内容。

VRF基本概念

可验证随机函数（VRF）是公钥密码学与哈希函数结合的另外一种应用方式。 只有私钥的持有者才能计算哈希。 但是任何拥有公钥的人都可以验证哈希的正确性。VRF有助于防止枚举基于哈希的数据结构攻击。

区块链中，大部分的共识算法，无论是 POW、POS，或是由他们衍生出来的 DPOS，都需要选出一堆或者一个节点来参与共识或者打包区块，这个过程虽然会有持币情况、设备配置、信誉等各种因素影响，但必须是随机的、无法被预测的。这时候就可能会用到随机算法。

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

使用 VRF，达到的目的跟 POW 的过程有些类似，就是为了随机而又安全地抽取出块节点。

目前有两个体制，一个VRF使用RSA，另一个VRF使用椭圆曲线（EC）。

VRF算法框架

VRF包含了一个密钥生成算法，它可以生成一个公共VRF密钥PK和私有的VRF密钥SK。

图中，M代表原始输入消息，总体分为生成证明（generation）和验证（verify）两部分。

生成过程

P = VRF_proof(SK, M) 生成证明P， R = VRF_proof_to_hash(P) 将证明转化成hash值，有时简写成 R = VRF_P2H(P)

VRF_hash(SK, M) = VRF_proof_to_hash(VRF_proof(SK, M))

验证过程

VRF_verify(PK, M, P) 利用公钥对检验证明P是否是基于原始消息M产生的证明，如果是返回合法，否则非法。

VRF满足的安全属性

唯一性要求

唯一性是指，对于任何确定的VRF公钥和任何输入M，有一个唯一的的VRF输出P，可以证明有效的。即使是一个恶意的证明者知道VRF私钥SK，也产生不了更多的有效证明。

抗碰撞性

像其他任何密码学散列函数一样，VRF需要抗碰撞性， 即使对于知道VRF私钥SK的恶意证明者，Collison抵抗也必须成立。

更确切地说，“完全抗碰撞”表现在计算上，对手无法找到两个不同的VRF输入M1和M2具有相同的VRF散列P，即使对方知道VRF密钥SK。

稍微弱一点的抗碰撞性，称为“可信抗碰撞”，即在 PK和SK在一种安全可信的方式下生成。

随机性要求

伪随机性确保了当一个对手验证者看到一个VRF散列输出R，而没有相应的VRF证明P时，R与随机值无法区分,即看到的R就像随机值一样（也就是hash函数的随机性）。 更准确地说，假设公共和私有VRF密钥（PK，SK）是 以值得信赖的方式产生。伪随机性保证了对于任何计算力有限的恶意对手，VRF散列在任何恶意对手选择的“目标”VRF输入M看起来都无法区分。

即不能从不同的输入中提取到任何有效信息。

“选择性伪随机性”是一种相对较弱的安全属性，在许多应用中已经足够了。在这里，对手必须选择目标VRF输入M独立于公共VRF密钥PK，以及在它观察VRF输出R和证明输入M上的P之间的联系。

需要指出的是，VRF输出R对于证明人来说不是随机的，并且对于知道与VRF输入M与对应的有效VRF证明P的一方来说也不是随机的。 这很容易理解，因为对证明人而言，相同的输入只会得到相同的输出，这一点无“随机性”。

小结

本文主要介绍了VRF的概念和算法结构，随机性体现在外部看来，找不到输出证明结果与输入之间的关系，给人一种“随机性”输出的感觉。

下一节继续说基于RSA公钥体制的VRF算法具体内容。

欢迎关注公众号：blocksight