主持人 > 博客 > 管理 > 随机数和去中心化网络：实现

随机数和去中心化网络：实现

介绍

function getAbsolutelyRandomNumer() {
        return 4; // returns absolutely random number!
}

与密码学中绝对强密码的概念一样，真正的“公开可验证随机信标”（以下简称 PVRB）协议只是尝试尽可能接近理想方案，因为在实际网络中，它不以其纯粹的形式适用：必须严格同意一位，必须有很多轮，并且所有消息必须非常快并且始终传递。 当然，实际网络中并非如此。 因此，在为现代区块链中的特定任务设计PVRB时，除了无法控制由此产生的随机性和加密强度之外，还会出现更多纯粹的架构和技术问题。

对于PVRB来说，区块链本身本质上是一种通信媒介，其中消息=交易。 这允许您部分地从网络问题、消息未传递、中间件问题中抽象出来 - 所有这些风险都由去中心化网络承担，并且它对 PVRB 的主要价值是无法撤销或破坏已发送的交易 - 这确实不允许参与者拒绝参与协议，除非他们对共识进行了成功的攻击。 这种安全级别是可以接受的，因此 PVRB 应该能够像主区块链一样抵抗参与者的串通。 此外，这还暗示，如果网络就主区块链达成一致，即使它也同意唯一公平的随机结果，PVRB 也必须成为共识的一部分。 或者，PVRB 只是一个由智能合约实现的独立协议，该智能合约相对于区块链和区块异步工作。 两种方法都有其优点和缺点，并且它们之间的选择非常重要。

PVRB的两种实现方式

让我们更详细地描述实现 PVRB 的两种选项：独立版本，使用独立于区块链的智能合约进行工作；以及共识集成版本，内置于协议中，根据该版本，网络就区块链和协议达成一致。交易纳入其中。 在所有情况下，我指的是流行的区块链引擎：以太坊、EOS 以及所有在托管和处理智能合约方面与它们类似的引擎。

独立合约

在此版本中，PVRB 是一个智能合约，它接受随机生产者（以下简称 RP）的交易，对其进行处理，组合结果，并最终得出任何用户可以从该合约接收的某个值。 该值可能不会直接存储在合约中，而是仅由数据表示，从中可以确定性地获得结果随机的一个且仅一个值。 在该方案中，RP是区块链的用户，任何人都可以参与生成过程。

独立合约的选项很好：

  • 可移植性（合约可以从区块链拖到区块链）
  • 易于实施和测试（合约易于编写和测试）
  • 实施经济方案的便利性（很容易制作自己的代币，其逻辑服务于PVRB的目的）
  • 在已经运行的区块链上启动的可能性

它也有缺点：

  • 对计算资源、交易量和存储（即cpu/mem/io）的严格限制
  • 合约内操作的限制（不是所有指令都可用，很难连接外部库）
  • 无法比区块链中包含的交易更快地组织消息传递

该选项适合实现需要在现有网络上运行、不包含复杂的密码学且不需要大量交互的PVRB。

共识整合

在此版本中，PVRB 在区块链节点代码中实现，内置或与区块链节点之间的消息交换并行运行。 协议的结果直接写入生成的块中，协议消息通过节点之间的 p2p 网络发送。 由于协议产生的数字要写入块中，因此网络必须就它们达成共识。 这意味着 PVRB 消息与交易一样，必须由节点验证并包含在块中，以便任何网络参与者都可以验证是否符合 PVRB 协议。 这自然而然地给我们带来了显而易见的解决方案——如果网络就一个区块及其中的交易达成共识，那么 PVRB 应该成为共识的一部分，而不是一个独立的协议。 否则，有可能一个区块从共识的角度来看是有效的，但没有遵循PVRB协议，从PVRB的角度来看该区块不能被接受。 因此，如果选择“共识整合”选项，PVRB 就成为共识的重要组成部分。

