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

我们生活的环境充满了随机性。运气、概率和命运的概念长期以来一直与随机性联系在一起。人类无法理解或预测的所有事物都倾向于被归类为随机的。生理上，我们也沉浸在随机的海洋中。从云的运动到粒子和波的行为，随机性几乎无处不在。

然而，尽管人类接触到了各种随机的事物，并且对随机性很熟悉交易区块哈希值如何生成，但仍然很难将其转化为计算机可以使用的东西。当我们谈论计算机系统中的随机性时，我们真正的意思是伪随机性，即在现实世界中尽可能多地模拟随机性，使其尽可能接近“真正的随机性”。以密码安全的伪随机数生成器为例，它是一种非常强大的随机性模拟。

随机数在隐私技术和密码学中发挥着重要作用。令人惊讶的是，通过生成随机数对消息进行异或运算提供了一种简单但非常强大的加密方案。即使是两方之间最简单的私人通信形式（即双方预先共享密钥的对称加密方案）也要求共享密钥是随机的。如果这个共享密钥不是随机的，加密是没有用的，因为任何知道密钥生成算法的人都可以确定密钥并解密消息。

随机数的重要性不仅体现在安全通信通道的建立上，还体现在通信对象的确认上。如果多人试图通过有限带宽的通道相互通信，则可以使用随机数来确定通道传送消息的合理顺序。

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

区块链是多方试图从全球角度就某种更新达成一致（共识）的成功案例。更新通常在一轮中完成，即在一个周期性的离散时间间隔内完成。

在互联网上，在一定时间内发送消息的数量（即吞吐量）是有上限的，并且发送消息必须花费一定的时间（即延迟），所有这些都对共识施加了一定的约束. 任何区块链共识协议的目标都是在上述约束范围内达成共识协议。公链上有数千个节点参与区块链的维护。如果每个节点都需要向其他所有节点发送消息并获得反馈，那么网络的局限性将大大增加达成共识的成本。这是因为一轮中通过网络发送的消息数量太大。因此，为了确保共识，需要通过减少通过 Internet 发送的消息数量来优化通信方案。

比特币实现这一协议（中本聪共识）的方式是使用工作量证明（PoW）作为随机数的来源交易区块哈希值如何生成，以确定在每一轮中将哪个区块添加到区块链中，从而减少消息传递。成本。由于 PoW 设置的问题在算法上非常难以解决，只有先解决的人才能将他们的块添加到分类帐中。由于多人同时解谜的概率非常低，PoW 可以作为一种机制来限制网络消息传递的数量。

理论上，任何试图取代 PoW 的共识机制都需要找到一种方法来限制网络可以传递的消息数量。大多数股权证明（PoS）协议用来解决这个问题的方法是根据验证者持有的代币数量选举一组验证者（维护和管理区块链的节点）组成一个小组委员会，并且那么这组 Validator 可以在网络范围内相互通信，并及时达成共识。

当然，为了公平选举小组委员会成员，确保没有人事先知道成员的身份，算法必须能够纳入一些公平无偏的随机数来源。一旦验证者组就下一个区块达成一致，该区块就会广播给网络中的每个人。

PoS 协议中小组委员会选举的理想随机数来源必须是无偏的，即没有人可以随意更改随机种子。为了实现不可处置性，随机性协议需要保证以下两点：

（注：我们将在以后的博文中探讨 i) 和 ii) 之间的权衡，以及这种权衡与网络同步模型的关系）

我们在 Mechanism Labs（一个 Twitter 帐户）上分析的小组委员会选举协议均不符合上述两点。因此，考虑到上述权衡，区块链共识协议应该使用可以连续生成随机数的随机数源，而不是一次只能生成一次性随机数的随机数源。因为区块链协议需要保证区块链在不让随机数来源成为瓶颈的情况下不断增长。即使对于共识优先的协议，随机数的来源也不应该是区块链停滞的原因。无论如何，nonce 源应确保协议可以专注于其他攻击，例如对验证者小组委员会的 DoS 攻击，使区块链陷入停顿等。

如果由于随机函数输出的随机数有偏差而导致区块链完全停止运行，社交层不得不付出巨大的协调成本来重启区块链。这将需要社区通过外部社交媒体平台就区块链的实际含义达成一致，这将是一个耗时的讨论，与首先解决 DAO hack 的成本相当。社交层的巨额成本也会动摇社区对区块链协议安全的信心，但只要偏差很小且有机制从偏差状态中恢复，几轮小偏差的影响对区块链的安全性比较薄弱，因为每一轮公链协议中给予验证者的所有协议奖励都比较小。对于小组委员会选举的每一轮或每一轮（每隔几轮），随机函数中的偏差必须非常大，以至于验证者可以欺骗协议以获取利润并降低区块链协议的安全性。

