随机数概论——VRF，Commit Reveal，BLS的原理及应用

编程入门行业动态更新时间:2024-10-21 20:42:27

本文主要介绍了随机数在区块链中的需求及重要性，主要介绍了VRF，Commit Reveal，BLS的原理及应用，之后会继续完善。

一、场景需求

1. 随机数的需求

依靠随机数来分配社会资源，已经应用到日常生活的方方面面。从幼儿园入学资格、到初高中分配学校、再到买车买房、政府招标，都依赖随机摇号抽签。人的一生，很多重大的选择，其实都是随机数帮助决定的。从经济角度上来讲，随机数广泛应用于密码学、数值计算模拟、统计研究、乐透博彩、游戏抽奖等场合，具有极高的商业价值。

人们为产生随机数，也发明了掷骰子，转转盘，抛硬币等统计方法，通过计算机生成伪随机数，利用量子力学原理获取随机数等。这些方法虽然很好的解决了随机数的随机性、不可控制性、不可预测性等方面的问题，但是却缺乏去中心性与可证公平性。

自然地，人们希望找到一种更公平的随机数生成和发布机制。而区块链作为一个去中心化的平台，为可证公平的随机数生成提供了天然的基础。

但是在公有区块链上设计一个可用的随机数发生器难度更大。除了基本的随机数统计学要求外，公有链上一个可用的随机数发生器至少要满足无法预测，不可操控，难以串谋，可证公平，可审计这几个特点。

因此，如何在区块链上设计并实现可证公平的随机数发生器成为近年来一个重要的研究问题。自从Randao 团队在2015 年提出使用Commit Reveal 方案后，又分别有Vitalik Buterin 提出的Randao++ 方案、部分DApps 使用Oraclize 从链下服务获取随机数的方案，来实现区块链随机数生成。

2. 真随机与伪随机

伪随机数一般由确定的算法生成的，其分布函数与相关性均能通过统计测试。但与真随机数相比，它们由算法生成，而不是一个真实的随机过程。伪随机数也只是尽可能地接近其应具有的随机性，但是因为有“种子值”，所以伪随机数在一定程度上是可控可预测的。伪随机数可使用取中法、同余法、移位法、梅森旋转算法等方式产生。

真随机数的产生不可预计，也不可能重复产生两个相同的真随机数序列。真随机数一般使用物理现象产生，比如掷钱币、掷骰子、晃动鼠标、转转轮、使用电子元件的噪音、使用大气噪声、核裂变等。真随机数发生器的技术要求一般比较高，生产效率一般比伪随机数低。另外，如果信息熵的信息量很有限，不一定能产生真随机数。真随机可以进一步区分为统计意义上的随机以及量子效应上的随机。一般认为，由于量子力学内在的随机性，其产生的随机数比传统物理学通过统计产生的随机数更“真”。

Linux内核提供了统计方式的真随机数生成器。它利用机器的噪音生成随机数，噪音源包括各种硬件运行时速，用户和计算机交互时速，比如击键的间隔时间、鼠标移动速度、特定中断的时间间隔和块IO请求的响应时间等。random利用大气噪音生成真随机数并对外提供。另外，通过监听真空内亚原子粒子量子涨落产生的噪音，澳大利亚国立大学的科学家们建造了随机数发生器并提供给互联网用户。

量子现象利用了在原子尺度下粒子的行为具有随机性，而且其本质还未被人类发现，因此可以将其看做一个具有良好不确定性的熵源；混沌现象是指在混沌系统中，初始量的微小差异会导致未来的发展截然不同，因此除非获得初始时刻的全部准确信息，则无法预测未来的发展趋势（eg. random）。

3. 随机数生成方案衡量标准

