区块链随机数生成面临的挑战

2019-01-11 11:01 栏目:经验之谈 来源:网络整理 查看()
随机数的生成在计算中一直很重要。虽然本地和云计算已经拥有可靠的伪随机数发生器(PRNG),但区块链提出了新的挑战。一般而言,区块链和Web 3的目标之一是网络中的计算机不需要相互信任。

从基本的意义上说,网络中的计算机在没有相互信任的情况下运行的方式是让多台计算机执行相同的软件,并且仅在某些部分(通常但不总是1/2或2/3)。只有在协议的结果是出于超出本文范围的原因达成一致的。

对于更新帐户余额等程序来说,这并不难。从帐户a的余额中减去一个数字,加上相同的数字减去帐户b的交易成本。但如果有随机性怎么办?

为什么这很重要?

1.协议:大多数股权证明算法使用随机函数来选择下一个验证器。如果随机性是可预测的或可偏置的(稍后更详细地讨论),则该组验证器可能被破坏。

2.应用程序:几乎所有应用程序(游戏,投票(候选订单)等)都是使用随机数生成的,用户不能依赖有偏见的应用程序。

首先,简要介绍伪随机数的生成。虽然有许多算法,但大多数PRNG都以“种子”——开头。基于某个值的0和1选择序列,例如,如何在屏幕上移动鼠标。 PRNG使用种子作为特殊曲线的起点,并且内部算法在曲线周围反弹,输出一系列确定但看似随机的数字(即,基于最后n个值的知识,除了概率曲线无法可靠地预测分布函数外的n + 1个值)。

本文不是讨论特定的曲线或算法,而是关注随机数生成的预期属性,区块链的特定挑战以及计算随机数的最佳时间和位置。
我们想要满足两个属性:
的随机性
不可预测的——被动对手无法通过观察系统提前预测结果。
无偏的——一个积极的对手不能通过操纵或隐藏结果来偏向系统。

由于计算机无法生成真正的随机数,我们要么需要一种方法来同意PRNG种子的数量,要么我们需要一些外部形式值来满足不可预测性和不可替代性。

已经使用的一种方法是使用散列函数的输出。它们没问题,但在实际执行之前,无法确定输出是基于输入的。为什么我们不同意使用当前或未来块头的某些哈希值作为随机数?假设你有一个投掷硬币的游戏。您可以获取块头哈希的最低有效位(LSB),然后使用0或1作为结果。由于所有权力都花在哈希值上,为什么不充分利用哈希值?

但是如何让块哈希生成器发布这个块呢?在工作证明区块链中,发布有效块的动机是块奖励。例如,如果散列的LSB为1,则块生成器将赢得$ 1,000,但是他的有效块以0结束,并且当前块的奖励等于$ 300。在这种情况下,他可以选择不扩散区块,因为如果他让另一个矿工找到该区块,那么预期值为500美元。

因此,这里,矿工赢得下注的概率大于50%(即,从他的网络散列功率百分比到1的跨度的50%)。

这可能只会产生50.001%的最终概率,但在高频交易和其他概率活动中,与竞争对手相比,这种规模优势可带来数百万美元的利润(我希望以协商一致的方式进一步解释任何共识)相关信息应该是专门用于共识咨询。工作证明经常被批评为“浪费”能量,并且一些解决方案是将这些CPU周期用于双重和通常利他目的,例如蛋白质折叠。浪费的能源实际上是保证链条安全的一个因素。:如果蛋白质折叠突然变得有价值,那么链安全性将成为第二优先。一旦您引入其他激励措施(例如将应用程序的输出引入共识参数),其中一个(咨询或应用程序)将被操纵。

我们的第一个目标(不可预测性)是一个更容易实现的目标,并已在分布式计算中得到解决。多人游戏就是这样的应用程序。:您希望游戏不可预测,但需要在许多本地计算机上执行,并且游戏的整体状态需要在参与者之间保持一致。第二个更难,因为你怎么能强迫别人说出他们不喜欢的东西呢?

理想情况下,我们应该有一个可验证的PRNG(我们假设PRNG是不可预测的)。可验证函数的计算时间和验证时间分别为p和np。这实际上意味着计算解决方案可能非常密集,但很容易验证它是否正确。

一个好的应用是验证器选择方案。每个人都会检查她是否是验证员。如果是这样,她可以计算并提出一个块。每个人都可以检查他们的验证器状态并验证实际验证器的真实性,这比从头开始计算验证器的任何人都快(并且在验证器提出阻止之前尝试贿赂或攻击验证器)。


