公共随机性与随机信标

公共随机性是许多现实世界安全协议的重要组成部分。在一些应用中，例如赌博和多人游戏，随机性增加了乐趣。在其他应用中，随机性为分配不可分割的资源提供了一种公平的方法，从绿卡到将电路法庭法官分配给案件再到体育比赛的种子分配。它也用于分配负资源，如税务审计或机场的二次安全筛查。

传统上，我们依赖可信的机构为这些协议生成随机性，但在web3世界中，我们需要做得更好。在这篇文章中，我们将探讨通过分布式随机信标构建公开可验证随机性的方法，然后讨论一些链上应用程序。（即将发布的Part II将专门关注领导者选举，同时评估其他领导者选举方法。）

期望的属性

生成随机数是一项 notoriously subtle 任务。例如，许多加密密钥因依赖于有缺陷的随机数生成器（Cloudflare 的熔岩灯 lava lamps 本可以作为一种创意缓解措施）而被泄露。然而，这只是 私有随机性，其中仅一个方需要生成并使用它。

相比之下，公共随机性是一个多方过程，这增加了难度。一个有效的生成公共随机性的协议将具备以下安全属性：

• 不可偏置：任何攻击者或攻击者联盟都不应能够偏置输出。
• 可靠性：任何攻击者都不应能够阻止协议生成输出。
• 可验证：任何人都可以轻松验证协议输出，并应与其他人看到相同的输出。
• 不可预测：如果协议在时间 T 1 生成输出，那么在某个时间 T 0 <T 1 之前，任何人都不应能够预测输出，理想情况下，T 0 应该非常接近 T 1。

不可偏置性是比不可预测性弱的属性，因为任何不可预测的协议必须是不可偏置的。计算机科学家会说不可偏置性 减少 到不可预测性，因为如果你可以偏置，你就可以预测。但有时我们希望分别讨论它们，因为它们可能依赖于不同的假设，例如，不诚实的多数可能预测结果，但不偏置它。

除了这些属性外，协议还应该高效运行并生成大量随机位。（实际上，对于大多数应用，生成 128 个随机位通常就足够了，使用它们给伪随机数生成器 [PNRG] 设定种子，以根据需要输出更多位。然而，每个输出的个别位应保持不可预测，以便用于彩票或资源分配等应用。）该协议在通信和计算成本方面理想上也应高效。

不同的协议可能在不同条件下实现这些属性。例如，一些协议可能对于任何 f 1 恶意节点的联盟是不可偏置的，对于任何 f 2 <f 1 恶意节点的联盟是不可预测的。还有不同程度的偏置。例如，在某些协议中，参与者可能能够通过“一个比特”来偏置输出——这意味着他们可以在两个可能输出之间选择。其他攻击可能使他们完全固定输出。然而，通常情况下，我们不希望容忍任何偏置（或可预测性）。

加密理想：随机信标

密码学家通常会首先考虑其问题的理想解决方案。在公共随机性情况下，随机信标 是一种理想化的服务，它定期生成满足所有必要安全要求的随机输出。

这种理想化的随机信标，类似于其他加密抽象——如随机预言机或通用群模型——在现实世界中并不存在。但这是一个有用的目标，并且是一个有用的模型来推理依赖于公共随机性的协议。

我们可以考虑几个理想随机信标的近似。

• 中心化信标：生成良好随机性最简单的方法是通过一个与第三方服务，如NIST 随机信标 或 random.org，它们从大气噪音中生成随机性并获得赌博使用的认证。对第三方的这种依赖完全削弱了去中心化的理念。事实上，在上面的例子中，我们必须信任相关组织正确生成随机性，且没有任何加密证明。
• 物理随机展示：许多传统彩票依赖于公共展示，这可能包括例如某个人伸手到印有不同数字的乒乓球容器中。不幸的是，这些方式通常容易被操控。例如，某些球可以放入冰箱里，而选择者可以被告知挑选冷球。
• 自然信标：一个常见的想法是使用天气或宇宙背景辐射等随机自然现象作为信标。不幸的是，所有提议的来源并未提供强一致性。不同的观察者会看到略微不同的值，这需要重新引入一个可信方来进行官方测量，带来了中心化信标的所有缺点。
• 半中心化信标：更好的方法是直接从比特币区块头或股票收盘价格中获取随机性，这样更容易公开验证，并且更难被任何一方完全控制。然而，对于工作量证明区块链随机性和股票价格随机性仍然存在微妙的攻击。例如，对于区块头，矿工可以选择不公布那些产生不喜欢的信标值的区块。或者，他们可以选择在找到了两个冲突的区块时，根据自己喜欢的信标输出来打破平局。

