介绍
“随机数生成太重要了，不能靠运气。”
罗伯特·卡维，1970
本文致力于在不可信环境中使用集体随机数生成的解决方案的实际应用。 简而言之，如何以及为什么在区块链中使用随机数，以及如何区分“好”随机数和“坏”随机数。 即使在一台计算机上，生成真正的随机数也是一个极其困难的问题，密码学家长期以来一直在研究这个问题。 那么，在去中心化网络中，随机数的生成更加复杂和重要。
正是在参与者彼此不信任的网络中，生成无可争议的随机数的能力使我们能够有效地解决许多关键问题并显着改进现有方案。 此外，对于没有经验的读者来说，赌博和彩票并不是这里的首要目标。
随机数生成
计算机本身无法生成随机数；它们需要外部帮助才能做到这一点。 计算机可以从例如鼠标移动、使用的内存量、处理器引脚上的杂散电流以及许多其他称为熵源的源中获取一些随机值。 这些值本身并不是完全随机的，因为它们在一定范围内或者具有可预测的变化模式。 为了将这些数字变成给定范围内的真正随机数，可以对它们应用加密变换，以从熵源的不均匀分布值生成均匀分布的伪随机值。 得到的值称为伪随机，因为它们不是真正随机的，而是确定性地从熵导出的。 任何好的加密算法在加密数据时都会产生密文，这些密文在统计上应该与随机序列无法区分，因此为了产生随机性，您可以采用熵源，即使在小范围内，熵也只能提供良好的重复性和不可预测性，剩下的工作是分散和混合比特，结果值将由加密算法接管。
为了完成一个简短的教育计划，我要补充一点，即使在一台设备上生成随机数也是确保数据安全的支柱之一。生成的伪随机数用于在各种网络中建立安全连接时，以生成加密密钥，用于负载平衡、完整性监控以及更多应用程序。 许多协议的安全性取决于生成可靠的、外部不可预测的随机数、存储它并且在协议的下一步之前不泄露它的能力，否则安全性将受到损害。 对伪随机值生成器的攻击极其危险，会立即威胁到所有使用随机生成的软件。
如果您学过密码学基础课程，您应该了解所有这些，所以让我们继续讨论去中心化网络。
区块链中的随机性
首先，我会谈论支持智能合约的区块链；它们是能够充分利用高质量、不可否认的随机性所提供的机会的区块链。 此外，为了简洁起见，我将这项技术称为“可公开验证的随机信标”或PVRB。 由于区块链是任何参与者都可以验证信息的网络，因此其名称的关键部分是“可公开验证”，即任何人都可以使用计算来获得证据，证明发布在区块链上的结果数字具有以下属性：
- 结果必须具有可证明的均匀分布，即基于可证明的强密码学。
- 无法控制结果的任何位。 因此，结果无法提前预测。
- 您不能通过不参与协议或通过攻击消息使网络过载来破坏生成协议
- 上述所有内容都必须能够抵御允许数量的不诚实协议参与者（例如 1/3 的参与者）的串通。
少数参与者串通产生受控偶数/奇数随机的任何可能性都是一个安全漏洞。 该组织阻止随机发布的任何能力都是一个安全漏洞。 总的来说，问题很多，而且这个任务也不是一件容易的事……
看来PVRB最重要的应用是各种游戏、彩票以及区块链上的任何类型的赌博。 确实，这是一个重要的方向，但区块链中的随机性还有更重要的应用。 让我们看看它们。
共识算法
PVRB 在组织网络共识方面发挥着巨大作用。 区块链中的交易受到电子签名的保护，因此“对交易的攻击”始终是在一个区块（或多个区块）中包含/排除交易。 而共识算法的主要任务就是就这些交易的顺序以及包含这些交易的区块的顺序达成一致。 此外，真正的区块链的一个必要属性是最终性——网络能够同意直到最终确定的区块的链都是最终的，并且永远不会因为新分叉的出现而被排除。 通常，为了同意一个区块是有效的，最重要的是，是最终的，需要收集大多数区块生产者（以下简称BP——区块生产者）的签名，这至少需要交付区块链给所有BP，并在所有BP之间分发签名。 随着 BP 数量的增长，网络中必要的消息数量呈指数级增长，因此，需要最终性的共识算法（例如 Hyperledger pBFT 共识中使用的）无法以所需的速度运行，从几十个 BP 开始，需要大量的连接。
如果网络中存在不可否认且诚实的 PVRB，那么，即使是最简单的近似，人们也可以根据它选择一个区块生产者，并在一轮协议中任命他为“领导者”。 如果我们有 N 区块生产者，其中 M: M > 1/2 N 是诚实的，不审查交易，也不分叉链来进行“双花”攻击，那么使用均匀分布的不受挑战的 PVRB 将允许以概率选择一个诚实的领导者 M / N (M / N > 1/2)。 如果每个领导者都被分配了自己的时间间隔，在此期间他可以产生一个块并验证该链，并且这些时间间隔在时间上相等，那么诚实节点的区块链将比恶意节点形成的链更长，并且共识算法依赖于链的长度。将简单地丢弃“坏”链。 这种为每个 BP 分配相等时间片的原则首先应用于 Graphene（EOS 的前身），并允许大多数区块通过单个签名关闭，这大大减少了网络负载，并使这种共识能够极快地发挥作用。稳步。 然而，EOS网络现在必须使用特殊的区块（最后不可逆区块），这些区块由2/3 BP的签名确认。 这些区块用于确保最终性（链分叉不可能在最后一个不可逆区块之前开始）。
此外，在实际实现中，协议方案更加复杂 - 对提议区块的投票分几个阶段进行，以在丢失区块和网络问题的情况下维护网络，但即使考虑到这一点，使用 PVRB 的共识算法也需要BP 之间的消息显着减少，这使得它们比传统的 PVFT 或其各种修改更快。
此类算法最突出的代表： 来自卡尔达诺团队，据说可以在数学上证明反对 BP 串通。
在 Ouroboros 中，PVRB 用于定义所谓的“BP 时间表”——根据该时间表，每个 BP 被分配自己的时隙来发布区块。 使用 PVRB 的一大优势是 BP 完全“平等”（根据其资产负债表的规模）。 PVRB 的完整性保证了恶意节点无法控制时隙的调度，因此无法通过提前准备和分析链的分叉来操纵链，而选择分叉只需依靠分叉的长度即可。链，无需使用棘手的方法来计算 BP 的“效用”及其区块的“权重”。
一般来说，在去中心化网络中需要选择随机参与者的所有情况下，PVRB 几乎总是最佳选择，而不是基于区块哈希等的确定性选项。 如果没有 PVRB，影响参与者选择的能力会导致攻击，攻击者可以从多个 future 中进行选择，以选择下一个腐败参与者或同时选择多个参与者，以确保在决策中获得更大份额。 PVRB 的使用使这些类型的攻击变得不可信。
扩展和负载平衡
PVRB 在减少负载和扩展支付等任务中也有很大好处。 首先，熟悉一下是有意义的 Rivesta“电子彩票作为小额支付”。 总体思路是，您可以玩诚实的彩票，奖金为 100$ = 1c，而不是从付款人向收款人支付 1 笔 100c 的款项，其中付款人每人向银行提供 1 张“彩票”中的一张100c 付款。 其中一张彩票赢得了一罐 1 美元，接收者可以将这张彩票记录在区块链中。 最重要的是，剩余的 99 张门票可以在没有任何外部参与的情况下，通过私人渠道以任何所需的速度在接收方和付款方之间转移。 可以阅读 Emercoin 网络上基于此方案的协议的详细描述 .
该方案存在一些问题，例如接收者在收到中奖彩票后可能会立即停止为付款人提供服务，但对于许多特殊应用，例如按分钟计费或电子订阅服务，这些可以忽略不计。 当然，主要要求是彩票的公平性，而为了实现它，PVRB 是绝对必要的。
随机参与者的选择对于分片协议也极其重要，其目的是水平扩展区块链，允许不同的节点只处理自己范围内的交易。 这是一项极其困难的任务，特别是在合并分片时的安全性方面。 公平选择随机 BP 来分配负责特定分片的人员（如共识算法中那样）也是 PVRB 的任务。 在集中式系统中，分片由平衡器分配；它只是根据请求计算哈希值并将其发送到所需的执行器。 在区块链中，影响此分配的能力可能会导致对共识的攻击。 例如，交易的内容可以由攻击者控制，他可以控制哪些交易进入他控制的分片并操纵其中的区块链。 您可以阅读有关在以太坊中使用随机数进行分片任务的问题的讨论
分片是区块链领域最雄心勃勃、最严重的问题之一；它的解决方案将允许构建具有出色性能和容量的去中心化网络。 PVRB只是解决该问题的重要模块之一。
游戏、经济协议、仲裁
随机数在游戏行业中的作用很难被高估。 对于去中心化网络来说，在线赌场中的显式使用以及计算玩家行为影响时的隐式使用都是极其困难的问题，因为去中心化网络无法依赖随机性的中央源。 但随机选择也可以解决许多经济问题，并有助于构建更简单、更高效的协议。 假设在我们的协议中存在关于某些廉价服务的支付的争议，并且这些争议很少发生。 在这种情况下，如果存在无争议的 PVRB，则客户和卖家可以同意以给定的概率随机解决争议。 例如，客户获胜的概率为 60%，卖方获胜的概率为 40%。 从第一个角度来看，这种方法是荒谬的，但它允许您以精确可预测的胜负份额自动解决争议，这对双方都有利，无需任何第三方的参与，也不会浪费不必要的时间。 此外，概率比可以是动态的并且取决于一些全局变量。 例如，如果一家公司经营状况良好，争议数量较少且盈利能力较高，那么该公司可以自动将解决争议的概率转向以客户为中心，例如70/30或80/20，反之亦然，如果纠纷花费了很多钱并且是欺诈性的或不充分的，你可以将概率转向另一个方向。
许多有趣的去中心化协议，例如代币策划的注册中心、预测市场、联合曲线等等，都是经济游戏，其中良好行为得到奖励，不良行为受到惩罚。 它们通常包含保护措施相互冲突的安全问题。 受到数十亿代币“鲸鱼”（“大权益”）攻击的保护，很容易受到数千个小余额账户（“女巫权益”）的攻击，以及针对单一攻击采取的措施，例如非为使大量股份无利可图而产生的线性费用通常会因另一次攻击而失去信誉。 由于我们讨论的是经济博弈，因此可以提前计算出相应的统计权重，并简单地将佣金替换为具有适当分布的随机佣金。 如果区块链具有可靠的随机性来源并且不需要任何复杂的计算，那么这种概率性佣金的实施就非常简单，这使得鲸鱼和女巫的生活都变得困难。
同时，有必要继续记住，控制这种随机性中的单个位可以让您作弊，将概率减少或增加一半，因此诚实的 PVRB 是此类协议中最重要的组成部分。
哪里可以找到合适的随机数？
理论上，去中心化网络中的公平随机选择使得几乎任何协议都可以证明是安全的，可以防止串通。 基本原理非常简单 - 如果网络就单个 0 或 1 位达成一致，并且不到一半的参与者不诚实，那么，经过足够的迭代，网络就可以保证以固定的概率就该位达成共识。 原因很简单，因为诚实的随机抽样者在 51% 的情况下会从 100 名参与者中选择 51 名。 但这是理论上的，因为…… 在实际网络中，为了确保文章中的安全级别，需要主机之间的许多消息、复杂的多通道加密技术，并且协议的任何复杂性都会立即增加新的攻击向量。
这就是为什么我们在区块链中还没有看到经过验证的抗PVRB，它已经使用了足够的时间来通过真实应用程序、多次审计、负载，当然还有真实攻击进行测试，没有它就很难称之为产品真正安全。
然而，有几种有前途的方法，它们在许多细节上有所不同，其中之一肯定能解决问题。 借助现代计算资源，密码理论可以非常巧妙地转化为实际应用。 将来，我们将很乐意谈论 PVRB 实现：现在有几种实现，每个实现都有自己的一组重要属性和实现功能，并且每个实现背后都有一个好主意。 参与随机化的团队并不多，每个人的经验对其他人来说都极其重要。 我们希望我们的信息能够让其他团队借鉴前辈的经验，更快地行动。
来源： habr.com