【共识系列.02】PBFT : 实用拜占庭容错算法

作者：笔触狂放9 | 2024-05-21 00:52:29

踩

pbft

【共识系列.02】PBFT : 实用拜占庭容错算法

1. PBFT基本介绍

$\quad$ PBFT包含三个阶段：一阶段消息分发+两阶段投票

$\quad$ 消息分发阶段主节点广播消息，投票阶段所有节点对主节点广播的消息投票，经过两个阶段投票，所有节点对主节点广播的消息达成一致。

$\quad$ 视图（view）：每个视图（view）包含一个主节点，主节点宕机之后，通过view-change操作实现换主。PBFT由视图驱动运转。

$\quad$ PBFT目的是要所有节点将某一确定的客户端请求（一个或批量）与一个sequence number（n）绑定起来，并保证在正常流程和view-change情况下，所有诚实节点产生一致的绑定关系。后续每个节点按照sequence number顺序执行客户端请求。

PBFT假设：

$\quad$ 拜占庭节点数量少于1/3；
$\quad$ 弱同步网络：异步网络中，存在GST（Global Stabilization Time），GST之后，网络进入同步状态；
存在安全的密码学方法实现消息认证。

2. PBFT Normal-case流程

$\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ 在这里插入图片描述
1.1 client发送请求
$\quad$ 客户端将自己的请求构造成REQUEST消息发送给主节点，或发送给从节点，并由从节点转发给主节点。

$\quad$ REQUEST消息结构：<REQUEST, o, t, c> $σ_c$
$\quad$ REQUEST代表消息类型，o代表操作请求，t为时间戳，c代表客户端， $σ_c$ 代表客户端c对其签名。

1.2 pre-prepare阶段
$\quad$ 主节点接收客户端发送的请求，为其构造PRE-PREPARE消息（或放到缓存区等待批量构造一个pre-prepare消息），之后广播给网络中其他节点，节点接收到主节点发送的PRE-PREPARE消息之后，验证签名并检查请求，通过后，进入prepare阶段。

$\quad$ PRE-PREPARE消息结构：<<PRE-PREPARE, v, n, d> $σ_p$ ,m>
$\quad$ PRE-PREPARE代表消息类型，m为客户端请求，v代表主节点view，n代表为消息分配的序号（sequence number），d为m的摘要。

$\quad$ 节点收到主节点发送的PRE-PREPARE消息后，从以下几方面进行检查：

签名正确，消息正确，d为m的摘要
节点view和PRE-PREPARE消息中的v一致；
不存在和PRE-PREPARE消息冲突的其他PRE-PREPARE消息；
编号n处于水位线之间。

1.3 prepare阶段
$\quad$ 节点接收到到主节点发送的PRE-PREPARE消息之后，验证签名并检查请求，通过后，构造PREPARE消息并广播给其他节点（由于PRE-PREPARE消息是由主节点发送的，因此主节点不再参与发送PREPARE消息，每个节点默认收到主节点的PREPARE消息）。节点收到2f+1个（包含自己的）PREPARE消息之后，验证签名，检查PREPARE消息中的v，n，d是否一致，一致则此消息在本节点prepared，节点对此消息进入commit阶段。

$\quad$ PREPARE消息结构：<PREPARE, v, n, d, i> $σ_i$
$\quad$ PREPARE代表消息类型，v代表view编号，n代表为消息分配的序号（sequence number），d为PRE-PREPARE消息中m的摘要，i代表节点。

1.4 commit阶段
$\quad$ 构造COMMIT消息广播给其他节点，并接收其他节点发送的COMMIT消息。收到2f+1个COMMIT消息（包含自己的）后，验证签名，检查COMMIT消息，检查通过，提交执行COMMIT消息对应的m请求。
$\quad$ COMMIT消息结构：<COMMIT, v, n, d, i> $σ_i$
$\quad$ COMMIT代表消息类型，v代表view编号，n代表为消息分配的序号（sequence number），d为PRE-PREPARE消息中m的摘要，i代表节点。

1.5 reply阶段
$\quad$ 节点执行完毕之后，将执行结果构造reply消息并返回给发送请求的客户端。客户端收到f+1个相同的reply消息，则代表其发送的请求被成功执行