去中心化随机信标（DRB）

解决中心化信标问题的自然方法是设计一个去中心化加密协议来生成公共随机性。这个问题有点类似于设计去中心化共识协议，只是更困难。不仅所有参与者需要就输出（随机性）达成一致，而且协议中恶意参与者无法偏置或预测输出。

设计用于模拟随机信标的协议称为分布式随机信标（DRB）。（其他名称包括“分布式抛硬币”。）该问题已研究了数十年，著名的不可行性结果在1980年代得到证明，但在区块链时代重新引起了兴趣。DRB可用于提供链上随机性，这将是公平、安全和透明的链上应用的关键组成部分。

经典方法：承诺-揭示协议

一个非常简单的两轮协议足以支持乐观情况下的DRB。在第一轮中，每个参与者 i 生成一个随机值 r i 并发布一个加密承诺 c i = Commit( r i)。在这个应用中，承诺可以简单是一个哈希函数，如 SHA-256。在每个参与者的承诺发布后，他们固定了对 r i 的选择，但承诺不会揭示其他参与者的贡献的任何信息。在第二轮中，每个参与者通过发布 r i “打开他们的承诺”。然后将所有随机值组合，例如通过进行异或或（最好）对它们的串联进行哈希。

该协议简单，并且只要即使有一个参与者随机选择他们的 r i，就会生成随机信标输出。不幸的是，它存在一个经典缺陷：当所有但一个参与者揭示他们的随机值时，最后一个参与者能够计算出假定的信标输出。如果他们不喜欢，他们可以拒绝发布他们的值，从而中止协议。忽略一个有缺陷参与者的贡献并不能解决问题，因为这仍然使攻击者在两个信标输出（一个是根据其贡献计算得出的，另一个则没有）之间选择。

区块链提供了这种问题的自然解决方案：可以要求每个参与者将一些资金放入保管中，如果他们不揭示他们的随机贡献，这些资金就会被没收。这正是经典的以太坊RANDAO 信标采用的方法。这种方法的缺点是输出仍然可以被偏置，这对攻击者来说可能值得，如果保管中的资金低于与信标结果相关的金额。要加强对偏置攻击的安全性，需要在保管中放入更多的硬币。

承诺-揭示-恢复协议

一些协议通过包括恢复机制来尝试使所有各方都显露他们的随机贡献，即使少数参与者退出，剩余的参与者仍然可以完成协议。协议在两种情况下产生相同结果很重要，以便各方不能通过选择是否退出来偏置结果。

实现这一目标的一种方法是让每个参与者 fournir给其他人其秘密的份额，使多数人能够重建它，例如，使用香农秘密共享。然而，一个重要的属性是其他人能够验证承诺的秘密已被正确共享，这需要使用一种称为公共可验证秘密共享（PVSS）的更强原语。

还有几种其他恢复机制，但它们都有相同的局限性。如果有 N 个参与者，我们希望在任意最多 f 个节点退出的情况下实现弹性，那么必须有 N-f 个参与者可以计算最终结果。但这也意味着一个恶意的 N-f 队伍可以提前预测结果，私下模拟恢复机制。这也可能在协议的第一轮中发生，这段时间这样的联盟可能会修改他们自己的随机选择并偏置结果。

换句话说，这意味着任何 N-f 的节点联盟必须至少包含一个诚实的节点。通过简单的代数，N-f > f，因此 f < N/2，这些协议天然需要一个诚实的多数。与只需 f<N（至少还有一个诚实参与者）的原始安全模型相比，这是一个显著的区别。

这些协议通常还需要显著的通信成本，以便在每次运行协议时在所有节点之间共享额外的PVSS信息。研究界在过去几年对此问题进行了大量工作，研究提案包括RandShare、Scrape、SecRand、HERB或Albatross，但似乎没有一个得到了现实世界的部署。

基于可验证随机函数的协议

意识到一组 N-f 参与者可以计算上述协议中的随机信标值导致了一个相对简单的方法：在 N 方之间共享一个长期秘密密钥，让他们使用它来评估可验证随机函数 (VRF)。秘密密钥通过一个 t-out-of- N 阈值方案共享，因此任何 t 参与者都可以计算 VRF（但更小的联盟无法）。对于 t = N-f，这提供了与上述承诺-揭示-恢复协议相同的对 f 恶意节点的弹性。

