如果我们彼此不信任，是否可以生成随机数？ 第1部分

嘿哈布尔！

在这篇文章中，我将讨论由彼此不信任的参与者生成伪随机数。 正如我们将在下面看到的，实现一个“几乎”好的生成器非常简单，但实现一个非常好的生成器却很困难。

为什么有必要在彼此不信任的参与者中生成随机数？ 应用领域之一是去中心化应用。 例如，接受参与者下注并以 49% 的概率将金额加倍或以 51% 的概率拿走的应用程序只有在能够无偏见地接收随机数的情况下才会起作用。 如果攻击者可以影响随机数生成器的结果，甚至稍微增加他在应用程序中获得支付的机会，他将很容易摧毁它。

当我们设计分布式随机数生成协议时，我们希望它具有三个属性：

1. 他一定是公正的。 换句话说，任何参与者都不应以任何方式影响随机数生成器的结果。

2. 他一定是不可预测的。 换句话说，任何参与者都不应该能够在生成数字之前预测将生成什么数字（或推断其任何属性）。

3. 该协议必须是可行的，即能够抵抗一定比例的参与者与网络断开连接或故意尝试阻止该协议的事实。

在本文中，我们将研究两种方法：RANDAO + VDF 和纠删码方法。 在下一部分中，我们将详细研究基于阈值签名的方法。

但首先，让我们看一个简单且常用的算法，它是可行的、不可预测的，但有偏差。

然道

RANDAO 是一种非常简单且非常常用的随机性生成方法。 所有网络参与者首先在本地选择一个伪随机数，然后每个参与者发送所选数字的哈希值。 接下来，参与者轮流揭示他们选择的数字，并对揭示的数字进行异或运算，该运算的结果成为协议的结果。

在泄露号码之前发布哈希值的步骤是必要的，以便攻击者在看到其他参与者的号码后无法选择自己的号码。 这将使他几乎能够单枪匹马地确定随机数生成器的输出。

在协议过程中，参与者需要两次做出共同决定（所谓的共识）：何时开始揭示所选数字，从而停止接受哈希值，以及何时停止接受所选数字并计算生成的随机数数字。 在彼此不信任的参与者之间做出这样的决定本身并不是一件容易的任务，我们将在以后的文章中回到它；在本文中，我们将假设我们可以使用这样的共识算法。

RANDAO 具有我们上面描述的哪些属性？ 它是不可预测的，与底层共识协议具有同样的生命力，但它是有偏见的。 具体来说，攻击者可以观察网络，在其他参与者透露他们的号码后，他可以计算他们的异或，并决定是否透露他的号码以影响结果。 虽然这可以防止攻击者单独确定随机数生成器的输出，但仍然给他带来了 1 位影响力。 如果攻击者控制多个参与者，那么他们控制的比特数将等于他们控制的参与者的数量。

通过要求参与者按顺序透露数字，可以大大减少攻击者的影响。 那么，只有最后打开的情况下，攻击者才能影响结果。 虽然影响明显较小，但该算法仍然存在偏差。

兰道+VDF

使 RANDAO 无偏差的一种方法是：在显示所有数字并计算 XOR 后，将其结果输入到函数的输入中，这需要很长时间来计算，但允许您检查计算的正确性计算速度非常快。

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

该函数称为可验证延迟函数，或 VDF。 如果计算最终结果的时间长于号码泄露阶段，那么攻击者将无法预测显示或隐藏其号码的效果，因此他将失去影响结果的机会。

开发优秀的 VDF 极其困难。 最近有一些突破，例如 这 и 这个 这使得 VDF 在实践中更加实用，以太坊 2.0 计划长期使用 RANDAO 和 VDF 作为随机数源。 除了这种方法是不可预测和公正的事实之外，它还有一个额外的好处，即如果网络上至少有两个参与者可用（假设所使用的共识协议在处理如此少量的参与者时是可行的），那么它就可行。

这种方法的最大挑战是设置 VDF，即使参与者拥有非常昂贵的专用硬件，也无法在发现阶段结束之前计算 VDF。 理想情况下，该算法甚至应该具有显着的安全裕度，例如 10 倍。 下图显示了一个攻击者的攻击，该攻击者拥有专门的 ASIC，这使得他能够比分配给 RANDAO 确认的时间更快地运行 VDF。 这样的参与者仍然可以使用或不使用他的号码来计算最终结果，然后根据计算结果选择是否显示。

对于上述VDF系列，专用ASIC的性能可以比传统硬件高100倍以上。 因此，如果披露阶段持续 10 秒，那么在此类 ASIC 上计算的 VDF 必须花费 100 秒以上才能具有 10 倍的安全裕度，因此在商用硬件上计算的相同 VDF 必须花费 100x 100 秒 = 约 3 小时。

以太坊基金会计划通过创建自己的公开免费 ASIC 来解决这个问题。 一旦发生这种情况，所有其他协议也可以利用该技术，但在此之前，RANDAO+VDF 方法对于无法投资开发自己的 ASIC 的协议来说将不那么可行。

有关 VDF 的许多文章、视频和其他信息已收集在 这个网站.

我们使用纠删码

在本节中，我们将了解一个随机数生成协议，该协议使用 擦除代码。 它可以容忍最多 ⅓ 的攻击者，同时保持可行，并允许最多 ⅔ 的攻击者存在，然后才能预测或影响结果。

该协议的主要思想如下。 为简单起见，我们假设正好有 100 名参与者。 我们还假设所有参与者本地都有一些私钥，并且所有参与者的公钥都是所有参与者都知道的：