在另一个方面，使用随机数的彩票游戏必须确保随机数源永远不会被操纵，因为即使是轻微的偏差也可以完全改变中奖结果。篡改彩票结果的影响是巨大的，因为中奖者会立即获得巨额奖励。因此，这个彩票游戏更喜欢一次性生成非一次性随机数的函数，即使这意味着随机函数的输出有时会停止。

本文将探讨无偏随机数来源在区块链协议设计中的重要性。在接下来的文章中，当我们考虑不可变协议时，我们倾向于使用不能暂停的协议。

一个理想的委员会选举方案应该 i) 不被支配，并且 ii) 只在新一轮开始时显示随机种子。如上定义，随机函数必须是不可偏转的。如果随机数被操纵（并且有协议内的奖励分配机制），就会造成奖励分配不公平。奖励分配不当意味着一些人会得到更慷慨的奖励。由于只有拥有权益的人才能成为验证人，而投票权与验证人的权益成正比，分配不公将导致区块链最终被少数验证人控制。因此，协议的非操纵程度决定了是否有人可以长期维护部分网络作为验证者。另一方面，在新一轮开始之前种子提前多长时间显示，决定了谁首先成为网络的一部分。可以看出，以上两个属性将决定区块链的去中心化程度。

由于小组委员会的选举发生在每一轮（或 epoch）中，从发布随机函数输出的随机数到该轮（或 epoch）开始所需的时间至关重要。在此时间范围内，攻击者可以使用随机函数输出的随机数来知道选择了哪些验证者。如果此输出被隐藏，试图攻击区块链协议的攻击者将无法提前知道所选择的验证者。这个时间范围的长短决定了协议抵御攻击的能力。更强的攻击者，即具有更多计算能力和资源来攻击网络的攻击者，可以在短时间内计算出选定的验证者。如果攻击者有足够的时间，他们将通过运行选举委员会使用的算法和为该轮提供的随机数种子来确定哪些验证器被选出，然后对该轮选定的验证器执行拒绝服务 (DoS) 攻击，这导致创建的空白块，在这一轮没有任何进展。对于区块链来说，即使停止一轮也可能是毁灭性的。想象一下，如果世界上没有人可以在几个小时内进行任何交易，比特币会是什么样子！因此，能够抵抗 DoS 攻击的节点首先应该成为验证者。另外，提前暴露种子也意味着共识协议只能对付较弱的攻击者，削弱了区块链的去中心化特性。然后对该轮选定的验证者执行拒绝服务 (DoS) 攻击，这会导致创建空白块，在该轮中没有任何进展。对于区块链来说，即使停止一轮也可能是毁灭性的。想象一下，如果世界上没有人可以在几个小时内进行任何交易，比特币会是什么样子！因此，能够抵抗 DoS 攻击的节点首先应该成为验证者。另外，提前暴露种子也意味着共识协议只能对付较弱的攻击者，削弱了区块链的去中心化特性。然后对该轮选定的验证者执行拒绝服务 (DoS) 攻击，这会导致创建空白块，在该轮中没有任何进展。对于区块链来说，即使停止一轮也可能是毁灭性的。想象一下，如果世界上没有人可以在几个小时内进行任何交易，比特币会是什么样子！因此，能够抵抗 DoS 攻击的节点首先应该成为验证者。另外，提前暴露种子也意味着共识协议只能对付较弱的攻击者，削弱了区块链的去中心化特性。想象一下，如果世界上没有人可以在几个小时内进行任何交易，比特币会是什么样子！因此，能够抵抗 DoS 攻击的节点首先应该成为验证者。另外，提前暴露种子也意味着共识协议只能对付较弱的攻击者，削弱了区块链的去中心化特性。想象一下，如果世界上没有人可以在几个小时内进行任何交易，比特币会是什么样子！因此，能够抵抗 DoS 攻击的节点首先应该成为验证者。另外，提前暴露种子也意味着共识协议只能对付较弱的攻击者，削弱了区块链的去中心化特性。

基于我们在对替代共识协议的元分析中剖析的不同区块链协议的用例，下面我们将从技术角度详细介绍各种随机数生成机制。

嫩薄荷

Tendermint 使用确定性的循环协议方案来选举提议者；协议不是随机的。提议者是根据基于投票权和验证者被选举次数的堆排序算法选出的。攻击者只能通过添加或移除质押来干扰协议，但这种干预无法立即生效，因为验证者需要很长时间才能移除或添加系统中的质押。尽管如此，攻击者有更长的时间提前计划如何操纵提议者的选择。

