区块链100讲：区块链中的随机数

2019独角兽企业重金招聘Python工程师标准>>>

我们生活的环境充满了随机性。一直以来&＃xff0c;运气&＃xff0c;概率和命运这些概念都与随机性紧紧联系在一起。所有人类无法理解或无法预测的事物往往都被归类为随机事物。从生理上来说&＃xff0c;我们也是沉浸在了随机海洋中。从云的运动到粒子和波浪的行为&＃xff0c;随机性简直无处不在。

然而&＃xff0c;尽管人类接触到了各种各样的随机事物&＃xff0c;对随机性很熟悉&＃xff0c;但依然难以将它转化为计算机可以使用的东西。当我们谈论计算机系统中的随机性时&＃xff0c;我们真正指的是伪随机性&＃xff0c;即尽可能模拟出现实世界应有的随机性&＃xff0c;使之近乎于“真正的随机性”。以密码学安全伪随机数生成器为例&＃xff0c;这是一个非常强大的随机性模拟。

随机数在隐私技术和密码学中发挥着重要作用。令人惊艳的是&＃xff0c;通过生成一个随机数来对一条消息进行异或运算&＃xff08;XOR&＃xff09;&＃xff0c;提供了一种简单但十分强大的加密方案。即使是双方之间最简单的私人通信形式&＃xff08;即双方提前共享密钥的对称加密方案&＃xff09;也要求共享的密钥是随机的。如果此共享密钥不是随机的&＃xff0c;则加密就毫无用处&＃xff0c;因为任何知道密钥生成算法的人都可以确定密钥然后解密该条消息。

随机数的重要性不仅体现在安全通信渠道的建立上&＃xff0c;还体现在确认通信对象上。如果多个人试图通过有限带宽的频道来互相通信&＃xff0c;则可以利用随机数来确定频道携带消息的合理顺序。

随机数能够有效帮助团体或计算机达成一致协议或共识。随机共识协议就是这样一个例子。本文将探讨随机数在区块链中的作用。

区块链就是一个多方尝试就全局视角的某种更新达成一致&＃xff08;共识&＃xff09;的成功案例。更新通常在一轮内完成&＃xff0c;也就是在一个周期性离散时间间隔内。

在互联网上&＃xff0c;特定时间段内发送的消息数量是有上限的&＃xff08;即吞吐量&＃xff09;&＃xff0c;并且发送消息必将花去一定的时间&＃xff08; 即延迟&＃xff09;&＃xff0c;这都对共识造成了一定的限制。任何区块链共识协议的目标是在上述限制范围内达成一致协议。在公链上有数千个节点参与了区块链的维护&＃xff0c;如果每个节点需要向所有其他节点发送消息并获得其反馈&＃xff0c;那么网络的限制会大大增加达成共识的成本。这是因为在一轮时间内通过网络发送的消息数量太大。因此&＃xff0c;为了确保共识&＃xff0c;则需要通过减少在互联网上发送消息的数量来优化通信方案。

比特币达成此协议&＃xff08;中本聪共识&＃xff09;的方式是通过使用工作证明&＃xff08;PoW&＃xff09;作为随机数源来确定每一轮中哪一个区块将会被添加到区块链中&＃xff0c;从而减少消息传递的费用。因为 PoW 设置的题目在算法上非常难解决&＃xff0c;只有最先算出来的人才能将他们的区块添加到分类帐中。由于多个人同时解开难题的概率非常低&＃xff0c;因此 PoW 可以作为一种限制网络消息传递数量的机制。

理论上&＃xff0c;任何试图取代 PoW 的共识机制都需要找到一种方法来限制网络传递消息的数量。大多数权益证明&＃xff08;PoS&＃xff09;协议用于解决该问题的方法是根据验证者持有的代币数量来选出一组验证者&＃xff08;维护与管理区块链的节点&＃xff09;组成一个小组委员会&＃xff0c;然后这组验证者可以在网络限制内相互通信并及时达成一致。

