miller
发布于

拜占庭共识

BFT(Byzantine Fault Tolerance)

即拜占庭容错,是一种共识机制,源于拜占庭将军问题,其目的是要解决在非信任环境下,节点如何达成共识的问题。

在现实世界,计算机和网络可能会因为硬件错误、网络拥塞或中断、以及遭到恶意攻击等原因出现不可预料的问题。而拜占庭容错技术就是用来处理现实中存在的上述异常问题,并满足所要解决的问题的规范要求。

区块链网络环境中,存在着运行正常的服务器,也存在有故障的服务器,还有破坏者的服务器。共识算法的核心是在正常节点间形成对网络状态的共识。通常发生故障的节点被称为为拜占庭节点,而正常的节点为非拜占庭节点。


BFT共识协议

一个分布式系统是由多个节点组成,节点之间需要网络发送消息通信,根据它们遵循的协议在某个任务消息达成共识并一致执行。这个过程中会出现很多类型的错误,但它们基本上可以分为两大类。

第一类错误是节点崩溃、网络故障、丢包等,这种错误类型的节点是没有恶意的,属于非拜占庭错误。

第二类错误是节点可能是恶意的,不遵守协议规则。例如验证者节点可以延迟或拒绝网络中的消息、领导者可以提出无效块、或者节点可以向不同的对等体发送不同的消息。在最坏的情况下,恶意节点可能会相互协作。这些被称为拜占庭错误。

考虑到这两种错误,我们希望系统始终能够保持两个属性:安全性(safety)和活跃性(liveness)。

· 安全性:在以上两类错误发生时,共识系统不能产生错误的结果。在区块链的语义下,指的是不会产生双重花费和分叉。

· 活跃性:系统一直能持续产生提交,在区块链的语义下,指的是共识会持续进行,不会卡住。假如一个区块链系统的共识卡在了某个高度,那么新的交易是没有回应的,也就是不满足liveness。

BFT(拜占庭容错协议)是一种即使系统中存在恶意节点也能保证分布式系统的安全性和活跃性的协议。根据Lamport[2]的经典论文,所有BFT协议都有一个基本假设:节点总数大于3f时,恶意节点最大为f ,诚实节点可以达成一致的正确结果。

PBFT

实用拜占庭容错算法(PBFT[3])是现实世界里首批能够同时处理第一类和第二类错误的拜占庭容错协议之一,基于部分同步模型,解决了之前BFT类算法效率不高的问题,将算法复杂度由节点数的指数级降低到节点数的平方级,使得拜占庭容错算法在实际系统应用中变得可行。

目前区块链中使用的BFT类共识协议都可以认为是PBFT的变形,与PBFT一脉相承。

  1. 正常流程

PBFT正常流程如下所示(图1中C为客户端,系统中有编号分别为0~3的四个节点,且节点3为拜占庭节点):

Alaya共识方案详解(一):初识BFT共识协议

正常流程为3阶段协议:

· pre-prepare:主节点(Primary)广播预准备消息(Preprepare)到各副本节点(Replica)

· prepare:该阶段是各个节点告诉其他节点我已经知道了这个消息,一旦某个节点收到了 包含n-f 个prepare消息(我们将使用QC也就是Quorum Certificate来指代,下同)则进入prepared状态

· commit:该阶段是各个节点以及知道其他节点知道了这个消息,一旦某个节点收到了n-f 个commit消息(QC)则进入committed状态

  1. 视图切换流程

视图切换(viewchange)是PBFT最为关键的设计,当主节点挂了(超时无响应)或者副本节点集体认为主节点是问题节点时,就会触发ViewChange事件,开始viewchange阶段。

此时,系统中的节点会广播视图切换请求,当某个节点收到足够多的视图切换请求后会发送视图切换确认给新的主节点。当新的主节点收到足够多的视图切换确认后开始下一视图,每个视图切换请求都要包含该节点达到prepared状态序号的消息。

在视图切换过程中,我们需要确保提交的消息序号在整个视图更改中也是一致的。简单来说,当一个消息定序为n,且收到2f+1个prepare 消息之后,在下个视图中,依然会被分配序号为n,并重新开始正常流程。

Alaya共识方案详解(一):初识BFT共识协议

如图2所示,viewchange会有三个阶段,分别是view-change,view-change-ack和new-view阶段。从节点认为主节点有问题时,会向其它节点发送view-change消息,当前存活的节点编号最小的节点将成为新的主节点。当新的主节点收到2f个其它节点的view-change消息,则证明有足够多的节点认为主节点有问题,于是就会向其它节点广播。

原文链接

浏览 (864)
点赞
收藏
评论