【PBFT算法】

口信消息型拜占庭问题之解的局限

该算法存在两个主要问题：

• 消息复杂度高：将军数为n、叛将数为f时，算法需要递归协商f+1轮，消息复杂度为O(n^(f+1))。例如叛将数为64时，消息数量远超int64表示范围。
• 理论化严重：算法仅关注忠将达成共识，不关心共识结果是否合理（如适合进攻时可能达成撤退共识）。

PBFT算法的核心原理

PBFT通过签名约束恶意节点行为，基于三阶段协议和大多数原则（2f+1）实现共识：

三阶段协议

1. 预准备阶段：主节点广播预准备消息给备份节点。
2. 准备阶段：备份节点广播准备消息，确认收到一致的指令。需收到2f个一致消息才进入下一阶段。
3. 提交阶段：节点广播提交消息，收到2f+1个验证通过的消息后执行指令。

关键点

• 签名机制：防止伪造消息，确保消息来源和内容可信。
• 客户端验证：客户端需收到f+1个相同响应才确认共识达成。
• 视图变更：主节点作恶时，通过轮换机制选举新主节点。

消息复杂度优化

PBFT将消息复杂度从O(n^{(f+1))降至O(n}2)，但仍需较多消息。例如13节点集群（f=4）需237条消息，适用于中小型系统。

适用场景

• 联盟链：如Hyperledger Sawtooth、Zilliqa。
• 相对可信环境：能容忍(n-1)/3个恶意节点，不依赖算力（与PoW对比）。

思考题答案

客户端需收到f+1个响应才能确保至少一个来自忠将。若仅收f个响应，可能全来自叛徒，导致错误共识。

对比其他算法

• Raft：不适用恶意节点场景。
• PoW：消耗算力，PBFT更高效但规模受限（O(n^2)复杂度）。

通过PBFT，苏秦可确保忠将们一致执行指令，即使存在叛徒干扰。