当然&＃xff0c;为了公平选举出小组委员会的成员&＃xff0c;保证没有人会提前知道成员的身份&＃xff0c;算法必须能够融入一些公平、无偏倚的&＃xff08;unbiasable&＃xff09;随机数源。一旦该组验证者在下一个区块上达成了一致&＃xff0c;那个区块就会被广播给网络中的每一个人。

在 PoS 协议中用于小组委员会选举的理想随机数源必须是不可支配的&＃xff08;unbiasable&＃xff09;&＃xff0c;即没有人可以随意改变随机种子&＃xff08;seed&＃xff09;。为了实现不可支配性&＃xff0c;随机性协议需要确保以下两点&＃xff1a;

随机函数总会生成一些随机数&＃xff1b;
随机函数生成的随机数没有被操纵

&＃xff08;注意&＃xff1a;我们在之后的博客文章中将会探讨 i&＃xff09;与ii&＃xff09; 之间的权衡&＃xff0c;以及这种权衡与网络同步模型的关系&＃xff09;

我们在 Mechanism Labs &＃xff08;一个推特号&＃xff09;上分析过的所有小组委员会选举协议都没有满足上面提到的两点。因此&＃xff0c;鉴于上述权衡&＃xff0c;区块链共识协议应该使用能不断产生随机数的随机数源&＃xff0c;而不是使用仅能一次性产生不可支配的随机数的随机数源。因为区块链协议需要确保区块链保持增长、不能让随机数源成为瓶颈。即使是偏好一致性的协议&＃xff0c;随机数源也不应该成为区块链停滞的原因。无论如何&＃xff0c;随机数源都应该确保协议能够专注于应付其他攻击&＃xff0c;比如对验证者组成的小组委员会实施 DoS 攻击使得区块链停滞等等。

如果区块链由于随机函数输出的随机数出现了偏差而完全停止运行&＃xff0c;那么社交层就得付出巨大的协调成本来重新启动区块链。这将要求社区通过外部的社交媒体平台就区块链实际上是什么的问题达成一致&＃xff0c;而这会是一个非常耗时的讨论&＃xff0c;此成本可与当初解决 DAO 黑客攻击的成本相当。社交层的巨额成本也会动摇社区对区块链协议安全性的信心&＃xff0c;但只要偏差非常小并且具备从偏差状态恢复的机制&＃xff0c;那么几轮的小偏差对区块链安全性的影响就比较微弱&＃xff0c;因为公有区块链协议每一轮给予验证者的所有协议奖励是相对较少的。每一轮或每一个时期&＃xff08;每几轮&＃xff09;进行小组委员会选举时&＃xff0c;随机函数中的偏差必须非常显著&＃xff0c;验证者才能以欺骗协议来牟利并降低区块链协议的安全性。

而在另一个领域内&＃xff0c;那些用到随机数的彩票游戏必须保证随机数源绝对不被操纵&＃xff0c;因为即使出现一点偏差也会完全改变中奖结果。由于中奖者能够获得大量的即时奖励&＃xff0c;所以篡改彩票结果带来的影响是巨大的。因此&＃xff0c;这种彩票游戏偏好于一次性生成不可支配随机数的函数&＃xff0c;即使这意味着随机函数的输出有时会停止。

本文将探讨基于区块链协议设计的背景下公正无偏的随机数源的重要性。接下来的文章中&＃xff0c;当我们考虑不可篡改的协议时&＃xff0c;我们是倾向于不会被中止的协议。

理想的委员会选举方案应该满足 i&＃xff09;不可被支配&＃xff0c;ii&＃xff09;只在新一轮开始时显示随机种子。随机函数必须如前文讨论的定义那样做到不可被偏转。如果随机数被操控&＃xff08;并存在协议内奖励分配机制&＃xff09;&＃xff0c;就会造成不公平的奖励分配。不恰当的奖励分配意味着一些人将获得更丰厚的奖励。由于只有拥有权益的人才能成为验证者&＃xff0c;并且投票权与验证者所拥有的权益成正比&＃xff0c;那么不公平的分配将导致区块链最终只掌控在少数验证者手里。因此&＃xff0c;协议的不可操纵的程度&＃xff0c;决定了是否有人可以长期作为验证者维护部分网络。另一方面&＃xff0c;种子在新一轮开始之前提前多久显示&＃xff0c;决定了谁可以首先成为网络的一部分。由此可见&＃xff0c;上述两个属性将决定区块链的去中心化程度。

