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