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

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

作者：MixBytes团队

介绍

function getAbsolutelyRandomNumer() {
    return 4; // 返回绝对随机数！
}

像许多加密概念一样，“公网上可验证随机信标”协议（简称 PVRB）仅接近理想的方案，并不能避免基本的限制。理想的方案在实际网络中并不可行：在一轮中应对唯一比特达成共识，轮次的数量，以及必须快速和始终送达的网络消息。这对于真实网络并不适用。针对现代区块链，自定义 PVRB 解决方案的开发涉及许多架构和技术问题，除了无法控制随机数生成和加密算法强度之外。

区块链作为 PVRB 的通信媒介，其中消息=交易。目前，我们可以暂时不考虑网络问题、消息不送达、软件中间件的问题——所有这些风险都由去中心化网络来处理。PVRB 享有其无法回滚或损坏已发送交易的优势，此外，参与者不能拒绝参与协议，除非他们成功攻击了网络共识。由于安全级别是可接受的，PVRB 在抵抗参与者之间的串通方面必须尽可能与区块链的主链一致。有一个提示，PVRB 应该是共识的一部分；如果网络同意主链，那么它也应该同意正确的结果随机数。否则，PVRB 仅是一个由智能合约支持的独立协议，与区块链和区块异步工作。这两种方法各有优缺点，它们之间的选择相当困难。

实现 PVRB 的两种方式

我们将更详细地描述两种选项：基于区块链独立智能合约的独立版本，以及嵌入协议的共识集成版（网络同意要包含的交易和区块）。在每种情况下，我将引用流行的区块链：以太坊、EOS 及其类似方式存储和处理智能合约的区块链。

独立合约

在这里，PVRB 是一个接受来自随机生产者（以下简称 RP）的交易的智能合约，处理这些交易，合并结果，最终生成任何合约用户都可以接收的某个值。该值可能不直接存储在合约中，但具有数据表示，从而允许确定结果随机性的唯一值。在该方案中，RP 是区块链用户，任何人都可以参与生成过程。

独立合约选项看起来不错，因为：

• 可移植性（合约可以在区块链之间“拖动”）
• 易于实现和测试（编写和测试合约非常方便）
• 便捷的经济方案（轻松创建具有 PVRB 特定逻辑的自有代币）
• 适用于现有区块链

它也有缺点：

• 对消耗计算资源的强大限制：交易复杂性、容量、网络速度和区块链存储（换句话说，传统的 cpu/mem/io/storage）

• 内部合约机器指令的限制（并非所有指令都可用，连接外部库较困难）

• 消息速度无法快于包含在区块链中的交易速度

如果我们想在一个不包含复杂密码学且不需要大量交互的现有网络中运行 PVRB，这个选项是合适的。

共识集成选项

在这里，PVRB 嵌入在区块链节点代码中或与区块链节点消息并行工作。协议结果直接写入生成的区块，而协议消息通过 p2p 网络在节点间传递。由于协议数值结果需要写入区块，网络必须对此达成一致。这意味着 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 和最终性结合在一个协议中——这样，最终区块将等同于最终的随机数——这正是我们努力获得的。从现在开始，参与者将在 N 秒内获得一个保证的随机数，并且确信它不可能被回滚或重播。

共识集成选项看起来不错：

• 相对于区块生产的可能异步实现——区块按常规方式生成，但 PVRB 协议可以并行工作并为每个区块生成随机数

• 能够实现甚至复杂密码学，无需智能合约的限制

• 能够组织比包含在区块链中的交易速度更快的消息，例如，协议的某个部分可以在节点之间无需网络交互而运作

它也有缺点：

• 测试和开发困难——你需要模拟网络错误、缺失节点和网络硬分叉

• 实现错误需要网络硬分叉

实施 PVRB 的这两种方式是可以接受的，但现代区块链中的智能合约在计算资源方面仍然相当有限，这使得任何严肃的密码学几乎不可能。但这种情况正在逐年改善。我们可以提到以太坊中的针对 zkSNARK 的预编译系统合约作为一个例子。

