区块链中的随机性

区块链中的随机性

随机事件在我们身边无处不在。比如，运气、概率和命运就与随机性密不可分。人类不理解或无法预测的一切事物往往被归类为随机事件。

随机事件在我们身边无处不在。比如，运气、概率和命运就与随机性密不可分。人类不理解或无法预测的一切事物往往被归类为随机事件。物理世界中也有许多随机事件，比如云的运动、粒子和波的轨迹等。然而，尽管它是那么的令人熟悉，人类却很难将周围的随机性转化为计算机可以计算的东西。

本文作者Aparna Krishnan，由格密链社区的周志强翻译。

当我们谈论计算机系统中的随机性时，我们指的是伪随机性，这是一种对现实世界随机性的模拟产物。不过，这两种随机性很难区分。我们在这里要讨论的是非常强大的模拟性随机（伪随机）。

随机性在隐私技术和密码学中发挥着重要作用。值得惊叹的是通过一个随机值与一条信息就能提供一种简单而强大的加密方案。比如对称密钥加密技术，两方进行交流时需要事先共享一个保密密钥，但即使是进行最简单的交流也需要确保共享密钥是随机的。如果此共享密钥不随机，则任何人都可以通过已知的密码算法与信息内容窃取保密密钥，加密也就失去了意义。

随机性的作用：

利用随机性可以在两个人之间构建一个安全的通信渠道，也可以用来确认通信双方的身份。此外，如果同时有很多人想通过有限带宽的通信渠道彼此通信，则可以使用随机性来公平地确定消息传递的顺序。随机性也可以用来帮助一群人或计算机达成一致。随机共识协议就是这样一个例子。这篇文章将探讨随机性在区块链中的作用。

区块链是帮助多方在全球层面上就某种程度的更新达成共识的完美例子。更新通常按照回合的方式完成，每个回合是一个周期性的离散时间段。

一般限制共识的的因素有两个：吞吐量（在互联网上的特定时间段内可以发送的消息数量上限）以及延迟（消息通过互联网发送所需的时间）。任何区块链共识协议的目标都是克服上述限制因素达成共识。在公链中，数千个节点参与维护区块链，如果每个节点都需要向其他所有节点发送消息并等待来自所有其他节点的响应，吞吐量与延迟将会让达成共识的成本大幅增加。成本高昂是因为一个回合中传递的信息数量太过庞大，因此为了达成共识而优化网络沟通方案的一个方式就是削减信息的数量。

比特币达成共识的方式（中本聪共识）是使用工作量证明（PoW）作为随机源确定每轮中哪一个区块将被添加到区块链中，从而减少消息传递的开销。因为PoW的计算非常复杂，且只有第一个解决难题的人拥有记账的权利，再加之多人同时解答出难题的概率极低，PoW机制就通过这种方式限制了网络中的信息数量。

当然，任何试图取代PoW的共识机制同样需要一种方法来限制网络传递的消息。大多数的权益证明协议（PoS）解决此问题的方法是选择验证者（即维护/管理区块链的节点），并根据他们抵押代币的数量成立一个委员会小组。然后，该验证小组可以在网络限制下合理地来回通信，最终高效地达成共识。

什么是理想的随机源：

当然，为了公平地选择这个委员会小组的成员并且保证没有人提前知道成员名单，算法必须要得到一些公平且不可篡改的随机源。一旦该验证小组在新区块上达成一致，该区块就会被广播给网络中的其他所有节点。

PoS协议中用于选择委员会成员的理想随机源应确保不可被篡改，随机性协议则需要确保以下两点：

i）随机性函数持续有输出
ii）随机性函数的输出尚未被操纵（注意：我们将在以后的文章中探讨如何平衡第一第二点，以及这与网络同步模型的关系）

我们机械实验室（Mechanism Labs）分析了当下所有的委员会成员选举协议，结论是没有一个协议能同时实现高性能与不可篡改。我们的看法是，鉴于上述权衡，区块链共识协议应选择一个始终有输出的随机源，而不是单单产生无篡改输出的随机源。这是因为区块链协议需要确保链持续增长且不能让随机源成为限制发展的因素。即使对于一致性协议，随机源也不应该是限制区块链发展的原因。总之，随机源应该为协议减轻负担，使协议能够专注于减轻其他攻击，如针对委员会小组的DoS攻击。

