Geekly articles weekly

随机数和分散网络：实现

引言


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必须在不包含复杂密码学且不需要大量交互的现有网络上运行。


共识整合


在该实施例中，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可能会成为“双重支出”攻击的受害者的用户，当BP“持有”区块并在网络“看到”一笔好的交易后将其发布时，终结性至关重要。 如果没有确定性，则已发布的派生用“坏”派生中的另一个用“好”交易替换该区块，在该交易中，相同的资金被转移到攻击者的地址。 就PVRB而言，确定性的要求仍在收紧，因为PVRB叉的构造意味着攻击者可以为随机房屋准备几种选择，以便为他发布最有利可图的东西，并限制可能的攻击时间是一个很好的解决方案。


因此，最好的选择是将PVRB和最终性结合在一个协议中-然后，最终块=随机完成，这正是您必须获得的。 现在，玩家将在N秒内获得有保证的随机性，并且他们可以确定不可能回滚或重放它。


共识集成选项是好的：


  • 关于块生成的异步实现的可能性-像往常一样生成块，但是与此同时，PVRB协议可以工作，这不会使每个块都是随机的
  • 能够执行甚至繁重的加密，而不受智能合约的限制
  • 能够以比交易更快的方式组织消息传递的能力，包括在区块链中，例如，部分协议可以在节点之间工作，而无需在网络上传播消息

它也有缺点：


  • 测试和开发中的困难-您必须模拟网络错误，节点丢失，网络硬分叉
  • 实施错误需要硬分叉网络

两种PVRB实施方法都具有生命权，但是现代区块链中的智能合约实施仍然在计算资源上非常有限，并且通常很难完全过渡到严格的密码学。 我们将需要认真的加密，这将在后面进行演示。 尽管此问题显然是暂时的，但需要使用合同中的严格加密技术来解决许多问题，并且这种情况逐渐出现（例如，以太坊中zkSNARK的系统合同）


提供透明和可靠的协议消息传递通道的区块链这样做是有原因的。 任何分散式协议都必须考虑到Sybil攻击的可能性，任何行动都可以由许多帐户的协同力量来完成，因此，在设计时，有必要考虑攻击者创建任意数量的协议参与者进行共谋的能力。


PVRB和块变量。


当我说到目前为止，还没有人在区块链中实施经过许多赌博应用程序验证的良好PVRB时，我没有撒谎。 那么，以太坊和EOS中如此众多的赌博应用程序在哪里呢？ 就像您所做的一样，这让我感到惊讶，好吧，您是从哪里来的呢？


在区块链中获得随机数的最喜欢的方法是从区块中获取某种“不可预测的”信息，并基于此信息进行随机化-仅缓存一个或多个值。 一篇关于这种方案问题的好文章。 您可以在块中采用一些“不可预测的”值，例如，块的哈希值，事务数，网络的复杂性以及其他预先未知的值。 然后将它们缓存一个或多个，理论上，您应该得到一个真正的随机数。 您甚至可以在方案中补充说，您的方案是“后量子安全的”（因为有量子安全的哈希函数:)）。


但是，即使是量子后安全哈希也不够用。 秘密在于对PVRB的要求，我从上一篇文章中回忆到它们：


  1. 结果应具有可证明的均匀分布，即基于可证明的强密码学。
  2. 无法控制结果的任何位。 结果，结果不能被预先预测。
  3. 您不能通过不参与协议或通过向网络过载攻击消息来破坏生成协议
  4. 以上所有内容均应避免串通协议中允许的不诚实参与者（例如，参与者的1/3）。

在这种情况下，仅满足条件1，不满足条件2，从块中散列不可预测的值，我们得到均匀的分布和良好的随机性。 但是BP至少有能力“发布或不发布”。 因此，BP至少可以从两个选项中选择随机性：“我们的”，如果有人制造障碍物，BP就会出现。 BP可以预先“监视”发布块的情况，然后决定是否执行。 因此，例如在轮盘赌中玩“奇偶”或“红/黑”游戏，他只有在看到获胜的情况下才能发布游戏。 它还为使用（例如）将来的区块的哈希值制定了无效策略。 在这种情况下，他们说“将使用随机数，该随机数是通过对当前数据和将来的块的哈希值进行哈希处理而获得的，该哈希值的高度为N + 42，其中N为当前块的高度。 这在某种程度上增强了该方案，但是尽管将来，它仍然允许BP选择，保留该块或进行发布。


在这种情况下，Soft BP非常复杂，但并不多。 只是在验证交易并将其包含在区块中时，会进行快速检查以查看是否会有收益，并可能会选择一个交易参数，以便获得很高的获胜概率。 同时，几乎每次都可以使用新的地址来赢取一点，而不会引起怀疑，因此很难抓住这样的操纵方法。


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


PVRB和提交发布。


好吧，这要归功于散列，至少得益于块散列和其他变量的相对不可预测性。 如果您解决了领先的矿工的问题，那么您应该得到一些更合适的东西。 让我们将用户添加到该方案中-尽管它们也会影响随机性：任何技术支持人员都会告诉您，IT系统中最随机的是用户操作：）


