家蛙树

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

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条评论
其他心得
1.Kafka排序服务原理 官方文档在google doc上, 参考翻译 https://www.jianshu.com/p/db006359133d 2. kafka 排序服务安装 所有的代码已分享在https://github.com/zealzeng/kafka-orderer-demo 2.1 安装环境 官方文档有一些简单的描述 https://hyperledger-fabric.readthedocs.io/en/release-1.4/kafka.h
Zealot · 16天前 
1.Andorid串口开发包一般使用google多年前提供的android-serialport-api, 提供自用分支 https://github.com/zealzeng/android-serialport-api 2.Android设备一般需要root, 保证设备串口文件如/dev/ttyS0, /dev/ttyUSB0等可读可写, 如果无权限, 则需要切到su执行chmod 666。需要注意的是有些设备su路径是/system/bin/su, 有些是/system
2.3 拜占庭问题 The Byzantine Generals Problem拜占庭将军问题是Lesilie Lamport等人 1982年发表的论文, 具体PDF链接, http://lamport.azurewebsites.net/pubs/byz.pdf 拜占庭问题假设一个场景,拜占庭的多个军队围攻地方的一个城市,军队的将军通过信使交换信息,在观察敌军的情况后将军们必须达成统一的作战计划。但是将军中可能有叛徒,会阻止其它将军达成一致决定。 将军们就需要一个算法保证所有忠诚的将军达
编写过一些链码的人可能会觉得是在操作一个简单的key-value数据库, 就是GetState和PutState去操作键值对,而对复杂些的一对多,多对多等实体关系和数据模型不知怎么设计。我们先从官方的例子入手一起探讨下。 1.简单转账例子 /fabric-samples/chaincode/chaincode_example02/go/chaincode_example02.go 假设链码调用peer chaincode invoke … -c ‘{“Args”:[“invoke”,”a
Zealot · 53天前 
区块链的真实数据依赖于物联网和智能设备,记一次折腾的android无线调试经历。 Android 4.2.2定制版智能硬件, USB口能插鼠标键盘, 但是不能USB调试。供应商两个方案, 要么开壳找到USB OTG排座, USB口自己接线, 但是开壳会导致硬件功能无法使用; 要么手工打包apk安装到硬件慢慢的toast。 摸索出第三条路。 搜索android无线调试, 基本都需要第一次USB调试线, adb tcpip 5555开启android设备端口监听, 之后adb connect ip