1. 每个参与者在本地提出一个长字符串，将其分成 67 个部分，创建纠删码以获得 100 个共享，这样任何 67 个共享就足以恢复该字符串，将 100 个共享中的每一个分配给其中一个参与者，并使用同一参与者的公钥。 然后发布所有编码共享。

2. 参与者使用某种共识来就特定 67 个参与者的编码集达成一致。

3. 一旦达成共识，每个参与者都会获取用其公钥加密的 67 个集合中每个集合中的编码共享，解密所有此类共享，并发布所有此类解密共享。

4. 一旦 67 个参与者完成步骤（3），由于纠删码的特性，所有商定的集合都可以被完全解码和重建，并且最终的数字可以通过参与者在（1）中开始的初始行的异或来获得。

该协议可以被证明是公正且不可预测的。 所产生的随机数是在达成共识后确定的，但直到 XNUMX/XNUMX 的参与者解码使用其公钥加密的部分之前，任何人都不知道。 因此，随机数是在足以重建随机数的信息发布之前确定的。

如果在步骤 (1) 中，其中一个参与者向其他参与者发送的编码共享不是某些字符串的正确擦除代码，会发生什么情况？ 如果没有额外的更改，不同的参与者要么根本无法恢复该字符串，要么将恢复不同的字符串，这将导致不同的参与者收到不同的随机数。 为了防止这种情况，您可以执行以下操作：每个参与者除了编码份额之外，还计算 默克拉树 所有这些份额，并向每个参与者发送编码份额本身和默克尔树的根，以及默克尔树中包含份额的证明。 在步骤（2）中的共识中，参与者不仅就一组集合达成一致，而且还就此类树的一组特定根达成一致（如果某个参与者偏离了协议，并向不同的参与者发送了不同的默克尔树根，并且在共识过程中显示了两个这样的根，该行不包含在结果集中）。 作为共识的结果，我们将拥有 67 条编码线和相应的默克尔树根，这样至少有 67 个参与者（不一定是提出相应线的同一个人），他们对于 67 条线中的每一条都有带有擦除代码份额的消息，以及其份额在相应树中出现的证明消失了。

当在步骤 (4) 中参与者破译某个字符串的 67 个节拍并尝试从中重建原始字符串时，可能有以下选项之一：

1. 恢复字符串，然后再次进行擦除编码，并针对本地计算的份额计算 Merkle 树，则根与达成共识的根一致。

2. 该行已恢复，但本地计算的根与达成共识的根不匹配。

3. 该行未恢复。

容易证明，如果上述选项（1）至少发生在一名参与者身上，则选项（1）发生在所有参与者身上，反之亦然，如果选项（2）或（3）发生在至少一名参与者身上，则对于所有参与者，选项 (2) 或 (3) 都会发生。 因此，对于集合中的每一行，要么所有参与者都将成功恢复它，要么所有参与者都将无法恢复它。 生成的随机数只是参与者能够恢复的行的异或。

阈值签名

另一种实现随机性的方法是使用所谓的 BLS 阈值签名。 基于门限签名的随机数生成器具有与上述基于纠删码的算法完全相同的保证，但对于每个生成的数字，通过网络发送的渐近消息数量明显较低。

BLS 签名是一种允许多个参与者为一条消息创建一个公共签名的设计。 这些签名通常用于节省空间和带宽，因为不需要发送多个签名。 

BLS 签名在区块链协议中的一个常见应用，除了生成随机数之外，就是 BFT 协议中的区块签名。 假设有 100 名参与者创建区块，如果有 67 名参与者签署，则该区块被视为最终区块。 他们都可以提交自己的 BLS 签名部分，并使用某种共识算法就其中 67 个部分达成一致，然后将它们合并为一个 BLS 签名。 任何 67 个（或更多）部分都可以用于创建最终签名，这将取决于组合了哪 67 个签名，因此可能会有所不同，尽管 67 个参与者的不同选择将创建不同的签名，但任何此类签名都将是有效的区块的签名。 然后，其余参与者只需通过网络接收和验证每个块的一个签名，而不是 67 个签名，这大大减少了网络的负载。

事实证明，如果参与者使用的私钥是以某种方式生成的，那么无论聚合哪 67 个（或更多，但不能更少）签名，得到的签名都是相同的。 这可以用作随机性的来源：参与者首先同意他们将签署的一些消息（这可能是 RANDAO 的输出或只是最后一个块的哈希值，只要它每次都会改变，这并不重要并且是一致的）并为其创建 BLS 签名。 在 67 个参与者提供他们的部分之前，生成的结果将是不可预测的，之后输出已经被预先确定，并且不能依赖于任何参与者的行为。

只要至少 XNUMX/XNUMX 的在线参与者都遵循协议，这种随机方法就是可行的，并且只要至少 XNUMX/XNUMX 的参与者遵循协议，这种随机方法就是公正且不可预测的。 值得注意的是，控制超过 ⅓ 但少于 XNUMX/XNUMX 参与者的攻击者可以阻止协议，但无法预测或影响其输出。

阈值签名本身是一个非常有趣的话题。 在本文的第二部分中，我们将详细分析它们是如何工作的，以及如何准确地生成参与者密钥，以便将门限签名用作随机数生成器。

总之

本文是技术博客文章系列中的第一篇 近。 NEAR 是一个用于开发去中心化应用程序的区块链协议和平台，重点是易于开发和易于最终用户使用。

协议代码是开放的，我们的实现是用Rust写的，可以找到 这里.

您可以查看 NEAR 的开发情况并在在线 IDE 中进行实验 这里.

您可以关注俄语的所有新闻： 电报群 和 VKontakte 群组，以及官方的英文 叽叽喳喳.

再见！

来源： habr.com