提供透明可靠的协议消息通道的区块链并非免费的。任何去中心化协议都必须考虑可能的 Sybil 攻击，只要有多个账户协同，就可以进行任何操作。在开发时，请记住攻击者能够从任意数量的协议参与者中形成串通。

PVRB 和区块变量

我并没有撒谎，到 2019 年春天为止，还没有人实现一个良好、强大的 PVRB 在区块链上并在赌博应用中测试它。那么以太坊和 EOS 中有如此多的赌博应用来自何处呢？我和你一样感到惊讶：在一个完全确定性环境中怎么可能有那么多“强”的随机数？

我“最喜欢”的获取区块链中随机数的方法是取自区块某些“不可预测”的信息并基于此生成一个随机数——只需对一个或多个值进行哈希即可。在这里可以找到关于这种方案可能缺陷的好文章 这里。你还可以选择区块中的任何其他“不可预测”值，例如，区块哈希、交易数量、网络复杂度，以及其他未知值。然后对其中一个或一些进行哈希，从理论上讲，得到良好的随机数。你甚至可以在白皮书中写下你的方案是“后量子安全”的（因为已经有量子安全哈希函数 :））。

可惜的是，即使是后量子安全的哈希也不够。秘密在于 PVRB 的要求，我引用之前文章的内容：

1. 结果应该具有可证明的均匀分布，即基于强密码学。

2. 任何比特均无法被控制。因此，结果无法提前预测。

3. 无法通过不参与协议或通过用攻击性消息过载网络来破坏生成协议。

4. 上述所有内容应抵抗可接受数量不诚实协议参与者（例如，1/3 的参与者）的串通。

在这种情况下，仅满足第一个要求。通过对不可预测的区块值进行哈希，我们将获得均匀分布和正确的随机数。BP 至少能够决定是否“验证一个区块或不验证”并从两个随机选项中选择：“自己的一个”和如果该区块是由其他人生成的。BP 可通过保留一个区块来作弊以观察发生的情况，然后决定是否将其发布。因此，例如，进行“单双”或“红/黑”轮盘赌投注，只有在获利时才能发布该区块。同样，采用未来区块的参数是毫无意义的，例如，仅仅是要生成的区块的哈希。在这种情况下，他们会说：“通过对当前数据进行哈希，并对一个高度等于 N+42 的未来区块进行哈希来获得随机性，其中 N 是当期区块高度”。这稍微增强了该方案，但 BP 仍然能够选择是持有还是发布一个区块。

这样的攻击在区块生产软件中并不是复杂的任务。当在区块中验证并包括一个交易时，会快速检查是否有获利可能，并可能选择交易参数以提高获胜的概率。同时，捕捉进行这种操弄的智能 BP 是几乎不可能的，因为每次他都可以使用新地址，逐渐获利而不引起怀疑。

因此，基于区块数据的方法不适合充当通用 PVRB 实现的角色。带有对赌注大小、玩家人数和/或 KYC 注册限制的简版，只适用于小型游戏。

PVRB 和承诺-揭示

好吧，至少我们有哈希，一个“几乎不可预测”的区块哈希和其他变量。如果我们能够解决矿工的前期操控问题，我们可能会得到更值得的东西。让我们在这个方案中添加用户，并允许他们对随机性结果产生影响：任何技术支持员工都会告诉你，IT 系统中最随机的事情就是用户操作 :)

当用户简单地发送随机数并通过其共同产品的哈希计算结果的“幼稚”方案，这是一个不好的场景。在这种情况下，最后一个玩家可以选择自己的随机数来控制结果。因此，最好使用一个众所周知的承诺-揭示模式。首先，参与者发送他们的随机数哈希（即“提交”），然后提交原始随机数（即“揭示”）。一旦收集到所有必要的提交，揭示阶段就开始，这意味着参与者只能发送先前提交哈希的随机数。现在我们将添加区块参数——最好使用未来区块的参数，因为随机数仅会在其中一个后续区块中出现——瞧！随机性来了！现在任何参与者都可以影响生成的随机性，能够用自己不可预测的随机性“击败”恶意 BP……你还可以通过对“提交”请求一些交易费用向协议增加安全性——安全存款，只有在“揭示”程序中才会返回。在这种情况下，承诺而不揭示将是不划算的。

