共识机制 – BFT 拜占庭容错 Byzantine Fault Tolerance

BFT 拜占庭容错 Byzantine Fault Tolerance 的出现是为了解决节点故障时,可能造成对分布式帐本系统的危害。

区块链是一个分布式的帐本系统,所有的网路参与者都以节点的方式连接,所有的讯息都透过广播形式来做传达。点对点网路中存在着两种节点:进行转帐交易的普通节点与负责管理全网路帐本的记帐节点。

我们假设在区块链网路中,传输的讯息有可能会被丢失、重複发送、损坏、延迟与乱序,且此区块链网路中的节点可以随意的参与或退出网路、伪造与延迟讯息、停止工作,还可能发生各种突发不可抗力的故障等等。这些就是着名的拜占庭将军问题。

 

拜占庭将军问题 The Byzantine Generals Problem

 

The Byzantine Generals Problem

拜占庭将军问题为 Leslie Lamport 于 1982 年所提出:

拜占庭帝国的 11 位将军出兵去打仗,但这 11 位将军散落在不同的位置,若要达成一起进攻或一起撤退的共识,唯一的方式就是透过传令来投票:每位将军都将自己的决策纪录複製 11 份,传令至其馀 10 位将军,并给自己留 1 份。最后取多数票来决定要继续出兵征战还是回守。

但若这 11 位将军都非诚实将军呢?假使其中有 2 位间谍广播的讯息为撤退,其馀 9 位忠诚的将军有 5 位判断进攻,而有 4 位判断撤退,如此最后的共识结果就会是全军撤退。此结果状态是相对可以接受的,毕竟全部 11 位将军的行动仍然保持全部撤退一至性。

若上述的 2 位间谍,对于 5 位投进攻的将军也表示他们投进攻,却对另外 4 位投撤退的将军表示他们投撤退,这样所有将军会产生分歧的行动,结果就糟了。

这种状态不一致,还感知不到的危险,即为广义的拜占庭将军问题。

 

实用拜占庭容错 Practical Byzantine Fault Tolerance

为了解决拜占庭将军问题,Miguel Castro 和 Barbara Liskov 在1999 年提出了 PBFT 实用拜占庭容错演算法:「只要间谍节点不超过 1/3,其馀的诚实节点依然可以透过投票达成共识并执行出行动一致性的结果。」

PBFT 演算法的核心理论是 n >= 3f +1

n 为系统裡的总节点数量,f 为系统裡允许出现的非诚实节点数量。意思为若系统裡有 10 个恶意节点,只要系统裡总共有 31 个以上的节点即能继续正常运作达成共识。也即是系统拥有不超过 (n-1) / 3 的容错率。

 

拜占庭容错现实应用

拜占庭容错在现实生活中除了区块链项目外的应用不少,只要一个大系统需要大量的感应侦测器做系统侦测回报,为了避免感应侦测器故障都需要拜占庭容错,譬如说飞机起降控制系统,甚至是 SpaceX 的工程师 Robert Rose 在 2013 的 Embedded Linux Conference 也宣称将採用容错系统。

 

共识机制延伸阅读