李无知

VRF从algorand开始使用以来，时不时在其他区块链产品中出现，比如chainlink就使用了VRF算法来产生随机数，一起来揭开VRF的神秘面纱吧。

先说结论

• VRF是一种哈希算法
• VRF结合了公私钥，是能够验证签名者身份的哈希函数，和数字签名类似
• VRF和数字签名不同点在于VRF产生的是哈希值，而数字签名产生的是加密值
• VRF生成的是哈希，哈希具有随机性，人们利用这一点来产生随机数

VRF是一种哈希算法

VRF具体是什么，我们来看看官方的定义:

A Verifiable Random Function (VRF) [MRV99] is the public-key version
of a keyed cryptographic hash. Only the holder of the VRF secret key
can compute the hash, but anyone with the corresponding public key
can verify the correctness of the hash

可以看到，VRF本质是一个哈希算法，类似于md5，sha256。

也就是VRF算法的结果，是产生一个哈希值，记住这一点非常重要。

传统哈希函数与数字签名

但VRF和其他的哈希算法是不同的。我们先看传统的哈希函数如何工作的。

比如我们有个文件需要通过网络传输，我们一般会对该文件计算一个哈希，哈希的计算有很多种方式，比如我们选用sha256：

hash = sha256(file)

然后我们会把（file，hash）一起传递给接收者，接受者收到（file，hash）之后，会重新计算一下file的哈希结果，是否等于我们传递给接收者的哈希，这样做的目的是为了保证文件在传输过程中数据没有被丢失或者篡改：

sha256(file) == hash

除了验证文件是否被篡改，我们还会验证发送者的身份，此时人们往往利用数字签名+哈希算法的方式。

比如小红需要通过发送文件给小明，则加上数字签名后，整体流程为：

1. 小红计算文件哈希: hash = sha256(file)
2. 小红对哈希加密，产生签名： signature = encrypt(hash, SK）。签名的其实就是加密encrypt，加密需要私钥SK
3. 小红把（file, signature, PK)发送给小明。PK是公钥PK
4. 小明首先对签名解密，得出一个哈希值： hash = decrypt(signature, PK)
5. 小明再次计算hash是否等于sha256(file)。如果相等，说明两个问题：
   • 文件未被篡。因为hash==sha256(file)
   • 发送者来自于小红。因为hash来自于decrypt(signature, PK)，只有SK和PK匹配，才可能得出正确的hash

数字签名使用非常广泛，其本质是先生成hash，再对hash加密，最终的结果是一个定长的加密数据。

VRF算法

数字签名需要先生成哈希，然后再对哈希加密，然后再验证，比较麻烦。

那么有没有一种算法：发送者直接生成一个hash值。验证者就能根据该hash进行身份验证呢？即省去了数字签名中的加解密步骤。

假设我们把该算法叫做f，还是小红发送文件给小明的场景，流程大致如下：

1. 小红利用私钥计算文件哈希：hash = f(SK, file)
2. 小红把(hash, PK, file)发送给小明
3. 小明验证hash，PK的合法性：verify(hash, PK, file) 。如果verify成功，则说明hash正确，公私钥也正确，达到数字签名的小红

这种假设的算法f是存在的，就是我们今天的主角VRF了。

没错，VRF是一种哈希算法，而不是加密算法，根据输入，产生一个哈希值。就可以验证发送者的身份。但算法本身，实际上还是利用了SK/PK。

我们看一下VRF算法的官方介绍，其中涉及的名词如下：

• SK， PK。公私钥
• alpha。用户的输入，比如前面例子中的file
• beta。VRF生成的哈希值
• pi。VRF proof，被verifier使用，用于验证beta的合法性
• Prover。拥有SK私钥，生成beta的角色
• Verifier。拥有PK公钥，验证beta合法性的橘色

VRF涉及的函数如下：

1. beta = VRF_hash(SK, alpha)。把输入生成哈希值
2. pi = VRF_prove(SK, alpha)。生成一个证明：pi，pi的作用是为了验证beta的合法性
3. beta = VRF_proof_to_hash(pi)。可以直接从pi生成beta。这个函数有几个作用，比如某些场景，prover只提供了pi，verfier依然可以计算出beta。又比如prover提供了pi和beta，那么可以通过这个公式验证二者是否相等，确保数据的正确性
4. VRF_verify(PK, alpha, pi)。verifier根据alpha, pi和PK，验证beta的合法性

