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,
效率大幅提升。 而实际上联盟链对于成员的加入都严格的审核和限制, 节点可以认为是信任的。
一致性和共识是区块链的核心,希望文章对大家有帮助。