区块链四：共识机制——PBFT算法深⼊讲解
@
背景介绍
共识机制是区块链⼀⼤知识领域， 作⽤就是维持分布式节点间的⼀致性，从⽽⽀撑去中⼼化中⼼，早在区块链之前，分布式系统就存在各种分布式的共识机制，共识机制不是区块链所发明，但区块链却对共识机制推⼴和进步有着重要影响。
共识算法分类
按应⽤场景分，共识算法可以分成两⼤类， 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节点)2018年宪法
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, 全⽹超过3分之⼆个prepare，则达成⼀致， commit超过三分之⼀则达成⼀致。
简单说就是坏⼏点要少于 三分之⼀。
灵魂拷问
1、为啥是少于三分之⼀，⽽不是少于⼆分之⼀？
如果是多数服从多数，⼆分之⼀确实能满⾜，但这⾥是有两个阶段 prepare， commit。
n个节点，设错误节点 f， 第1到f个是错误节点， f+1 到n 是好节点pre-prepare -prepare, n-f 个节点都正确⼴播 prepare消
息，prepare-commit, n-f个好节点⼜k节点发⽣了view-change (下⾯有讲解)或者其他状况，那么最终commit就达不到true。
n-f-k > f， 其中 k < (n-f)/2 得 n>2f + (n-f)/2 n>3f
得到 f 只能少于三分之⼀节点。
从上⾯的说明也知道，如果对于请求request r1 若commit(m) 成功达成⼀致，则不可能存在 commit(m’) 也达成⼀致，因此不可能存在分叉的情况。这⾥也回答了第三个问题（问题三，出现分叉了怎样处理两边的结果，不存在的）。
追问吴桂显
为啥要分开两阶段，⼀阶段就搞掂不⾹吗？
——这⾥是为了保证request的顺序，第⼀阶段分配顺序号，第⼆阶段才是做业务。
曾树生>qq黄钻这⾥也提到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】
历史