1.6 检查点与垃圾回收
$\quad$ 共识过程中，节点收到的每条消息都会保存在本地。当节点确认自身与其他多数节点在某点实现同步一致之后，节点会将该点以前的共识消息释放掉，进行垃圾回收。稳定检查点即节点确认其他多数节点已经与自身达成同步一致状态的sequence number。PBFT定期生成稳定检查点（比如sequence number每间隔100就生成一次）。
$\quad$ 过程：当节点准备生成稳定检查点时，广播CHECKPOINT消息<CHECKPOINT，v, n, d, i> $σ_i$ ，其中n是准备生成稳定检查点的sequence number，d是n对应的请求执行完成之后的状态摘要，i是节点。若节点收到2f+1个不同节点的相同CHECKPOINT消息（包括自己的），则在此sequence number生成稳定检查点，2f+1个CHECKPOINT消息则作为生成该稳定检查点的证明。生成稳定检查点之后，稳定检查点之前保存的共识消息都会被释放掉。

1.7 水位线
$\quad$ 主节点在广播PRE-PREPARE消息（ <<PRE-PREPARE, v, n, d> $σ_p$ ,m>）时，需要为消息分配指定sequence number n，意在将二者绑定。为限制主节点盲目分配sequence number，PBFT通过水位线限制主节点分配sequence number的范围，low-water mark h等于最新检查点sequence number，high-water mark H等于h+k，为避免稳定检查点影响共识运行，k要比生成检查点周期数大。

3. PBFT Failure-case流程（View-change）

$\quad$ PBFT需要主节点广播PRE-PREPARE消息，主节点超时未响应或超时未发起请求时，触发view-change实现换主。
$\quad$ 节点View-change时，停止接收除了检查点、VIEW-CHANGE和NEW-VIEW外的其他消息。节点发送VIEW-CHANGE消息，并接收其他节点的VIEW-CHANGE消息。

$\quad$ VIEW-CHANGE消息结构：<VIEW-CHANGE, v+1, n, C, P, i> $σ_i$

$\quad$ VIEW-CHANGE代表消息类型，v+1代表新view编号，n代表本节点最新稳定检查点的sequence number，C代表生成最新稳定检查点的证明（2f+1个有效的CHECKPOINT消息），P代表节点本地sequence number大于n并且已经prepared的请求，P是一个集合，其中每个元素对应一个已经prepared的请求以及2f个有效的来自不同节点的prepare消息（证明该请求确实已经在本节点prepared）。
$\quad$ view v+1的主节点收到2f个有效的VIEW-CHANGE消息后，构造NEW-VIEW消息并广播给其他节点。
$\quad$ NEW-VIEW消息结构：<NEW-VIEW, v+1, V, O> $σ_p$
$\quad$ NEW-VIEW代表消息类型，v+1代表新view编号，V代表2f+1个VIEW-CHANGE消息（包含新主节点的），O是PRE-PREPARE消息集合。

$\quad$ O的计算方式：
$\quad$ 1）主节点从V的所有VIEW-CHANGE消息中找到最新的稳定检查点，并将其sequence number作为min-s；主节点从V的所有VIEW-CHANGE消息中找到sequence number最大的prepared消息，并将其sequence number作为max-s。
$\quad$ 2）对处于min-s和max-s之间的每个sequence number，主节点在V的所有VIEW-CHANGE消息P中寻找是否存在该sequence number上的prepared消息，若存在，则构造<PRE-PREPARE, v+1, n, d> $σ_p$ ；若不存在，则构造<PRE-PREPARE, v+1, n, dnull> $σ_p$ 。其中d代表请求的摘要，dnull代表 null 请求的摘要。dnull说明在该sequence number 上没有请求，执行时直接忽略。
$\quad$ 其他节点收到主节点广播的NEW-VIEW后，验证消息签名，按照相同的方式计算O，并检查是否与主节点计算出来的O相同。相同则接受NEW-VIEW，并执行O中未执行过的消息。

4. 安全性与活性

$\quad$ 安全性：在同一view内，同一sequence number，若m和m’（不一样的两个消息）同时达到prepared状态，则说明各有2f+1个节点对m和m’投了prepare票，节点总个数有3f+1，两个2f+1中交集节点个数至少为f+1个，也就说明至少一个诚实节点既对m也对m’投了票，很显然，诚实节点不会做这种事情，所以这种事情不会发生。总结来说，同一view内，同一sequence number，不会有两个冲突的消息同时达成prepared状态，也就不会有两个冲突的消息最终达成共识。
$\quad$ 若有诚实节点在commit阶段完成后提交了请求m，则说明该诚实节点收到了2f+1个对应的commit消息，也进一步说明m在f+1个诚实节点达到了prepared状态。view-change过程中，新的主节点会收集2f+1个节点本地所有达到prepared状态的消息，其中将必定包含m的prepared状态消息。最终该消息会被带到下一个view并被其他诚实节点提交。
$\quad$ 综上，无论是同一view内，还是跨view，PBFT两阶段投票协议加view change 协议可以保证安全性。

