NEAR：区块链协议中的随机性
我们今天发表了一篇简短的论文，描述了 NEAR 协议中使用的随机信标。在这篇随附的博客文章中，我们讨论了为什么随机性很重要，为什么它很难，以及它在其他协议中是如何解决的。
许多现代区块链协议，包括 NEAR，都依赖随机源来选择在协议中执行某些操作的参与者。如果恶意行为者可以影响这种随机性来源，他们可以增加被选中的机会，并可能危及协议的安全性。
分布式随机性也是构建在区块链上的许多分布式应用程序的关键组成部分。例如，接受参与者投注并支付两倍金额的 49% 而没有支付 51% 的智能合约假设它可以获得一个无偏的随机数。如果恶意行为者可以影响或预测随机数，他们可以增加在智能合约中获得支付的机会，并将其耗尽。
当我们设计一个分布式随机算法时，我们希望它具有三个属性：
它必须是不偏不倚的。换句话说，任何参与者都不能以任何方式影响随机发生器的结果。
它需要是不可预测的。换句话说，任何参与者都不能在生成之前预测将生成什么数字（或对其任何属性的推理）。
协议需要容忍一定比例的参与者离线或试图故意停止协议。
在本文中，我们将介绍分布式随机信标的基础知识，讨论为什么简单的方法不起作用。最后，我们将介绍 DFinity、Ethereum Serenity 和 NEAR 使用的方法，并讨论它们的优缺点。
RANDAO
RANDAO 是一种非常简单且因此非常常用的随机性方法。总体思路是，网络的参与者首先都私下选择一个伪随机数，向这个私下选择的数字提交一个承诺，所有人都使用某种共识算法就一组承诺达成一致，然后都透露他们选择的数字，达成一个对显示的数字达成共识，并将显示的数字的 XOR 作为协议的输出。
它是不可预测的，并且具有与底层共识协议相同的活性，但有偏见。具体来说，一旦其他人开始透露他们的号码，恶意行为者就可以观察网络，并根据迄今为止观察到的号码的异或来选择透露或不透露他们的号码。这允许单个恶意行为者对输出产生一点影响，而控制多个参与者的恶意行为者具有与他们控制的参与者数量一样多的影响。
RANDAO + VDF
为了使 RANDAO 无偏见，一种方法是使输出不仅仅是 XOR，而是比分配的显示数字所需的时间更多的执行时间。如果最终输出的计算时间比揭示阶段的时间长，则恶意行为者无法预测他们揭示或不揭示其数量的效果，因此无法影响结果。
虽然我们希望计算随机性的函数为生成随机数的参与者花费很长时间，但我们希望随机数的用户不必再次执行相同的昂贵函数。因此，他们需要以某种方式快速验证随机数是否正确生成，而无需重新进行昂贵的计算。
这种计算时间长、计算验证速度快、每个输入都有唯一输出的函数称为可验证延迟函数（简称VDF），事实证明设计一个非常复杂。最近有多项突破，即这一突破和这一突破，以太坊目前计划使用带有 VDF 的 RANDAO 作为他们的随机信标。除了这种方法不可预测且无偏见之外，它还有一个额外的优势，即即使只有两个参与者在线也具有活跃性（假设底层共识协议在参与者很少的情况下具有活跃性）。
这种方法的最大挑战是 VDF 需要以这样一种方式进行配置，即使是拥有非常昂贵的专用硬件的参与者也无法在揭示阶段结束之前计算 VDF，并且理想情况下具有一些有意义的安全余量，例如 10 倍。下图显示了一个参与者的攻击，该参与者拥有一个专门的 ASIC，允许他们运行 VDF 的速度比分配给揭示 RANDAO 承诺的时间快。这样的参与者仍然可以计算有和没有他们的份额的最终输出，并根据这些输出选择显示或不显示：
对于链接在专用 ASIC 之上的 VDF 系列，其速度可能比传统硬件快 100 倍以上。因此，如果揭示阶段持续 10 秒，则在此类 ASIC 上计算的 VDF 必须花费超过 100 秒才能获得 10 倍的安全裕度，因此在传统硬件上计算的相同 VDF 需要花费 100 x 100 秒 = ~3 小时.
以太坊基金会计划解决这个问题的方式是设计自己的 ASIC 并免费公开提供。一旦发生这种情况，所有其他协议都可以利用该技术，但在此之前，RANDAO + VDF 方法对于无法投资设计自己的 ASIC 的协议来说并不可行。
阈值签名
由 Dfinity 开创的另一种随机性方法是使用所谓的阈值 BLS 签名。（有趣的是，Dfinity 雇佣了 BLS 中的 L 人物 Ben Lynn）。
BLS 签名是一种允许多方在消息上创建单个签名的结构，通常用于通过不需要发送多个签名来节省空间和带宽。区块链中 BLS 签名的常见用法是在 BFT 协议中签名块。假设 100 名参与者创建了区块，如果其中 67 人签署了一个区块，则该区块被认为是最终的。他们都可以提交自己的部分 BLS 签名，然后使用某种共识算法对其中的 67 个达成一致，然后将它们聚合成一个 BLS 签名。任何 67 个部分都可用于创建累积签名，但生成的签名将不同，具体取决于聚合的 67 个签名。
事实证明，如果参与者使用的私钥是以特定方式生成的，那么无论聚合什么 67 个（或更多，但不是更少）签名，生成的多重签名都是相同的。这可以用作随机性的来源：参与者首先同意他们将签署的一些消息（它可能是 RANDAO 的输出，或者只是最后一个块的哈希，只要它是每次都不同并达成一致），并在其上创建多重签名。在 67 名参与者提供他们的零件之前，输出是不可预测的，但即使在提供第一部分之前，输出已经预先确定并且不受任何参与者的影响。
这种随机性方法是完全无偏见且不可预测的，并且只要 2/3 的参与者在线（尽管可以针对任何阈值进行配置），它就会一直存在。虽然 ⅓ 离线或行为不端的参与者可能会停止算法，但至少需要 ⅔ 参与者合作才能影响输出。
但是，有一个警告。上面，我提到这个方案的私钥需要以特定的方式生成。密钥生成过程，称为分布式密钥生成，简称 DKG，非常复杂，是一个积极研究的领域。在最近的一次会谈中，Dfinity 提出了一种非常复杂的方法，其中涉及 zk-SNARKs，这是一种非常复杂且未经时间测试的加密结构，作为其中的步骤之一。一般来说，对阈值签名，尤其是 DKGs 的研究还没有处于可以轻松应用于实践的状态。
随机分享
NEAR 方法受到另一种称为RandShare的算法的影响。RandShare 是一种无偏见且不可预测的协议，可以容忍多达 1/3 的参与者是恶意的。它相对较慢，并且链接的论文还描述了两种加速方法，称为 RandHound 和 RandHerd，但与 RandShare 本身不同，RandHound 和 RandHerd 相对复杂，而我们希望协议非常简单。
RandShare 的普遍问题除了交换的大量消息（参与者将一起交换 O(n^3) 条消息）外，事实上，虽然 ⅓ 在实践中是一个有意义的活跃度阈值，但影响的能力却很低。输出。有几个原因：
影响输出的好处可能大大超过停止随机性的好处。
如果参与者控制了超过 1/3 的 RandShare 参与者并使用它来影响输出，则不会留下任何痕迹。因此，恶意行为者可以在不被发现的情况下做到这一点。拖延共识是自然可见的。
某人控制 1/3 的算力/权益的情况并非不可能，并且鉴于上述 (1) 和 (2)，拥有此类控制权的人不太可能试图阻止随机性，但可以并且可能会尝试影响它。
NEAR 方法
我们最近发表的一篇论文中描述了 NEAR 方法。它是无偏见且不可预测的，并且可以容忍多达 1/3 的恶意行为者的活跃性，即如果有人控制 1/3 或更多的参与者，他们可以停止协议。
但是，与 RandShare 不同的是，它最多可以容忍 ⅔ 的恶意行为者，然后才能影响输出。这对于实际应用来说是明显更好的阈值。
该协议的核心思想如下（为简单起见，假设正好有 100 个参与者）：
每个参与者拿出他们自己的输出部分，将其分成 67 个部分，对其进行擦除编码以获得 100 个共享，这样任何 67 个都足以重建输出，将 100 个共享中的每一个分配给一个参与者并用该参与者的公钥。然后他们共享所有编码的共享。
参与者使用一些共识（例如 Tendermint）来就这些来自 67 个参与者的编码集达成一致。
一旦达成共识，每个参与者都会获取以这种方式发布的 67 个集合中的每个集合中的编码共享，这些共享是用他们的公钥编码的，然后解码所有这些共享并立即发布所有这些解码的共享。
一旦至少有 67 名参与者完成了步骤 (3)，所有商定的集合都可以被完全解码和重建，最终的数字可以作为参与者在 (1) 中提出的初始部分的 XOR 获得。
该协议为何无偏见和不可预测的想法类似于 RandShare 和阈值签名的想法：最终输出是在达成共识后决定的，但直到 ⅔ 的参与者解密用他们的公钥加密的共享时，任何人都不知道。
处理所有极端情况和可能的恶意行为使其稍微复杂一些（例如，参与者需要处理步骤（1）中有人创建无效纠删码的情况），但总的来说整个协议非常简单，例如用所有证明、相应的密码原语和参考来描述它的整篇论文只有 7 页长。如果您想阅读更正式的算法描述，或者对其活性和抗影响性的分析，请务必查看它。
利用纠删码的类似想法已经在 NEAR 的现有基础设施中使用，其中特定时期的块生产者创建所谓的块，其中包含特定分片的所有事务，并分发这些块的纠删码版本向其他区块生产者提供 merkle 证明，以确保数据可用性。
Last updated