不可预测：不可预测是针对所有参与者的，不管是生产者和消费者，都无法根据历史数据预测下一个随机数的可能值，即便是稍稍提高一点点预测的成功率都做不到，即具有马尔可夫性质。在公共随机数的方案中，还要求任何人根据任何公开信息也都不能提高预测概率，例如Bitcoin Beacon的方案中，即便知道区块的历史数据，矿池的公钥，待打包的交易列表等，也无法获得预测上的优势。
不可串谋：在随机数的生成过程中，部分参与方联合起来，互相交换各自的私有信息，并不能影响随机数的生成过程或改变随机数的结果，或具有其他比较优势，比如相比其他人提前获得即将生成的随机数的结果。
不可提前获知：随机数的参与方同时知晓该随机数，任何一方不能提前知道结果。
不可篡改：即随机数的生产者不能伪造一个随机数出来，而当一个随机数生成好后，该随机数无法被任何人修改。
不可选择：随机数的生产过程可能同时有很多个随机数生成，生产者无法只选择其中的某一个提供出去，或用其中一个替代另外一个。
不可隐瞒：生产者在随机数生成完成后，不能拒绝公开该随机数。即生产好的随机数一定会被公开，无法被隐藏或者撤回。
可参与：随机数的生成过程中，随机数的相关方可以容易的参与进来，随机数生成方案应该为一般人的广泛参与提供便利，降低或消除参与门槛，参与的权力不应该被剥夺。
可审计：在随机数生成过程结束后，其整体过程是可以被时候审计的。
成本：随机数的生产成本应该尽可能低
响应速度：随机数的生成过程应该足够快

4. 随机数发生器方案及评价

中心化随机数发生器
- NIST随机数生成器：NIST Randomness Beacon用于实现公共随机数源。它使用两个独立、商用的随机数发生器，每个发生器配备一个独立的物理熵源和SP800-90认可组件。能够实现不可预测（任何算法都无法预测该生成器将会给出的随机数），自主（能够抵抗不相关者介入或阻止分发随机数的过程），一致（一组用户访问该服务能够确实地获得相同的随机数）的随机数源。
- random：使用大气噪音生成随机数。即先用录音设备获得大气中的声波，再检测其细微变化作为生成随机数的熵源。
Bitcoin Beacon

斯坦福和普林斯顿的Bonneau&Goldfeder 等于2015年提出可将比特币的区块数据作为一个不依赖第三方的公开随机源，并分析了区块头所包含的熵，以及根据该熵所生成的随机数的安全性。

用比特币区块数据生成随机数的问题在于，其通用安全性不够高，无法防止“块保留攻击（Block Withholding Attacks）”，即参与者可以贿赂矿工丢弃不利于自己的区块，从而在博彩类的应用中获得相对优势。比特币单个区块的奖励是固定的，因此，所有依赖于该方法获得的随机数有一个固定的安全上限，不能根据应用的具体情况动态调整，导致其适用性有很大的限制。此外，Bitcoin Beacon 方案中，普通用户无法参与区块的生成，虽然串谋的成本较高，但矿工并不能避免嫌疑。因此该方案仍然不是一个可证公平的随机数方案。

Algorand

采用Verifiable Random Functions(VRF)选择出块人，委员会成员及解决分叉。

VRF的流程和特点：考虑如下情形：有一个公共的难以找到原象的函数F，现在Bob给出一条信息x，要求Alice用她的秘钥s计算出F(s, x) = v作为一个随机数输出，因为s对公众不可见，所以Bob收到v难以判断这个v是否是Alice诚实计算F(s, x)得出的。VRF实现了：让Alice在给出v的同时也给出一个proof和一个对应s的公钥p，Bob可以用p和proof来验证v是否是F(s, x)。

VRF的签发是由一个参与者完成的，因此该参与者可以选择不发布对自己不利的签名，和Bitcoin Beacon有相似的缺点，因此不适合用来作为可证公平的随机数发生器。

Dfinity

Dfinity的共识算法建立在随机数的基础上，通过BLS签名算法实现随机数的生成，由一组人产生签名，任何个人都无法预测签名结果，单个人无法阻止签名发布。

BLS 是一种门限签名技术。首先将用户分组，第一轮由一个组产生一个随机数，之后每一轮选一个组对上一轮产生的随机数签名，作为这一轮的随机数输出，每个成员都无法提前预知签名结果。其中签名过程使用BLS 签名机制，保证在签名过程中没有个体能够提前预知签名结果，因此无法操纵随机数。

BLS 很好的解决了Withholding 攻击的问题，且生成随机数过程不可操纵，无法预测，很难串谋，是一个比较理想的随机数生成方案。

DAO

DAO是一种无中心的组织结构，组织规则由代码描述并强制执行，任何人可自由加入退出，不同参与者间地位平等，刚好可以满足我们对于公共随机数的设计目标。因此区块链技术以及DAO理论，可以用来支撑并指导公共随机数的设计和实现。