$\quad$ 活性：PBFT通过换主协议保证算法活性。为避免频繁换主，连续换主时，超时时间递增；为实现快速换主，当节点收到f+1个换主消息时，触发本节点换主；换主时，通过轮转成为新主的权利避免超过连续f轮恶意换主。

5. PBFT复杂度分析

$\quad$ Normal-case：投票过程中，每个节点都需要将自己的消息广播给其他节点，all to all的消息传播模式，网络复杂度为O( $N^2$ )，N为节点总个数。
$\quad$ view-change时：每个节点构造VIEW-CHANGE消息广播给其他节点，每个VIEW-CHANGE消息包含“本地最新稳定检查点n及相应证明”和“n后面达到prepared状态的消息及相应证明”，又因每个证明中包含2f+1条CHECKPOINT或PREPARE消息，所以总的网络复杂度为O( $N^3$ )，N为节点总个数。新的主节点广播NEW-VIEW消息，NEW-VIEW消息中包含2f+1个VIEW-CHANGE消息，网络复杂度为O( $N^3$ )，N为节点总个数。
$\quad$ 连续换主时，可能产生O( $N^4$ ) 网络复杂度。

6. 为什么拜占庭节点不能超过或等于1/3

$\quad$ 解释1：总的节点个数为N个，拜占庭节点个数为f个，为保证算法活性，每次收集投票只能收集N-f个，但实际收集的投票可能包含f张恶意节点的投票，因此只可以保证收集到N-2f张诚实节点投票。需保证诚实节点投票的个数占诚实节点的大多数，因此N-2f>f，即N>=3f+1。
$\quad$ 解释2：算法实际运行过程中，一方面，为保证算法活性，每次投票只能收集N-f张投票；另一方面，为保证前面达成的结果能够传到后面（前后投票或者前后view），需保证前后同时参与投票的节点至少包含一个诚实节点，即前面投票的N-f个节点和后面投票的N-f个节点交集至少需要f+1个，如下图。

$\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ $\quad$ 在这里插入图片描述

7. PBFT为什么是三阶段

6.1 两阶段为什么不行
$\quad$ 假设算法为两阶段：
$\quad$ a. 客户端将自己的请求转发给主节点（或者通过其他的从节点转发给主节点）；
$\quad$ b. 主节点构造PRE-PREPARE消息，并转发给其他节点（由于主节点可能是恶意节点，因此主节点发送给其他节点的PRE-PREPARE消息可能是不一致的）；
$\quad$ c. 节点验证PRE-PREPARE的签名，视图，水位线等，验证通过则发送PREPARE消息到其他节点（这一步节点间不会交互，主节点发送不一致的消息在这一步不会被检测出来）；
$\quad$ d. 当节点收到2f+1个（包括自己的）相同的PREPARE消息，则此消息在该节点prepared，之后执行消息。

$\quad$ 考虑一种情况，在sequence number n，主节点给f+1个诚实节点（这些节点的集合我们称为M）发送了消息m，给其他f个诚实节点（这些节点的集合我们称为M’）发送了消息m’，之后进入prepare阶段，M（f+1个）会给m投票。假设另外f个拜占庭节点（包括主节点）只向M中的部分节点（M1）发给m投票的prepare消息，M1中的节点会提交m，而由于M2中的节点始终无法收到2f+1个相同的投票，则不会去提交。节点发现主节点发生拜占庭错误后，发起view-change请求。
$\quad$ 新主节点会收集2f+1个节点的状态，但假如收集的消息中不包含已经提交的消息（因为只有少于f+1个诚实节点的M1提交了m），新主节点不会重新发起m，系统的安全性被破坏。
$\quad$ 所以两阶段不可以安全地达成共识。

6.2 三阶段为什么可以
$\quad$ 节点在第二阶段prepared之后，发送commit消息，commit阶段每个节点会收集其他节点的commit消息，如果收到2f个相同的commit消息，并且自己本身已经prepared，则提交执行请求。

$\quad$ 节点提交请求时需要2f+1个commit消息，意味着有2f+1个节点对消息已经达到prepared状态，其中至少包含f+1个诚实节点（这f+1个节点集合表示为H）。view-change时，新主节点收集2f+1个VIEW-CHANGE请求，其中必定包含H中的VIEW-CHANGE消息。如此，新主节点会将当前已经commit的消息带到下一轮，否则，继续换主。
$\quad$ 总结来说，commit阶段是要在view-change时，新主节点能够把被部分诚实节点已经提交的请求在下一轮重新提起，使得没有提交的诚实节点也会提交，保证view前后一致性。

转载请注明出处。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/600163