Skip to content

Latest commit

 

History

History
113 lines (73 loc) · 11.7 KB

8_2.md

File metadata and controls

113 lines (73 loc) · 11.7 KB
Raw

实用拜占庭算法(PBFT)

PBFT算法假设的环境又比Raft算法更加的’恶劣‘，Raft算法只支持容错故障节点，而PBFT算法除了需要支持容错故障节点之外，还需要容忍恶意节点。在PBFT算法中假设了系统中存在一个恶意节点，它可以伪装成自身发生了故障或者与其它节点的通信产生了延迟，以便对整个系统造成最大的破坏。但是这个恶意节点所能造成的错误在计算上是受限的，不能破坏节点间用到的密码学技术。比如恶意节点不能产生正常节点的有效签名，或者根据彩虹表等方式根据消息摘要反向得到原始消息内容等。

PBFT算法也是一种基于状态机的复制的共识算法，在算法中节点只有两种角色，主节点（primary）和副本（replica），两种角色之间可以相互转换。两者之间的转换又引入了视图（view）的概念，视图在PBFT算法中起到逻辑时钟的作用。

为了更好的容错性，PBFT算法最大的容错节点数量( n - 1 ) / 3，也就是是说4个节点的集群最多只能容忍一个节点作恶或者故障。而Raft算法的最大容错节点是( n - 1) / 2，5个节点的集群可以容忍2个节点故障。

算法容错

PBFT算法的容错数量是(n-1)/3， 而为什么PBFT算法只能容忍(n-1)/3个作恶节点呢？

假设节点总数是n，其中作恶节点有f，那么剩下的正确节点为n - f，意味着只要收到n - f个消息就能做出决定，但是这n - f个消息有可能由f个是由作恶节点冒充的，那么正确的消息就是n - f - f个，为了多数一致，正确消息必须占多数，也就是n - f - f > f但是节点必须是整数个，所以n·最少是3f+1个。

或者可以这样理解，假定f个节点是故障节点，f个节点是作恶，那么达成一致需要的正确节点最少就是f+1个，当然这是最坏的情况，如果故障节点集合和拜占庭节点集合有重复，可以不需要f+1个正确节点，但是为了保证最坏的情况算法还能正常运行，所以必须保证正确节点数量是f+1个。

算法流程

在算法开始阶段，主节点由 p = v mod n计算得出，随着v的增长可以看到p不断变化，论文里目前还是轮流坐庄的方法，这里是一个优化点。

首先客户端发送消息m给主节点p，主节点就开始了PBFT三阶段协议，三个阶段分别是预准备（pre-prepare），准备（prepare），提交（commit）。

其中pre-prepare和prepare阶段最重要的任务是保证，同一个主节点发出的请求在同一个视图（view）中的顺序是一致的，prepare和commit阶段最重要的任务是保证请求在不同视图之间的顺序是一致的。

  • 主节点收到客户端发送来的消息后，构造pre-prepare消息结构体< <PRE-PREPARE, v, n, d>, m >广播到集群中的其它节点。
  1. PRE-PREPARE标识当前消息所处的协议阶段。
  2. v标识当前视图编号。
  3. n为主节点广播消息的一个唯一递增序号。
  4. d为m的消息摘要。
  5. m为客户端发来的消息。
  • 副本(backup)收到主节点请求后，会对消息进行检查，检查通过会存储在本节点。与此同时节点自身会进入到PREPARE状态，广播消息< <PREPARA, v, n, d, i> >，其中i是本节点的编号。对消息的有效性有如下检查：
  1. 检查收到的消息体中摘要d，是否和自己对m生成的摘要一致，确保消息的完整性。
  2. 检查v是否和当前视图v一致。
  3. 检查序号n是否在水线h和H之间，避免快速消耗可用序号。
  4. 检查之前是否接收过相同序号n和v，但是不同摘要d的消息。

  • 副本收到2f+1（包括自己）个一致的PREPARE消息后，会进入COMMIT阶段，并且广播消息< COMMIT, v, n, D(m), i >给集群中的其它节点。在收到PREPARE消息后，副本同样也会对消息进行有效性检查，检查的内容是上文a, b, c。

  • 副本收到2f+1（包括自己）个一致的COMMIT个消息后执行m中包含的操作，其中，如果有多个m则按照序号n从小到大执行，执行完毕后发送执行成功的消息给客户端。

下面就是算法的流程图：

前面中介绍了Pbft算法的正常流程，但是还有一些可用性方面的问题没有解决，比如日志无限增长，主节点故障，增删节点。

日志压缩

Pbft算法在运行的过程中，日志会不断累积的，但是在实际的系统中，无论是从日志占用的磁盘空间，还是新节点加入集群，同步日志的网络消耗来看，日志都不能无限的增长。

Pbft采用检查点（checkpoint）机制来压缩日志，其本质和Raft算法采用快照的形式清理日志是一样的，只是实现的方式不同。

为每一次操作创建一个集群中稳定检查点，代价是非常昂贵的，Pbft为常数个操作创建一次稳定检查点，比如每100个操作创建一次检查点，而这个检查点就是checkpoint，当这个checkpoint得到集群中多数节点认可以后，就变成了稳定检查点stable checkpoint。

当节点i生成checkpoint后会广播消息<CHECKPOINT, n, d, i>其中n是最后一次执行的消息序号，d是n执行后的状态机状态的摘要。每个节点收到2f+1个相同n和d的checkpoint消息以后，checkpoint就变成了stable checkpoint。同时删除本地序号小于等于n的消息。

