Roll with Move：在 Aptos 上实现安全、即时的随机性

作者： Alin Tomescu 和 Zhuolun Xiang

简短摘要：这是首个为 PoS 区块链提供的在链上安全、即时的随机性 API，仅适用于 Aptos。如果您需要一个随机数，只需调用 aptos_framework::randomness::u64_integer()。如果您需要字节，则调用 aptos_framework::randomness::bytes()。

概述
在这篇博客文章中，我们介绍了 Aptos Roll，一个安全即时的随机性 API 以及其底层加密实现，将为下一代随机化 dapps 提供动力。

Aptos Roll 的核心在于两个新颖的加密构造：加权公开可验证的秘密共享（wPVSS）方案和加权可验证随机函数（wVRF），它们经过精心设计并与 Aptos 区块链协议集成在一起。

让我们深入了解 Aptos Roll 的核心技术细节！

如何使用 Aptos Roll
链上随机性的需求在许多应用中都会出现，例如去中心化游戏、抽奖、随机 NFT、随机空投等。此外，许多区块链应用将从随机性中受益，以提高公平性、安全性和功能性。

Aptos Roll 为这些应用提供了一个简单的 Move API 接口，以即时提供不可预测且无偏见的随机值：

• randomness::u64_integer() 函数：立即返回一个均匀采样的 64 位无符号整数。
• randomness::bytes(n: u64) 函数：立即返回一个长度为 n 的均匀采样的字节向量。
• randomness::permutation(n: u64) 函数：立即返回一个均匀采样的 [0, 1, 2, …, n-1] 向量。

此 API 的一个显著特点是即时交付：Move 智能合约只需调用该 API，即可立即获得随机性。这与从外部随机性信标获取随机性相比，对开发人员来说更为方便，因为智能合约需要提交并等待未来生成的随机数。

有关更多详细信息，请参阅我们的 Aptos 改进提案（AIP）41，其中深入描述了此 API。

为什么它很酷
易于使用的 API：Aptos Roll 提供了易于使用的 API，可以立即向调用方提供随机性。这些即时 API 比基于 commit-and-reveal 过程的解决方案（一个承诺事务后跟一个使用事务）更方便使用。

与区块链一样安全：Aptos Roll 不需要额外的信任假设，仅依赖于区块链的权益证明（PoS）验证器集的安全性和可用性。具体来说，对于控制不到 50% 权益的对手来说，Aptos 上的随机性既不可预测也不具有偏见。

新颖的加密技术：在 PoS 环境中设计一个可扩展的随机性信标需要解决一些难题。

• 首先，Aptos Roll 有一个新颖的加权公开可验证的秘密共享（wPVSS）算法，该算法可以由每个验证器高效运行，并且是可聚合的，有助于减少通信开销。
• 其次，Aptos Roll 有一个通信效率高的可聚合加权分布式密钥生成（wDKG）生成协议。
• 第三，Aptos Roll 有一个新颖的加权可验证随机函数（wVRF），验证器每轮都要对其进行评估，并且每个验证器的通信量是常数，而不是与验证器的股份成线性关系。

背景
Aptos 是一个权益证明（PoS）区块链，其共识算法在称为“纪元”的每两小时间隔内运行。每个纪元内的验证器和他们的权益分配保持不变，并在纪元边界之间进行更改。下一个纪元的验证器直到新纪元开始时才上线。

区块链还解耦了共识（即当前名为 Jolteon 的 BFT 共识协议）与执行（即名为 BlockSTM 的乐观并发控制执行引擎），其中每个块首先由共识确定，然后执行以更新区块链状态。

这种解耦对于网络上的链上随机性尤为重要，因为它允许网络首先对交易的顺序进行承诺，然后再稍后计算和揭示随机性。

设计
这种方法使验证器能够在每个纪元的开始通过加权分布式密钥生成（wDKG）协议共同生成一个共享秘钥。

这个共享秘钥只能由 50% 或更多的股份重建，因此可以安全地用于为该纪元中的每个块计算随机性种子。

种子通过在共享秘钥下对特定于块的非偏见消息（例如纪元号和轮数）进行加权可验证随机函数（wVRF）评估来计算。最后，此块种子用于伪随机地派生该块中每个 API 调用的随机性。

从高层次上看，这总结了您需要了解的有关此随机性方法的所有内容。从低层次上看，事情更加有趣。事实证明，在权益证明（PoS）设置中联合生成共享秘钥，同时频繁且高效地在此秘钥下评估 wVRF 是一个难以解决的开放问题。

