找回密码
 立即注册

扫一扫,登录网站

首页 百科 查看内容
  • 2195
  • 0
  • 分享到

并行化Lamport的99%容错共识

2018-9-16 06:56

来源: Unitimes 作者: Vitalik Buterin

并行化Lamport的99%容错共识


如果我们想要实现95%的容错,那么为了达到2−40(大约1万亿分之一)的失败率,我们需要有足够的随机抽样节点,同时有2−40的概率导致这些节点都是攻击者,这需要 log(2−40)÷log(0.95) ≈ 540个节点。

这意味着如果我们想要在 δ 网络延迟中存活的话,则每个参与者的扩展周期将需要是2 *δ,因此整个算法需要花费1080 *δ时间来运行。鉴于网络延迟假设本身必须非常保守,这是非常不理想的。

我们可以改进这个算法,在 n 轮运行中得到1−O(1)/n的容错。假设我们选择了一大组节点(接近无限大),并将它们全部安排到n的子集中,其中每个子集并行运行共识。

如果攻击者控制了≤1−ln(2)/n的份额,那么其完全控制任意给定集合的概率<1/2。每个用户可以接受共识的输出作为各个共识过程的模态(即最频繁的)结果。

因此,攻击者需要破坏超过一半的集合,而当集合的数量接近无穷大时,这种可能性接近于零。

更具体地说,假设有700个集合并行运行,我们的目标是实现1−1/n的容错。那么攻击者有1/e 的可能会完全控制任一给定的集合。

攻击者控制多数集合的概率是约为2−40.36。如果我们将容错放宽到1−2/n,那么攻击者完全控制任意给定集合的概率只有1/e2,这时我们只需要68个集合就足够了。同理,实现1−3/n容错只需要32个集合就足够了。
版权申明:本内容来自于互联网,属第三方汇集推荐平台。本文的版权归原作者所有,文章言论不代表链门户的观点,链门户不承担任何法律责任。如有侵权请联系QQ:3341927519进行反馈。
标签: 容错共识
相关新闻
发表评论

请先 注册/登录 后参与评论

    回顶部