使用确定性随机算法意味着随机种子在每轮之前就已经公布，并且可以提前确定提议者。

阿尔戈兰德

Algorand 的随机数方案如下：每个被选为提议者的验证者 v 使用公式 < seedr, π > ← VRFskv (seedr−1||r) 计算轮次 r 的种子，其中 skv 是验证者 v 的密钥，seedr- 1 是上一轮的随机种子。

VRF 用于证明第 r-1 轮接受的块包含 π 和第 r 轮的种子。如果给定的 VRF 证明无法验证给定的种子，则每个人都会计算新一轮的种子 H(seedr-1||r)，其中 H 是哈希函数。这意味着必须提前选择每个验证者的密钥，以确保它们不会干扰随机种子。

当网络不能很好地同步时，攻击者可以完全控制消息链接（证明说明：这里感觉像是一个“异步”假设），因此可以删除提议的块并强制用户支持空白块，从而计算 A未来选举的随机种子。因此，Algorand 需要弱同步假设，即在每个时间长度 u 内，必须存在时间长度 s (s < u) 的强同步，以保证协议的不可操作性。只要 s 的值足够大，以至于在时间段 b 内至少产生一个诚实块，选择密钥 skv' 的攻击者 v' 就不能在 r 轮内操纵随机种子。

只有在提出一个区块后，才会生成一个新的随机数种子，以及一个可用于验证的公共 VRF 证明。这确保了提议者和随机种子不会提前泄露，同时保证 Algorand 能够抵抗针对提议者的 DoS 攻击，即使在节点离线甚至暂时损坏时也能实现自适应安全性。

确定性

对于大多数协议，攻击者通常会中止协议以调用回退机制，从而操纵随机数。但是 Dfinity 使用的阈值方案是不可操纵的，因为选择阈值是为了确保攻击者不能通过阻止阈值签名的生成来中止协议（因为随机数种子来自阈值签名）。因此必须根据以下公式选择阈值 t：t ∈ [f + 1, n - f]，其中 f 是攻击者控制的签名数，n 是方案中的签名总数，t是用于生成随机数阈值的签名。选择此阈值是为了确保攻击者既无法预测签名生成的结果，也无法阻止签名生成。

需要注意的是，在任何 BLS 方案中，只要攻击者拥有超过 50% 的押金，他们就可以操纵最终的签名和 nonce。但是，如果攻击者拥有如此大的权益，那么其他类型的攻击也可能发生，这违反了 Dfinity 协议的基本假设。

一旦诚实的验证者进入第 r 轮，就会显示随机种子。虽然诚实验证者进入与新一轮正式开始之间的时间差很小，但对于拥有大量计算资源的攻击者来说，识别并拒绝提议者就足够了。这就是为什么 Dfinity 只能对付温和的攻击者而不能对付瞬间瘫痪的原因。

雷氏菌

在哈希函数实例化的随机数预言机方案中，提议者将根据以下公式确定：H_nonce(pk,q) < Dp，其中 H 是用作随机数预言机的哈希函数，pk 是验证者，q是给定的迭代时间，nonce 是散列函数的熵源。Nonce 由前一个区块的提议者选择。设置难度参数 D_p，以便在单个迭代时间内，以概率 w 选择委员会成员作为提议者。

如果攻击者提出一个块，她可以操纵为下一轮哈希函数生成熵的随机数，从而影响谁提出下一个块。但是，为了降低随机数方案的可篡改性，哈希函数中相同的nonce值不仅用于选择下一轮的proposer，还用于选择下r轮的proposer。这使得攻击者在计算上难以通过强制改变随机数值来连续成为下 r 轮的提议者。虽然这种策略只会失去多项式安全性，但它具有可预测性的缺点（稍后讨论）。该方案只能处理慢自适应攻击者。

在上述算法中，当哈希函数重复使用相同的 nonce 值播种时，它可以让攻击者提前预测出提议者是谁。由于在一个 epoch 中重复使用相同的 nonce 值作为熵，随机种子在新一轮开始之前被泄露，从而允许攻击者破坏提议者或执行 DoS 攻击。

卡斯帕 FFG

Casper FFG 计划使用的随机数方案基于以下算法：

在一个 epoch 开始时，每个验证者提交 H(H(H(…Sv ))))，其中 S 是验证者提交的种子。R 被赋值为 R 和哈希函数中的原像的异或运算（R := R⊕ 哈希内层的原像）。在一轮中，验证者可以创建或中止一个块。

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

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

随机数是密码学和区块链的重要组成部分。糟糕的随机数方案会通过以下方式破坏区块链的安全性： i) 停止区块链协议；ii) 导致中心化。因此，探索随机性在区块链协议中的作用是理解区块链安全的重中之重！