区块链四：共识机制——PBFT算法深入讲解

@TOC

背景介绍

共识机制是区块链一大知识领域， 作用就是维持分布式节点间的一致性，从而支撑去中心化，早在区块链之前，就存在各种分布式的共识机制，共识机制不是因区块链所发明，但区块链却对共识机制推广和进步有着重要影响。

共识算法分类

按应用场景分，共识算法可以分成两大类， 1、有坏人节点， 2、无坏人节点。
1、 有坏人节点，典型拜占庭问题，即系统中可能出现故意传送假结果的节点导致分布式系统结果错误，这种场景重点是在存在坏人的情况下能达成大家认可的一致结果。 其中BFT，PBFT， POW，POS都属于这类。
2、 无坏人几点，此类分布式共识算法，只需要保证各节点行动一致，并在部分节点down后能继续工作，一般在封闭式的分布系统使用，其中有Raft，Paxos。

对几种常见共识算法，大都类似的思路， 就是 一个组长（primary）带着N个成员（backup）干活，由组长派活收集各节点的状态，再确定结果是否一致， 类似分布式事务的二段提交。

其中不同算法主要解决这几个问题思路不一样，

1. 系统如何判断达成一致？
2. 组长down了或部分节点down了怎样保持系统可用性？
3. 出现分叉了怎样处理两边的结果？

PBFT

这部分就讲解PBFT算法，怎样解决以上几个问题。
PBFT的算法思想， 以状态机运作，包括节点状态，消息状态， 由组长带领大家统一步调处理消息，而消息的是否继续迁移下一个状态，则通过多少节点达成一致，最后消息达到处理完的状态。

消息处理：

消息状态迁移路径： request -> pre-prepare -> prepare-> commit -> reply

C 代表Client， 客户端向系统主节点（0：组长）发送一请求request， 请求开始进入处理阶段
pre-prepare : 主节点参与把request分配一个唯一的编号 request-number n, 并把request跟n一起组成pre-prepare消息广播给所有成员(backup节点)

prepare : 所有成员(backup节点)，收到pre-prepare消息， 依靠签名字段检查消息是否来源于主节点，确认无误，将request编号和本节点签名组成prepare消息，广播给其他所有成员，表示自己认可这请求编号和准备好了。

Commit ：所有节点，若收到的prepare消息，依靠签名检查是否正确，若prepare消息数量超过全部节点数量的3分之二， 则认为系统达成一致认可该请求和请求编号，对所有节点广播commit消息，表示该节点可以进行request的业务。

Reply : 所有节点, 若收到commit消息，依靠签名检查消息是否正确，若commit的消息数量超过所有节点的3分之一，则完成request要求的业务，并构建reply消息，直接回复给client。Client根据是否收到超过3分之1个节点的正确回复，判断系统是否完成了请求request。

上面的图及说明就是PBFT的请求处理过程，那么回到上面的问题，

问题一：系统判断达成一致？
这里分两个阶段，prepare, commit, 全网超过三分之二个prepare，则达成一致， commit超过三分之一则达成一致。

简单说就是坏几点要少于 三分之一。

灵魂拷问

1、为啥是少于三分之一，而不是少于二分之一？
如果是多数服从多数，二分之一确实能满足，但这里是有两个阶段 prepare， commit。
n个节点，设错误节点 f， 第1到f个是错误节点， f+1 到n 是好节点pre-prepare -prepare, n-f 个节点都正确广播 prepare消息，prepare-commit, 当收到n-f 确认消息时，节点是不能确认这里n-f个消息时有多少来源f节点的，最多可能是f个节点，也就是n-f个消息中最多有个f是假消息，也不能影影响共识结果，因此 n-f-f > f 因此 f< n/3。

另一种理解，n-f个正常节点中，如果出现分歧，也能达成一致性，那么
(n-f)/2 >f，得 n>3f, f<n/3。

从上面的说明也知道，如果对于请求request r1 若commit(m) 成功达成一致，则不可能存在 commit(m’) 也达成一致，因此不可能存在分叉的情况。这里也回答了第三个问题（问题三，出现分叉了怎样处理两边的结果，不存在的）。

追问

为啥要分开两阶段，一阶段就搞掂不香吗？
——这里是为了保证request的顺序，第一阶段分配顺序号，第二阶段才是做业务。

这里也提到commit阶段可能k节点做视图转换，这是什么？
——这就涉及第二个问题，下面分晓。

问题二： 组长down了或部分节点down了怎样保持系统可用性？

视图转换

上面保证分布式系统的正确性safety，做正确的事，而视图转换则是为了可用性liveness， 假如primary节点down了，系统怎样？ 要保证系统继续可用，就要使用view-change。

PBFT有一个全局的视图编号view number: v，主节点primary是根据 v mod n =i 得到 节点i为主节点。视图转换，就是v递增，主节点primary也相应转移到另一个节点。

1. 当client发送请求primary后，一定时间没收到回复，则会发送请求给其他backup节点， backup 节点收到request后，起一个timer，如果timer过期，还没执行这个request(commit还没达一致)，则backup节点发起view-change

2. Backup 节点会广播一个view-change 消息，包含原来视图编号 v 合下个视图编号v+1
   如果节点收到的view-change 消息多于三分之二，则说明view-change达成一致。

3. 当 v+1 mod n = j , 新的primary节点j，收到足够的view-change消息后， 就广播new-view消息，告诉其他节点使用新视图。

4. 其他节点收到new-view后，确认消息签名正确，进入新视图；

有了视图转换，如果主节点down了，就会触发视图转换更换另一个主节点，如果下一个主节点也是down的，则继续切换，直到找到可用的主节点。因此保证只有有超过三分二的节点是好的，系统就可用。

可用性liveness，还要保证当视1图转换时候，可能有节点已经commit序列n，而有的节点只commit到序列n-1.，转移视图后，怎样保证request在各节点都能正确一致执行。
这还要引出下问题，checkpoint 机制。

Checkpoint机制：

这里就需要checkpoint， 这里checkpoint跟其他系统日志checkpoint基本一样。系统定期创建checkpoint，记录最新稳定提交的操作，并广播checkpoint消息，当节点收到超过三分之二的创建checkpoint消息，该checkpoint达成一致。视图转换时候带上最新的checkpoint，在checkpoint以后的请求，视为不稳定的，需要重做。

总结

PBFT算法是通过节点消息状态机方式达成请求处理的一致性，再通过视图转换，checkpoint机制确保系统的可用性，而本文概要介绍了这几方面的原理，但也过滤具体算法细节，有兴趣建议查看论文【引用1】

1 PBFT算法论文 http://pmg.csail.mit.edu/papers/osdi99.pdf

历史

区块链三：深入解析比特币交易原理
区块链二：比特币的区块数据结构
区块链一 ：区块链应用介绍和展望