同时checkpoint还有一个提高水线（water mark）的作用，当一个stable checkpoint被创建的时候，水线h被修改为stable checkpoint的n，水线H为h + k而k就是之前用到创建checkpoint的那个常数。

视图切换

在正常流程中，可以看到所有客户端发来的消息m都是由主节点p广播到集群的，但是当主节点突然宕机，又怎么保证集群的可用性呢？

这个时候就要依赖视图切换（view-change），视图切换提供了一种当主节点宕机以后依然可以保证集群可用性的机制。view-change通过计时器来进行切换，避免副本长时间的等待请求。

当副本收到请求时，就启动一个计时器，如果这个时候刚好有定时器在运行就重置（reset）定时器，但是主节点宕机的时候，副本i就会在当前视图v中超时，这个时候副本i就会触发view-change的操作，将视图切换为v+1。

  • 副本i会停止接收除了checkpoint，view-change和new view-change以外的请求，同时广播消息<VIEW-CHANGE, v+1, n, C, P, i>的消息到集群。
    1. n是节点i知道的最后一个stable checkpoint的消息序号。
    2. C是节点i保存的经过2f+1个节点确认stable checkpoint消息的集合。
    3. P是一个保存了n之后所有已经达到prepared状态消息的集合。
  • 当在视图( v+1 )中的主节点p1接收到2f个有效的将视图变更为v+1的消息以后，p1就会广播一条消息<NEW-VIEW, v+1, V, Q>
    1. V是p1收到的，包括自己发送的view-change的消息集合。
    2. Q是PRE-PREPARE状态的消息集合，但是这个PRE-PREPARE消息是从PREPARE状态的消息转换过来的。
  • 从节点接收到NEW-VIEW消息后，校验签名，V和Q中的消息是否合法，验证通过，主节点和副本都 进入视图v+1。

当p1在接收到2f+1个VIEW-CHANGE消息以后，可以确定stable checkpoint之前的消息在视图切换的过程中不会丢，但是当前检查点之后，下一个检查点之前的已经PREPARE可能会被丢弃，在视图切换到v+1后，Pbft会把旧视图中已经PREPARE的消息变为PRE-PREPARE然后新广播。

  • 如果集合P为空，广播<PRE-PREPARE, v+1, n, null>，接收节点就什么也不做。
  • 如果集合P不为空，广播<PRE-PREPARE, v+1, n,d>

总结一下，在view-change中最为重要的就是C，P，Q三个消息的集合，C确保了视图变更的时候，stable checkpoint之前的状态安全。P确保了视图变更前，已经PREPARE的消息的安全。Q确保了视图变更后P集合中的消息安全。回想一下pre-prepare和prepare阶段最重要的任务是保证，同一个主节点发出的请求在同一个视图（view）中的顺序是一致的，而在视图切换过程中的C，P，Q三个集合就是解决这个问题的。

主动恢复

集群在运行过程中，可能出现网络抖动、磁盘故障等原因，会导致部分节点的执行速度落后大多数节点，而传统的PBFT拜占庭共识算法并没有实现主动恢复的功能，因此需要添加主动恢复的功能才能参与后续的共识流程，主动恢复会索取网络中其他节点的视图，最新的区块高度等信息，更新自身的状态，最终与网络中其他节点的数据保持一致。

在Raft中采用的方式是主节点记录每个跟随者提交的日志编号，发送心跳包时携带额外信息的方式来保持同步，在Pbft中采用了视图协商（NegotiateView）的机制来保持同步。

一个节点落后太多，这个时候它收到主节点发来的消息时，对消息水线（water mark）的检查会失败，这个时候计时器超时，发送view-change的消息，但是由于只有自己发起view-change达不到2f+1个节点的数量，本来正常运行的节点就退化为一个拜占庭节点，尽管是非主观的原因，为了尽可能保证集群的稳定性，所以加入了视图协商（NegotiateView）机制。

当一个节点多次view-change失败就触发NegotiateView同步集群数据，流程如下；

  • 新增节点Replica 4发起NegotiateView消息给其他节点；
  • 其余节点收到消息以后，返回自己的视图信息，节点ID，节点总数N；
  • Replica 4收到2f+1个相同的消息后，如果quorum个视图编号和自己不同，则同步view和N；
  • Replica 4同步完视图后，发送RevoeryToCheckpoint的消息，其中包含自身的checkpoint信息；
  • 其余节点收到RevoeryToCheckpoint后将自身最新的检查点信息返回给Replica 4;
  • Replica 4收到quorum个消息后，更新自己的检查点到最新，更新完成以后向正常节点索要pset、qset和cset的信息（即PBFT算法中pre-prepare阶段、prepare阶段和commit阶段的数据）同步至全网最新状态；

增删节点

Replica 5新节点加入的流程如下图所示；

  • 新节点启动以后，向网络中其他节点建立连接并且发送AddNode消息；
  • 当集群中的节点收到AddNode消息后，会广播AgreeAdd的消息；
  • 当一个节点收到2f+1个AgreeAdd的消息后，会发送AgreeAdd的消息给Replica 5
  • Replica 5会从收到的消息中，挑选一个节点同步数据，具体的过程在主动恢复中有说明，同步完成以后发送JoinNet
  • 当集群中其他节点收到JoinNet之后重新计算视图view，节点总数N，同时将PQC信息封装到AgreeJoinOrExit中广播
  • 当收到2f+1个有效的AgreeJoinOrExit后，新的主节点广播UpdateNet消息完成新增节点流程

删除节点的流程和新增节点的过程类似：