a16z：如何用去中心化方式构建可公开验证的随机性信标？

Foresight News 阅读 1836 2022-10-20 12:01:56

公共随机性是许多协议的重要组成部分，但我们仍然缺乏提供高安全性的去中心化随机性信标。

原文：Public Randomness and Randomness Beacons（a16z crypto）

作者：Joseph Bonneau、Valeria Nikolaenko

编译：aididiaojp.eth，Foresight News

封面：Photo by Austin Chan on Unsplash

公共随机性是现实世界安全协议的重要组成部分。在赌博和多人游戏中，随机性会增加乐趣。在绿卡办理、法官案件分配和体育比赛等其他事件中，随机性提供了一种分配不可分割资源的公平方式。税务审计或机场的安全抽查等事件同样具有随机性。

传统上，我们依靠受信任的权威来确保随机的真实性，但在 Web3 世界中，我们有更好的方式来实现这一点。本文将探索通过分布式随机信标来构建可公开验证的随机性的方法，包括一些链上应用的实际部署分析。

属性要求

生成随机数是一项非常奇妙的事件。许多加密密钥依赖于错误的随机数生成器，最终导致密钥被泄露。准确来说这是私人随机性，只有一方需要生成和使用它。

相比之下，公共随机性是一个多方参与的过程，大大提高了安全性。而产生安全公共随机性的协议将具有以下属性：

无偏差性：任何攻击者或攻击者联盟都不能使输出产生偏差。
可靠性：没有攻击者能够阻止协议输出。
可验证性：任何人都可以轻松验证协议输出，并且应该看到与其他人相同的输出。
不可预测：如果协议在时间 T 1 产生输出，那么在某个时间 T 0 <T 1，没有人能够预测关于输出结果的任何事情。

无偏差性是比不可预测性更弱的属性，因为任何不可预测的协议都必须是无偏差的。如果你能够对产出结果造成偏差影响，就可以借此做出预测，所以无偏差性的要求弱于不可预测性。例如大多数人预测结果时会依赖于不同的假设，并根据不同的预测来操作，所以实际上不会对其产出造成实质影响。

除了这些属性之外，该协议还应该能够高效地运行，并产生大量随机位数。实际应用中，应用程序产生 128 个随机位通常就足够了。为了能作为彩票或资源分配等用途，对于输出的每个单独位都应保持不可预测性。理想情况下该协议在通信和计算成本方面也应该是实用的。

不同的协议可能会在不同的条件下实现这些属性。例如某些协议可能对任何 f 1 个恶意节点的联盟都是无偏的，并且对任何 f 2 <f 1 个恶意节点的联盟都是不可预测的。在某些协议中参与者可能能够将输出偏置「一位」，这意味着他们可以在两个可能的输出之间进行选择。其他攻击可能允许他们完全固定输出。然而通常情况下我们根本无法容忍任何偏见或可预测性。

密码学解决方案：随机信标

密码学家通常从完美的解决方案开始思考。例如在公共随机性构建中，随机信标是一种理想化的解决方案，它定期产生满足所有必要安全要求的随机输出。

这种理想化的随机信标类似于在现实世界中并不存在的随机预言或通用模型。但存在一个模型可以用来推理公共随机性协议。

我们可以考虑一些理想随机信标的近似方案。

中心化信标：产生良好随机性的最简单方法是通过具有 NIST 随机性信标或 random.org 等服务的中心化第三方，它根据大气噪音中的无线电波产生随机性。这种对第三方的依赖完全破坏了去中心化的理念。在上面的示例中，在无需任何加密证明的情况下，我们必须相信相关组织正在正确地生成随机性。
物理随机性验证：许多传统彩票依赖于公共验证，例如在一个装有不同数字的乒乓球容器抽取乒乓球来获得随机数。不幸的是这些通常很容易被操纵。例如可以将某些球放在冰箱中，然后根据温度不同来选择乒乓球。
自然信标：一个常见的想法是使用随机的自然现象，如天气或宇宙辐射作为信标。但所有提议的来源都没有强烈的共识。不同的观察者会看到略有不同的值，这需要重新引入可信方进行官方测量，这样就会具有中心化信标的所有缺点。
半中心化信标：直接从比特币区块头或股票收盘价中获取随机性，这更容易公开验证，任何一方都更难以完全控制。然而，对工作量证明区块链随机性和股价随机性的微妙干预仍然存在。例如，使用区块链标头，矿工可以选择保留标头产生他们不喜欢的信标值的区块。或者他们可以选择在根据首选信标输出找到两个碰撞区块时进行干预。