在网络共识级别描述 PVRB 实现时，无论如何都无法避免最终性问题。 最终性是确定性共识中使用的一种机制，它锁定最终的区块（以及通向该区块的链），即使发生并行分叉，也永远不会被丢弃。 例如，在比特币中就没有这样的机制——如果你发布了一条更复杂的链，它将取代任何不太复杂的链，无论链的长度如何。 以 EOS 为例，最后的区块是所谓的最后不可逆区块，平均每 432 个区块出现一次（12*21 + 12*15，预投票 + 预提交）。 这个过程本质上是在等待2/3的区块生产者（以下简称BP）签名。 当出现比最后一个 LIB 更旧的分叉时，它们会被简单地丢弃。 这种机制可以保证交易被包含在区块链中并且永远不会回滚，无论攻击者拥有什么资源。 此外，最终的区块是由 Hyperledger、Tendermint 和其他基于 pBFT 的共识中的 2/3 BP 签名的区块。 此外，制定一个确保最终性的协议作为共识的附加组件也是有意义的，因为它可以与区块的生产和发布异步工作。 这是一个很好的 文章 关于以太坊的最终性。

最终性对于用户来说极其重要，如果没有最终性，他们可能会发现自己是“双花”攻击的受害者，其中 BP“持有”区块，并在网络“看到”良好交易后发布它们。 如果没有最终确定性，则发布的分叉会将具有“好”交易的区块替换为来自“坏”分叉的另一个区块，其中相同的资金被转移到攻击者的地址。 就PVRB而言，最终性的要求更加严格，因为为PVRB构建分叉意味着攻击者有机会准备多个随机选项以发布最有利可图的选项，并且限制可能的攻击时间是一种选择好的解决方案。

因此，最好的选择是将PVRB和最终性结合到一个协议中——然后最终确定的区块=最终确定的随机数，而这正是我们需要得到的。 现在玩家将在 N 秒内收到保证的随机数，并且可以确定不可能回滚或再次重播。

共识集成选项很好：

  • 与块的生成相关的异步实现的可能性 - 块像往常一样生成，但与此同时，PVRB 协议可以工作，这不会为每个块产生随机性
  • 能够实施重型加密技术，而不受智能合约的限制
  • 组织消息交换的速度比区块链中包含的交易更快，例如，协议的一部分可以在节点之间工作，而无需通过网络分发消息

它也有缺点：

  • 测试和开发方面的困难 - 您将不得不模拟网络错误、丢失节点、网络硬分叉
  • 实施错误需要网络硬分叉

这两种实现 PVRB 的方法都具有生命权，但现代区块链中智能合约的实现在计算资源方面仍然相当有限，而且向严格的密码学的任何过渡通常都是不可能的。 我们将需要严格的密码学，如下所示。 虽然这个问题显然是暂时的，但需要在合约中进行严格的密码学来解决许多问题，并且它正在逐渐出现（例如，以太坊中 zkSNARKs 的系统合约）

区块链提供了透明且可靠的协议消息传递通道，但它并不是免费的。 任何去中心化协议都必须考虑到 Sybil 攻击的可能性；任何行动都可以通过多个账户的协同力量来完成，因此，在设计时，需要考虑到攻击者创建任意数量协议的能力参与者串通一气。

PVRB 和块变量。

当我说还没有人在区块链中实施经过许多赌博应用程序测试的良好 PVRB 时，我并没有撒谎。 那么以太坊和EOS上这么多的赌博应用程序从哪里来呢？ 这让我感到惊讶，也让你感到惊讶，他们从哪里在完全确定性的环境中获得如此多的“持久”随机数？

在区块链中获得随机性的最喜欢的方法是从块中获取某种“不可预测”的信息，并根据它生成一个随机信息 - 只需对一个或多个值进行散列即可。 关于此类方案问题的好文章 这里。 你可以取区块中任何“不可预测”的值，例如区块哈希、交易数量、网络复杂度以及其他提前未知的值。 然后对它们进行哈希处理，一个或多个，理论上，你应该得到一个真正的随机数。 您甚至可以在白皮书中添加您的方案是“后量子安全”的（因为存在量子证明哈希函数:)）。

