13 | PBFT算法:有人作恶,如何达成共识?
该思维导图由 AI 生成,仅供参考
- 深入了解
- 翻译
- 解释
- 总结
PBFT算法是一种能在实际场景中落地的拜占庭容错算法,在区块链中得到广泛应用。相比口信消息型拜占庭问题之解,PBFT算法解决了消息数指数级暴增的问题,能够在拜占庭错误发生时达成共识。文章介绍了口信消息型拜占庭问题之解的局限,指出其消息复杂度为指数级暴增,难以在实际场景中落地。而PBFT算法通过改进,能够在实际场景中应用,为读者提供了对PBFT算法的基本原理和实际落地应用的理解。PBFT算法通过签名约束恶意节点的行为,采用三阶段协议,基于大多数原则达成共识。与口信消息型拜占庭问题之解不同,PBFT算法实现的是一系列值的共识,而不是单值的共识。相比Raft算法,PBFT算法能容忍(n - 1)/3个恶意节点或故障节点,适用于相对“可信”的场景中,如联盟链。然而,PBFT算法的消息复杂度为O(n ^ 2),随着消息数增加,网络时延对系统运行的影响也会增大,限制了其适用范围为中小型分布式系统。 PBFT算法通过视图变更的方式处理主节点作恶,当发现主节点作恶时,会推举新的主节点。总体而言,PBFT算法在解决实际共识问题方面取得了重要进展,但仍需在中小型分布式系统中使用。
《分布式协议与算法实战》,新⼈⾸单¥59
全部留言(38)
- 最新
- 精选
- 笑若海如果接收到小于f+1个消息就认可服务返回结果,可能都是来自f个恶意节点的消息,导致客户端接受恶意结果。f+1保证至少一个正确结果,如果其中存在恶意消息,客户端会发现不一致性,认为请求处理失败。 这又引发一个新问题,客户端怎么确定f值?
作者回复: 加一颗星:),f = (n - 1)/3
2020-03-11317 - DFW对于 pbft 算法,核心过程有三个阶段,分别是 pre-prepare (预准备)阶段,prepare (准备)阶段和 commit (提交)阶段。对于 pre-prepare 阶段,主节点广播 pre-prepare 消息给其它节点即可,因此通信次数为 n-1 ;对于 prepare 阶段,每个节点如果同意请求后,都需要向其它节点再 广播 parepare 消息,所以总的通信次数为 n*(n-1),即 n^2-n ;对于 commit 阶段,每个节点如果达到 prepared 状态后,都需要向其它节点广播 commit 消息,所以总的通信次数也为 n*(n-1) ,即 n^2-n 。所以总通信次数为 (n-1)+(n^2-n)+(n^2-n) ,即 2n^2-n-1 ,因此pbft算法复杂度为 O(n^2) 。
作者回复: 加一颗星:)
2020-05-09316 - 沉淀的梦想客户端要收到 f+1 个结果,我理解这个是为了防止 f 个叛徒直接给客户端返回 ok。不太理解的是为什么准备阶段要收到 2f 个一致的包含作战指令的准备消息,提交阶段需要 2f+1 个验证通过呢?这两个也设置成 f+1,不可以吗?
作者回复: 加一颗星:),问题1:2f个准备消息和预准备消息是相同的,所以,加上主节点,就是2f + 1了,也就是说准备阶段的2f个,等同于提交阶段的2f + 1。问题2:如果设置为f + 1,那么就会被恶意节点干扰,比如,在准备和提交阶段,f个恶意节点,都很配合,但在最后,它们却不返回响应消息给客户端,这时客户端可能始终无法收到f + 1个一致的响应消息,也就是达成共识失败,然后客户端不断重试,肯定不行了。
2020-03-11212 - 竹马彦四郎的好朋友影法師我按照老师第一讲的OM算法写了个简单的递归(https://yfscfs.gitee.io/post/极客时间之分布式协议与算法实战-01-拜占庭将军问题有叛徒的情况下如何才能达成共识/) 几乎不可用,22个节点的拜占庭将军问题,至少要吃掉2个G的内存才能跑出结果~
作者回复: 加一颗星:),你的演示程序和内存问题的分析,我看了,很棒,我后面补充个演示程序吧。
2020-05-059 - Fs这就是为什么区块链的效率提升不上去?达成共识的时间效率太低
作者回复: 加一颗星:),是的,这也是为什么Hyperleger Fabric最终没有采用PBFT,而是通过法律来约束“节点作恶”的行为。
2020-03-124 - 6 7 8 9 10最后消息数的算法,看不懂呢
作者回复: 对哪一步的计算,不理解呢?
2020-03-114 - superfq请问老师,f值是怎么确定的?在一个动态集群中怎么确定f值
作者回复: 加一颗星:),f = (n - 1)/3。
2020-06-173 - myrfy老师,可以详细解释一下视图变更是什么意思吗
作者回复: 好,我后面补充下,具体说说和演示下。
2020-03-113 - 右耳听海麻烦老师补充下pbft实现一系列共识值pbft做了些什么优化,消息数是随一系列值倍数增加吗
作者回复: 加一颗星:),是倍数增加的,相当于一轮新的共识协商。更多细节,我后面补充说说吧。
2020-03-152 - Purson如果将军数为 n、叛将数为 f,那么算法需要递归协商 f+1 轮,消息复杂度为 O(n ^ (f + 1)),是怎样算出来的,第一讲说了两轮的能看明白,但是没有说3轮的,找不到递推关系,希望老师详细说一下BFT和PBFT两者区别
作者回复: 加一颗星:),问题1:和另外一个问题重复了,详细推导过程和原理,我后面做个补充。问题2:BFT一般是拜占庭容错,在这里,你指的是指口信消息型拜占庭问题之解(om)吧?om与PBFT主要区别,除了消息复杂度外,还有就是om不关心达成共识的值是什么,pbft是就指定值达成共识;om非常理论,很难在实际场景中落地,pbft实用,在实际场景中,能落地。
2020-03-132