去中心化随机信标 (DRB)

解决中心化信标问题的一种方法是设计一个去中心化密码协议来确保公共随机性，这有点像设计去中心化的共识协议，但难度会更高。所有参与者都需要就输出（随机性）达成一致，而且协议中的恶意参与者也无法对输出产生偏见或预测。

旨在模拟随机信标的协议称为分布式随机信标 DRB（又名「distributed coin-flipping」）。DRB 在 1980 年代被验证是无法解决的，现在由于区块链技术的诞生，有了新的实现可能。如果 DRB 可用于提供链上随机性，这将是构建公平、安全和透明的链上应用程序的关键要素。

经典方法：承诺 - 披露协议

在乐观情况下，一个非常简单的两轮协议足以满足 DRB 的需求。在第 1 轮中，每个参与者 i 生成一个随机值 r i 并发布一个加密承诺 c i = Commit( r i )。在这个过程中，承诺可以简单地是一个像 SHA-256 这样的哈希函数。在每个参与者的承诺发布后，他们被锁定在他们对 r i 的选择中，但承诺不会透露任何有关其他参与者贡献的信息。在第 2 轮中，每个参与者通过发布 r i「开启他们的承诺」。然后组合所有随机值，散列它们之间的连接。

这个协议很简单，只要有一个参与者随机选择他们的 ri ，就会产生一个随机信标输出。不幸的是，它存在一个经典缺陷：当只有一个参与者透露了他们的随机值时，最后一个参与者能够计算假定的信标输出。当他们计算出输出结果时，就可以根据自己的喜好来选择是否发布他们的结果或终止协议。而忽略错误参与者的贡献并不能解决问题，因为这仍然让攻击者可以在两个信标输出之间进行选择。

区块链为这个问题提供了一种补救措施：每个参与者都可能被要求将一些资金放入托管中，如果他们不透露他们的随机贡献，这些资金就会被没收。这正是以太坊上经典的 RANDAO 信标所采用的方法。这种方法的缺点是输出仍然可能有偏差，如果托管中的资金少于信标结果上的资金量，这对攻击者来说可能是值得的。想要更好地抵御偏向攻击的安全性需要将更多的代币放入托管中。

承诺 - 披露 - 恢复协议

一些协议不是试图强迫所有各方透露他们的随机贡献，而是包含一个恢复机制，这样即使少数参与者退出，其余参与者也可以完成协议。协议在任何一种情况下都产生相同的结果，这样各方就不能通过选择是否退出来影响输出结果。

实现此目的的一种方法是让每个参与者向其他参与者提供秘密的共享，以便他们中的大多数人可以使用例如 Shamir 的秘密共享来重新使用。然而，一个重要的属性是其他人可以验证提交的秘密是否已被正确共享，这需要使用更强大的可公开验证的秘密共享保障（PVSS）。

其他几种恢复机制也是可以使用的，但它们都有相同的限制。如果有 N 个参与者，并且如果任何最多 f 个节点的组退出，那么任何 Nf 个参与者组都必须能够计算最终结果。但这也意味着 Nf 参与者的恶意联盟可以通过私下模拟恢复机制来提前预测结果，这个过程可能发生在协议的第一轮期间，在此期间恶意联盟可以修改他们自己的随机性选择并使结果产生偏差。