但唉，即使是后量子安全哈希也是不够的。 秘密在于PVRB的要求，让我从上一篇文章中提醒您：

  1. 结果必须具有可证明的均匀分布，即基于可证明的强密码学。
  2. 无法控制结果的任何位。 因此，结果无法提前预测。
  3. 您不能通过不参与协议或通过攻击消息使网络过载来破坏生成协议
  4. 上述所有内容都必须能够抵御允许数量的不诚实协议参与者（例如 1/3 的参与者）的串通。

在这种情况下，只满足要求1，不满足要求2，通过对块中不可预测的值进行散列，我们将得到均匀的分布和良好的随机性。 但英国石油公司至少可以选择“是否发布该区块”。 因此，BP 至少可以从两个随机选项中进行选择：“它自己的”和如果其他人出块就会出现的选项。 BP 可以提前“窥探”如果他发布了一个区块将会发生什么，并简单地决定做或不做。 因此，例如，当玩轮盘赌中的“奇数”或“红/黑”时，只有当他看到胜利时，他才能发布区块。 这也使得使用“来自未来”的块哈希等策略变得不可行。 在这种情况下，他们说“将使用随机数，它是通过对当前数据和高度为 N + 42 的未来块的哈希值进行哈希而获得的，其中 N 是当前块的高度。 这稍微加强了该计划，但仍然允许 BP（尽管是在未来）选择是持有区块还是发布区块。

在这种情况下BP软件变得更加复杂，但也不是很多。 简而言之，当验证交易并将其包含在区块中时，会快速检查是否会获胜，并且可能会选择一个交易参数以获得较高的获胜概率。 同时，要抓住一个聪明的 BP 进行此类操纵几乎是不可能的；每次你都可以使用新地址并一点点获胜而不引起怀疑。

因此使用来自块的信息的方法不适合作为PVRB的通用实现。 在有限版本中，由于赌注大小、玩家数量和/或 KYC 注册限制（以防止一名玩家使用多个地址），这些方案可以适用于小型游戏，但仅此而已。

PVRB 和提交揭示。

好的，这要归功于散列以及至少块散列和其他变量的相对不可预测性。 如果你解决了抢先交易矿工的问题，你应该会得到更合适的东西。 让我们将用户添加到该方案中 - 让他们也影响随机性：任何技术支持员工都会告诉您，IT 系统中最随机的事情是用户的操作:)

当用户简单地发送随机数并且将结果计算为例如其总和的散列时，天真的方案是不合适的。 在这种情况下，最后一个玩家可以通过选择自己的随机数来控制结果。 这就是使用广泛使用的提交-显示模式的原因。 参与者首先发送随机数中的哈希值（提交），然后自己打开随机数（显示）。 “揭示”阶段仅在收集了必要的提交后才开始，因此参与者可以准确地发送他们之前发送的随机哈希值。 现在，让我们将所有这些与一个块的参数放在一起，这比从未来获取的参数更好（随机性只能在未来的块之一中找到），瞧 - 随机性已经准备好了！ 现在，任何玩家都可以影响由此产生的随机性，并且可以通过用自己的、事先未知的随机性覆盖它来“击败”恶意 BP……您还可以通过在揭示阶段不打开协议来添加针对破坏协议的保护 - 简单地要求在提交交易时附加一定金额的保证金，该保证金仅在披露过程中才会退还。 在这种情况下，承诺而不透露将是无利可图的。

这是一个很好的尝试，这样的方案也存在于游戏 DApp 中，但可惜，这又是不够的。 现在不仅是矿工，协议的任何参与者都可以影响结果。 仍然可以控制价值本身，变化性较小且有一定成本，但是，就像矿工的情况一样，如果抽奖结果比参与 PVRB 协议的费用更有价值，那么随机-生产者（RP）可以决定是否公开，并且仍然可以从至少两个随机选项中进行选择。
但惩罚那些犯下罪行但不透露的人成为可能，这个计划将会派上用场。 它的简单性是一个重要的优势——更严格的协议需要更强大的计算。