VRF对应的操作流程为：

1. Prover计算beta = VRF_HASH(SK,alpha)
2. Prover计算pi = VRF_Proof(SK,alpha)。pi常常被叫做proof，用于证明beta的合法性
3. Prover把beta和pi递交给Verifier
4. Verifier计算beta = VRF_P2H(pi)是否成立，若成立，继续，否则中止
5. Prover把PK，alpha递交给Verifier
6. Verifier计算True/False = VRF_Verify(PK,alpha,pi),True表示验证通过，False表示验证未通过。

翻译成小红发送文件给小明的场景，VRF版本流程大致如下：

1. 小红计算file的哈希值：hash = VRF_HASHf(SK, file)
2. 小红计算hash值的proof: proof = VRF_Proof(SK, file)
3. 小红把proof和hash交给小明
4. 小明计算hash=VRF_P2H(proof)是否成立，若成立，继续，否则中止
5. 小红继续把PK， file交给小明
6. 小明计算True/False = VRF_Verify(PK， file, proof)，True表示验证通过，False表示验证未通过。

整个流程非常清晰，其中比较难以理解的是VRF proof部分，也就是pi。根据数字签名的经验，verifier拥有了PK和哈希值beta，就应该可以直接验证了SK和alpha了。但VRF并非如此 ，而是需要借助中间值pi，利用pi来验证beta。pi这里扮演了辅助验证的作用。

至于为什么一定要引入pi，这里我也不太清楚，希望大家可以赐教。

总结如下：

• Prover拥有SK, alpha。生成beta, pi
• Verifier拥有PK，alpha, beta, pi。验证1)beta是由alpha产生的。2)beta是由prover提供的

此外VRF是一种算法，并不是具体的实现，具体的实现有很多种，在其RFC文档中就

• RSA Full Domain Hash VRF (RSA-FDH-VRF)。基于RSA的VRF算法
• Elliptic Curve VRF (ECVRF)，基于EC的VRF算法

VRF与随机数

前面比较了VRF和数字签名，VRF算法和数字签名算法的使用效果看似差不多，但是还是有区别的：

1. 数字签名产生的加密数据，而VRF产生的结果是哈希
2. VRF的整体流程更为简洁（个人认为），用户看不见的加解密过程

VRF优点虽然有，但并不多，人们往往也更习惯用数字签名来处理签名场景，导致VRF虽然1999年就提出，但长期默默无闻。

区块链的兴起，反而让VRF大放异彩，原因就在于VRF生成的结果是一个哈希值，而哈希值具有不可预测的特点。

具体来说，VRF算法生成的哈希值在以下方面体现了随机性：

1. 不可预测性：对于给定的输入值（alpha）和私钥（SK），VRF算法生成的哈希值（例如beta）是不可预测的。即使输入值只有微小的变化，生成的哈希值也会完全不同。这种不可预测性使得哈希值在加密通信、随机数生成等场景中可以用作一种安全的随机性源
2. 均匀分布性：VRF算法生成的哈希值通常具有均匀分布的特性。这意味着在哈希空间中，每个可能的哈希值出现的概率大致相等。在理想情况下，均匀分布的哈希值可以提供更好的随机性和抗碰撞性
3. 伪随机性：哈希算法的输出值（哈希值）看起来是随机的，尽管它们是由确定性的计算过程生成的。这种伪随机性是基于哈希函数的性质和输入值的变化，使得输出值具有类似于真随机数的性质

而哈希值，不就是可以转化成数字的么？那是不是意味可以利用VRF可以生成一个随机数？而且是可以验证生成者身份的随机数？

聪明的你！

Ref

• https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/
• https://www.jianshu.com/p/c3f239a6c858
• https://eprint.iacr.org/2017/099.pdf
• https://dash.harvard.edu/bitstream/handle/1/5028196/Vadhan_VerifRandomFunction.pdf