上述随机数发生器评测结果

二、VRF介绍

1. Why VRF？

场景

在区块链场景中，有的框架会用算法随机产生出块节点与验证节点（如Algorand），甚至解决分叉。按传统的随机算法，按一定的哈希规则随机轮询，选出一个节点来记账/验证。如果这个随机轮询的规则是谁都可以复现的，那么可以推测出将来的某个记账/验证节点，集中攻击它。

为了解决这个问题，就引入了VRF，只有自己能够完成这个哈希过程，而别人只能在他声明之后验证这个过程，防止有人可以提前推测出将来的记账节点。

POS中的权益研磨（Grinding）

在任何基于区块链的权益证明算法中，都需要某种机制，来随机从当前活跃验证者集合中选择能够产生下一个区块的验证者。举个例子，如果当前活跃的验证者集合由持有40以太币的Alice，持有30以太币的Bob，持有20以太币的Charlie与持有10以太币的David组成，那么你想让Alice成为下一个区块的创建者的概率为40%，而Bob的概率为30%等（在实践中，不仅要随机选择一个验证者，而是要（随机产生）一个无限验证者序列，只有这样如果Alice不在线的时候，就可以有其他人在过段时间替代她，但是这并没有改变问题的本质）。在非基于区块链的算法中，出于不同的原因也经常需要考虑随机性。
——以太坊Github《Proof of Stake FAQ》

基于PoS的区块链协议最基本的一个问题就是模拟领导者选举过程。为了在股东们之间的选举达到一个真正的随机性，系统中就必须要引入熵(entropy)，但引入熵的机制可能会容易被敌手操作。例如，一个控制一群股东的敌手可能会试图模拟协议的执行，尝试不同的股东参与者的顺序以此来找到对敌对股东有力的继续者。这会导致一个叫做"grinding"的致命弱点，敌对参与者可能会使用计算资源来倾斜领导者选举。
——Ouroboros白皮书《Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol》

VRF的目的
VRF的目的就是要生成随机值，既要无法被预测，同时又要可验证，可重放。

2. VRF是什么?

VRF是可验证随机函数(verifiable random function)，一方面具有伪随机性，另一方面它还具有可验证性(输出包括一个非交互零知识证明)

伪随机性
可验证性

VRF 的方式是，实现本地抽签，各个节点自己抽签，如果抽中了之后，大家可以很容易地验证这个结果确实是你生成的。

eg. 假设现在是round 10（第10 轮），节点们可能会轮流抽签，以节点自己的私钥+ 一个全网都知道的随机数（比如是这轮的轮次10）作为输入，生成了一个随机数（0-100）；设置一个条件：100 个节点轮流抽签，谁先抽出来的随机数大于10，就是这一轮的打包者。假设5 号节点抽到了11，可是只有5 号知道其他人不知道，因此他在广播这个随机的同时还需要广播一个零知识证明。通过零知识证明，全网只需要通过5 号的公钥就可以验证，接受5 号为这轮打包者。图解如下：

3. VRF具体的操作流程？

证明者生成一对密钥，PK、SK；
证明者计算result = VRF_Hash（SK，info），proof = VRF_Proof（SK，info）；
证明者把result，proof，PK递交给验证者；
验证者计算result = VRF_P2H（proof)，True/False = VRF_Verify(PK, info, proof)

True表示验证通过，False表示验证未通过。所谓的验证通过，就是指proof是否是通过info生成的，通过proof是否可以计算出result，从而推导出info和result是否对应匹配、证明者给出的材料是否有问题。

4. 抽签有没有必要用VRF？

相比随机预言机

普通哈希Hash(a)=b，所有人都可以重现，检验正确性；
VRF是Hash(SIG(sk, a))=b，别人无法复现这个过程。但是可以拿b，pk，和中间信息验证b是跟a对应的。

相比非对称加密