PVRB 和确定性签名。

还有另一种方法可以强制 RP 提供伪随机数，如果提供“原像”，则它无法影响该伪随机数 - 这是确定性签名。 这样的签名例如是RSA，而不是ECS。 如果 RP 有一对密钥：RSA 和 ECC，并且他用自己的私钥签署某个值，那么在 RSA 的情况下，他将得到一个且只有一个签名，在 ECS 的情况下，他可以生成任意数量的签名不同的有效签名。 这是因为在创建 ECS 签名时，会使用由签名者选择的随机数，并且可以以任何方式选择，从而使签名者有机会选择多个签名之一。 对于 RSA：“一个输入值”+“一个密钥对”=“一个签名”。 无法预测另一个 RP 将获得什么签名，因此可以通过组合签署相同值的多个参与者的 RSA 签名来组织具有确定性签名的 PVRB。 比如之前的随机。 这个方案节省了大量的资源，因为签名既是根据协议对正确行为的确认，也是随机性的来源。

然而，即使具有确定性签名，该方案仍然容易受到“最后参与者”问题的影响。 最后一个参与者仍然可以决定是否公开签名，从而控制结果。 你可以修改方案，在其中添加区块哈希，进行轮次，这样结果就无法提前预测，但所有这些技术，即使考虑到许多修改，仍然没有解决单个参与者对集体的影响问题导致环境不受信任，只能在经济和时间限制下工作。 此外，RSA密钥的大小（1024和2048位）相当大，区块链交易的大小是一个极其重要的参数。 显然没有简单的方法可以解决这个问题，让我们继续吧。

PVRB 和秘密共享方案

在密码学中，有一些方案可以允许网络就一个且仅有一个PVRB值达成一致，同时这种方案可以抵抗某些参与者的任何恶意行为。 沙米尔的秘密共享方案是一项值得您熟悉的有用协议。 它的作用是将一个秘密（例如，一个秘密密钥）分成几个部分，并将这些部分分发给N个参与者。 秘密的分布方式使得 N 中的 M 部分足以恢复它，并且这些可以是任意 M 部分。 如果在手指上，则有一个未知函数的图形，参与者在图形上交换点，收到M点后，可以恢复整个函数。
给出了很好的解释 维基 但是实际使用它以便在你的头脑中播放协议对于以下方面很有用： 演示 页。

如果 FSSS（Fiat-Shamir 秘密共享）方案以其纯粹的形式适用，它将是一个坚不可摧的 PVRB。 最简单的协议可能如下所示：

  • 每个参与者生成自己的随机数并将其分配给其他参与者
  • 每个参与者都透露了其他参与者的秘密
  • 如果某个参与者拥有M股以上，则可以计算出该参与者的数量，并且该参与者的数量是唯一的，与显示的参与者集合无关
  • 显示的随机数的组合是所需的 PVRB

在这里，个体参与者不再影响协议的结果，除非随机性披露阈值的实现完全取决于他。 因此，如果有所需比例的 RP 在协议上工作并且可用，则该协议可以工作，实现加密强度的要求，并抵抗“最后参与者”问题。

这可能是一个理想的选择，这种基于 Fiat-Shamir 秘密共享的 PVRB 方案例如在 这 文章。 但是，如上所述，如果你尝试在区块链中正面应用它，就会出现技术限制。 以下是 EOS 智能合约中协议的测试实现示例及其最重要的部分 - 检查已发布的份额参与者： 码。 从代码中可以看出，证明验证需要多次标量乘法，而且使用的数字非常大。 需要理解的是，在区块链中，验证发生在区块生产者处理交易的那一刻，一般来说，任何参与者都必须轻松验证协议的正确性，因此对验证功能的速度要求非常严格。 在此选项中，该选项被证明是无效的，因为验证不符合交易限制（0.5 秒）。

一般来说，验证效率是在区块链中使用任何高级加密方案的最重要要求之一。 创建证明、准备消息——这些过程可以脱链并在高性能计算机上执行，但无法绕过验证——这是 PVRB 的另一个重要要求。

