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