最近,Dan Boneh在一篇关于可验证延迟函数的论文中提出了解决这个问题的方法。 VDF提出的功能只能在单个CPU线程上计算(通常基于多个方块),以防止有更多CPU的对手使用并行处理来计算解决方案。使用nsteps进行计算的VDF解决方案可以在log(n)步骤中进行验证,因此诚实的节点可以比对手计算新解决方案更快地验证解决方案的正确性。

Boneh关于VDF的论文直到2018年才发表,他们甚至承认他们的样本功能需要改进。这是最前沿的工作,我们可以期待很多进步。

解决第二个特征(无偏见)很困难,因为您无法强迫某人执行计算或显示结果。目前最重要的方法是提交公共计划。我们的目标是公开同意PRNG种子,以便没有人可以通过秘密改变种子或拒绝传播解决方案来偏向结果。

首先,每个人都同意使用伪随机函数。之后,很容易验证每个人都在使用正确的函数,因为我们可以自己运行该函数并验证结果。现在我们需要同意使用什么种子,但我们不希望任何人提前知道种子。

例如,让我们制作一个三参与提交 - 显示方案:应用程序所有者(例如在线赌博网站),用户和执行计算的节点。每一方都可以生产种子,但不会透露。相反,每一方都显示种子的哈希值。

此时,每一方都有自己的种子和另一个种子的哈希。接下来,每个人都展示他或她真正的种子。伪随机函数的最终种子是S=S1 XOR S2 XOR S3

如果你是S3并且你收到S1和S2,你现在可以创建一个新的S3',它可以翻转你需要的任何比特来获得你想要的最终种子。但是你已经发送了S3的哈希值。如果你之后尝试更改S3,每个人都会知道!每个人都承诺在他们知道其他种子之前创造种子,即使一方没有透露计算结果,其他人也是必要的。该信息用于计算功能输出并同意。

该委员会的披露计划仍有缺陷。:最后披露的人可以在其他人面前查看最终结果,并决定不透露结果是否不好。原则上,有两种方法可以解决这个问题。:技术上和经济上。例如,技术解决方案可以使用智能合约来保存单个种子,然后在双方确认他们已经接收到每个种子的散列之后显示所有种子。在经济上,您可以惩罚那些不透露您身份的人。

这是一个相当高的水平,这仍然是一个悬而未决的问题;新的解决方案可能存在缺陷。随机性和决定论是对立的,因此令人信服的是,他们不信任的人所产生的随机数将成为分散计算中不断变化的挑战。

[1]在集中计算中,我们依靠监管机构和国家来惩罚不公平行为,但我们的目标是通过计算完成这项任务,因为攻击要么不可能,要么代价高昂。

[2]有些应用实际上是这样做的,不要使用它们!

[3]人类可能正在努力解决这样的问题。:“300美元肯定比50美元50%的机会更有价值吗?”但对于可能下注数千次的计算机,答案显而易见。

[4]攻击更容易证明公平。更改任何参数会更改输出的哈希值。例如,将时间戳更改1毫秒。现在您需要做的就是贿赂验证者。

[5]如果您将视频游戏视为分布式状态机,那么它就是一个很好的例子。状态可以由每个角色的坐标,状态,健康,财富,武器收集等来表示。虽然所有用户都有不同的硬件和不同的连接速度,但所有用户都需要尽可能接近实时地计算和同意这种状态。这或多或少通过中央游戏服务器作为某种管弦乐指挥来完成,以确保每个人都在运行正确的软件。将状态设置为帐户的键值存储,并将导体替换为资源证书,以便您基本上可以利用以太坊。

{6}将数字提升多次的原因是每一步取决于前一步的结果,这在普通代数中不是这种情况,而是在具有溢出或模运算的固定大小的位数组中。

[7] XOR本质上是一个开关。 0不做任何事,1拨动开关。也就是说,0 XOR 0=0,0 XOR 1=1,1 XOR 0=1,1 XOR 1=0.假设应用程序将使用前100个随机数,攻击者希望通过操纵S来获得优势。选择此S,攻击者需要尝试数十亿种子,然后使用最有利于前100种输出的种子。要选择S3',将所需的S与S1 XOR S2进行比较,其中S3'为0,它们匹配,1为不一致。

微信二维码
微信客服二维码

文章均源于网络收集编辑侵删

提示:不接受技术开发以外的任何咨询!

郑重申明:左链接科技以外的任何单位或个人,未经同意不得擅自转载该文章!
虚拟币开发,虚拟币交易平台开发,山寨币交易平台开发 Keywords: 虚拟币开发 虚拟币交易平台开发 山寨币交易平台开发