在密码学签名算法中，大都会引入随机性，也就是对相同信息的多次签名会得到不同的签名值，因此矿工可以不断对相同的输入SK和block，计算签名，以满足结果小于D。那么理论上任何人都会成为出块者，只要计算足够多次的签名。
有些非对称加密方式得到的随机数不是均匀分布的，如RSA
缺乏零知识，不管使用确定性签名还是随机性签名，都存在个安全隐患。就是一旦将自己的出块凭证公布，任何人都可以公开验证，包括攻击者。那么攻击者可以对出块节点进行攻击，使其不能出块。使用VRFs的方式，矿工只需要公布自己的R表明自己的出块权，当出完块的时候再公布P，那么攻击者就无法在出块之前知道谁具有出块权，因此也就无法实施针对性的攻击。

5. 应用

Consensus：共识算法中安全性

VRF Sortition，Smart Contracts，例如本体，Cardano，Dfinity，Algorand等，不同点在于如何产生输入以及输出怎样用。VRF的返回结果可以用来公开或私密地完成节点或节点群体的选择。eg. Dfinity利用mod操作来唯一，公开的确定一个group。Algorand，Ouroboros Praos是私密选择，即计算出哈希值后，如果哈希值小于某个阈值，节点可以私密地知道自己被选中。

本体-VBFT共识算法：
1. 根据VRF 从共识网络中选择备选提案节点，各个备选节点将独立提出备选区块；
2. 根据VRF 从共识网络中选择多个验证节点，每个验证节点将从网络中收集备选的区块，进行验证，然后对最高优先级的备选区块进行投票；
3. 根据VRF 从共识网络中选择多个确认节点，对上述验证节点的投票结果进行统计验证，并确定出最终的共识结果。
4. 所有节点都将接收确认节点的共识结果，并在一轮共识确认后开启新的共识。
Algorand中：
1. 先选打包者，选完打包者选委员会，委员会用BA*进行选区块。
2. 输入值由前一个随机数(最初的随机数是协议给定的)和某种代表高度，轮次的变量进行组合，然后用私钥对之进行签名(或者先签名再组合)，最后哈希一下得出最新的随机数。
3. 条件：①签名算法应当具有唯一性；②避免在生成新随机数时将当前块的数据作为随机性来源之一。
Dfinity中：

交保证金提高门槛，并降低参与节点的数量，然后选打包者，选完打包者选公证人，对区块权重进行排序，选出区块。
Cardano的共识机制-Ouroboros Praos：

在根据Random seed选举slot leader时，通过VRF确保slot leader不被事先计算出来被攻击。

IOST的高效分布式分配片

使用了VRF来进行领头节点的选举，通过VRF得到随机数之后，会将结果进行广播，然后其他节点会进行统计，得到随机数值最小的作为分片领头节点。是一种交互式的选举方式。
Key Transparency

密钥管理系统，使消息传递在不相信服务端的情况下做到点对点的安全上的提升。
DNSSEC

DNS服务的安全性。

三、Commit Reveal介绍

1. Commit Reveal是什么？

Commit Reveal 是一种在规定时间内可以有多人一起参与产生随机数的流程。

2. 技术原理

第一阶段：收集有效sha3(s)

所有希望参与随机数生成的生产者，在指定的时间窗口期内（例如以太坊的6个出块周期，大约72秒），向合约C发送m个以太的保证金，同时附上其任意挑选的数字s的sha3(s)。

第二阶段：收集有效s

之前成功提交sha3(s)的所有生产者，在第一阶段结束后，在第二阶段指定的时间窗口期内，向合约C发送各自在第一阶段选中的数字s。合约C检查数字s是否合格的。如果合格，保存该s到最终随机数生成函数的seeds中。

第三个阶段：计算随机数，发放保证金及奖励

全部的s_i收集完成后，以f(s_1, s_2, ..., s_n)作为最终的随机数，把随机数写入到C的存储空间中，向所有请求该随机数的其他合约返回结果。把生产者在第一阶段发送的保证金退还，同时把本期随机数生成过程中，其他合约支付给C的手续费作为奖励发送给本期的所有生产者。

方案约束：为了保证随机数结果不被操纵，兼顾安全和效率，合约C有如下这些额外规则约束：
- 第一阶段中，如果先后有两个同样的sha3(s)被提交，只接受第一个。
- 第一阶段中，有一个最小参与人数的设定，如果在窗口期时间内未能达到预设人数，则本期随机数构造失败。
- 如果提交的sha3(s)结果被合约C接受，则在第二阶段必须提交s。
  
  (a)如果在第二阶段的窗口期中某个参与者没能提交s的话，则在第一阶段中发送的m个以太会被没收，不再返还。
  
  (b)如果在第二阶段未能收集到全部的s，则本期随机数生成失败，退还其他合约支付的手续费后，将本期收集的保证金分发给在第二阶段成功发送s的其它生产者。

