2.3 拜占庭问题
The Byzantine Generals Problem拜占庭将军问题是Lesilie Lamport等人
1982年发表的论文, 具体PDF链接, http://lamport.azurewebsites.net/pubs/byz.pdf
拜占庭问题假设一个场景，拜占庭的多个军队围攻地方的一个城市，军队的将军通过信使交换信息，在观察敌军的情况后将军们必须达成统一的作战计划。但是将军中可能有叛徒，会阻止其它将军达成一致决定。
将军们就需要一个算法保证所有忠诚的将军达成一致的行动，少数的叛徒将军无论如何阻碍也不能得逞。
拜占庭问题看似简单，实际的难点是，如果将军们传递的是口头消息的话，如果忠诚的将军少于2/3,这个问题是无解的。
简单入手, 3个将军有一个叛徒的情况, 假定传递的命令是进攻或撤退。
图一Lieutenant2是叛徒,
Lieutenant1就没法判断是进攻还是撤退。
图二Commander是叛徒,Lieutenant1也无从判断。
论文的结论是n个将军,f个叛徒将军, 当n >= 3f + 1时, 才能达成一致。也就是说最少是4个将军, 一个叛徒。
算法推导是在论文Reaching Agreement in the Presence of Faults
http://lamport.azurewebsites.net/pubs/reaching.pdf
以上证实的是算法的可行性，前提是假设将军们的口头消息能及时传递, 而具体落实的算法则是PBFT, 时间复杂度为O(n^2),
“Practical Byzantine Fault Tolerance”, 地址
http://xueshu.baidu.com/usercenter/paper/show?paperid=9d8dd9d6b9702d49e38555e22bed64c5
消息传递可使用数字签名保证安全。
具体算法如下
(1)所有节点会选择一个leader节点, leader节点负责接收client请求,假定replica 0为leader.
(2)pre-prepare预准备, leader会整合client多个请求,验证数字签名，并对请求排序, 最后生成一条广播消息道其它节点（PRE-PREPARE,v,n,d）,m） , 期中v为视图view编号(视图是以leader为主节点,其它为副本节点), n是收到的请求分配一个序号, d是收到的消息的摘要, m是收到的消息。
(3)prepare准备阶段, 收到消息的副本节点会校验主节点的数字签名，验证视图，序号，摘要等是否未处理过, 才接收预处理请求, 向其它所有节点发送（PREPARE,v,n,d,i）消息, i为当前副本节点的编号， 并且记录pre-prepare和prepare消息到日志。
(4)commit提交阶段, 主节点和副本节点收到prepare消息会验证签名，视图, 编号，摘要等，确定收到2f+1的prepare消息之后, 提交（COMMIT, v, n, d, i）到其它节点。
(5)reply阶段, 当节点收到2f+1个COMMIT消息后, 认为网络达成了共识, 返回（REPLY, v, t, c, i, r）给调用客户, r是返回结果。而客户端收到f+1个相同reply消息后才认为网络达成共识。
而主节点如果作恶, 或者超时不广播, 副本节点可检查主节点作恶或下线，发起view change广播请求，
所有节点会收集视图变更信息，确认主节点v+1,
主节点收集更新变更信息和原有请求信息，最后恢复一些基准数据和
服务，有兴趣读者自行研究论文。
不少BFT的改良版本,
快速拜占庭容错共识算法FBFT, BFT-PoS, BFT-DPoS, 可以继续了解下。
2.4 非拜占庭问题
非拜占庭问题, 可以认为攻城的将军都是可信任的,
但节点可能会奔溃无法通信，Paxos和Raft算法是归属到这一类。
值得一提的是, hyperledger fabric
0.6还是实现了PBFT, 可惜效率低下, 1.0之后直接切换kafka/zookeeper集群实现的共识, 实际应该也是raft,
效率大幅提升。 而实际上联盟链对于成员的加入都严格的审核和限制, 节点可以认为是信任的。
一致性和共识是区块链的核心，希望文章对大家有帮助。
