分布式系统一致性和共识基础(二)

Zealot
区块链
2019-01-17

2.3 拜占庭问题
The Byzantine Generals Problem拜占庭将军问题是Lesilie Lamport等人 1982年发表的论文, 具体PDF链接, http://lamport.azurewebsites.net/pubs/byz.pdf

拜占庭问题假设一个场景,拜占庭的多个军队围攻地方的一个城市,军队的将军通过信使交换信息,在观察敌军的情况后将军们必须达成统一的作战计划。但是将军中可能有叛徒,会阻止其它将军达成一致决定。

将军们就需要一个算法保证所有忠诚的将军达成一致的行动,少数的叛徒将军无论如何阻碍也不能得逞。

拜占庭问题看似简单,实际的难点是,如果将军们传递的是口头消息的话,如果忠诚的将军少于2/3,这个问题是无解的。

简单入手, 3个将军有一个叛徒的情况, 假定传递的命令是进攻或撤退。
图一Lieutenant2是叛徒, Lieutenant1就没法判断是进攻还是撤退。
图二Commander是叛徒,Lieutenant1也无从判断。

t_18ec194ab10b4ef9b0a3f1d414a87b5e.png

论文的结论是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

消息传递可使用数字签名保证安全。
具体算法如下

t_8ee6145045b641bd93a5a03165ae4745.png
(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消息后才认为网络达成共识。

t_543c71298da34435957becf43cb0a021.png

而主节点如果作恶, 或者超时不广播, 副本节点可检查主节点作恶或下线,发起view change广播请求, 所有节点会收集视图变更信息,确认主节点v+1, 主节点收集更新变更信息和原有请求信息,最后恢复一些基准数据和
服务,有兴趣读者自行研究论文。
不少BFT的改良版本, 快速拜占庭容错共识算法FBFT, BFT-PoS, BFT-DPoS, 可以继续了解下。

2.4 非拜占庭问题
非拜占庭问题, 可以认为攻城的将军都是可信任的, 但节点可能会奔溃无法通信,Paxos和Raft算法是归属到这一类。
值得一提的是, hyperledger fabric 0.6还是实现了PBFT, 可惜效率低下, 1.0之后直接切换kafka/zookeeper集群实现的共识, 实际应该也是raft, 效率大幅提升。 而实际上联盟链对于成员的加入都严格的审核和限制, 节点可以认为是信任的。

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

点赞 0
0条评论
其他心得
Zealot · 154天前 
1.简介 Fabric CA基于开源项目CFSSL开发, 主要为fabric网络提供PKI证书服务,是MSP生成的基础。可能有人会问, 官方不是有cryptogen工具批量生成MSP吗? cryptogen实际是辅助测试工具,默认不同orderer,org都有不同的CA, 如果一个org要追加个peer或user, cryptogen就不管用了。生产环境我们建议使用fabric ca全面管理证书, 如果想简单来而区块链组织,节点和用户基本不会变, cryptogen也没问题。 2.
Zealot · 51天前 
去年得知蚂蚁金服放出SOFA的部分开源项目, RPC部分号称源于阿里内部的HSF, HSF当年可是把dubbo 1.x踢出局的, 只是没想到京东改造dubbo为JSF, 当当改为dubbox。国内蛮多电商公司实施服务化就直接上dubbo 1.x或dubbox。这应该是阿里没想到的, 所以现在dubbo 2.x又回笼为apache的顶级项目, 把dubbox合并还继续完善。 朋友说他们公司花了千万买了SOFA的商业版, 那么值钱的东西今天抽空过了一下开源部分的SOFAStack和dubbo2.x文档
Zealot · 60天前 
Fabric 1.4.1引入Raft排序服务, 运维界比较出名的etcd实现的orderer服务。后生可畏, etcd是中国一个年轻人的作品, 实现了raft协议, 在k8s等容器化, 虚拟化, 集群化有官方应用。etcd也是go语言编写, fabric开窍了, 直接把etcd和orderer整合了, 相比kafka/zookeeper的排序服务,搭建简单多了,也比kafka这些省了很多资源(kafka默认开的堆是2GB..), 所以个人是强烈推荐使用,尽量出来不久,但在1.4LTS维护,
Luoying web framework Luoying web framework contains a bundle of components to accelerate J2EE development Github地址 https://github.com/zealzeng/luoying-web Maven地址 <dependency> <groupId>com.whlylc</groupId> <artifac
Zealot · 68天前 
Hyperledger Fabric v2.0 Alpha引入两大新功能,新的Fabric链码生命周期和FabToken. 新的链码生命周期 2.0支持链码的去中心化的治理,引入新的流程在节点上安装链码,在通道上启动实例。新的链码生命周期允许多个组织对链码的参数协同达成一致,例如链码的背书策略。新的模型的改进点如下: (1) 多个组织必须确认同意链码的参数 1.x版本里,一个组织拥有修改链码参数的能力,例如修改背书策略,通道的其它成员也被同步而更改。新的链码生命周期更灵活一些,它兼容支