这是一个不错的尝试（这种方案也用于不同的 DApp 中）。可悲的是，这仍然不够。现在不仅矿工能影响结果，任何协议的参与者也可以。这仍然可能用较少的变量和金钱控制一个值，但与矿工的情况一样，如果奖励超出 PVRB 协议参与费用，则随机数生产者（RP）可以决定是否揭示，并从两个随机数选项中选择。

好吧，至少我们有机会惩罚那些提交但不揭示的参与者，该方案稍后会有用。此外，其简单性也是一个严重的优势，因为更复杂的协议需要更多的计算。

PVRB 和确定性签名

确定性签名是另一种良好的方法，让 RP 生成一个它无法影响的伪随机数。例如，RSA 签名就是其中之一，而 ECS（椭圆曲线签名）则不是。如果 RP 拥有一对密钥（RSA 和 ECS），并用其私钥签署某个值，RSA 只允许生成一个唯一签名，而 ECS 则允许生成任意数量的有效签名。在创建 ECS 签名时，签名者可以选择任意随机数，从而有机会选择其中几个签名。使用 RSA 就是“一个输入值” + “一对密钥” = “一个签名”。无法预测其他 RP 的签名，因此可以通过将多个参与者的 RSA 签名组合在一起，构建使用确定性签名的 PVRB，这些参与者曾签署同一个值（例如，先前的随机数）。这样的方案节省了大量资源，因为签名既可以作为正确协议行为的确认，又可以作为随机性的来源。

然而，确定性签名并非无所不能，方案仍然容易受到“最后参与者”问题的攻击。最后一个参与者仍可以决定是否发布签名，从而控制结果。我们可以改进方案，添加区块哈希，制作轮次以确保结果无法提前预测，但所有这些技术无法解决参与者在不可信环境中对集体结果的影响，仅在经济和时间约束方面有效。此外，RSA 密钥可能相当长（（1024 和 2048 位），这是区块链交易的重要参数。显然，没有简单的方法来解决此问题，继续前进吧。

PVRB 和秘密分享方案

存在一些密码学方案，允许网络协商一个独特的 PVRB 值，同时抵御一些参与者的任何恶意行为。这样一种有用的协议是 Shamir 的秘密分享。它用于将某个秘密（例如，秘密密钥）分成若干部分，并将这些部分分发给 N 参与者。以这样的方式分发秘密，只需要从 N 中获取 M 部分就能恢复，并且这可以是任何 M 部分。简单地说，拥有某个未知函数的图形，参与者交换图上的点，在收到 M 点之后，整个函数可以被恢复（线性函数需要两个点，二次函数需要三个点等等）。

在 wiki 上有很好的解释；你也可以在这个 demo 页面实时尝试协议。

如果 FSSS（Fiat-Shamir 秘密分享）方案可以以其纯粹形式应用，那么 PVRB 就是不可攻破的。在其最简单的形式中，协议可能如下所示：

• 每个参与者生成一个随机数并向其他人分发其份额
• 每个参与者揭示其他参与者的秘密部分
• 如果某个参与者收集了超过 M 个份额，则可以计算出他的数字。这个数字是唯一的，无论“揭示”的参与者集合如何
• 所要求的 PVRB 是揭示的随机数的组合

在这里，个别参与者不再影响协议结果，除了在随机性揭示阈值（M 从 N）恰好依赖于他的情况下。因此，考虑到有必要的可用诚实 RP 遵循规则，协议根据强密码学要求运作，并抵抗“最后参与者”问题。

这可被视为理想选项。基于 Fiat-Shamir 秘密分享的 PVRB 方案，在 这篇文章 中有描述。如我之前提到的，如果尝试在区块链中以其纯粹形式应用，那么技术限制不可避免地出现。这里有一个协议测试实现的例子，在 EOS 智能合约中，最重要的部分是检查发布的参与者份额：代码。很明显，证明验证需要进行几次标量乘法，而数字是非常大的。同时，我们应记住，在区块链中，验证函数是在区块生产者处理交易时被调用的。通常，任何参与者应该能够轻松验证协议的正确性，因此“verify()”函数的速度要求十分严格。我们的方案没有成功，因为验证没有满足交易时间限制（0.5 秒）。

