PBFT算法_pbtf算法 python实现 csdn

1.前提假设

1.1系统同步模型

区块链是一个典型的分布式系统，而分布式系统中如果要研究共识的话，就需要明确系统同步模型。

同步模型分为：

synchrony：节点所发出的消息，在一个确定的时间内，肯定会到达目标节点；

asynchrony：节点所发出的消息，不一定会到达目标节点；

partial synchrony：节点所发出的消息，虽然会有一定延迟，但消息一定会送达；

synchrony是最理想的情况，若分布式系统为一个同步系统，共识算法的设计可以简化不少。在同步系统中节点的问题认定就是：超时没收到消息。asynchorny是更贴近现实的模型，但根据FLP impossible原理，但在asynchrony假定下，共识算法不可能同时满足safety和liveness。但我们为了设计符合实际应用场景的共识算法，目前的BFT类共识算法大多是基于partial synchrony假定，在PBFT原论文中称之为：weak synchrony。

即PBFT假设系统是异步的，网络中消息会出现延迟，但不会被无限的延迟。

1.1.1safety 和 liveness

① safety：坏的事情永远不会发生，也就是共识机制不会产生错误的结果，比如一部分节点返回yes，另一部分返回no，在区块链的实际情况下，指的就是不会产生区块链分叉。

② liveness：好的事情一定会发生，也就是系统持续有响应，在区块链的实际情况下，指的是共识机制持续正常运行，不会卡住，假如一个区块链系统的共识机制卡在了某个位置，那么新的交易是无法进行回应的，也就是不满足liveness。

1.2模型容错类型

PBFT算法假定错误可以是拜占庭类型的，也就是可以容忍任意类型的错误，比如节点作恶、说谎等。这跟crash-down类型的错误不一样，raft、paxos这类共识算法只允许crash-down的类型错误。节点智能crash但不能产生假消息

1.2.1引入参数

PBFT容忍无效或者恶意节点数：f

系统中总节点数为：n

对于不同的错误类型，保证协议正常工作的总节点数如下表

1.2.2防止拜占庭类错误总节点的数目的推算

①.假设系统中可能存在f个拜占庭结点，系统中有n个节点并且需要根据节点发送过来额消息进行判断。

②.为了使共识机制正常运作，在收到n-f个消息的时候，就应该对消息进行处理，因为可能有f个节点根本不发送消息。

③.我们根据收到的n-f个消息进行判断，判断的原则为至少有f+1个节点相同结果，即n-f>f。

④.在收到的n-f个消息中，无法确定其中有无错误节点过来的消息，其中也可能存在f个假消息。所以n-f-f>f。

1.3系统建模

由一组节点构成状态机复制系统，一个节点作为主节点（primary），其他节点作为备份节点（back-ups）。轮到某个节点作为主节点时，这称为系统的一个view（视图）。当节点出了问题，就需要进行view的更新，切换到下一个节点担任主节点。主节点更替不需要选举的过程，而是采用round-robin方式。

当系统的主节点接收到client（客户）发送来的请求，并产生pre-prepare消息，进入共识流程。

我们需要系统满足以下条件：

1.deterministic（确定性）：在一个给定状态上的操作，产生一样的执行结果。

2.起点一致性：保证每个节点都有相同的起始状态

要保证non-fault节点对于执行请求的全局顺序达成一致。

2.共识机制流程

正常状态下的共识机制如下图所示。

 共识机制发挥作用的三个阶段(pre-prepare、prepare、commit)

其中pre-prepare阶段和prepare阶段确保了在同一个view下，正常节点对于消息m达成了全局一致的的顺序，使用order<v，m，n>来表示，在view = v下，正常节点都会对消息m，确认一个序号n。接下来的commit过程，配合上viewchange的设计（主节点可能会发生故障），实现了view的切换，也保证了对于m的的全局一致顺序，即order<v+1,m,n>，视图切换到v+1，依然会对消息m，确认序号n。

以下会将分别介绍五个阶段

2.1 request

客户端c向primary节点发送请求。消息格式为<REQUST,o,t,c>。o为请求的具体操作，t为请求时客户端追加的时间戳，c为客户端标识。REQUST：包含消息内容m，消息摘要d(m)。客户端对于请求进行签名

2.2 pre-prepare

①primary节点收到客户端的请求，进行校验客户端请求消息签名，非法请求则予以丢弃。正常则进入

②primary节点收到请求m，将请求m广播给其他节点，并给请求m分配一个序号n，并广播给其他节点。广播后消息会存在本地的lo中。

pre-prepare阶段的消息格式,其中v表示当前view的编号，n为表示给m分配的序号，d为客户端消息摘要，m为消息内容。<PRE-PREPARE, v, n, d>为主节点签名。

③当back-up节点i节点收到主节点发来的pre-prepare消息时，会做以下几项验证操作：

        1.验证主节点发来的消息签名。

        2.当前副本节点没有收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息。

        3.收到的消息序号n，在当前接收窗口内<h,H>。

        4.d与m的摘要是否一致。

若以上全部通过，则接受该消息，之后进入prepare阶段。该节点会广播（向所有节点包括primary节点广播）prepare消息。之后将消息存入自己的log中。

2.3 prepare

节点收到prepare消息后，会验证签名并检查是否为当前view的消息，同时检查消息序号n是否在当前的接收窗口内，验证通过则接受该消息，保存到自己的log中。

