PBTF拜占庭容错算法

《区块链从入门到放弃》拜占庭容错算法


随着比特币价格水涨船高、突破天际,几乎大街小巷的人基本都知道比特币。而区块链作为比特币的底层技术,自然也渐渐被人们所熟识。本系列文章从零开始介绍区块链的概念,及其应用场景,最后讲讲放弃区块链的原因。


《区块链从入门到放弃》拜占庭容错算法


第四篇——拜占庭容错算法

在解释拜占庭容错算法之前,先思考一下这个问题:

有4个将军(编号为ABCD),要去攻打一个部落,这个部落只有在3个将军同时进攻的时候才可以被攻破。

这4个将军里面有1个叛徒。

他们分成4路进攻,在临进攻前,要确定一个统一的进攻时间。

要怎么确定进攻时间,才可以保证至少有三个将军一起进攻或者都不进攻?

解法一:某一将军通知其他三位将军进攻时间

这种解法下有如下情况:

情况①:

将军A派出三个通讯兵,分别去告诉BCD,下午6点进攻。

到了下午6点,ABC发起进攻,D没有发起进攻。

这种情况下,进攻成功,而且发现了D是叛徒。


情况②:

假如叛徒就是A呢?

将军A派出三个通讯兵,去告诉B下午1点进攻,去告诉C下午3点进攻,去告诉D下午5点进攻。

到了下午1点,B进攻,失败。到了下午3点,C进攻,失败。到了下午5点,D进攻,失败。

这种情况下,进攻失败。


《区块链从入门到放弃》拜占庭容错算法



因此解法一不成立。

解法二:某一将军通知其他三位将军进攻时间,这三位将军收到的同时,去告诉其他两位将军自己收到的命令。最后每个人执行自己收到的最多的命令。

情况①:

将军A派出三个通讯兵,分别去告诉BCD(叛徒),下午6点进攻。

B收到A命令以后,派出自己的通讯兵,告诉CD下午6点进攻。C收到A命令以后,派出自己的通讯兵,告诉BD下午6点进攻。D收到A命令以后,因为D是叛徒,为了破坏进攻,派出自己的通讯兵,告诉BC下午3点进攻。

最终,ABCD收到的命令分别如下:

A:6点 6点 6点

B:6点 6点 3点

C:6点 6点 3点

D:6点 6点 6点

B和C收到的6点比3点多,因此他俩6点进攻。再加上6点进攻的A,三个人进攻,成功。


《区块链从入门到放弃》拜占庭容错算法



情况②:

假如叛徒就是A呢?

将军A(叛徒)派出三个通讯兵,去告诉B下午1点进攻,去告诉C下午3点进攻,去告诉D下午5点进攻。

B收到A命令以后,派出自己的通讯兵,告诉CD下午1点进攻。C收到A命令以后,派出自己的通讯兵,告诉BD下午3点进攻。D收到A命令以后,派出自己的通讯兵,告诉BC下午5点进攻。

最终,ABCD收到的命令分别如下:

A:1点 3点 5点

B:1点 3点 5点

C:3点 1点 5点

D:5点 1点 3点

因为BCD收到的信息无法得出进攻时间,因此都不进攻,同时可以发现A是叛徒。

《区块链从入门到放弃》拜占庭容错算法


可以看出,解法二是可行的解决方案。

拜占庭将军问题,实际上和上面的问题类似。解决方案就是拜占庭容错(PBFT),其核心是:

信息在计算机间互相交换后,各计算机列出所有得到的信息,以大多数的结果作为解决办法。在N≥3F+1的情况下,一致性是可能实现的(N为计算机总数,F为有问题的计算机总数)。

区块链上的共识机制主要解决由谁来构造区块,以及如何维护区块链统一的问题。

拜占庭容错解决的也是谁来发起信息,如何实现信息的统一同步的问题。

将拜占庭容错映射到区块链中,即:

● 每个将军都有一份实时与其他将军同步的消息账本。

● 账本里有每个将军的签名都是可以验证身份的。如果有哪些消息不一致,可以知道消息不一致的是哪些将军。

● 尽管有消息不一致的,只要超过半数同意进攻,少数服从多数,共识达成。

目前,拜占庭容错算法被广泛地应用在联盟链中。

Filecoin挖矿技术服务(排名服务、挖矿技术方案定制)

热门文章