一、什么是VRF
背景：
在传统的区块链中，常用的随机算法是基于伪随机数生成器（Pseudorandom Number Generator，PRNG）的。PRNG是一种确定性算法，它根据一个初始种子生成一个看似随机的序列。在区块链中，通常使用的是伪随机数序列来选择区块的创建者、确定验证节点的轮换顺序等。
然而，传统的随机算法存在一些问题：
- 可预测性：传统的随机算法是基于确定性的计算，因此它们的输出序列是可以被预测的。如果攻击者能够推测或预测到随机数序列，他们可能会通过选择适当的时间点参与区块创建或验证，以获取不当的利益。
- 中心化：传统的随机算法通常由中心化的实体（如区块链网络的维护者或特定的随机数生成器服务提供商）提供。这导致了对于生成随机数的可信第三方的依赖，这种中心化结构可能存在单点故障和潜在的安全风险。
- 不可验证性：传统的随机算法通常没有提供对随机数的验证机制。区块链的参与者无法独立验证所使用的随机数是由特定的算法和种子生成的，这可能导致对随机性的不信任。
VRF：
可验证随机函数 VRF（Verifiable Random Function）是一种具有验证性质的随机数生成器 RNG 。它是一个密钥相关函数，将输入映射到一个随机的输出，并且可以生成一个证明，证明输出确实是由特定的输入和密钥生成的。VRF 在许多密码学和安全协议中具有广泛的应用，包括随机数生成、身份验证、匿名通信、区块链和分布式系统等领域。它提供了一种可信的随机性生成机制，并通过附带的证明确保生成结果的可验证性和完整性。
总结下来就是：可验证、随机生成
一些特性：
- 随机性：VRF 能够生成统计上均匀且不可预测的随机输出。这意味着输出具有高度的随机性，无法被预测或推导出来。
- 可验证性：VRF 生成的输出可以被有效地验证。验证者可以使用公钥、输入和输出来验证生成的证明，以确保输出确实是由相应的输入和密钥生成的，而不是被伪造或篡改的。
- 不可伪造性：VRF 的输出是不可伪造的，即除非持有私钥，否则无法生成有效的输出和相应的证明。
- 不可区分性：VRF 的输出是不可区分的，即在没有密钥的情况下，无法区分两个不同输入对应的输出。
二、随机数和证明生成
四个函数：
- 生成密钥：在可验证随机函数中，生成密钥的过程通常使用密码学算法来确保安全性。这个步骤涉及生成一个公钥-私钥对，其中公钥可以公开共享，而私钥必须保密。生成密钥的算法通常是基于数学问题的难解性，例如基于大素数分解或椭圆曲线算法。公钥-私钥对在可验证随机函数中的其他步骤中起到关键的作用。
- 生成随机数输出：在可验证随机函数中，生成随机数的过程是通过使用密钥和其他随机性源来生成一个随机输出。**生成随机数的算法必须是不可预测的，并且应该具有统计上的均匀性，以确保生成的随机数是真正的随机。**这个步骤的目的是产生一个可验证的随机数，以便在后续步骤中进行验证。
- 计算零知识证明：在可验证随机函数中，计算零知识证明的过程用于证明生成的随机数确实是由特定的密钥和算法生成的，并且没有其他信息泄漏。在这个步骤中，生成者将使用密钥和其他相关信息来计算一个证明，以表明生成的随机数满足特定的性质，例如统计均匀性或不可预测性。
- 验证随机数输出：在可验证随机函数中，验证随机数输出的过程是用于验证生成的随机数的正确性和可验证性。验证者将使用生成者提供的公钥、生成的随机数和零知识证明来验证生成的随机数是否确实是由特定的密钥和算法生成的，并且证明是否有效。如果验证成功，则可以确认生成的随机数是可信和可验证的。
通过这些步骤的组合，可验证随机函数提供了一种能够生成可信随机数的机制，并且可以对生成的随机数进行验证，以确保其符合特定的性质和安全要求。这对于许多密码学和安全应用非常重要，例如密码生成、随机数生成和加密协议等。
具体实现：
- 证明者生成一对密钥，PK、SK；
- 证明者计算 value = VRF_Hash（SK，Seed），proof = VRF_Proof（SK，Seed）；
- 证明者把 value，proof，PK 递交给验证者；
- 验证者计算 value = VRF_P2H（proof)，True/False = VRF_Verify(PK, Seed, proof)
其中，e(·,·)是双线性映射。
可验证随机函数抽签：
广播后验证以下两个条件是否成立：
- 利用 proof 和 seed 验证随机数 value 是否正确
- 利用通过二项分布函数得到 j’ 是否与 j 相等
假设两个条件均成立，那么就证明这个抽签结果是正确的，是可信的。
三、VRF的应用
VRF 生成的随机数和证明可以用于区块链上的许多应用，如非交互式抽奖系统、可验证的交易托管机制、区块链和智能合约等。VRF 可验证随机函数推出后就在 NFT 和链游热潮中被广泛使用
- 非交互式抽奖系统：VRF可以为抽奖游戏保障公平、可验证且高效的结果。
- 可验证的交易托管机制：VRF可以支持自动托管服务，保障用户的匿名性。
- 区块链和智能合约：VRF 已经成为了去中心化协议和应用重要的组成部分。
- Algorand先选打包者，选完打包者选委员会，委员会用BA*进行选区块。
- Dfinity中，交保证金提高门槛，并降低参与节点的数量，然后选打包者，选完打包者选公证人，对区块权重进行排序，选出区块。
- VBFT，本体的共识算法中，首先选打包者，打包之后，选投票者对这些包进行投票，之后选确认者，对这些票数进行统计，选出区块。
其他场景：
- 零知识数据库的构建：可验证随机函数可以用于构建零知识数据库，其中数据库持有者可以向查询者证明其数据库中是否存在特定的数据项，而无需透露实际的数据内容。生成者可以使用可验证随机函数生成一组随机数，并在生成每个数据项时计算相应的证明。验证者可以使用这些证明来验证查询的结果，从而验证数据库持有者对查询的回答的正确性，同时保护数据库的隐私和安全性。
- 域名系统的消息传输：在域名系统（DNS）中，可验证随机函数可以用于确保消息的随机性和完整性。生成者可以使用可验证随机函数生成随机数，并将其附加到消息中。验证者可以使用生成者的公钥和接收到的随机数来验证消息的完整性，并确保消息没有被篡改。这可以提供对DNS消息的验证和安全性保护，防止攻击者对DNS进行欺骗或劫持。
除了共识算法，其实在其他的方面也有一些项目使用了VRF，比如 IOST 的高效分布式分配片中，就使用了 VRF 来进行领头节点的选举。不过于上面所说的离线抽签方案不同，这里的选举通过VRF得到随机数之后，会将结果进行广播，然后其他节点会进行统计，得到随机数值最小的作为分片领头节点。是一种交互式的选举方式。
四、写在最后
基于 VRF 的抽签机制的优点：
- 抽签过程不需要与其他节点通信，直接在本机就能够的到这个抽签结果，而且这个 x 输入是大家公认的，针对同一个 x 的输出 value 是固定的，因此无法通过多次尝试来改变抽签结果
- 某个节点收到其他节点的抽签信息之后，可以用附带的 proof 来证明随机数的正确性，保证它的确是由私钥的拥有者计算出来的。因此这个抽签结果是无法被伪造的。
- VRF 主要用来的得出一个伪随机数，抽签的部分主要是由一个二项分布函数负责，而通过构建二项分布的参数，我们可以很方便的控制需要被得出的中签权益的个数，适配不同的需要抽签的场景。
参考：