前沿资讯网>比特币>正文

共享硬币算法

摘要
共享硬币算法, 既然最多有/ 个节点崩溃,所有的节点总会接收到n - / 个硬币 和 n - / 个硬币集 (第 3 行和第 5 行)。因此,所有的节点能够顺利运行并且也能保证结束。

 硬币称重算法,硬币算法


    1 :以 1/n 的概率使本地硬币cu = 0,否 则 cu = 1


    2:广播 myCoin(cu)


    3 : 等 待 n _ / 个硬币到来,并将它们存储在本地的硬币集合


    4 : 广播 mySet(Cu)


    5 : 等 待 n - / 个硬币集合


    6: i f 在这些集合中,至少有一个硬币为 0 then


    7: return 0


    8: else


    9: return 1


    10: end if


    既然最多有/ 个节点崩溃,所有的节点总会接收到n - / 个硬币 和 n - / 个硬币集 (第 3 行和第 5 行)。因此,所有的节点能够顺利运行并且也能保证结束。


    我们现在证明算法在/ < n/ 3 时的正确性。为了简化证明过程,我们假定 n = 3 / + 1,也就是说,我们假定最坏的情况。


    引 理 3.23. W是一个节点,W 是硬币集,W 中的每个硬币至少出现 在 / + 1 个 被 u 接收到的硬币集合中。贝lj |則 彡 / + 1成 立 。


    证 明 .我 们 用 C7 来 标 记 u 接收到的所有硬币的多重集合u 。注意, M接收到的硬币正好是 |C | = (n _ /)2 个 (可能有重复)。因 为 w 接收了ra- / 个硬币集,而每一个硬币集中包含n —/ 个硬币。


    假设引理 3.23不成立,那么,最多 只 有 / 个硬币出现在全部n - /个硬币集中,而其他所有的 (n - / ) 个硬币最多只出现在/ 个硬币集中。换句话说,w 接收到的所有硬币数将受下面的限制:


    1^1 ^ /?(?-/) + (?-/)?/ = 2/(n - /).我们的假设是n > 3 /,也就是说,n-/ > 2 / 。因此,|(7|彡2/(n - / )< (n - /)2 = |C7|:矛盾。

引 理 3.24.所有好节点都能看到W 中的所有硬币。


    证明 .设硬币 w e W 。根 据 灰 的 定 义 ,我们知道w 至少出现在 / + 1个节 点 u 所接收到的硬币集中。由于每一个其他节点也需要接收到n - /个硬币集才能结束等待,因此每一个节点也将收到上述/ + 1个硬币集合中的至少一个。由此可见,w 必然发送到在每一个节点中。 

11译者注:多重集合中,同一个元素可以出现多次。


    12译者注:若引理3.23不成立,则最多有/ 个硬币出现在/ + 1个集合中。但 是 n = 3 / + l ,因 此 / + 1 < ? _ / 。这样我们依旧得到了上述式子。


    定 理 3.25.如果崩溃的节点最多为/ < n/3,算 法 3.22实现了一个共享的硬币13。


    


    证明.我们先估计算法中所有节点都返回1 的概率值的下界。根据算法第 1 行,所有节点选择硬币值等于1 的概率为 (1 —l /n)" ? 1/e s 0.37。


   在这种情况下 1 会成为最终的决策值。这只是所有节点选择1 为决策值的下限,在很多其他情况下,1 也有机会成为决策值,这取决于消息传输的情况以及节点崩溃的情况。但 是 0.37的概率已经足够好了,所以我们也不需要再考虑这些其他的场景。


    在 W 中至少出现一个0 的概率为 1 —(1 - l /r〇,l,根 据 引 理 3.23我 们 知 道 |則 彡 / + 1 ? n/ 3 , 因此这个概率值约为1 —(1 _ l /n)n/3 ?1 - (1/e)1/3 s 0.28。这 个 0 将被所有的节点看到(引 理 3.24),因此所有节点都决定选择0 值。


    由此可见,算 法 3.22实现了一个共享的硬币。


    我们只证明了最坏的情况。通过选择较小的/ ,很 显 然 / + 1兴n/3。但是 ,引 理 3. 23也 适 用 于 |W | 彡 n - 2 / 的情况。要证明这个结论需要替换在证明过程中导出矛盾的论述:最多n - 2/ —1 个硬币能出现在所有的n _ / 个硬币集中,并且(n _ 2 / _ 1) = 2/ + 1个硬币可出现在最多/ 个硬币集中。


    剩下的证明过程就类似了,唯一的不同在于其中的数学部分不是很简单,需要稍作变换。利用修改的引理我们知道 |W | > n/3,因此定理3.25在 任 何 / < n/ 3 的情况下都成立。


    我们隐含了一个假设:消息的传递时间和顺序是随机的。如果我们需要一个 0 值 ,但是想要推举 0 值的节点发送消息很缓慢,那么没有节点会看到这些 0 值 ,这样的话算法也不能继续进行。


    定 理 3.26.将 算 法 3.22和 算 法 3.15结合起来,我们就得到一个随机共识算法,这个算法能在常数级的可预期的轮数中结束,并且能容忍最 多 / < n/ 3 个节点崩溃。


    【免责声明】以上文章是今日小编为您介绍硬币算法的个人观点,请读者仅作参考,投资有风险,入市须谨慎!本站不拥有所有权,不承担相关法律责任。如需了解“硬币称重算法”请关注:【什么是区块链 http://www.whw999.com/chain/】,如若转载,请注明。


什么是比特币(Bitcoin)

[1]什么是比特币(Bitcoin)在2009年诞生以来,刚开始几乎一文不值,并且只有小众的技术圈粉熟悉;短短几年发展迅速,

09月18日 10:51

比特币的意义和价值,比特币今日有哪些价值

比特币的意义和价值,比特币今日有哪些价值,直到今天,关于比特币的话题仍充满了不少争议。但大部分人应该都会认可,比特币 是数字货币历史上,

09月17日 15:00

美国的销售税和比特币可能令人困惑

美国的销售税和比特币可能令人困惑,在美国的过去两年中,联邦政府和各州一直试图掌握加密货币的概念,并将其应用于传统的金融法律,如税收。

09月13日 14:25

比特币价格应稳定在5000美元附近,比特币今日价格如何走势

比特币价格应稳定在5000美元附近,比特币今日价格如何走势,主流经济学家在其下行趋势期间对比特币说些好话并不常见,但Mohamad El-Erian再一次例外。

09月13日 14:11

重新审视ICO诈骗,ICO受证券法保护的美国法官规则

重新审视ICO诈骗,ICO受证券法保护的美国法官规则,布鲁克林的一位美国地区法官作出了具有里程碑意义的判决,对最初的硬币发行(ICO)市场产生了深远的影响。

09月12日 15:42