3. 方案评价

缺点：生成随机数的速度较慢，从接到随机数生成请求，到生成随机数，至少需要10个块以上的组织协调时间，在以太坊不缩短出块间隔的情况下，耗时在3分钟以上；因为需要参与者多次发送交易提交数据，其生产和使用成本较高。
优势：其参与门槛基本为零，任何人都可以随时加入一个随机数的生成过程，在防止串谋和可证公平方面拥有非常特殊的优势。

4. 应用

Rando，低频率、高中奖额博彩（如乐透摇奖）

四、BLS介绍

1. Why and What？

BLS 是一种多人蔘与生成随机数的方式，其目标是给消费者在可证公平的前提下以一种更高效的方式来提供随机数。

首先BLS 生成随机数涉及分组和初始化。分组就是把所有参与人随机分成M 组，每组N 人。初始化是分组结束后根据BLS 的签名机制为每个组员生成自己的私钥以及全组的公钥P。为了提高效率分组为线下完成，且分组结果会运行一段时间，然后定期重新分组，以保证公平性。

2. BLS签名

（1）思想：N个成员组成一个组，一个组有一个逻辑上的私钥S（使用S对消息签名的结果记为SIG，S对应公钥记为P），而每个成员i只拥有这个秘钥的一部分s_i，完整的秘钥S不存在于任何人手中，没人能直接计算出SIG。签名时，每个人用自己的秘钥s_i对一个信息签名得到sig_i，只有收集了k个（某个预先设定的值）成员的签名，才能够计算出签名SIG。

（2）特点：秘钥由全网共同决定，无法预知，无法操控。

（3）初始化：要让BLS签名机制运行起来，需要一次初始化，生成成员的私钥和全组公钥。

每个成员i生成自己的随机数组ran_i（对其他人保密，包括同组成员）。
使用一个（BLS签名机制给出的）函数f计算出send_{ij} = f(ran_i , j)，通过私密通道发送send_{ij}给成员j（对不同的j，send_{ij}不同；f有单向性，用send_{ij}和j无法得到rani）。对所有j(= 1, 2, ..., N)，成员i要对成员j发送send_{ij}（对于i = j，则计算出send_{ii}记录在本地）。
每个成员j收集数据send_{1j} , send_{2j} , ..., send_{Nj}，用（BLS签名机制给出的）函数v验证send_{ij} (i = 1, 2, ..., N)的合法性（v(send_{ij} ) = 1则合法，v(send_{ij}) = 0则非法）。
全部合法后，用它们计算出自己的秘钥s_j，s_j对应的公钥pub_j，和S对应的公钥P。
将pub_j以及P广播。

（4）执行步骤：

每个成员i用秘钥s_i对消息M签名得到sig_i并广播sig_i。
每个成员j收集其他成员广播的sig_i，并用pub_i验证，通过验证通过则作为有效签名接受。当收集到k个有效签名（包括自己的签名sig_j），则计算出最终签名SIG并广播SIG。

3. BLS签名产生随机数

（1）思想：将全网分为h个组，第一组生成一个随机数SIG_1，使用SIG_1选取下一个组，被选中的组签名这个随机数得到SIG_2，使用SIG_2选取下一个组，再对SIG_2签名得到SIG_3。如此重复，过程中已经参与过随机数生成的组不再参与随机数生成，直到第h个组生成SIG_h作为最终的随机数输出。

（2）具体流程：

将全网节点分为h个组G = g_1, g_2, ..., g_h
g_1生成一个随机数SIG_1并广播，将g_1从G中剔除。
对i = 2, 3, ..., h，执行：取g_{work} = G (sig_{i−1}mod|G|)，将g_{work}从G中剔除，g_{work}对SIG_{i−1}签名得到SIG_i并广播。
最终得到的SIG_h为最后输出的随机数。这个过程保证每一步的签名都是一个随机数，每个组都无法预测后续组的签名结果。只有最后一个组有操纵SIG_h的优势，当最后一个组有不超过k个非法成员，则SIG_h是安全的，但是无法预测哪个组会担任SIG_h的生成任务。