PVRB 和门限签名

熟悉秘密共享方案后，我们发现了一整类由关键字“阈值”联合起来的协议。 当某些信息的披露需要 N 个诚实参与者中的 M 个参与，并且诚实参与者的集合可以是 N 的任意子集时，我们称之为“阈值”方案。 正是它们让我们能够处理“最后一个参与者”的问题，现在如果攻击者不透露他的部分秘密，另一个诚实的参与者将为他做这件事。 这些方案允许就一种且仅一种含义达成一致，即使该协议被某些参与者破坏。

确定性签名和阈值方案的结合使得开发一种非常方便且有前途的方案来实现PVRB成为可能——这些是确定性阈值签名。 这里 文章 关于门限签名的各种用途，这是另一个很好的用途 长读 来自达世币。

上一篇文章介绍了 BLS 签名（BLS 代表 Boneh-Lynn-Shacham， 这里 文章），这对程序员来说有一个非常重要且极其方便的品质 - 公钥、秘密、公钥和 BLS 签名可以使用简单的数学运算相互组合，而它们的组合仍然有效的密钥和签名，使您可以轻松聚合许多签名合为一个，多个公钥合为一个。 它们也是确定性的，对于相同的输入数据会产生相同的结果。 由于这种特性，BLS 签名的组合本身就是有效的密钥，这允许实现一种选项，其中 N 个参与者中的 M 个生成一个且仅有一个签名，该签名是确定性的、可公开验证的且不可预测，直到第 M 个参与者打开它为止。参与者。

在具有阈值 BLS 签名的方案中，每个参与者都使用 BLS 签署某些内容（例如先前的随机数），而公共阈值签名是所需的随机数。 BLS 签名的加密属性满足随机质量的要求，阈值部分可防止“最后参与者”，并且密钥的独特组合性使实现许多更有趣的算法成为可能，例如，允许协议消息的有效聚合。

因此，如果您在区块链上构建 PVRB，您很可能最终会得到 BLS 阈值签名方案，有几个项目已经在使用它。 例如，DFinity（这里 实现电路的基准测试，以及 这里 可验证秘密共享的示例实现），或 Keep.network（这是他们的随机信标 黄皮书，但 例子 服务于协议的智能合约）。

实施PVRB

不幸的是，我们仍然没有看到在 PVRB 区块链中实现的现成协议已证明其安全性和稳定性。 尽管协议本身已经准备就绪，但从技术上将它们应用到现有解决方案中并不容易。 对于中心化系统来说，PVRB没有意义，而去中心化系统在所有计算资源上都受到严格限制：CPU、内存、存储、I/O。 设计 PVRB 是不同协议的组合，以便创建至少满足某些可行区块链的所有要求的东西。 一种协议计算效率更高，但需要 RP 之间的更多消息，而另一种协议需要很少的消息，但创建证明可能是一项需要数十分钟甚至数小时的任务。

我将列出您在选择优质 PVRB 时必须考虑的因素：

  • 加密强度。 您的 PVRB 必须严格无偏，无法控制单个位。 在某些方案中情况并非如此，因此请致电密码学家
  • “最后一个演员”问题。 您的 PVRB 必须能够抵御控制一个或多个 RP 的攻击者可以选择两种结果之一的攻击。
  • 协议破坏问题。 您的 PVRB 必须能够抵御控制一个或多个 RP 的攻击者决定是否随机的攻击，并且可以保证或以给定的概率影响这一点
  • 消息数量问题。 您的 RP 应向区块链发送最少的消息，并尽可能避免同步操作，例如“我发送了一些信息，我正在等待特定参与者的响应”之类的情况。 在 p2p 网络中，尤其是地理位置分散的网络中，您不应指望快速响应
  • 计算复杂度问题。 PVRB 链上任何阶段的验证都应该非常容易，因为它是由网络的所有完整客户端执行的。 如果使用智能合约来实现，那么速度要求非常严格
  • 可访问性和活跃性问题。 您的 PVRB 应努力对部分网络在一段时间内不可用且部分 RP 完全停止工作的情况具有弹性
  • 可信设置和初始密钥分发问题。 如果您的 PVRB 使用协议的主要设置，那么这是一个单独的大而严肃的故事。 这里 例子。 如果参与者必须在启动协议之前告诉对方他们的密钥，那么如果参与者的组成发生变化，这也是一个问题
  • 发展问题。 所需语言的库的可用性、其安全性和性能、宣传、复杂测试等。