验证效率是区块链中任何先进密码学方案最重要的要求之一。证明和消息生成可以在链外进行，并由高性能计算机执行，但验证不能被忽视——这是 PVRB 另一个重要需求。

PVRB 和阈值签名

秘密分享方案开启了一整类协议，统一在“阈值”这一伞下。当我们需要 M 个诚实参与者从 N 中披露某个信息时，就可以讨论“阈值”方案，诚实参与者的集合可以是 N 中任意子集。它们可以解决“最后参与者”的问题：如果攻击者不揭露他的秘密部分，其他诚实参与者将代为揭露。反之，这使我们能够就唯一的结果达成一致，即使某些参与者在破坏协议。

结合确定性签名和阈值方案，我们可以发展出一种非常便捷且有前景的 PVRB 方案——确定性阈值签名。这里有一篇 文章，关于各种阈值签名和用例，Dash 还提供了一篇不错的 长文。

最后一篇文章涉及 BLS 公钥和私钥的签名（BLS 是 Boneh-Lynn-Shacham 的缩写，你可以在 这里 了解更多），可以使用简单的数学运算进行组合——这对开发者很方便。这些组合仍然是有效密钥和签名，使其能够轻松将许多签名聚合为一个，并将多个公钥聚合为一个。它们的确定性使得在输入数据相同时获得相同的结果成为可能。由于这一特性，BLS 签名组合成为有效密钥，从而使得从 N 参与者中选取 M 个诚实参与者能够产生唯一的、可确定的，公开可验证的，且在 M 方揭示之前不可预测的签名。

在 BLS 阈值签名方案中，每个参与者都使用 BLS 签署某个内容（例如，先前的随机数）并将其份额发送到区块链。BLS 签名的密码学特性符合随机性质量要求，阈值部分对“最后参与者”具有保护作用，而唯一的密钥兼容性则允许许多有趣的算法（例如，有效聚合协议消息的算法）。

因此，如果你在 2019 年春夏季为你的区块链构建 PVRB，你很可能会选择 BLS 阈值签名方案；几个项目已在应用此方案。例如，DFinity （ 这里 ）是实现该方案基准工具，而 这里 是可验证秘密分享实施的一个示例）、Keep.network（其随机信标 黄皮书在这里，而管理协议的智能合约示例 示例 在这里）。

实现 PVRB

不幸的是，仍然没有实现真实的具有密码学强度的 PVRB 区块链协议，能在真实 DApp 中证明其安全性和稳定性。尽管现有的协议已准备就绪，但很难将其应用于现有解决方案。PVRB 对于中心化系统毫无用处，而去中心化系统在计算资源方面严格受限：CPU、内存、存储、I/O。开发 PVRB 涉及不同协议的组合，使其至少能够与一个真实可行的区块链匹配。某个协议在计算上更高效，但可能需要在 RPs 之间进行了更多的消息传递；另一个协议则需要很少的消息，但证明的生成可能需要十几分钟甚至几个小时等等……

在选择高质量的 PVRB 时，你必须考虑以下因素：

1. 它应具备密码学强度，即绝对不偏向于任何人，无法让任何人控制单个位或其他统计属性。对于某些方案不适用此条，因此最好请教密码学专家。

2. “最后参与者”问题。你的 PVRB 必须抵抗当一个攻击者操控一个或若干 RP 能选择两个可能结果之间的攻击。

3. 协议破坏。你的 PVRB 必须抵抗当攻击者控制一个或若干 RP 决定是否生成随机数时的攻击，并能够影响随机信标的生成。

4. 消息数量。你的 RP 应发送尽量少的消息到区块链，并尽可能避免同步行为，例如“信息发送，等待特定参与者的响应”。在对等网络中你不会期待快速回复，特别是在地理上分散的网络中。