由于每一轮&＃xff08;或每一个时期&＃xff09;都会进行小组委员会的选举&＃xff0c;因此从公布随机函数输出的随机数到那一轮&＃xff08;或那一个时期&＃xff09;开始所需的时间是至关重要的。在此时间范围内&＃xff0c;攻击者可以利用随机函数输出的随机数得知哪些验证者获选。如果此输出被隐藏&＃xff0c;则试图攻击区块链协议的攻击者将无法提前得知获选的验证者。此时间范围的长短决定了协议对攻击的承受能力。较强的攻击者&＃xff0c;即具有较多计算能力和资源去攻击网络的人&＃xff0c;能够在短时间内计算出获选的验证者。如果攻击者有足够的时间&＃xff0c;他们会通过运行选举委员会所用的算法以及该轮给定的随机数种子来确定哪些验证者当选&＃xff0c;然后对该轮获选的验证者进行拒绝服务&＃xff08;DoS&＃xff09;攻击&＃xff0c;导致空白区块的产生&＃xff0c;令该轮无任何进展。对区块链来说&＃xff0c;即使是停止一轮&＃xff0c;后果也是毁灭性的。设想一下&＃xff0c;如果几小时内世界上没有人可以进行任何交易&＃xff0c;比特币会变成什么样&＃xff01;因此&＃xff0c;有能力抗 DoS 攻击的节点才应该首先成为验证者。另外&＃xff0c;提前显示种子也意味着共识协议只能应对较弱的攻击者&＃xff0c;这弱化了区块链的去中心化性质。

基于我们曾在替代性共识协议的元分析中剖析的不同区块链协议的使用案例&＃xff0c;下面我们会从技术角度详细介绍各种随机数的生成机制。

Tendermint

Tendermint 是使用一种确定的循环协议方案来选出提议者的&＃xff1b;该协议不具备随机性。提议者是根据投票权和验证者被选次数的堆排序算法选出的。攻击者只能通过添加或删除权益来干预协议&＃xff0c;但这种干预不能立即生效&＃xff0c;因为验证者在系统中移除或者添加权益所需的时间很长。尽管如此&＃xff0c;攻击者就可以有更长的时间提前计划好如何操纵提议者的选择。

使用确定性的随机算法意味着随机种子会在远早于每一轮之前公布&＃xff0c;提议者也能被提前确定。

Algorand

Algorand 的随机数方案如下&＃xff1a;被选为提议者的每一位验证者 v 使用公式 ← VRFskv (seedr−1||r) 来计算 r 轮的种子&＃xff0c;其中 skv 是验证者 v 的密钥&＃xff0c;seedr-1 是前一轮的随机种子。

VRF 是用来证明 r-1 轮中接受的区块包含了 π 以及 r 轮的种子。如果给定的 VRF 证明未能验证给定的种子&＃xff0c;则每个人计算新一轮的种子 H(seedr−1||r)&＃xff0c;其中 H 是哈希函数。这意味着必须提前选好每位验证者的密钥&＃xff0c;确保他们无法干预随机种子。

当网络不能很好地同步时&＃xff0c;攻击者完全控制了消息传递链接&＃xff08;校对注&＃xff1a;感觉这里像在说“异步”假设&＃xff09;&＃xff0c;因此可以删除提议的区块并强制用户支持空白的区块&＃xff0c;从而计算出未来用于选举的随机种子。因此&＃xff0c;Algorand 要求弱同步假设&＃xff0c;即在每个时间长度为 u 的周期中&＃xff0c;必须存在时间长度为 s&＃xff08;s

只有当一个区块被提议之后&＃xff0c;才会生成一个新的随机数种子&＃xff0c;和一个可用来验证的公开 VRF 证明。这确保了提议者和随机种子没有被提前泄露&＃xff0c;同时保证 Algorand 能够抵御针对提议者的 DoS 攻击&＃xff0c;即使在节点离线甚至瞬间腐化的模式下都能实现自适应安全。

Dfinity