当用户仅发送随机数并且将结果计算为例如其总和的哈希值时，幼稚的方案不适合。 在这种情况下，最后一个玩家可以选择自己对结果的随机控制。 因此，使用了非常广泛使用的提交公开模式。 参与者首先从其随机数（commit）发送哈希，然后自己打开随机数。 “公开”阶段仅在收集了必要的提交之后才开始，因此参与者可以准确发送他们较早发送哈希值的随机数。 现在，我们将所有这些参数都用块的参数盲目了，它比从未来获得的参数更好（您只能在将来的一个块中找到随机性），瞧-随机已经准备好了！ 现在，任何玩家都可以影响最终的随机性，并且可以通过使用自己以前未知的随机变量阻止恶意BP来“击败”恶意BP。您还可以通过不在披露阶段打开协议来增加对协议破坏的保护-只需承诺对交易应用一定的金额即可-保险押金，仅在揭露程序期间退还。 在这种情况下，进行提交而不进行显示将是不利的。


这是一个很好的尝试，并且这种方案也出现在游戏DApp中，但是，这还不够。 现在，不仅是矿工，而且协议中的任何参与者都可以影响结果。 仍然可以用较小的可变性和金钱来控制价值本身，但是，像矿工一样，如果抽奖的结果比PVRB协议中的参与费更有价值，则随机生产者（RP）可以决定是否披露并且仍然可以从至少两个随机选项中进行选择。
但是，有机会惩罚那些犯有不披露义务的人，这种方案仍然有用。 它的简单性是一个主要优势-更严格的协议需要功能更强大的计算。


PVRB和确定性签名。


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


但是，即使具有确定性签名，该架构仍然容易受到“最后参与者”问题的影响。 最后的参与者仍然可以决定是否发布他的签名，从而控制结果。 您可以细化方案，向其添加块哈希，进行回合，以便无法提前预测结果，但是所有这些方法，即使考虑了许多改进，仍然无法解决一个参与者在不受信任的环境中对集体结果产生影响的问题，并且只能起作用在经济和时间限制的情况下。 此外，RSA密钥（1024位和2048位）的大小非常大，而区块链交易的大小是一个非常重要的参数。 显然，以一种简单的方式将无法正常工作，我们可以走得更远。


PVRB和秘密共享计划


在密码术中，有一些方案可以允许网络就PVRB的一个值和唯一一个值达成一致，而此类方案可以抵抗部分参与者的任何恶意行为。 要了解的一种有用协议是Shamir的秘密共享方案。 它用于将秘密（例如，秘密密钥）划分为几个部分，并将这些部分分发给N个参与者。 秘密的分配方式是，N中的M个部分足以恢复它，而它可以是M个部分。 如果在手指上，然后具有未知功能的图，则参与者交换图上的点，并且在接收到M点之后，可以恢复整个功能。
Wiki中给出了一个很好的解释，并且在演示页面上使用它进行操作实际上会失去头脑中的协议。


如果FSSS（菲亚特-沙米尔秘密共享）方案以其纯净形式适用，那将是无可匹敌的PVRB。 在最简单的版本中，协议可能如下所示：


  • 每个参与者生成自己的随机变量，并将其分配给其他参与者
  • M shares, , ,
  • random- PVRB

, , threshold- . , RP , , “last actor”.


, PVRB secret sharing - , , . , , , . - EOS — share : . , proof- , . , verify , block-producer , , verify . , (0.5 ).


— - . proof-, — off-chain , — PVRB.


PVRB threshold signatures


secret sharing, , “threshold”. M N, N, “threshold” . “last actor”, , , . , .


threshold- PVRB — threshold-. threshold-, longread Dash.


BLS (BLS Boneh-Lynn-Shacham, ), — , , BLS , , . . , BLS , , M N , , publicly verifiable, , M- .


threshold BLS signatures BLS - ( ), threshold- . BLS , threshold- “last-actor”, , , , .


, PVRB , BLS threshold signatures, . , DFinity ( , , verifiable secret sharing), Keep.network ( random beacon yellowpaper , -, ).


PVRB


, , PVRB , . , , . PVRB , : CPU, memory, storage, I/O. PVRB — , , . , RP, , proof- , .


, PVRB:


  • . PVRB unbiasable, . ,
  • “last actor” . PVRB , , RP .
  • . PVRB , , RP , ,
  • . RP “ , ”. p2p , ,
  • . PVRB on-chain , . -,
  • liveness . PVRB , RP
  • trusted setup . PVRB setup , . . - — ,
  • . , , , ..

threshold BLS — , , , threshold. , , , , , , , realtime, , , threshold . , threshold-, , (slashing) , . , BLS , , EOS Ethereum — . — WebAssembly EVM, . (), . , 1024 2048 bit RSA, 4-8 , Bitcoin Ethereum.


— , . , Go geth, Rust Parity, C++ EOS. JavaScript , JavaScript , WebAssembly, -.


结论


, , , , , . , , setup- , whitepaper- , - “ , ”.


, PVRB Haya , threshold BLS signatures, PVRB , - . , : secret sharing random_seed, threshold BLS , . , , , , , , — , , . — , , governance .


PVRB, , , , , , , , , , - . , , .


, , , , :)

Source: https://habr.com/ru/post/zh-CN452340/

More articles:


All Articles