PBFT算法
Cuiting Shi, OneThing Tech LTD.
Thursday, December 6, 2018
1. 背景 --------------------------------------------------------------------------- 1 2. PBFT算法模型 ---------------------------------------------------------------- 3 2.1 基本概念 ------------------------------------------------------------------- 3 3. 三阶段协议 -------------------------------------------------------------------- 4 3.1 pre-prepare阶段 --------------------------------------------------------- 6 3.2 prepare阶段 -------------------------------------------------------------- 7 3.3 commit 阶段 -------------------------------------------------------------- 8 4. 算法优化 ---------------------------------------------------------------------- 9 4.1 检查点协议 ---------------------------------------------------------------- 9 4.2 视图变更协议 ------------------------------------------------------------ 11 4.2.1 维持计时器 ---------------------------------------------------------- 11 4.2.2 请求视图变更 -------------------------------------------------------- 12 4.2.3 切换到新视图 -------------------------------------------------------- 13 5. PBFT算法应用 -------------------------------------------------------------- 15 6.参考 -------------------------------------------------------------------------- 16
1
2
1. 背景
通常情况下，分布式系统由很多节点组成，系统的可靠性要求系统必须具备应付异常节点发送过来的不一致消息的能力。分布式的这个场景最早由 Lamport，Shostak 和 Pease 于1982年形象地描述为拜占庭将军问题([1]Leslie Lamport 1982)，即多个拜占庭将军各自率领了小分队驻扎在敌方城市之外，他们需要对是否进攻敌军达成统一的作战计划，但是这些将军之间存在反叛者，他们可能会篡改、延迟或者丢弃其他将军的命令，迷惑其他可信将军。拜占庭将军问题就是要找到一个算法来保证可信将军之间能够达成一致的作战计划。
Lamport他们证明了对于拜占庭将军问题，系统中如果存在??个不可信节点，那么只有总节点数不少于3??+1才存在一个算法解决该问题。下面我们来简单地证明这个问题解的不可能性，假设系统中总共有3个节点，Commander是提议者，记为C，Lieutenant 1 和Lieutenant 2 是验证节点，记为 LT1 和 LT2。这三个节点中存在一个作恶节点，下面我们证明在存在一个作恶节点的情况下，无论是提议者还是验证节点，系统均无法达成统一的共识。
如图1-1所示，假设 C 是作恶节点，另外两个节点是可信节点。C 向节点LT1和LT2发送了相互矛盾的命令— 进攻和撤退，那么LT1在接收到C发送过来的进攻命令和LT2转发过来的命令撤退，那么它就无法确定是要进攻还是撤退。
图1-1 提议者是作恶节点
1
区块链课程13.共识层：PBFT共识算法 - 图文