让我们深入探讨以下一些有趣的细节。

加权分布式密钥生成（wDKG）来自加权公开可验证的秘密共享（wPVSS）
在新纪元开始之前，旧纪元的验证器将合作处理一个共享秘钥给新纪元的验证器。

具体来说，每个旧验证器充当发牌员：他选择一个随机值并将其秘密地与所有新验证器共享，通过可靠的多播发送一个加权公开可验证的秘密共享（wPVSS）记录。这个记录将包含每个验证器的加密信息，该加密信息是该验证器所处理的随机值的秘密份额。重要的是，每个旧验证器都可以向新验证器发牌，尽管新验证器甚至还没有上线，因为他们的纪元还没有开始。

一旦每个旧验证器从 66% 或更多的股份中收到安全子集的有效记录，它将将有效记录聚合到一个单独的最终聚合记录中，并将其传递给共识。这个聚合记录将加密每个新验证器的最终共享秘钥份额，该秘钥份额将是 66% 或更多股份的随机值的总和。在同意第一个有效的聚合记录后，验证器完成 wDKG 并开始新纪元。

最后，当新纪元开始并且新验证器上线时，他们可以从聚合记录中解密他们所拥有的共享秘钥份额。此时，新验证器将准备通过以下方式以秘密共享方式评估 wVRF，为每个块生成随机性。

其中一个关键的创新是设计一个可聚合的 wPVSS，具有快速的交易时间和快速的验证时间以及较小的记录大小。这是非常困难的，因为我们在加权设置中，共享秘钥只能由 50% 或更多的股份重建。为了确保这一点，最简单的做法是向每个验证器按比例发行与他们的股份相关的秘密份额，但这可能变得相当低效。这个挑战已经通过仔细地将股份四舍五入到较小的权重并设计一种新颖的 wPVSS 而得到解决，该 wPVSS 在处理数千个份额时仍然保持效率。这些细节将在不久的将来在学术论文中公开发表 [3]。

加权可验证随机函数（wVRFs）
一旦新验证器之间建立了共享秘钥，他们可以合作在秘钥下评估加权可验证随机函数（wVRF）。这是每块为了产生上面提到的块的随机性种子而进行的操作。

当一个块达成最终共识时，每个验证器将使用其从聚合的 wPVSS 记录中解密的份额，为该块生成其 wVRF 份额，并通过可靠的组播将其广播。一旦从 50% 或更多的股份中获得了 wVRF 份额，每个验证器将它们组合成（并同意）最终的 wVRF 评估，这成为块种子。最后，将此种子附加到块上并将块发送到执行。

重要的是，只有 50% 或更多的股份才能计算 wVRF 评估，这确保了不可预测性。此外，wVRFs 的唯一性和 wPVSS 方案的保密性确保了对控制不到 50% 股份的对手的不可偏见性。

使这种方法实际可行的关键创新是新型 wVRF 方案，它必须对每个验证器的股份数量与它们的权重成比例的加权设置进行高效的评估。再一次，这是一个具有挑战性的问题。

例如，一个简单的想法是为每个验证器分配一个固定的权重，并使用这些权重对 wVRF 进行评估。然而，这种方法会导致验证器的股份与其 wVRF 份额之间的比例与股份权重不匹配，从而增加了计算成本并降低了效率。因此，需要一种创新的方案来解决这个问题。

为了解决这个问题，我们设计了一个新型的加权可验证随机函数（wVRF），该函数使用一种创新的方法来处理权重和份额之间的比例关系。这种方法通过精心设计 wVRF 的数学结构来优化计算效率和精度，从而在加权设置中实现了高效的评估。

这种 wVRF 的具体细节将在学术论文中公开发表 [4]，但在这里我们可以概述其核心思想。该方案使用一种称为“分段加权抽样”的方法来处理权重和份额之间的比例关系。通过将每个验证器的份额细分为多个较小的份额，并根据其权重对这些较小的份额进行加权抽样，我们可以精确地匹配股份权重与 wVRF 份额之间的比例关系。这种方法不仅提高了计算效率，还降低了计算成本并提高了安全性。

通过使用这种新型的 wVRF 方案，我们可以确保在权益证明（PoS）设置中安全、高效地生成块的随机性种子，从而为区块链提供了一种实用的解决方案来生成不可预测性和不可偏见性的随机性。

