并行化Lamport的99%容错共识

并行化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个集合就足够了。

并行化Lamport的99%容错共识

扫一扫手机访问

发表评论