例如，阈值 BLS 签名有一个重大问题 - 在开始工作之前，参与者必须相互分发密钥，组织一个阈值将在其中起作用的组。 这意味着去中心化网络中至少一轮交换必须等待，并且考虑到生成的兰特在游戏中是必需的，几乎是实时的，这意味着现阶段有可能破坏协议，阈值方案的优点就丧失了。 这个问题已经比以前的问题简单了，但仍然需要开发一个单独的程序来形成阈值组，必须通过向不遵循规则的参与者存款和提取资金（削减）来在经济上得到保护。协议。 此外，具有可接受安全级别的 BLS 验证根本不适合（例如）标准 EOS 或以太坊交易 - 根本没有足够的时间进行验证。 合约代码是WebAssembly或EVM，由虚拟机执行。 加密函数尚未在本机实现，并且工作速度比传统加密库慢数十倍。 许多协议仅仅基于密钥量并不能满足要求，例如RSA的1024和2048位，比比特币和以太坊中的标准交易签名大4-8倍。

不同编程语言的实现也发挥了作用——这种实现很少，特别是对于新协议。 集成到共识中​​的选项需要使用平台语言编写协议，因此您必须在 Go 中查找代码（用于 geth）、在 Rust 中查找代码（用于 Parity）、在 C++ 中查找代码（用于 EOS）。 每个人都必须寻找 JavaScript 代码，并且由于 JavaScript 和密码学并不是特别亲密的朋友，WebAssembly 将提供帮助，它现在无疑声称是下一个重要的互联网标准。

结论

我希望在上一篇中 文章 我设法让您相信，在区块链上生成随机数对于去中心化网络生活的许多方面都至关重要，并且通过本文，我表明这项任务非常雄心勃勃且困难，但已经存在良好的解决方案。 一般来说，协议的最终设计只有在进行大量测试之后才有可能，这些测试考虑到从设置到故障模拟的各个方面，因此您不太可能在团队白皮书和文章中找到现成的配方，我们当然也不会决定在未来一两年内写下“这样做，完全正确”。

再见，我们正在开发的区块链PVRB 哈亚，我们决定使用阈值 BLS 签名，我们计划在共识级别实施 PVRB，因为尚不可能在智能合约中进行具有可接受安全级别的验证。 我们有可能同时使用两种方案：首先，昂贵的秘密共享来创建长期的 random_seed，然后我们将其用作使用确定性阈值 BLS 签名的高频随机生成的基础，也许我们会将自己限制为仅其中一项计划。 不幸的是，不可能提前说出协议是什么；唯一的好处是，就像在科学中、在工程问题中一样，负面结果也是结果，解决问题的每一次新尝试都是解决问题的又一步。涉及该问题的每个人的研究。 为了满足业务需求，我们解决一个具体的实际问题——为游戏应用提供可靠的熵源，所以我们还要关注区块链本身，特别是链终结性和网络治理的问题。

尽管我们还没有在区块链中看到经过验证的抗PVRB，它已经被使用了足够的时间来通过真实应用程序、多次审计、负载，当然还有真实攻击进行测试，但可能的路径数量证实了这一点存在解决方案，以及这些算法中的哪些最终可以解决问题。 我们很乐意分享结果，并感谢其他也在解决此问题的团队提供的文章和代码，使工程师不必两次踩同一个耙子。

所以，当你遇到设计去中心化随机的程序员时，要细心和关怀，必要时提供心理帮助:)

来源： habr.com

添加评论