对于大部分协议&＃xff0c;攻击者通常会中止协议来调用回退机制&＃xff0c;从而操纵随机数。但 Dfinity 使用的门限签名方案&＃xff08;threshold scheme&＃xff09;是不可操纵的&＃xff0c;因为选择阈值的原则就是确保攻击者无法通过阻止生成门限签名来中止协议&＃xff08;因为随机数种子是从门限签名中推导出来的&＃xff09;。因此阈值 t 必须根据以下公式进行选择&＃xff1a;t∈[f &＃43; 1&＃xff0c;n - f]&＃xff0c;其中 f 是攻击者控制的签名数&＃xff0c;n 是方案中的总签名数&＃xff0c;t 是用于生成随机数的签名阈值。选择该阈值是为了确保攻击者既无法预测签名生成的结果&＃xff0c;也无法阻止签名的生成。

需要注意的是&＃xff0c;在任何 BLS 方案中&＃xff0c;只要攻击者拥有 50&＃xff05; 以上的保证金&＃xff0c;他们就能够操控最终的签名与随机数。然而&＃xff0c;如果一名攻击者拥有如此大份额的权益&＃xff0c;也会出现其它类型的攻击&＃xff0c;这种情况就违反了 Dfinity 协议的基本假设。

一旦诚实的验证者进入到第 r 轮&＃xff0c;随机种子就会被揭示。虽然从诚实的验证者进入到新一轮正式开始之间的时间差很小&＃xff0c;但这个时间差足以让具有大量计算资源的攻击者识别出提议者并对其进行 DoS 攻击。这就是为什么 Dfinity 只能应对温和的攻击者而无法应对瞬时瘫痪的状况。

Thunderella

在哈希函数实例化的随机数预言机方案中&＃xff0c;提议者将依据以下公式来确定&＃xff1a;H_nonce(pk,q)

如果攻击者提议了一个区块&＃xff0c;她可以操控为下一轮哈希函数生成熵的 nonce 值&＃xff0c;从而影响下一个区块的提议者的人选。然而&＃xff0c;为了降低随机数方案的可篡改性&＃xff0c;在哈希函数中相同的 nonce值不仅仅用于选择下一轮的提议者&＃xff0c;也会用于选择接下来 r 个轮次的提议者。这使得攻击者在计算上很难通过强制改变 nonce 值来让自己连续成为接下来 r 个轮次的提议者。虽然这种策略仅损失了多项式安全性&＃xff0c;但它具有可预测性的弊端&＃xff08;后面也会讨论到&＃xff09;。该方案仅能够应对慢速自适应的攻击者。

在上述算法中&＃xff0c;当重复使用相同的 nonce 值给哈希函数喂送种子时&＃xff0c;就会导致攻击者能够提前预测到谁是提议者。由于在一时期中相同的 nonce 值被重复用作熵&＃xff0c;从而导致随机种子在新一轮开始之前被泄露&＃xff0c;使得攻击者可以对提议者进行腐化或者实施 DoS 攻击。

Casper FFG

Casper FFG 计划使用的随机数方案是基于以下算法&＃xff1a;

一个时期开始时&＃xff0c;每个验证者承诺 H (H (H (..Sv ))))&＃xff0c;其中 S 是验证者承诺的种子。 R 赋值为 R 与哈希函数内原象的异或运算&＃xff08;R :&＃61; R⊕ Pre-image of the inner layer of hash&＃xff09;。在一轮中&＃xff0c;验证者可以创建或中止一个区块。

如果在回退机制中没有生成随机数&＃xff0c;这可能会造成比可预测或可操纵的随机数更大的问题&＃xff0c;因为你将不再需要 1/3 的恶意者来中止协议&＃xff0c;1个人就足够了。

作为当前提议者的验证者是知道下一轮的随机种子的。

随机数是密码学和区块链的重要部分。不良的随机数方案会通过以下方式破坏区块链的安全性&＃xff1a;i&＃xff09;停止区块链协议&＃xff1b;ii&＃xff09;导致中心化。因此&＃xff0c;在理解区块链的安全性时&＃xff0c;探究随机性在该区块链协议中的角色乃是重中之重&＃xff01;