5. 计算复杂性。任何 PVRB 阶段的链上验证应该是简单的，因为所有全网客户端都会进行。若实现智能合约，速度要求将非常严格。

6. 可及性和生存力。你的 PVRB 应该对可能的网络故障具备强韧性（即当其暂时不可用且部分 RP 停止工作时）。

7. 可信设定和初始密钥分配。如果你的 PVRB 涉及初级协议设置，这可能会导致某些问题。这里有一个 例子。如果参与者在启动协议之前必须互相告知密钥，这也会是个问题，因为参与者名单可能会发生变化。

8. 开发问题。所需语言中库的可用性、安全性和性能、公共可达性、复杂测试等等。

例如，阈值 BLS 签名存在一个显著瓶颈——在开始之前，参与者必须共享密钥并组织阈值组。这意味着我们不得不跳过至少一个回合的过程，并 而已鉴于随机数对于实时游戏至关重要，协议的破坏风险相当大，而阈值方案的优势便显得无用。这个问题比以前的问题更简单，但我们仍然需要开发一个独立的阈值组程序，这需要通过保证金和基金罚款（slashing）来保护协议实施 کا，如果参与者未遵照协议。此外，具有可接受安全级别的 BLS 验证会重叠标准 EOS 或以太坊交易-没有足够的时间来完成这个。合约代码由虚拟机执行- WebAssembly 或 EVM。加密功能尚未被原生实现，且速度比普通的加密库慢得多。许多协议根本不满足密钥长度的要求：例如，RSA 的 1024 和 2048 位。这是标准比特币和以太坊交易签名大小的 4-8 倍。

在不同的编程语言中也应该有实现，但当前并不多，特别是对于新协议。为了将 PVRB 集成到共识中，我们需要用平台语言编写代码，即寻找 Go 代码（用于 geth）、Rust（用于 Parity）和 C++（用于 EOS）。JavaScript 代码甚至更难找到，由于 JavaScript 和密码学并不密切相关，所以请阅读 WebAssembly。它看起来正在成为下一个重要的互联网标准。

结论

我希望在之前的文章中，我能说服你，区块链中的随机数生成对许多去中心化网络的诸多方面至关重要。今天我展示了这项任务极具雄心，又非常困难，但也有一些良好的解决方案。实话说，协议架构只有在进行涉及从设置到故障模拟的所有方面的大规模测试后才能被视为最终的。你不太可能在白皮书或文章中找到现成的食谱。我们也无法给出建议。在至少未来几年内。

到目前为止，在 Haya 区块链上进行开发，我们选择了阈值 BLS 签名，计划在共识层面实施 PVRB，因为智能合约不允许足够安全的验证。我们可能同时使用这两种方案：首先，使用昂贵的秘密分享创建长期的随机种子，随后将作为高频随机数生成的基础，采用确定性阈值 BLS 签名。我们可能会限制自己使用单一方案。无法提前说出协议将会如何，然而，在工程学中，负结果也是结果，每一次解决问题的新尝试都是研究各方的另一个进展。为了满足业务要求，我们目前在解决一个具体的实际问题——向游戏应用提供可靠的熵源，因此我们也必须关注区块链，特别是最终性问题和网络治理。

到目前为止，仍然没有一个经过验证的 PVRB 能够长时间使用，并在真实区块链应用中通过多次审计、负载测试和应对真实攻击；然而，一些潜在解决方案证明了总会有出路，其中一些算法最终将解决这个问题。我们乐意分享成果，同时感谢其他团队的文章和代码，让工程师们不会犯同样的错误两次。

所以，如果你遇到正在开发去中心化随机数生成器的开发者，请保持小心，并在必要时提供心理支持 :)

• MixBytes 是谁？

MixBytes是一个专业的区块链审计员和安全研究人员团队，专注于为 EVM 兼容和基于 Substrate 的项目提供全面的智能合约审计和技术顾问服务。请加入我们的 X，以跟上最新行业趋势和见解。

• 原文链接： mixbytes.io/blog/random-...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～