当节点满足以下3点时表明节点达成了prepared状态，记为prepared（m,v,n,i）

        1.在log中存在消息m

        2.在log中存在m的pre-prepare消息，pre-prepare（m,v,n）

        3.在log中存在2f个来自其他节点的prepare消息，prepare（m,v,n,i）

至此，可以确保view在不发生切换的情况下，对于消息m有全局一致的顺序。此外记录pre-prepare和prepare消息到log中，用于View Change过程中恢复未完成的请求操作。

也就是说在view不变的情况下：

        1.一个正常节点i，不能对两个及两个以上的不同消息，达成相同序号n的prepared状态。也就是不能同时存在prepared（m,v,n,i）和prepared(m',v,n,i)

        2.两个正常节点i、j，必须对相同的消息m达成相同序号n的prepared状态。

prepared状态十分重要，其涉及到view转换时，为了保证view切换前后的safety特性，需要将上一轮的view的信息传递到新的view。在pbft中就是将prepared状态信息传递到新的view。即新的view中需要在上一轮view的prepared信息基础之上，继续进行共识。

达成prepared状态后，节点会广播commit消息<COMMIT,v,n,d,i>i.

2.4 commit

当节点接收commit消息后，会进行一下几步验证：

        1.验证其他节点发来的消息签名。

        2.当前副本节点没有收到了一条在同一v下并且编号也是n，但是签名不同的commit信息。

        3.收到的消息序号n，在当前接收窗口内<h,H>。

        4.d与m的摘要是否一致。

当节点i满足：

达成了prepared（m,v,n,i）状态，并且收到了2f+1个commit（v,n,d,i）消息，则该节点达成了commit-local（m,v,n,i）状态。

达成commit-local状态之后，节点对于消息m就有了一个全局一致的顺序，可以执行reply to客户端了。

其中commit-local状态说明有2f+1个节点达成了prepared状态。其中需要记录其他节点发来的commit消息到log中。

2.5 relpy

节点达到commit-local后运行客户端的请求操作o，并返回<REPLY, v, t, c, i, r>给客户端，r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。

3.垃圾回收

在以上算法流程中，为了确保在view change的过程中，能够恢复先前的请求，每一个副本节点都记录一些消息到本地的log中，当执行请求后back-up节点需要把之前该请求的消息清楚掉。最简单的做法是在reply消息后，再执行一次当前状态的共识同步，但这样会消耗很多资源，因此可以在执行完多条请求K条，后执行一次状态同步。这个状态同步消息就是checkpoint消息。

back-up节点i发送<CheckPoint,n,d,i>给其他节点，n是当前节点所保留的最后一个视图的请求编号，d是当前状态的一个摘要，该checkpoint消息记录到log中。如果back-up节点i收到了2f+1个验证过的checkpoint消息，则清楚先前日志中的消息，并以n作为当前的stable checkpoint。

实际上当副本节点i向其他节点发出checkpoint消息后，其他节点还没有完成K条请求，所以并不立即对节点i的请求作出响应，它还会按自己的节奏向前行进，但此时发出的checkpoint并未形成stable，为了防止节点i的处理请求过快，设置一个上文提到的高低水位区间[h,H]来解决这个问题。低水位h等于上一个stable checkpoint的编号，高水位H=h+L，L为我们指定的数值，等于checkpoint周期处理请求数K的整数倍，比如L=2K。当节点i处理请求超过H时，就会停止脚步，等待stable checkpoint发生变化，再继续前进。

以上机制类似于计算机网络中的滑动窗口机制。

4.视图切换（view change）

若primary节点作恶，它可能会给不同的请求编上相同的序号，活不分配序号，或让相邻序号不连续，back-up节点应当有义务来主动核实这些序号的合法性。若primary节点离线或者作恶，客户端设置超时机制，若超时，客会向所有back-up节点广播请求消息。back-up节点检测出primary节点作恶或离线，发起view change协议。

back-up节点向其他节点广播<VIEW-CHANGE,v+1,n,C,P,i>消息，

        n:为最新的stable checkpoint的编号

        C:对应于n的check-point 2f+1个CHECKPOINT消息集合

        P: 一个组成的集合,m表示消息，m的序号是大于n的，表示序号为m的达成prepared状态的消息集合。内容包含关于m的1个pre-prepare消息和2f条prepare消息集合。

        i:节点id

当主节点p = v+1 mod |R| 收到2f个有效的VIEW-CHANGE消息后，向其他节点广播<NEW-VIEW,v+1,V,O>消息，V为有效的VIEW-CHANGE消息集合。O是主节点重新发起的未经完成的PRE-PERPARE消息集合。PER-PREARE消息集合的选取规则：

1.选取V中最小的stable checkpoint编号min-s，选取V中prepare消息的最大编号max-s。

2.在min-s和max-s之间，如果存在P消息集合，则创建<<PRE-PREPARE，v+1，n，d>，m>消息。否则创建一个空的PRE-PREPARE消息，即：<<PRE-PREPARE，v+1，n，d（null）>，m（null）>，m（null）为空消息，d（null）空消息摘要。

back-up节点收到primary节点的NEW-VIEW消息，验证有效性，若通过，则进入view = v+1，并开始O中PRE-PREPARE消息处理流程。