PBFT共识算法阅读笔记

PBFT共识算法

pbft 算法的除了需要支持容错故障节点之外,还需要支持容错作恶节点。假设系统节点数为 N,有问题的节点为 f。有问题的节点中,可以既是故障节点,也可以是作恶节点,或者只是故障节点或者只是作恶节点。那么会产生以下两种极端情况:

  • f个问题节点既是故障节点又是作恶节点,那么根据少数服从多数的原则,系统中正常节点只要有f+1个就会保证系统达成正确的共识,这种情况下支持最大容错节点的数量是(n-1) /2
  • 故障节点和作恶节点都是不同的节点,那么就会有f个作恶节点和f个故障节点,当发现是故障节点时,会被系统排除在外,所以根据少数服从多数的原则,系统中只要有f+1个正常节点就可以保证系统正确达成共识,在这种情况下,系统支持的最大容错节点的数量是(n -1)/3

综上两种情况,pbft算法最大支持容错节点数量是(n-1)/3

pbft是一种状态机副本复制算法,所有的副本在一个视图轮换的过程中操作,主节点通过视图编号以及节点数集合来确定,主节点 p = v % n, v 是视图编号,n是节点个数,p是主节点的编号

PBFT算法流程

pbft的基本流程只要有以下四个步骤:

  • 客户端发送请求给主节点
  • 主节点广播请求给其他节点,节点执行pbft算法的三段协议
  • 处理后三阶段后,返回消息给客户端
  • 客户端收到来自f+1个节点的相同消息后,共识正确完成
    下图即为pbft算法的流程

pbft-consensus-behavior

REQUEST

客户端c向主节点p发送<REQUEST, o, t, c>请求。o: 请求的具体操作,t: 请求时客户端追加的时间戳,c:客户端标识。REQUEST: 包含消息内容m,以及消息摘要d(m)。客户端对请求进行签名。

PRE-PREPARE

主节点收到客户端的请求,需要进行校验:客户端请求消息签名是否正确。如果是非法请求丢弃。如果请求正确,就分配一个编号n,编号n主要用于对客户端的请求进行排序。然后广播一条<<PRE-PREPARE, v, n, d>, m>消息给其他副本节点。其中,v:视图编号,d客户端消息摘要,m消息内容。<PRE-PREPARE, v, n, d>进行主节点签名。n是要在某一个范围区间内的[h, H],在垃圾回收时候可以使用

PREPARE

副本节点收到主节点消息pre-prepare消息后,需要进行校验:

  • 判断主节点pre-prepare消息签名是否正确
  • 当前副本节点是否之前已经收到在同一个v下并且编号是n,但是签名不同的pre-prepare消息。
  • m的摘要和d是否一致
  • n是否在[h,H]内

如果不满足以上任何一点,即为非法请求,丢弃。如果都满足,这个节点向其他所有节点(包括主节点)发送一条<PREPARE, v, n, d, i>消息,其中v, n, d, m与上述PRE-PREPARE消息内容相同,i是当前副本节点编号。<PREPARE, v, n, d, i>进行副本节点i的签名,供其他节点进行验证。同时把<<PRE-PREPARE, v, n, d>, m><PREPARE, v, n, d, i>消息记录到本地的log中,以便在View Change过程中恢复未完成的请求操作

COMMIT

主节点和副本节点收到<PREPARE, v, n, d, i>消息,需要对消息进行以下校验:

  • 副本节点的<PREPARE, v, n, d, i>消息签名是否正确
  • 当前副本节点是否已经收到了同一个视图v的n。
  • n是否在[h,H]内
  • d是否和当前已收到的<<PRE-PREPARE, v, n, d>, m>的d相同

同样的,如果不满足以上任何一点,即为非法请求,丢弃。如果副本节点i收到了2f+1个验证通过<PREPARE, v, n, d, i>消息内容相同,则向其他节点包括主节点发送一条<COMMIT, v, n, d, i>消息,其中v, n, d, i与上述PREPARE消息内容相同, 把<COMMIT, v, n, d, i>进行副本节点i的签名。同时记录<COMMIT, v, n, d, i>消息到log中,用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log。中。

REPLY

主节点和副本节点收到<COMMIT, v, n, d, i>消息后,需要进行校验:

  • 副本节点COMMIT消息签名是否正确
  • 当前副本节点是否已经收到了同一视图v下的n
  • d与m的摘要是否一致
  • n是否在区间[h, H]内

如果不满足就丢弃,如果副本节点i收到了2f+1个通过验证的<COMMIT, v, n, d, i>消息,说明当前系统已经达成共识,运行客户端的请求o,并且返回<REPLY, v, t, c, i, r>给客户端,其中,r:是请求操作结果,客户端如果收到f+1个相同的REPLY消息,说明客户端发起的请求已经达成全网共识,否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中

Garbage Collection

为了确保在View Change的过程中,能够恢复先前的请求,每一个副本节点都记录一些消息到本地的log中,当执行请求后副本节点需要把之前该请求的记录消息清除掉。可以在执行完多条请求K后,执行一次状态同步。这个状态同步消息就是CheckPoint消息。

副本节点i发送<CheckPoint, n, d, i>给其他节点,n是当前节点所保留的最后一个视图请求编号,d是对当前状态的一个摘要,该CheckPoint消息记录到log中。如果副本节点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发生变化,再继续前进。

View Changes

如果主节点作恶,它可能会给不同的请求编上相同的序号,或者不去分配序号,或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求,客户端设置超时机制,超时的话,向所有副本节点广播请求消息。副本节点检测出主节点作恶或者下线,发起View Change协议。
副本节点向其他节点广播<VIEW-CHANGE, v+1, n, C, P, i>消息。n是最新的stable checkpoint的编号,C是2f+1验证过的CheckPoint消息集合,P是当前副本节点未完成的请求的PRE-PREPARE和PREPARE消息集合。

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

  • 选取V中最小的stable checkpoint编号min-s,选取V中prepare消息的最大编号max-s
  • 在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)空消息摘要

副本节点收到主节点的NEW-VIEW消息,验证有效性,有效的话,进入v+1状态,并且PRE-PREPARE消息处理流程。

总结

PBFT算法由于每个副本节点都需要和其他节点进行P2P的共识同步,因此随着节点的增多,性能会下降的很快,但是在较少节点的情况下可以有不错的性能,并且分叉的几率很低。PBFT主要用于联盟链,但是如果能够结合类似DPOS这样的节点代表选举规则的话也可以应用于公联,并且可以在一个不可信的网络里解决拜占庭容错问题。

文章名: 《PBFT共识算法阅读笔记》
文章链接:https://blog.hrhr7.cn/index.php/archives/28/
联系方式:tensor7@163.com
除特别注明外,文章均为Cupidr原创,转载时请注明本文出处及文章链接
Last modification:November 22nd, 2019 at 08:02 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment