作者：BlockPunk 社区：果壳宇宙（ID:DfinityFun） 前言 4000年前的东方大陆，萨满缓慢的从篝火的灰烬中扒出龟甲，龟甲上随机的裂纹会决定部落下一次狩猎的时机；3000年前的地中海，尊贵的雅典神官主持着抽签仪式，他们要随机选出五百位优秀公民，来参与城邦政务的讨论；2000年前的中东，行商围坐在一张赌桌旁，紧张的注视着桌面上转动的四面骰子，它的最终结果会决定一大笔财富的归属。 在上千年的人类历史里，我们一直不断地探寻着可靠的随机数，并将随机数用在生活的各个方面，民主与共和的抽签制度，战争时期的军情传递、生产上的模型计算，以及赌博娱乐时的可信参照。 对可靠随机数的追求，更是人类对公平的追求，对随机数的承认，可以说是人类最早的关于公正的共识。而在2000多年后的现代，人类发明了计算机，开始了崭新的数字纪元，随机数成为了整个虚拟世界的基础。 真随机数 我们祖先朴实的技术而言，人类创造了很多生成随机数的方法，但这些随机数的随机强度与不可预测程度，并不比烧龟甲来的更高。 这里就要讲到真随机数与伪随机数了。古代的人类观察物理世界时，会发现到处都存在着随机的波动，这种随机性在他们看来，是上天的旨意，你完全没法预测未来会怎么样。真正的随机性，只存在于物理世界，大气噪声、宇宙背景辐射、放射物的衰变期、量子塌缩现象，通过观测这些现象，得到的随机数是完全无规律可循的。 《百万乱数表》图片来自网络 上世纪40年代，兰德公司利用模拟电路制成的电脉冲发生器生成了100万个随机数，并将其出版为《百万乱数表》，一直销售到今天。现在看来这似乎是一个异想天开的行为艺术，但在当时却是非常重大的突破。 熔岩灯 有趣的是，在互联网时代的今天，仍有人在使用这种方法。一家名叫Cloudflare的云服务商，通过图像识别实时处理熔岩灯中蜡的形状，计算量化来获取真随机数，从而对数据进行高强度的加密。这听起来好像有些愚蠢，但其实它的随机强度，却远强于现在主流的随机数。 假随机数 我们可以从物理现象中得到神秘而无穷的随机性，但有些现象并不能精确量化。但同时我们需要巨量的随机数来加密数据、训练模型、公平仲裁，仅依靠自然界的随机数是远远不够的。 这也是计算机之父，冯诺依曼思考过的。在1946年， 冯诺依曼参与了美军氢弹的设计，他在一台名为ENIAC的计算机上，模拟计算核聚变的过程。而这个模型的训练，需要对随机数进行快速的存取，但ENIAC的内存不够大，无法保存长真随机数，因此冯诺依曼设计了一个算法，来模拟一个随机性的混乱状态。 ENIAC计算机 | 图片来自网络 这个算法是这样的：首先获得一个很短的随机值，比如操作时刻的毫秒数，作为这个算法的“种子”，然后将“种子”平方，输出平方结果的中间部分数字，再作为“种子”重复上述操作。重复足够的次数后，就获得了一个“随机数”。 这被称为平方取中法，这也只是无数假随机数算法中的一种，这个算法输出的序列，只取决于最初种子的随机性。由于机器的确定性，同样的种子，就可以计算出同样的随机数。 种子的位数决定了随机数的随机度，当你设定一个两位的种子生成一个10位随机数，在函数产生重复循环之前，最多只能得到100个可用的随机数；而在自然界中，10位随机数应该存在一百亿种可能。这两者之间巨大的数量级差别，就是随机数真与假的区别。 只要你使用基于“种子”的假随机数，必然会出现重复循环的过程，也就是说，只要知晓了你的随机数算法，另一台计算机迟早能暴力尝试出相同的随机数。这就是区块链钱包的密钥生成随机函数被攻破后，暴力盗取密钥的手段。 假随机数存在规律的周期，点集中表现为脉络 图片来自网络 当然这种随机数是足够使用的，我们必须引入计算机科学中非常重要的一个概念，时间边界，也就是在多长的时间里，这个随机数是安全不重复的。和我们使用密码车锁一样，我们知道正确的密码必在一万种的组合方式之中，但一个个尝试需要花费好几天时间，这个时间边界内都算是安全，假随机数也是如此。 我们闭眼敲键盘的随机字符串，其实也有规律可循，这就是QWER的键盘布局，通过分析后破解随机数的可能性就会很大 这依然无法满足区块链的使用要求，因为我们需要一个能在固定时间内，分布式的获取随机数的方法，而不能依赖于任何一个中心主体。 区块链为什么需要随机数 在传统互联网中，随机数是作为密码学与隐私安全的基础，通过共享随机的密钥，两个节点间就可以进行加密的私人通讯，而在区块链中，就是使用私钥密钥传输财产；同时随机数还广泛应用于有限带宽下的多节点通讯，可以利用随机数来决定数据发送的合理顺序，来协调多方节点，在区块链上，就是利用基于随机数的共识算法，协调交易确认者，保证一段时间内大家只对部分节点的消息进行反馈更新，从而在网络消息数有限的情况下获得一致。 而在区块链与加密的世界里，随机数上再次投射出了人类对公平的追求。我们的世界是随机的，过去无法更改，但未来不可预测，这是对生命最大的公平。区块链上一样，我们通过随机数的可信，脱离人性的干扰，获得链上的公正性，保证整个系统的去中心化程度与可信性。特别是权益证明PoS越来越火的现在，我们比以往任何时候都需要一个安全、稳定、可信的随机数，来保证密钥对的生成、链上数据的加密、出块权力的裁定、智能合约的运行。 总结 公平的决定出块权力，维持一致性共识。部分PoW与PoS机制下，依靠随机数选定出块者或者出块组的，包括DPoS机制下的循环出块的顺序，也是依靠随机数决定。 私钥的生成。目前私钥只要由各钱包自定随机数方法生成，存在较大安全隐患。 链上应用的随机数源。保证博彩、游戏、抽奖、分发、调查等应用的公平公正，此类容易被黑客攻击。 数据加密。链上数据因为是公开审查的，需要强度较高的加密，通过足够强的随机数确保链上数据的隐私与安全。 链上随机数的难点 虽然区块链还是基于过去的互联网技术，但是在随机数生成部分却有着非常大区别。 传统的随机数产生方式是中心化的，产出的随机数，与特定机器的状态值、物理状态相关，而同一个随机数算法，在不同的节点上得到的随机数是不同的，并且也没法针对每一个随机数进行验证，因此传统的方式无法产生一致性的随机性，这和区块链不兼容。 因此区块链上的随机数，需要重头开始设计机制，从而来获得满足分布式特点的结果。因此到目前为止，没有真正意义上完美的方案，区块链上的真随机数是缺失的，连假随机数都很难获得。 链上随机数的原则 1.不可预测 因为随机数决定着整个协议层包括所有以上层级的公正性，如果这个随机数是能提前预见的，那么就可以伺机发动攻击。当然这个不可预测性是存在时间边界的，一般以区块链时间为边界，通过控制计算难度，或设置等待，来增加预测的难度。简而言之，有两种方案： 保证随机数从区块时间上看是串行的（VRF/VDF） 保证随机数产生的难度，并按情况调节难度（哈希碰撞） 2.不可干扰 随机数决定着区块（非拜占庭容错系统中）的共识确认，因此如果能干扰到随机数的发生，无需掌握超越上限的节点/算力，就可以间接的控制区块链未来的走向，虽然干扰可能很微小，但多次干扰积累下来就会出现较严重的问题（“放大攻击”）。有两种解决方案： 保证随机数生成是非交互的（阀值签名方案），或完全根据节点本身状态计算（哈希碰撞） 设置随机数生成时延，需要等待长时间的复杂计算才能得出随机数，让干扰者无法预估自己施加的影响 3.可验证 应该详细表述为，可被简单验证，这表示随机数必须能够被任何节点快速进行验证其合法性，这样分布式的节点才能通过检验随机数，确认某一节点的出块资格，从而达成一致性。如果验证效率很低，需要很长时间，那么节点间共识的达成就会遥遥无期，区块链无法使用。 不符合上述原则的一些解决方案 为了解决区块链上的随机数难点，自发的产生了许多解决方案，以下简述以下不符合上述三个原则的方案，虽然他们各自都有自洽的逻辑与一定的安全性，但在现阶段还是存在问题的，在对安全需求不是那么高的地方仍可以使用。这不不针对某个项目，而是指出相似范式的问题 1.使用链下真随机数 不在链上计算随机数，而是使用从物理现象中获得的真随机数，比如大气噪声、电子脉冲，以及依赖包含热噪声电路的芯片组。但是对区块链来说，链下部分是不可见的，默认就是不可信的，链下获得随机数一定需要一个第三方上传至链上，这不仅违背了区块链的去中心化精神，完全无法验证，且存在篡改与提前预知的风险。就算使用预言机来去中心化的获取链下的真随机数，但仍存在物理上的人为干扰。因此这种方案非常不可取。 2.将当前块的数据作为随机源 很多的链上博彩类Dapp，都习惯直接引用最近区块的哈希根值等作为合约的随机种子，再来产生随机数。虽说简介的借助了链上算力的保证，如此产生的随机数看似足够有公信力，但需要考虑到多维度的安全性。首先，区块上的数据是透明的，所有节点都能获取，攻击者同样能用来攻击合约，唯一的障碍就是不开源的随机数算法。第二点，出块人获得出块资格后，可以尝试变更打包交易顺序、尝试打包不同交易，来产生最有利于他的哈希根值，从而扩大自己中奖的概率，这对其他参与者是不公平的。 3.借助分布式组织产生随机数 因为随机数的强度来源于种子的随机性，因此就有人提出由一个分布式组织来产生足够随机的种子，依赖与本地节点的特殊状态或控制者的“自由意志”，向链上上传秘密与验证，以特殊算法组合种子，再在链上产生随机数。先不论链下的合谋可能（有经济设计制约），这种方案还是存在“最后参与者攻击”的可能，也就是最后一个上传秘密的参与者，可以知道此前的全部秘密，他可以控制自己的秘密来干扰最终随机数的产生。且在掌握了函数算法后，可以预测影响的规律，如此可以多次施加干扰，进而不断扩大自己的影响，这就是“放大攻击”。 三类方案 虽然区块链上的随机数并不完美，但随这越来越多的项目认识到了随机数对效率和冗余度的巨大优化，随机数的可信与高效显得越来越重要。因此这里总结了三类相对成熟方案，并指出了相关项目与方案优缺点。 哈希碰撞 在PoW系统中，矿工的客户端有一个基于本节点状态的随机数发生器，可以输出随机数序列，然后再计算其哈希值，一但生成的哈希值在规定的大小范围内，就是为获得了出块资格，其他节点获取这个随机数值，计算一次哈希值即可进行验证，因此它的验证是十分简洁的。 因此这个随机数得经历数百兆亿次随机数发生后，才有机会获得一个符合要求的随机数，因此它的随机程度非常的高；同时由于得出随机数消耗的资源非常大，想要提前几个区块预测这个随机数几乎是不可能的；由于随机数完全根据节点本身状态输出随机数，因此这个随机数不会其他攻击者干扰；即时的难度调整（调整哈希值的大小范围），在安全时间边界内不会出现被攻破的情况。 PoW的共识特点，使得其天然具备随机性的（randomness for free）。 优点： 随机性最强，安全性号，非常适合驱动共识层； 产生随机数时不需要使用网络带宽。 缺点： 计算冗余度，计算消耗大，资源浪费； 难以在应用层使用； 不具备唯一性，可以同时存在多个满足要求的随机数，可能导致区块分叉； 无法抵抗并行加速破解，计算机持有多的人可以连续预测多个随机数。 可验证随机函数（VRF） VRF（Verifiable Random Function）算法于1999年由莫卡利教授提出，由于其较好的安全性与效率，被越来越多区块链项目拿来优化共识过程，让共识的随机数部分占用计算资源变少，让资源更多地被交易的确认与合约的运行所占用。 集合上图简述生成步骤： 0.生成随机数签名专用公私钥对； 1.获得一个足够随机的种子，可以直接使用上一轮结果，与区块高度、时间的变量等进行组合； 2.用随机数私钥对之进行签名（共同参与随机数生成），或是先签名再组合； 3.对签名后的值做哈希摘要，得出最新的随机数； 4.检查随机数是否在合法范围中，判断是否抽签成功进入出块组（部分项目不需要这个过程） 5.根据公钥与轮次等输入，计算证明，接受随机数后验证者使用函数进行验证。 因此这样产生的随机数，节点可以轻松验证其是否合乎算法，"Verifiable"就这样做到了；而经过足够复杂的算法，加上哈希摘要过程，获得足够随机分布的结果，“Random”得到了保证。 VRF主要结合PoS机制一起使用，来进行出块人（群）的随机选择，个别项目中直接决定区块的一致性选择。这个随机数的生成过程可以完全在一个节点的链下运行，同时也可以整个运行在链上。 需要注意的是签名随机的部分，VRF的这个签名随机算法应当具备唯一性，也就是说用同一把密钥，对同一个数据签名随机多次，只有唯一的一个随机数能被公钥验证，这就能防止产生随机数时，多次运行签名随机部分，来获得最有利于自己的随机数。 优点： 算力要求低，产出随机数效率高； 产生唯一性、确定性的随机数，不易出现分叉； 验证可滞后于随机数产生，适合进行秘密选举； 可设置为（输入为上轮结果）抗并行加速破解，矿机多者也无法连续预测随机数。 缺点： 验证步骤较多，秘密选举下需要多次验证； 随机数分布均匀性不好，因为是根据特点密钥计算的； 带宽占用高，延时长，是为让秘密选举的节点互相确认，BLS项目问题不大； Algorand 每一个节点都获取前一轮确认区块上的随机种子，集合轮次时间等，在链下单独运行VRF函数，然后对结果进行哈希摘要，节点将结果与网络中哈希值范围进行比较（比较类似于PoW哈希比对），范围内的成员便有资格参与验证与出块。…