如果区块链由于随机性函数停止输出而完全停止，在社会层面上将需要巨大的协调成本来重新启动区块链。社群需要花费大量的时间通过外部社交媒体平台就区块链的形式达成一致，这样做的成本与解决DAO黑客的成本相当。这种巨额成本也会动摇社区对区块链协议安全性的信心。

另一方面，只要偏差很小并且存在修正偏差的机制，仅仅几轮的轻微偏差带给区块链安全性的影响也会很小。这是因为在每一轮公共区块链协议中给予验证者的协议内奖励相对较小。但是由于每轮或每个时期（一组轮次）都会选择新的小组委员，因此在随机性函数中总会存在某个显著的偏差，让验证者可以钻空子赚钱并导致区块链协议的安全性降低。此外，主打随机性的彩票游戏需要确保随机源不被操纵，因为即使一点偏差也会改变彩票的赢家。这是因为篡改彩票结果的效果是巨大的，可以获得了大量的即时奖励。因此，这样的游戏适合仅保证无篡改输出的随机性函数，即使这意味着随机函数的输出有时会停止。

不可篡改随机源的重要性：

接下来我们将讨论在设计区块链协议时不可篡改的随机源的重要性。下文开始，我们提到的协议默认都是不会停止的协议。

理想的委员会选举方案须具备以下两点：

1.不可篡改
2.只在新一轮的开始时显示随机种子。

鉴于上述两点，随机函数也需要具有不可篡改性。如果随机性可以被操纵（并且存在协议奖励分配机制），就会导致奖励的不公平分配。不公平的奖励分配意味着一些人获得更多的奖励。由于只有那些有抵押的人才能成为验证者，并且投票权与验证者所拥有的权益资产成正比，结果将导致区块链最终被某些人掌控。

可以说，哪个协议抗篡改的程度高，它就能在长远中获得维持部分网络的权力。另外，在新一轮回合开始之前公布种子的时间提前量决定了谁可以首先成为网络的一部分。因此，上述两个属性将决定区块链的去中心化程度。

用于选择委员会小组的协议是每一轮或每几轮运行的，因此从该随机函数的输出发布的时间到回合开始的时间是至关重要的。在此时间范围内，攻击者可以使用随机函数的输出来确定哪个验证节点会被选中。如果这个输出被隐藏，则试图攻击区块链协议的攻击者将无法提前确定验证节点。此时间范围的长度决定了协议可以承受的攻击者的强度。强大的攻击者（即具有更多算力和资源攻击网络的人）能够在很短的时间内算出验证节点。如果攻击者有足够的时间，通过委员会成员选择算法和给定轮次的随机种子，就能够确定验证节点。确定验证节点后，攻击者就能够对验证节点发起DoS攻击，从而导致空块以及步骤缺失。

区块链即使只停止一轮也会有非常可怕的后果。想想如果世界上所有人在几个小时内无法进行任何交易，比特币会发生什么！因此，应该选择抗DoS攻击的节点成为验证节点。另一方面，提前揭示随机种子意味着共识协议只能抵抗较弱的攻击，这减弱了区块链的去中心化属性。

现有随机性生成机制：

下面我们将详细介绍各种随机性生成机制。以下内容基于我们在《替代共识协议的元分析》中分析的区块链协议：

Tendermint
Tendermint共识机制使用确定性循环协议方案来选择提议者; 协议不具有随机性，提议者基于投票权和被选为验证者的次数确定。攻击者只能通过绑定或解除绑定权益对协议施加影响，因为这是对于协议的唯一输入手段。同时，协议不会在短时间内出现偏差，因为验证者需要很长时间才能绑定（即向系统抵押保证金）或者解除绑定（即从系统中撤回保证金）。不过，在这种机制下攻击者可以提早很久作出计划，误导提议者作出错误选择。
使用确定性随机算法意味着在每轮投票之前可以公开随机种子，不过提议者也会被提前确定。