DFINITYpioneered这种方法作为其共识协议的一部分，使用阈值BLS签名（其作为VRF）。独立的drand 随机信标基本上采用相同的方法，在每轮中一组参与者对计数器进行阈值BLS签名。entropy 联盟 是一个开源的 drand 实例，每 30 秒产生一次随机性，目前总共有 16 个参与节点（截至 2022 年 9 月），由多家公司的大学研究小组组成。

这些方法的一个缺点是初始化阈值密钥相对复杂，当节点加入或离开时重新配置密钥亦是如此。然而，在普遍情况下，这些协议非常高效。

如上所述，仅仅签署计数器值并未为每轮增加任何新的随机性，因此，如果足够多的参与者密钥被泄露，则在未来的每一轮中，协议都将是可预测的。

链灵 VRF结合该方法（使用NSEC5 VRF）与所请求随机性的外部来源，通常在实践中是一个最近的区块头。这些数据随后通过 VRF 运行，由一方或按阈值分组运行。

以太坊的信标链 目前使用基于BLS的VRFs：每一轮的提议者将他们的VRF值添加到混合中。这与承诺-揭示范式相比，节省了一轮通信（假设长期常见的BLS公钥注册一次），尽管该设计继承了一些承诺-揭示方法的警告，包括通过不公布输出来偏置信标输出的可能性。

基于可验证延迟函数的协议

最后，一个有前途的新方向是利用时间基的密码学，特别是可验证延迟函数（VDFs）。这种方法有望提供良好的通信效率和韧性，抵御 N-1 个恶意节点。

回到最初的承诺-揭示协议，传统承诺可以被 定时承诺 代替，以消除参与者拒绝揭示其随机贡献的问题。定时承诺可以由原始承诺者高效打开，或者由任何愿意计算慢函数（实质上是VDF）的人打开。因此，如果有任何参与者在承诺揭示协议中退出，他们的承诺仍然可以由其他人打开。重要的是，打开承诺的最小时间必须足够长，以至于无法在协议的第一轮（承诺阶段）期间完成，否则恶意参与者可能会迅速打开其他人的承诺，从而修改自己的贡献并偏置结果。

利用现代VDF，有一种更优雅的单轮协议是可能的：完全省去承诺。每个参与者可以简单地发布他们的随机贡献 r i，最终结果是对每个参与者的贡献进行组合，并经过 VDF 处理。计算 VDF 的时间延迟确保没人可以以偏置最终输出的方式选择自己的承诺。该方法在 2015 年被 Arjen Lenstra 和 Benjamin Wesolowski 提出为UNICORN，确实是开发 VDFs 时的一个关键动机应用。

这种方法已经在实际中看到一些部署。Chia 在其共识协议中实现了这一版本，使用类群中的重复平方 VDFs。Starkware 使用基于 SNARK 的 VDF 实现了一个概念验证 VDF 基础的信标。以太坊还计划使用该方法，并为计算 VDF 生成随机数建设一个专用的 ASIC，以便在共识层生成随机性。

\\*\

公共随机性是许多协议的基本组成部分，但我们仍然缺乏任何提供高安全性的标准 DRB。设计空间广阔，以上方法的许多混合和组合都是可能的。例如，可以将基于 VRF 的协议与基于 VDF 的协议结合起来，以增加新的熵，例如，正如RandRunner所提议的那样。以太坊的信标链目前使用 VRFs，但未来可能会添加 VDFs，消除区块被扣押攻击所带来的偏置可能性。

何时可以接受诚实多数协议仍然是一个悬而未决的问题。对于一组相对较小、经过审核的参与者——如 entropy 联盟——诚实多数假设是合理的。另一方面，仅需一个诚实参与者的协议具有固有优势——更多参与者只会增强安全性。这意味着这些协议可以通过开放、无许可的参与方式进行部署。

在 Part II 中，我们将讨论共识协议中随机化领导者选举的具体应用，它的设计目标略有不同，因此已提出更多的协议和方法。

Joseph Bonneau 是 a16z crypto 的研究合伙人。他的研究聚焦于应用密码学和区块链安全。他曾在墨尔本大学、纽约大学、斯坦福大学和普林斯顿大学教授过加密货币课程，并获得剑桥大学计算机科学博士学位，以及斯坦福大学的学士和硕士学位。

Valeria Nikolaenko 是 a16z crypto 的研究合伙人。她的研究聚焦于密码学和区块链安全。她还在 PoS 共识协议中的长程攻击、签名方案、后量子安全和多方计算等主题上工作。她在斯坦福大学的 Dan Boneh 教授指导下获得了密码学博士学位，并作为核心研究团队的一员在 Diem 区块链上工作。

编辑：Tim Sullivan

• 原文链接： a16zcrypto.com/posts/art...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～