原文作者：Joseph Bonneau 和 Valeria Nikolaenko
原文标题：Public Randomness and Randomness Beacons
共随机性是许多现实世界安全协议的重要组成部分。在某些应用程序中，例如赌博和多人游戏，随机性会增加乐趣。在其他应用中，随机性提供了一种公平的方式来分配不可分割的资源，从绿卡到巡回法院法官的案件分配，再到体育比赛的种子。它还用于分配负面资源，例如税务审计或机场的二次安检。
传统上，我们依赖受信任的权威来为这些协议生成随机性，但在 web3 世界中，我们需要做得更好。在这篇文章中，我们将探索通过分布式随机信标构建可公开验证的随机性的方法，然后讨论一些链上应用程序。（即将发布的第二部分将特别关注领导人选举，同时提供对替代领导人选举方法的评估。）
生成随机数是一项众所周知的微妙任务。例如，许多加密密钥已经泄露，因为它们依赖于一个有缺陷的随机数生成器（Cloudflare 的熔岩灯墙可以作为一种创造性的缓解措施）。然而，这只是私人随机性，只有一方需要生成和使用它。
相比之下，公共随机性是一个多方参与过程，这大大增加了难度。产生公共随机性的良好协议将具有以下安全属性：
无偏倚：任何攻击者或攻击者联盟都不应该能够使输出产生偏差。可靠：任何攻击者都不能阻止协议产生输出。
可验证：任何人都可以轻松验证协议输出，并且应该看到与其他人相同的输出。
不可预测：如果协议在 T1 时间产生输出，那么在某个时间 T0＜T1 之前，没有人应该能够预测关于输出的任何事情，理想情况下，T0 非常接近 T1。
无偏倚是比不可预测性更弱的属性，因为任何不可预测的协议都必须是无偏的。计算机科学家会说，无偏倚会降低为不可预测性，因为如果你有偏见，你就可以预测。但有时我们会想要分别推理它们，因为它们可能依赖于不同的假设——例如，不诚实的多数人可能会预测结果，但不会对其产生偏见。
除了这些属性之外，该协议还应该能够高效地运行并产生大量随机位。（在实践中，应用程序生成 128 个随机位通常就足够了，使用它们来播种伪随机数生成器 [PNRG] 以根据需要输出更多位。但是，对于输出的每个单独位都应保持不可预测性，以用于此类应用程序作为彩票或资源分配。）理想情况下，该协议在通信和计算成本方面也应该是有效的。
不同的协议可能会在不同的条件下实现这些属性。例如，某些协议可能不受任何 f1 恶意节点联盟的偏见，并且无法被任何 f2＜f1 恶意节点联盟预测。也有不同程度的偏见。例如，在某些协议中，参与者可能能够将输出偏置“一位”——这意味着他们可以在两个可能的输出之一之间进行选择。其他攻击可能允许他们完全修复输出。然而，通常情况下，我们根本不想容忍任何偏见（或可预测性）。
密码学家通常从考虑问题的理想解决方案开始。在公共随机性的情况下，随机信标是一种理想化的服务，它定期产生满足所有必要安全要求的随机输出。
这种理想化的随机信标，类似于其他加密抽象——例如随机预言或通用组模型——在现实世界中并不存在。但这是一个有用的目标，也是一个有用的模型来推理依赖公共随机性的协议。
我们可以考虑一些理想随机信标的近似值。
集中式信标：产生良好随机性的最简单方法是通过具有 NIST 随机性信标或 random.org 等服务的集中式第三方，它从大气噪声中产生随机性，并经认证可用于赌博。这种对第三方的依赖完全破坏了去中心化的理念。实际上，在上面的示例中，我们必须相信相关组织正在正确地生成随机性，而无需任何加密证明。
物理随机性展示：许多传统彩票依赖于公共展示，例如，可能包括有人伸手伸入一个装有不同数字的乒乓球容器。不幸的是，这些通常很容易操作。例如，某个球s 可以放在冰箱中，然后可以告诉选择器选择冷的。
自然信标：一个常见的想法是使用随机的自然现象，如天气或宇宙背景辐射作为信标。不幸的是，所有提议的来源都没有提供强烈的共识。不同的观察者会看到略有不同的值，这需要重新引入可信方进行官方测量，具有中心化信标的所有缺点。
半集中式信标：更好的方法是直接从比特币区块头或股票收盘价中获取随机性，这更容易公开验证，任何一方都更难以完全控制。然而，对工作量证明区块链随机性和股价随机性的微妙攻击仍然存在。例如，使用区块链标头，矿工可以选择保留标头产生他们不喜欢的信标值的块。或者，他们可以选择在根据首选信标输出找到两个碰撞块时打破平局。
解决集中式信标问题的一种自然方法是设计一个分散的密码协议来产生公共随机性。这个问题有点像设计去中心化的共识协议，只是更难。不仅所有参与者都需要就输出（随机性）达成一致，而且协议中的恶意参与者也不应该对输出产生偏见或预测。
旨在模拟随机信标的协议称为分布式随机信标 (DRB)。（其他名称包括“distributed coin-flipping”。）这个问题已经研究了几十年，在 1980 年代证明了著名的不可能结果，但在区块链时代重新点燃了兴趣。DRB 可用于提供链上随机性，这将是公平、安全和透明的链上应用程序的关键要素。
在乐观情况下，一个非常简单的两轮协议足以满足 DRB 的需求。在第 1 轮中，每个参与者 i 生成一个随机值 ri 并发布一个密码承诺 ci=Commit(ri)。在这个应用程序中，承诺可以简单地是一个像 SHA-256 这样的哈希函数。在每个参与者的承诺发布后，他们被锁定在他们选择的 ri 中，但承诺不会透露有关其他参与者贡献的任何信息。在第 2 轮中，每个参与者通过发布 ri 来“开启他们的承诺”。然后组合所有随机值，例如通过对它们进行异或或（最好）散列它们的连接。
该协议很简单，只要其中一个参与者随机选择他们的 ri，就会产生随机信标输出。不幸的是，它存在一个典型的缺陷：当所有参与者都透露了他们的随机值时，最后一个参与者能够计算假定的信标输出。如果他们不喜欢它，他们可以拒绝发布他们的值，中止协议。忽略错误参与者的贡献并不能解决问题，因为这仍然让攻击者在两个信标输出之间进行选择（一个用他们的贡献计算，一个不计算）。
区块链为这个问题提供了一种自然的补救措施：每个参与者都可能被要求将一些资金放入托管中，如果他们不透露他们的随机贡献，这些资金就会被没收。这正是以太坊上经典的 RANDAO 信标所采用的方法。这种方法的缺点是输出仍然可能有偏差，如果托管中的资金少于信标结果上的资金量，这对攻击者来说可能是值得的。更好地抵御偏向攻击的安全性需要将更多的代币放入托管中。
一些协议不是试图强迫所有各方透露他们的随机贡献，而是包含一个恢复机制，这样即使少数参与者退出，其余参与者也可以完成协议。重要的是，协议在任何一种情况下都产生相同的结果，这样各方就不能通过选择是否退出来偏向结果。
实现这一目标的一种方法是让每个参与者向其他参与者提供其秘密的共享，以便他们中的大多数人可以使用例如 Shamir 的秘密共享来重建它。然而，一个重要的属性是其他人可以验证提交的秘密是否已被正确共享，这需要使用更强大的原语，称为可公开验证的秘密共享 (PVSS)。
其他几种恢复机制也是可能的，但它们都有相同的限制。如果有 N 个参与者，并且如果任何最多 f 个节点的组退出，我们想要弹性，那么任何 N-f 个参与者组都必须能够计算最终结果。但这也意味着 N-f 参与者的恶意联盟可以通过私下模拟恢复机制来提前预测结果，这也可能发生在协议的第一轮，在此期间，这样的联盟可以修改他们自己的随机性选择并使结果产生偏差。
换句话说，这意味着任何 N-f 个节点的联盟必须至少包含一个诚实节点。通过简单的代数，N-f > f，所以 f < N/2，这些协议本质上需要诚实的多数。这与原始的 commit-reveal 安全模型有很大不同，后者只需要 f< N（至少一个诚实的参与者）。
这些协议通常还需要大量的通信成本来在协议的每次运行中在所有节点之间共享额外的 PVSS 信息。在过去的几年里，研究界在这个问题上做了相当多的工作，研究提案包括 RandShare、Scrape、SecRand、HERB 或 Albatross，但似乎都没有看到实际部署。
意识到一组 N-f 个参与者可以计算上述协议中的随机信标值，导致了一种更简单的方法：在 N 方之间共享一个长期密钥，并让他们使用它来评估可验证随机函数 (VRF)。密钥通过 t-out-of-N 阈值方案共享，因此任何 t 参与者都可以计算 VRF（但较小的联盟不能）。对于 t=N-f，这为 f 个恶意节点提供了与上面讨论的 commit-reveal-recover 协议相同的弹性。
DFINITY 率先使用这种方法作为其共识协议的一部分，使用阈值 BLS 签名（用作 VRF）。独立的 drand 随机信标使用基本相同的方法，一组参与者阈值-BLS-在每一轮中签署一个计数器。熵联盟是 drand 的开源实例，它使用 16 个参与节点（截至 2022 年 9 月）每 30 秒产生一次随机性，由公司和大学研究小组共同运行。
这些方法的缺点是初始化阈值密钥相对复杂，当节点加入或离开时重新配置密钥也是如此。但是，在常见情况下，协议非常有效。
如上所述，简单地签署一个计数器值并不会在每轮中增加任何新的随机性，因此如果足够数量的参与者密钥被泄露，那么该协议将在未来的每一轮中都是可预测的。
Chainlink VRF 将这种方法（使用 NSEC5 VRF）与请求随机性的各方指定的外部随机源相结合，通常是实践中最近的区块链标头。然后，此数据通过 VRF 馈送，该 VRF 由一方运行或阈值化到一组。
以太坊的信标链目前使用基于 BLS 的 VRF：每一轮的提议者将他们的 VRF 值添加到组合中。与 commit-reveal 范例相比，这节省了一轮通信（假设长期 BLS 公钥注册一次），尽管这种设计继承了 commit-reveal 方法的一些警告，包括通过保留输出来偏置信标输出的可能性.
最后，一个有前途的新方向是使用基于时间的密码学，特别是可验证延迟函数 (VDF)。这种方法有望提供良好的通信效率和鲁棒性，并具有对 N-1 个恶意节点的弹性。
回到最初的 commit-reveal 协议，传统的承诺可以用定时承诺代替，以消除参与者拒绝透露他们的随机贡献的问题。定时提交可以由原始提交者或任何愿意计算慢函数（本质上是 VDF）的人有效地打开。因此，如果任何参与者退出提交-显示协议，他们的承诺仍然可以被其他人打开。至关重要的是，打开承诺的最短时间足够长，以至于不能在协议的第一轮（提交阶段）完成，否则恶意参与者可以足够快地打开其他人的承诺，从而修改自己的贡献并偏向结果.
现代 VDF 可以实现更优雅的一轮协议：完全放弃承诺。每个参与者可以简单地发布他们的随机贡献 ri，最终结果是每个参与者的贡献的组合，通过 VDF 运行。计算 VDF 的时间延迟确保没有人可以选择他们的承诺以使最终输出有偏差。这种方法由 Arjen Lenstra 和 Benjamin Wesolowski 在 2015 年提出为 UNICORN，并且确实是 VDF 开发中的关键激励应用。
这种方法已经看到了一些实际的部署。Chia 实现了一个版本作为其共识协议的一部分，在类组中使用重复平方的 VDF。Starkware 使用基于 SNARK 的 VDF 实现了基于概念验证的 VDF 信标。以太坊也计划使用这种方法，构建一个专用的 ASIC 来计算 VDF，以在共识层生成随机性。
公共随机性是许多协议的重要组成部分，但我们仍然缺乏任何提供高安全性的标准 DRB。设计空间很大，上述方法的许多混合和组合都是可能的。例如，可以将基于 VRF 的协议与基于 VDF 的协议结合起来，这会增加新的熵，例如 RandRunner 提出的。以太坊的信标链目前使用 VRF，但未来可能会添加 VDF，以消除区块扣留攻击的偏见可能性。
当诚实多数协议可以接受时，这也是一个悬而未决的问题。对于一个相对较小的、经过审查的参与者群体——比如熵联盟——诚实的多数假设是合理的。另一方面，只需要一个诚实参与者的协议有一个固有的优势——更多的参与者只能提高安全性。这意味着这些协议可能会在开放的、无需许可的参与下进行部署。
在第二部分中，我们将讨论随机领导者选举在共识协议中的具体应用，其设计目标略有不同，因此提出了更多的协议和方法。
Joseph Bonneau 是 a16z crypto 的研究合伙人。研究重点是应用密码学和区块链安全。曾在墨尔本大学、纽约大学、斯坦福大学和普林斯顿大学教授加密货币课程，并获得了剑桥大学的计算机科学博士学位和斯坦福大学的学士/硕士学位。
Valeria Nikolaenko 是 a16z crypto 的研究合伙人。研究重点是密码学和区块链安全、PoS 共识协议中的远程攻击、签名方案、后量子安全和多方计算等主题。Valeria Nikolaenko 在 Dan Boneh 教授的指导下获得了斯坦福大学的密码学博士学位，并作为核心研究团队的一员从事 Diem 区块链工作。