Algorand
Algorand共识机制中的随机性方案如下：每轮被选为验证者的v会为回合r计算出种子，公式为<seedr, π > ← VRFskv (seedr−1||r)，公式中skv是验证者v的密钥，seedr−1是前一轮的随机种子。

r-1轮接受的块中包含VRF证明π和r轮的种子。如果给定的VRF证明未验证给定的种子，每个人将用加密哈希函数来计算新一轮的种子，公式为seedr=H (seedr-1) || r)。这意味着每位验证者必须选择好自己的密钥，以确保种子不会发生偏差。

当网络不是强同步时，如果攻击者完全地控制住消息传递链接，进而删除区块提议并强制用户就空块达成一致，就能借此计算出后续的随机种子。因此，Algorand需要弱同步，即在每个长度为u的周期中，必须存在长度为s <u的强同步周期，使协议具有抗偏差性。只要强同步时期s足够长使得b时间段内产生至少一个诚实的区块，选择密钥的攻击者v'就不能使r轮的随机性种子产生偏差。

只有当一个块被提出时，新种子和VRF证明才会去公开地验证它。这确保了提议者和随机种子不会提前泄露。这确保Algorand能够抵御针对提议者的DoS攻击，并且在擦除与瞬时腐化中保持自适应安全性。

Dfinity:
在几个协议中，攻击者通常会通过中止协议来调用回退机制，从而引入偏差。Dfinity使用的阈值方案是抗偏差的，因为阈值的选择是为了防止攻击者通过阻止阙值签名（阙值签名是随机种子的创造来源）来中止协议。这使得阙值需要符合以下公式：t∈[f + 1，n - f] 其中f是攻击者控制的签名数，n是方案中的签名总数，t是生成随机性所需的签名阈值。符合条件的阈值确保了攻击者无法预测签名创建的结果，更无法阻止签名的创建。

需要注意的是，如果攻击者拥有任何BLS方案中所有存款的50％以上，就能够操纵最终的签名和随机性。但是，如果攻击者真的拥有如此大的股权占比，他们也会有其他的攻击选择，这就打破了Dfinity协议的基本假设。

只要有诚实的验证者前进到第r轮，随机种子就会被公布。虽然诚实的验证者到达r轮与新一轮正式启动之间的时间差距很小，但这个差距足以让拥有大量算力的攻击者找到提议者并发起DoS攻击。这就是Dfinity只能承受轻度适应性攻击而不能承受瞬时腐化的原因。

Thunderella:
在哈希函数实例化的随机预言方案中，提议者由以下公式确定：H_nonce(pk，q)<Dp 其中H是作为随机预言的哈希函数，pk是验证者的公钥，q是给定的时间步骤，而nonce是哈希函数的熵来源。nonce由前一个块的提议者决定。设定难度参数D_p使得在单个时间步骤中，委员会成员被选为提议者的概率为w。

如果攻击者提出了一个块，他就可以影响下一轮哈希函数的熵来源（nonce），进而影响下一个块中选出的提议者。这种情况下，为了减少随机性方案的偏差值，哈希函数会使用相同的熵来源选择r轮的提议者而不是下一轮提议者。因此攻击者很难暴力改变熵来源，也就无从成为下一轮的提议者。不过这种策略仅能保证多项式安全损失，它伴随着对可预测的妥协，这一点将在后文讨论。总之，该方案导致这个协议仅能够承受慢速适应攻击。

在上述算法中，当重复使用相同的熵来源为哈希函数提供种子时，会导致攻击者能够提前预测出提议者。在一个时期内相同的熵来源被重新用作熵，会导致随机种子在新一轮的开始之前被泄露。造成的后果为攻击者可以腐化提议者或者发起DoS攻击。

Casper FFG:
Casper FFG计划使用的randao方案采用以下算法：
在轮次开始时每个验证者都提交H(H(H(... Sv))))，其中S是验证者提交的种子。R：=R⊕双层哈希表内层的原像。在一个回合中，验证者可以生成或中止一个区块。

如果在回退机制中不具有随机性，这似乎是比随机性可预测或可偏差更严重的问题，因为那样你不再需要1/3的恶意节点才能中止协议，而是1个人就足够。只需要满足，那个人验证者当前是提议者，且下一轮的种子已经公布，即可1个人中止协议。