欢迎大家关注我的公众号:程序那些事
回复「资料」即可免费获得千本技术秘籍!区块链,java,前端,大数据,人工智能,安全,架构,算法,数据库,面试技巧等等方面,应用尽有先到先得!

理解分布式一致性:拜占庭容错与PBFT

之前的几篇文章我们讲了分布式协议里面的Paxos协议和Raft协议。这两个协议主要适用于可信节点的情况,所谓可信节点就是节点只会出现因为系统或者网络问题的宕机情况,不会有恶意节点。

那么如果有恶意节点的情况下,我们怎么去达成共识呢?一个很简单的办法就是少数服从多数,下面我们看一下拜占庭是做的。

拜占庭问题

先看一下我们要解决的问题,也叫做拜占庭将军问题。

话说有一天有n个拜占庭将军相约于魔法师大峡谷中,他们的目标就是推掉对方的塔。塔有点强大,只有不少于m个将军同时去推塔才能成功,如果一个一个的去推塔,就免不了身死道消的结果。那时候他们的微信版本还比较低,不能建群聊天,只能一对一的通信。

将军之间并不是表面上看起来的一条心,假如一个将军想组织大家在下午两点钟去偷塔,那需要怎么样操作才能保证不少于m个将军同时执行”两点钟偷塔“这个命令呢?

这个问题就叫做拜占庭将军问题,是指在不可信任环境下的分布式一致性问题。

这里我想强调一点,分布式一致性是指各个节点之间的数据同步一致,跟数据正确与否没有关系。

拜占庭容错BFT

拜占庭容错是分布式协议的一种属性,如果这种协议可以解决不可信任环境下的分布式一致性问题,那么它就是拜占庭容错。

PBFT(Practical Byzantine Fault Tolerance)

PBFT是拜占庭容错的一种实现。它的性能很高并且低延时,能够解决不信任节点的问题。

其有如下几个特征:
1. 同一时间只有一个Leader向外发送消息,其它节点只是被动接收消息。
2. 所有的节点互相之间通信,并且将其收到的消息转发给其他节点,从而达成多数共识。
3. 节点之间的消息需要保证:A:节点收到的消息确实是某个节点转发的。B:消息在发送过程中不会被篡改。

在这里插入图片描述
如果想让PBFT正常工作,那么恶意节点个数不能大于总节点个数的1/3。

正常来讲,节点个数越多,恶意节点所占有的比率就会越低,系统就会越稳定,但是因为所有的节点之间需要两两通信,节点个数的增多会带来节点之间通信的压力。

下面看下PBFT的工作流程:

  1. 客户端发给服务器说我要执行命令A。
  2. Leader将该命令分发给所有被动节点。
  3. 客户端收到f+1(f 是系统能够承受的最大恶意节点个数,即系统总节点个数为3f+1)个相同的结果,那么客户端即认为共识完成。

这里Leader是随机选择出来的,如果选出来的Leader在给定的时间内并没有发出广播,那么系统会自动挑选新的Leader并进入下一轮。

why 3f+1 ?

很多同学可能不理解为什么对于f个恶意节点来说,至少要3f+1个节点才能正常工作。这里给大家解释一下。

之前在Paxos和Raft协议里面,我们给大家讲过在可信任节点的环境里面,达成共识的条件是收到的消息需要>n/2 ,即要收到大多数节点的反馈才能表示共识完成。

那么在有不可信节点f的情况下,我们的可信任节点个数是n-f个,我们收到的可信任节点个数的反馈必须>(n-f)/2才表示绝大多数可信任节点已经收到消息了。同时我们也可能收到f个不信任节点发来的消息,那么当(n-f)/2 > f 的时候,根据多数原则,我们可以区分出哪些是信任消息,哪些是不可信任消息,因此得出 n> 3f .

PBFT 的优点

  1. 一致性结果一旦产出,不会更改。在区块链世界,像是比特币,以太坊,经常会听到区块确认的概念,这个就是结果不确定的问题,他们用的POW算法是以链的长度来决定最终的区块,当有更长的链产生的时候,之前的交易会被完全推翻。而PBFT不会存在这个问题。
  2. 相对于POW,PBFT对能源的消耗会少很多很多,再也不用浪费资源去挖坑了。

PBFT 的缺点

说完优点说缺点。其实前面我们也提到了,PBFT需要节点之间两两通信,当节点个数太多的话,节点之间通信的消耗会大大增加。所以PBFT只适合用在联盟内部少数节点的情况。像是Hyperledger这样的联盟链。

同时,PBFT也可能会受到女巫攻击(Sybil attack),这个后面我们有时间再单独讲。

更多教程请参考 flydean的博客

Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注