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集群实现的共识, 效率大幅提升。 而实际上联盟链对于成员的加入都严格的审核和限制, 节点可以认为是信任的。

一致性和共识是区块链的核心，希望文章对大家有帮助。

补充, 修正了原文一些错误, 最新的1.4.1支持etcd实现的raft共识, 推荐使用这个orderer服务。