复联4：Daniel vs 灭霸

本文主要内容包括随机性的基本概念，以及大家比较关心的一些区块链项目中的当红炸子鸡是如何获取随机性的，以及随机性和区块链之间的关系，主要是这三个方面。不会涉及到传统的伪随机发生器。（这里说明一下，作者把 Nervos 的几个 CXO Daniel 、Jan、Terry 都调侃了一遍...

随机性的定义

话说灭霸获得无限手套，集齐6颗无限原石。只要灭霸发动“比心”攻击，宇宙一半的生命就会消失，这时候复联派出了终极武器—Daniel！
“Daniel，就决定是你了！”

这时，电视里又开始在放《武林外传》，Daniel看到吕秀才。

于是，Daniel 灵机一动，跑去找灭霸。
Daniel：尊敬的灭霸先生，听说你要消灭宇宙一半的生命？
灭霸：请求是没有用的，所有生命都是随机选择的，绝对公平！这是为了宇宙的平衡，宇宙的未来。
于是，Daniel 深吸了一口气，提出了一连串的问题。
Daniel：那什么是随机？随机的源头在哪里？你了解无限手套随机选择的原理吗？如何验证你的选择是随机的呢？你怎么知道自己的选择是不受干涉而完全公平的呢？选择出来的人被选择之后还是随机的吗?@&*(@^$^&@*!(&#*!……”

Daniel：好吧，我们从最简单的开始，什么是随机性？
灭霸：那太简单了，就是均匀分布。
Daniel：01230123 是随机序列吗？
灭霸：还要与出现的位置无关。
Daniel：xxxxx 是随机序列吗？
灭霸：我知道了，再加个相互独立。
Daniel：xxxxx 是随机序列吗？这个是自然数 e，是 2.871828828

从以上的对话中可以看出，光从均匀性出发定义随机性是不够的，因为每一个数字出现的概率是一样的，并不能保证他们就是独立的。那么加上相互独立的话，这个序列是随机的吗？我们可以认为它是随机序列，但是是有限定条件的，这类随机序列只能用在仿真当中。比如我们想要模拟人流的泊松到达，用这样的随机序列是可以的，但是在密码学中这样的随机序列是不够的，我们还需要不可预测性。比如我们用自然对数的底e的数码作为随机序列。e确实可以被认为在统计上是均匀分布和独立的（尽管没有完全证明），用来做仿真是足够的，但是不能用作密码学中的随机种子。因为对手有可能通过一定长度的已知序列猜测到是在使用e。密码学的随机种子要求任意片段序列不能预测该序列余下的部分，这是密码学中独有的特性，目前接下来的内容都是可以适用于密码学中的随机序列。

随机性的分类

随机性和随机性之间是有差别的，我们来简单说明下随机性的分类。从真假来分类，可以分为真随机数发生器和伪随机数发生器。还有一种与之正交的分类，是硬件随机数发生器和软件随机数发生器。

真随机数发生器通常是通过物理手段，包括量子过程。软件真随机数发生器是存在的：Linux下有个/dev/urandom，是一个软件真随机数发生器，采集机器运行过程中的噪音数据来获取足够的熵源。

伪随机数发生器通常通过单向函数来构造，伪随机数发生器通常可以将熵源，也就是随机种子进行扩充，比如真随机数发生器产生了 1bit 的随机数，那么伪随机数发生器就可以将这 1 比特扩充到 10bit 或 100bit，但是它的熵还是 1bit。

为什么把量子过程单独领出来讲呢？因为在量子力学没有被推翻之前，它是目前理论上能够证明的真随机。从物理学原理上它是天然蕴含在理论里的随机性像。其他获取随机数的手段，像大气噪声，我们还不能完全从理论上证明它是随机的，也许未来某一天有人能找出它的规律呢？

• 那么伪随机数发生器存在吗？在密码学安全吗？
• 很遗憾，不存在.
• 这个问题等价于P是否等于NP；然而还没有被证明出来。
• 那为什么还要去用呢？
• 我们现在统计学上的一些检测手段可以检测出你这个发生器产生的随机序列是否满足密码学的计算安全性的要求。
• 如何判断一个序列的随机数程度？
• 用统计学统计学测试。
• 能够完全证明吗？
• 不能。
• 有理论证明随机数发生器吗？
• 有，量子随机数发生器。
• 伪随机数和不可预测性的关系？
• 伪随机性等于多项式时间不可预测性。

所有的真正的伪随机数发生器生成的随机数序列一定是不能被在多项式时间内预测的，也就是给定一个伪随机数发生器，已知它产生的随机序列的任意片段，是无法在多项式时间内以高于一半的概率预测出下面的1bit。

如何从区块链上取得随机数

伪随机数发生器不能直接用在区块链上。为什么？
伪随机数发生器生成的随机序列难道不是不可预测的吗？

不可预测性的前提是说伪随机数发生器作为一个黑盒，除了它的输出，外界无法得知其他一切信息。但是区块链上的一切都是公开透明的，包括使用的伪随机数发生器也是透明的，种子也是一样的，你怎么选取种子呢？一旦你知道了种子，知道了随机数的算法，那么后面的不可预测性不必再考虑了，完全能够预测到后面的序列了。

真随机数发生器呢？

可以，但是很难做到去中心化。例如以太坊现在常用的随机数发生器就是通过 Oraclize，引入random.org（random.org 是一个网站，它声称提供真随机数。）大家通过 oraclize 把真随机数入到智能合约中，这是一个比较普遍的用法。比如 Fomo3D，他们之前用了一个并不安全的，在区块链上取随机数的方法。
那么归根结底，在区块链这样的一个系统当中随机性可以来自哪里呢？这个随机性来自“人类的行为”。我们现在从最简单的情况开始去逐步构造一个区块链上可以使用的公平的随机数发生器。下文所涉及到的在分布式的环境下的协议都可以转换为区块链的环境，因此不对“分布式”和“区块链”做区分。

v1.0 斯里兰卡炒饼

例如，现在有 Jan 和 Daniel 两个人，在他们面前有一盘炒饼，他们都想吃，但是这个炒饼只够一个人吃。因此，他们现在需要一个分布式的随机数发生器来决定由谁来吃这个炒饼。假设最后输出的结果是 0，那就给 Jan；是 1 的话就给Daniel。


为了构造这样的一个公平的协议——历史上叫做 coin-flipping 或者 coin-tossing 协议，我们要求二人分别对协议进行输入。这样的协议需要满足所有的输入与输出都是独立的。Jan 和 Daniel 他们之间肯定是不可能共谋的，这样他们俩的输入就相互独立了。现在只需要满足输出和两个输入也分别是相互独立的；第二个性质就是只要有一个输入是均匀选择的，那么结果就是均匀分布的。也就是说，即使 Daniel 一直选 1，只要Jan的选择是均匀的，那么到最后输出的结果就是均匀的。现实中满足这些条件的构造方式有很多，其中一种是异或操作：在给定 Daniel 选 1 的情况下（Jan 不知道），Jan 不管选 0 还是 1，输出结果都是是 0/1 各一半的可能性；给定 Daniel 选 0 的情况同理。另一种方法是利用 mod 运算。

v2.0 槐花饼

但是这里就有一个问题。Daniel 比较聪明，他等 Jan 选好了输入进去之后，再进行选择，由于协议的交互对于两人来讲是公开的，他能看到 Jan 的选择。如果看到 Jan 选 0，那他就选 0；如果看到 Jan 选 1，那他就选 1。异或起来永远是 1，这样无论 Jan 怎么选择都是 Daniel占 据优势。

为了防止这种作弊行为，这时候我们引入新的机制：承诺。也就是说，要让 Daniel 即使知道 Jan 选择了什么，也不能根据 Jan 的选择去更改自己的选择。怎么做呢？在第一个承诺阶段，我们先让他们把随机数签名，签名结果输入进协议。在这样的情况下，通过第二个揭示阶段，把签过名的随机数输入进去，与第一个阶段的承诺进行比对成功之后，再异或出结果，获得我们想要的随机数。签名而不采用哈希函数的目的，是为了保证输入的随机数是由本人输入，而不是别人伪造输入的，然而在区块链的设定下，我们可以直接使用哈希函数，因为通常区块链的交易都是带有签名的。

v3.0a 一个比特币一碗的蛋炒饭

但是这样还不够，还有问题。假设此时 Terry 来了，这次他们一共三个人要决定一份蛋炒饭的所有权。多了一个人之后，Daniel 发现事情有转机，他又想到了个主意：如果最后结果看起来不太妙，不是我吃的话，我就不进行揭示阶段直接假装晕倒。刚才的协议之下，我们实际上规定了只有所有人都输入的情况下，参与者才有输出结果。假如参与者承诺，但却没有揭示，那怎么办？是重新再来一遍，还是就取剩下两个人的输入呢？这两种方法是都有问题的：如果要重新来一遍，那么攻击者就可以通过这种方法在每次自己不利的情况下强行使得协议重新运行；如果只取剩下两个人的输入，攻击者同样可以选择是否放弃输入来趋利避害。因此，我们需要有惩罚机制来保证参与者不得随意放弃。当参与者在承诺的时候，必须要向协议上交一个比特币——如果是带有智能合约的区块链的环境，这样的操作十分容易。如果Daniel 不按时揭示，那就没收 Daniel 的比特币分给 Jan 和 Terry。由于蛋炒饭的价值通常并不会超过一个比特币，Daniel 不会选择这样的方式进行作弊。这样的一个惩罚机制，就是为了防止拒绝服务攻击。

v3.0b 集齐七颗龙珠才能召唤的蛋炒饭

除了惩罚之外，还有另外一种方式，我们称之为集齐七颗龙珠才能召唤的蛋炒饭。简单来讲，就是之前的 coin-tossing 的协议，再追加一个门限机制。我们可以理解为对于拒绝服务这种攻击，我们增强了系统的健壮性，使得它能够容忍一定程度的拒绝服务。这样的门限机制总的说来有三种。

第一种门限机制是简单地取前 t 个输入。但是这种方式不抗女巫攻击，假设 Daniel 是黑客帝国的复制人，他复制了一万个自己，这样，Daniel 有很大的可能占有前 t 个输入，等同于控制了整个随机数。因此，这种门限的方法是不抗女巫攻击的，只能用在 permissioned 环境下，在知道总人数的情况下，只取前 t 个。

第二种方法有三种形式：一种是无分发者的秘密分享；另一种是无分发者的可验证秘密分享；最后一种是无分发者的公开可验证秘密分享。这些都归入到使用无分发者的秘密分享这一类，秘密分享可以将一个秘密分成多个碎片，只有集齐一定数量才能将秘密恢复出来。当然，这三种方式是有区别的。第一种无法验证，秘密碎片可以被伪造。第二种是秘密碎片可被验证，但是验证不是每个人都可以做的，每个人只能验证自己的份额。最后一种是可被公开验证的，每个人都可以验证所有的秘密碎片。这种方式需要每产生一个随机数都进行一次秘密分享来保证门限机制。比如说有 N 个人，假设只需要有 t 个人提交了就能输出我们想要的随机数，我们需要 r 个这样的随机数。因此我们需要这 N 个人相互交互至少r轮。另一个局限是，方案需要在许可环境下实施，协议必须知道总人数 N，才能知道门限 t。

无分发者的秘密分享首先要分发，比如说 Jan，把他的随机数分成三份，发给 Terry 和 Daniel 每人各一份。每个人都像 Jan 这样做之后，每个人手上都有 3 份来自不同的人，包括自己，的份额。此时，再把这些份额拼成份额向量广播给所有人，这样每个人只要手里有两份（包括自己的）这样的向量就能恢复出 Jan、Daniel 和 Terry 三人的随机数，然后就可以算出最终的随机数。而无分发者的公开可验证秘密分享，在分发的时候多了一些数据。这些数据就是proof。所有人通过收到的 proof 验证收到的份额。验证通过就可以说明这个份额确实和其他发出去的份额是一致的。

无分发者的秘密分享

无分发者的公开可验证秘密分享

第三种方法是分布式密钥生成+门限签名。门限签名可以理解为秘密分享应用到了签名方案中，但是它又不是单纯将两者相叠加。通常的签名是，一个人用自己的私钥加密了消息之后，大家可以用公钥进行验证。而该方案使用的门限签名则是，同样有一对公私钥，但是每个人分别只有私钥的其中一个碎片；每个人可以利用自己碎片进行签名，这些签名可以被公钥的相应碎片验证；并且，这些碎片中的任意 t 个合起来可以计算出来一个可以被完整的公钥验证的签名。因此，这样的签名过程并不需要所有人参与，只需要 n 个人中的 t 个人的有效签名就可以了。而且无论是哪 t 个人，最后生成的签名是一样的。并且签名过程中涉及到的私钥不会被泄露，这使得多轮无交互签名成为可能。当然，这个总的公私钥对不是凭空出来的，它的生成需要所有人在一开始运行分布式密钥分发协议才能生成有这样的密码学特性的公私钥对。同时，这个方案还是存在必须要知道总人数的问题。

v4.0 桂花糕

在这里介绍下这四个项目：Algorand、Cardano，Dfinity 和 Randao 分别是如何利用上述三种基本的方案构建随机数生成协议的。

Algorand 的共识过程利用了随机抽签，它的随机抽签所依赖的种子本质是通过取前t个输入来生成的。Algorand 的共识过程要求节点先在本地抽签，通过一个 Verifabale Random Function 算出来一个可验证的确定的随机数，这样的随机数是根据上一轮的公共信息加上每个节点自己的私钥计算出来的，是唯一确定的，并且可被其他人验证。随机数被用于每个节点的本地抽签。本地抽签后，每个人知道自己是否被选中。之后，被选中的人广播抽签结果、证明和候选区块到全网节点，根据区块的 quality 大小，选出来候选区块。而确定哪个区块的 quality 更大是需要做 BA 共识的，这个时候，就需要再进行一轮本地抽签，所有的节点会自己知道是否被选中去做 BA*（一个拜占庭类型的共识），去投票选自己认为的 quality 最高的候选区块，投票会进行很多轮，每一轮都要重新进行一次本地抽签。可以看出，Algorand共识的本质就是我们每个人都生成一个随机数。但是我们最终只想要一个随机数，这样我们才能根据最后确定的随机数去决定哪个块会被全网接受。这个时候的方案就是根据某种确定的规则从众多备选结果中取一个，方法是通过拜占庭共识达成一致，这就是 Algorand 的核心思想。

Dfinity。它的机制和 algorand 很像，也需要一个委员会，委员会会运行一个分布式的生成随机种子的协议。一样，我们先假设已经有了这样的随机数种子了，这样，随机数种子可以被利用算出每一个节点的排名。同时节点可以注册进入不同的组，不同的组中可以有相同的节点。委员会就是在这些组中随机挑选的一个，随机种子是刚刚提到的那个种子。此时，大家都可以提交候选区块，广播给所有的节点，但是在所有人做区块认证的时候，诚实节点总是会选择排名最高的块签名，签好后，广播给所有的节点，直到节点收到或拥有某个获得一半以上签名的区块。一轮的公共种子实际上是根据上一轮的种子以及开始设置的密钥对唯一生成的。其实就是无分发者的秘密分享加上门限签名的方案。首先，在最开始，会有一次分布式密钥生成来进行初始化配置。此时，组内的 n 个人必须要全部参与到这个协议中。通过这样一种方式，每个人获得一把私钥的一个碎片，以及用来验证这些碎片正确性的证明，这个碎片是用来做门限签名的。私钥的碎片，用来对上一轮生成的随机数和轮数拼在一起的字符串进行签名，然后广播之。这样的 n 个签名中只需要任意t个就可以拼出完整的可被公钥验证的签名，这个签名就是当前轮的随机数。整个过程，算法是确定的，对于一个节点来讲，唯一不确定的是其他人的签名结果。值得注意的地方就是 Dfinity 此处采用基于 BLS 的门限签名方案，这个方案的第一个好处就是仅需要进行一次全局设置。之前提到的秘密分享，每次都需要分享一次给每一个人。但是使用门限签名，除了密钥分发的阶段，之后的阶段只需要 n 个人中 t 个人提交有效的签名即可得出结果。第二个好处就是唯一性，无论哪 t 个人提交，最后对同样消息生成的签名都是相同的，这保证了最后生成的随机数是无法被偏移的。

随机数与共识

随机数生成与共识协议有着千丝万缕的关系，主要体现为以下两点。

防止女巫攻击的方法之一是不可预测的随机抽签。不论是 PoW，还是 PoS，我们都可以理解为一种随机抽签的方法。不管公有链上的共识协议再怎么设计，包括比特币在内，都是在通过某种方式产生一定的随机性。矿工通过 PoW 竞争出块，使得出块的人变得不确定，从而防止了通过伪装大量节点获利的女巫攻击。

区块链上的随机数安全依赖于共识协议。以 Randao 为例，针对 Fomo3D 的攻击同样对 Randao 有效。由于以太坊的激励机制和共识协议的特点，矿工会优先打包手续费高的交易，所以攻击者可以通过 Censorship Attack，人为调整打包区块时包含的交易，或者制造高手续费的垃圾交易，迅速的把区块的 Gas Limit 耗光，阻止其他人的特定交易上链。当 Randao 即将计算出的结果不理想时，可以通过这种方式强行将协议终止，令无辜的节点蒙受损失，自己从中获利。尽管这样的手段有时成本较高，但这样的攻击仍然有无法忽略的可能性发生，而这样的攻击之所以成立的原因，实际上根植于共识协议的设计。再例如 Grinding Attack。

Fomo3D 采用了取上一个块的哈希值作为种子的方法生成随机数。这种情况下，矿工可以把所有的区块组织的可能性都试验出来，然后选择一种对自己最有利的方式打包交易。这种攻击手段就是 Grinding Attack。尽管这样的攻击手段有一定的成本，但是如果随机数所牵涉的利益足够，例如用在某些赌博游戏里，矿工想要从中获利非常容易。

因此，区块链上随机数的生成是需要上下文环境的，必须要给定情景。拿 Randao 来讲，如果它的某一个随机数的生成，只和 0.01 个 eth 相关，那么攻击者将没有足够的理由去破坏它的公平性。如果押金不够多，那么 Randao 就有可能是不安全的。

作者简介：

邱飞旸，清华大学本科毕业生，黑客马拉松爱好者，Blockchain Dev Meetup 讲师之一。主要研究方向有：分布式共识、密码学。Blockchain Dev Meetup 是由「Nervos」基金会和「秘猿科技」 赞助的技术分享活动，我们是崇尚开源、务实笃行的极客团队。