换句话说，任何 Nf 个节点的联盟必须至少包含一个诚实节点。通过简单的代数，Nf > f，所以 f < N/2，这些协议需要多数的诚实节点。这与原始的 commit-reveal 安全模型有很大不同，后者只需要 f<N（至少一个诚实的参与者）。

这些协议通常还需要大量的通信成本来在协议的每次运行中在所有节点之间共享额外的 PVSS 信息。在过去的几年里研究界在这个问题上做了相当多的工作，研究提案包括 RandShare、Scrape、SecRand、HERB 或 Albatross，但似乎都没有看到实际应用。

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

在意识到一组 Nf 个参与者可以计算上述协议中的随机信标值之后，有了一种更简单的方法：在 N 个参与方之间共享一个长期密钥，并要求使用它来评估可验证的随机函数 (VRF)。密钥通过 t -out-of- N 阈值方案共享，任何 t 个参与者都可以计算 VRF（但较小的联盟不能）。对于 t = Nf ，这为 f 个恶意节点提供了与上面讨论的承诺 - 披露协议相同的安全弹性。

Dfinity 使用阈值 BLS 签名（用作 VRF），并率先使用这种方法作为其共识协议的一部分。独立的 drand 随机信标使用基本相同的方法，一组参与者阈值 BLS 在每一轮中签署一个计数器。League of Entropy 是 drand 的开源实例，它是由公司和大学里的研究小组共同运行，截至 2022 年 9 月共使用 16 个参与节点，每 30 秒产生一次随机性。

这些方法的缺点是初始化阈值密钥相对复杂，当节点加入或离开时重新配置密钥也是如此。但是在常见情况下协议是非常有效。

如上所述，简单地签署一个计数器值不会在每轮增加任何新的随机性，但如果足够数量的参与者的密钥被泄露，那么该协议将在未来的每一轮中都是可预测的。

Chainlink VRF 将这种方法（使用 NSEC5 VRF）与请求随机性的各方指定的外部随机源相结合，通常是实践中最常见的区块链标头。然后数据通过 VRF 馈送，该 VRF 由一方运行或阈值化到一组。

以太坊的信标链目前使用基于 BLS 的 VRF：每轮的提议者将其 VRF 值添加到组合中。与 commit-reveal 范例相比，节省了一轮通信（假设长期 BLS 公钥注册一次），尽管这种设计继承了 commit-reveal 方法的一些缺陷，包括通过保留输出来偏置信标输出的可能性。

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

最后一个有前景的新方向是使用基于时间的密码学验证，特别是可验证的延迟函数 ( VDF )。这种方法有望提供良好的通信效率，并具有对 N-1 个恶意节点的防御稳健性。

回到最初的 commit-reveal 安全协议，传统的承诺可以用定时承诺代替，以消除参与者拒绝透露他们随机贡献的问题。定时提交可以由原始提交者或任何愿意计算慢函数（本质上是 VDF）的人有效地完成。因此如果任何参与者退出 commit-reveal 协议，他们的承诺仍然可以被其他人执行。至关重要的是执行承诺的最短时间足够长，不能在协议的第一轮（提交阶段）完成，否则恶意参与者可以足够快地打开其他人的承诺，从而修改自己的贡献并影响输出结果。

现代 VDF 可以实现更实用的一轮协议：完全放弃承诺。每个参与者可以简单地发布他们的随机贡献 r i，最终结果是每个参与者的贡献的组合通过 VDF 运行。计算 VDF 的时间延迟确保没有人可以选择他们的承诺以使最终输出有偏差。这种方法由 Arjen Lenstra 和 Benjamin Wesolowski 在 2015 年提出，是 VDF 开发中的关键激励应用。

这种方法已经看到了一些实际的部署。Chia 在其共识协议制定中使用了重复平方的 VDF。Starkware 使用基于 SNARK 的 VDF 实现了基于概念验证的 VDF 信标。以太坊为了在共识层产生随机性，也计划使用这种方法，构建一个专用的 ASIC 来计算 VDF。