Verifiable Random Function

Table of Contents

1. VRF 简介

可验证随机数(Verifiable Random Function, VRF)的概念由 Micali, Rabin, and Vadhan 于 1999 年在论文 Verifiable Random Functions 中提出。VRF 在 RFC9381 中被标准化。

在介绍 VRF 前,我们先介绍一下 Keyed-Hash Message Authentication Code (HMAC)。所谓 HMAC 就是在计算 Hash 时加了一个密码:

Hash = HMAC(Key, Message)

下面是 HMAC 的一些例子:

HMAC_MD5("key", "The quick brown fox jumps over the lazy dog") = 80070713463e7749b90c2dc24911e275
HMAC_SHA1("key", "The quick brown fox jumps over the lazy dog") = de7c9b85b8b78aa6bc8a7a36f70a90701c9db4d9
HMAC_SHA256("key", "The quick brown fox jumps over the lazy dog") = f7bc83f430538424b13298e6aa6fb143ef4d59a14946175997479dbc2d1a3cd8

对于 HMAC,当我们要验证得到是 Hash 是否确实由 Message 产生时,必须事先知道 Key。

有没有办法在“不泄露 Key”的情况下,别人可以校验某 Hash 确实是根据某 Message 产生的呢? 这就是 VRF 要解决的问题。

2. VRF 的工作流程

VRF 的工作流程:

  1. Prover 生成一对公私钥,分别为 Pub_Key,Pri_Key;
  2. Prover 计算哈希输出 Hash_Value = VRF_hash (Pri_Key, Message);
  3. Prover 计算出对应的“证明” Proof_Value = VRF_prove (Pri_Key, Message);
  4. Prover 把两个信息:Hash_Value 和 Proof_Value,提供给 Verifier;
  5. Verifier 校验 Hash_Value == VRF_proof_to_hash (Proof_Value) 是否成立,如果不成立则放弃;成立就接着往下验证;
  6. Verifier 校验 VRF_verify (Pub_Key, Message, Proof_Value) 是否通过,如果通过,则表示 Hash_Value 确实是根据 Message 生成的。

在上面的流程中,私钥 Pri_Key 仅仅 Prover 知道;Verifier 使用 Pub_Key 和 Proof_Value 就可以校验 Hash_Value 是否真由 Message 生成的。

参考:https://datatracker.ietf.org/doc/html/rfc9381

3. VRF 和数字签名的区别

我们知道,数字签名可以对消息进行签名,而别人可以检验这个签名的合法性。乍一看,VRF 和数字签名很像,那它们有什么区别呢?

VRF 和数字签名的区别有:

  1. 数字签名的结果不一定是确定的,也就是说同一个私钥对同一个消息进行签名,可以给出多个合法的签名;而 VRF 要求对于同一个私钥和同一个消息,总是得到相同的输出。
  2. 数字签名的结果不可预测,但它不一定是“伪随机的”,也就是说,数字签名的输出在取值范围内的分布可能不是均匀的。而 VRF 对输出的要求更高,要求是“伪随机的”。

参考:https://crypto.stackexchange.com/questions/50681/what-is-the-difference-between-signatures-and-vrf

4. VRF 应用

VRF 常用于 PoS 区块链中,进行随机 Leader 的选举。 在 PoS 区块链中,需要随机选择一个 Leader 节点打包区块。一般来说, 不能让局外人知道下一个 Leader 节点是谁,否则容易被恶意者集中攻击。并且选举过程要是随机的、可验证的,这时 VRF 可派上用场。 比如,PoS 区块链 Cardano 就使用 VRF 来选择 Leader 节点打包区块。

此外,VRF 在 Chainlink 中有广泛应用,可参考:https://chain.link/education-hub/verifiable-random-function-vrf

Author: cig01

Created: <2020-06-06 Sat>

Last updated: <2024-04-24 Wed>

Creator: Emacs 27.1 (Org mode 9.4)