区块链中的数学 - 随机可验证函数(VRF)

本文主要介绍了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

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-10-02 19:57
  • 阅读 ( 289 )
  • 学分 ( 42 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

53 篇文章, 954 学分