VRF VS VDF

1.1 VRF

VRF（Verifiable Random Function），具体可参看：

• Verifiable Random Functions (VRFs) draft

VRF具有：

• 唯一性（对于同一消息，多次签名均为唯一相同结果的基于公钥签名机制）
• 抗碰撞性
• 伪随机性

VRF的算法主要包含VRFkeygen, VRFeval,VRFverify：

1.2 VDF

VDF（Verifiable Delay Function）相关知识可参看：

• 可验证延迟函数（VDF）
• Boneh等人2018年论文《 Verifiable Delay Functions》

VDF中包含3个基本算法VDFSetup, VDFEval, VDFVerify：

其中VDFSetup(x,t) 为密码学hash函数需分$t$步计算，计算过程无法并行，但是计算结果可快速验证。VDF的无法并行特性，可用于替换当前能源低效的并行PoW共识，但是，对于具有快速运算速度的硬件（ASIC）节点，VDF存在“赢者通吃”问题。

3.区块链中的随机数

采用PoS共识的区块链系统中，随机数是非常重要的要素，用于保证在选择验证者组时的公平和不可预测性。
计算机本身不利于生成随机数，因为计算机是确定性设备（相同的输入总是相同的输出），所以由计算机生成的随机数人们通常称为伪随机数——需依赖用户或某种类型oracle提供的足够随机的种子，如气象站的气象噪声、心跳或灯泡频率等，以获得一组看起来随机分布的数据。但是相同的种子，生成的结果总是相同的。
当输入随时间和空间变化时，则对于全球到处分布的某种区块链的所有节点，不太可能都获得相同的结果。若节点采取不同的输入来构建区块，则会产生分叉。因此，真实世界的熵不适合用作区块链随机数的种子。
目前区块链生产环境中使用的随机数方案主要有2种：

• RANDAO
• VRF

而波卡采用的是VRF方案。

3.1 采用VRF生成随机数

波卡中使用的VRF与Ouroboros Praos中使用的几乎一样。Ouroboros随机数在 BABE中可安全的生成区块且运行良好。不同之处在于，波卡的VRF不需要依赖中心化的时钟（存在的问题是：谁的中心化时钟？），波卡的VRF仅需依赖其自身的历史结果来决定当前和未来的结果，其将slot number作为clock emulator，用于评估时间。

slot为6秒时长内的离散时间单位，每个slot中可包含一个区块，也可不包含。多个slot可组成 epochs，在波卡中，2400个slot组成1个epoch，也就是说每个epoch时长为4小时。

在每个slot，每个验证者会掷骰子，以下作为VRF函数的输入：

• 私钥：为这些掷骰子产生结果的特定key
• epoch 随机值：为the hash of VRF values from the blocks in the epoch before last $(N-2)$，因此过去的随机值会影响当前的pending随机值$(N)$。
• slot number。

VRF的输出为：

• RESULT：随机值。将该值与协议中设置的阈值比对，若该值低于阈值，则摇出该值的验证者为该slot的合格的区块生成候选人。该验证者创建并向网络提交区块，区块中需附带RESULT和PROOF值。
• PROOF：为该随机值的证明，证明生成该随机值的过程是正确的。

波卡中的钓鱼者节点：会监控波卡网络中collator和validator的错误行为，同时会验证Relay Chain的区块。由于钓鱼者可获取由验证者生成区块中的RESULT和PROOF值，一旦发现有基于非法随机值生成的非法区块，则可报告作弊的验证者。而如果所有的验证者摇出的值都高于阈值时，波卡有 相应的共识策略来解决，保证区块的生成时间几乎为constant time的。

3.2 采用RANDAO生成随机数

以太坊中采用 RANDAO来生成链上随机数。
RANDAO要求每个节点基于某一seed进行数千次hash运算。验证者会公开该轮的最终hash值，而随机值是基于每个参与者的entry来派生的。只要有一个忠实的验证者参与，都可保证该随机值是安全的（经济上不可行的攻击）。

RANDAO可选择搭配VDF使用。

3.3 采用VDF来生成随机数

VDF需要一定时间才能完成计算，即使在并行计算机上也是如此。
VDF可独立产生唯一的输出，且可公开快速验证。将RANDAO输出作为VDF的输入，引入了一个延迟，使得攻击者试图影响当前随机性的行为过时。

VDF将通过ASIC设备来运行，需可独立于节点运行。尽管只需要运行一个就可保证系统安全，但它将是开源的，且可以几乎免费分发，运行VDF既不便宜也没有激励，这会给选择这种方法的区块链用户带来不必要的摩擦。

参考资料

[1] VDF research
[2] 2020年Orlicki论文 《 Fair Proof-of-Stake using VDF+VRF Consensus》
[3] 波卡Wiki Randomness
[4] Boneh等人2018年论文《 Verifiable Delay Functions》