4. 方案评价

（1）安全性考虑

签名初始化时：若k个成员串通，使用BLS签名机制生成这k个人的秘钥并共享，独占这一组的签名权。
签名执行第二步：如果一个成员收集了k − 1个其他成员的签名，并与自己的（还未广播的）签名组合计算出SIG，发现SIG对自己不利，则可以选择不广播自己的签名。如果因此造成全网只有k−1个成员签名被广播，则签名会失败。当全网有多于N−k个成员可能做出此行为，则这个情况有发生的可能性。
假设当k < N/2，若全网有k个成员对一个并非全网大多数成员同意的消息进行签名，则这k个成员能够“伪造”集体意愿。
如果生成的随机数与全网大多数成员有直接的利益关系，那么在生成随机数的最后一步，很可能有超过一半的成员拒绝给出正确的签名SIG_h使得随机数生成失败。

综合1 , 2 , 3点，BLS系统可以抵御max(k −1, N −k)个非法成员。在DFINITY中，N = 400, k = 201，当某个组内超过一半成员为非法成员，才会出现签名失败或伪造签名的情况。事实上BLS签名方法在将全网节点分组时使用VRF进行随机分组，在这个过程没有作弊的前提下能提供较高的容错率：以全网有10, 000用户为例，当3, 000人为恶意用户时，分组时某一组会有超过一半恶意节点的概率不足1e ^{−17}，4000人为恶意用户时，这一概率为1^{e −5}，而且概率会随着N提高(k = N/2 + 1)而进一步降低，但是无论N取到多高，都无法做到50%容错，当恶意用户上升到50%左右时，上述概率会急速上升到50%附近。因此可知这一随机数生成机制并不适合用于与全网利益直接相关的问题之中，而对于只与全网部分节点（< 50%）利益相关的问题中，上述4个问题发生的可能性很低。

（2）安全策略

初始化阶段
1. 有兴趣参与提供BLS 方案服务的生产者向系统发起申请，由系统确定入围帐号
2. 设定Feldman 秘密分享的参数，通过分布式密钥分发机制形成一个BLS 服务提供组。
3. 该BLS 服务组的每个成员向获得的私钥对应的以太坊地址转入一笔押金，该押金在BLS 服务组存续期间，不得转出。如果在BLS 服务组到期之前，有人提前退出，则扣除其部分押金。
提供服务阶段
1. 随机数消费者向该BLS 服务对应的智能合约R 发送请求，请求包括待签名的内容（如果为空则为当前块的hash）以及支付的手续费。智能合约R 记录下待签名内容。
2. BLS 服务组检测到区块链上的随机数生成请求后，链外协调服务组一起签名并合并签名得到随机数。该随机数由一指定用户写入到智能合约R 中。
审计监督
1. 为了防止消费者和某些服务者成员勾结，提前获取某些内容的签名结果，然后有选择的提供待签名内容给BLS 服务，获得比较优势从而获益，可以通过以下的惩戒条例来避免串谋，并使得服务者不敢接受贿赂提供私下签名。
2. 如有人出示某成员私钥对内容s 的签名结果，且该内容s 未出现在智能合约的已签名的历史记录中，则可判定该成员私自签名，罚没押金。
3. 考虑到区块链重组的可能性，该成员可以申辩，申辩内容应该包括包含内容s 的区块。
4. 成员必须保有一定的押金在系统中，该押金的私钥拥有者可以转移走押金，这样可避免成员向特定人群公开自己的私钥。
5. 为了防止成员在BLS 服务组到期之前，私自转走押金，增加一条规则，如在默认到期之前提前转走押金，则扣除20% 的押金给坚持到期的其他成员。
6. 每个BLS 服务组会有一个健康指标，该指标由押金状况，签名响应速度，节点在线率等指标构成。健康指标对外公示，消费者可挑选服务组的服务。服务组的健康度可能会影响其服务的收费标准。

（3）方案评价

生成的过程在链外组织，响应速度快，通常只需要一个区块的时间就能生成随机数；消费者发起随机数生成请求，生产者在下一个块写入随机数，只需要发送两次交易就可以完成随机数的生成和调用，生产和使用成本都很低，适合用于高频，同时对于防串谋的需求不那么苛刻的场景。