例如，基于最先进的基于BLS的VRF的简单解决方案将使wVRF份额大小与验证器的权重成线性关系。这将导致每块的通信开销过大，并减慢共识速度。

相比之下，wVRF方案将份额大小从线性减少到常数，在计算块种子时保持通信开销最优。

下表总结了Aptos Roll与其他区块链在链上随机性之间的差异，其中Aptos模型是唯一适用于具有即时交付随机性API的PoS区块链的安全解决方案。

DFINITY 依赖于阈值 DKG（tDKG）和阈值 VRF（tVRF），而不是加权设置。这是因为 DFINITY 假设一个非权益证明（PoS）的安全模型，在该模型中，只要不超过三分之一的验证者（而不是权益）受到损害，链仍然安全。这种阈值设置比 Aptos 的加权设置要简单得多，因为总份额数可以设置为验证者的数量（例如，数百个）。相比之下，在 Aptos 的加权设置中，总份额数与总权益成比例，即使四舍五入后也会更大（例如，数千个）。

像 Drand 这样的外部信标也依赖于在服务器委员会中实现 tDKG 和 tVRF。因此，在阈值设置中更容易实现。不幸的是，当 dapp 消耗生成的随机数时，它现在必须对随机数信标的可用性和安全性进行外部信任。此外，随机数不能立即消耗，而是通过提交和揭示过程来消耗，这使得开发更加麻烦且对随机数的访问更加延迟。同样的问题也适用于 Algorand 的随机数信标设计，该设计依赖于从单独的外部随机数信标中消耗随机数。

一种非常有前途的随机数生成方法是使用可验证的延迟函数（VDF）。Chia采用了这种方法，其优势在于，即使所有验证者都被破坏，不可预测性仍然成立，前提是没有人能够比最初设置的延迟更快地评估VDF。不幸的是，这种方法无法快速产生随机数，因为它基于延迟计算随机数。此外，基于VDF的方法不容易提供即刻交付的随机数，因为这将需要为每个块生成一个VDF，这对于低延迟的区块链来说很困难，因为VDF本质上很慢。换句话说，如果块的生产频率高于VDF，那么这些块将无法获得即刻随机性。

最后，一些随机性设计并不假定现实威胁模型，并且可能受到单个恶意验证者的偏见或预测。

在Flow的设计中，验证者对提议的块A进行投票并附加他们的VRF评估，允许下一个块B的提议者聚合投票并揭示块A的随机性。这允许通过策略性地不提议块B来产生偏见，使块A成为孤立的块。

Celo允许一个块的提议者选择随机性，对其承诺并在随后的块中揭示它。这为拒绝揭示随机性或根据预期交易做出知情预测以最大化利润提供了途径。

在以太坊中，每个区块提议者会对当前的纪元编号进行VRF（可验证随机函数）评估。然后，该纪元的随机性被定义为提议者的VRF评估的最佳努力组合。不幸的是，这种方法很容易产生偏见，因为一个或多个勾结的区块提议者如果不喜欢结果，可以选择不混合他们的贡献。此外，这种方法非常慢，因为纪元每6.4分钟才发生一次。

致谢
我们希望感谢Dan Boneh、Valeria Nikolaenko以及整个a16z加密研究团队对我们设计的审查和帮助验证。

脚注和参考文献
[1] Aptos Roll依赖于将每个验证者的权益四舍五入到较小的权重。这对于实现实际性能非常有利，但对保密性和可用性有影响。具体来说，任何四舍五入方案都会导致四舍五入误差：即一些玩家可能获得比他们应得的更多的秘密份额，而其他玩家可能获得更少。因此，这实际上将阈值秘密共享方案转变为斜坡秘密共享方案，具有不同的保密阈值和不同的重建阈值。通常情况下，重建阈值更高。因此，为了保持活动的持续性，该机制需要确保任何66%或更多的权益可以重建，同时保密性可以抵御任何33%或更少的权益。为了最小化MEV攻击的影响，我们选择提高保密阈值，将其设置为50%，同时仍保持重建阈值低于66%，以应对33%的对手。

[2] 在这里，验证者可以选择持有33%的权益，因为如[1]所述不存在四舍五入问题，但他们保守地等待更多的权益以更抵御MEV攻击，在这些攻击中，验证者勾结以预先确定共享的秘密。

[3] 使用加权VRFs的分布式随机性，Sourav Das、Benny Pinkas、Alin Tomescu、Zhuolun Xiang；2024