区块链解读33-PBFT算法

解读区块链，PBFT算法（Practical Byzantine Fault Tolerance）

根据拜占庭问题演变而来的拜占庭共识算法PBFT算法，在拜占庭问题被提出后，一直有各种共识算法来解决拜占庭问题，但是无论从执行流程的复杂度还是算法效率来说目前公认的PBFT是效率最好的算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。再配图拜占庭问题。

 

 

PBFT算法设定系统为异步的分布式，网络中单一节点失效的一个独立事件。作者使用了加密技术来防止欺骗攻击和重播攻击，把消息设定为：公钥的签名 消息验证码（MAC） 消息摘要（message digest）。并且假设整个网络中，所有的节点都知道每个节点的公钥可以做签名认证。当然还有一些前提：恶意节点的算力不能破坏加密算法，不然基本保障就不存在了，恶意节点不能无限延长节点通讯，消息摘要哈希算法具备无碰撞性。

和之前拜占庭问题一样，网络中节点还是要求n个节点，恶意节点m，n>3m 1。在系统中要求整个系统有安全性和活性。整个系统通过状态机副本复制的特性来传递信息。

先谈论下安全性，在n>3m 1的情况下，安全性就是副本复制数量（<m）允许一定的失效，系统通过对这些失效节点控制改变访问全新来恢复恶意节点的攻击。

活性，同步的方式不提供安全性，但是提供活性，在异步系统中，通过同样受到请求后失效的副本不超过m，并且延时时间控制，那么最终这个消息会在异步模式中再次重新发送被接受，同样保证了系统的活性。

纯理论来理解还是有一定的难度，通过算法流程简单解释下：先假设有n个节点，有m个失效节点，n>3m 1，有3m 1个副本，副本集为F{3m 1}。现实中可能有多余3m 1的副本，但是理论上有效的只是这么多，再多余的副本可能是多次传输而来。在整个环境中设置一个主节点（P），其他为备节点（B），设置一个环境状态（V），副本集合数|F|，在主节点P失效后启动p=v mod|F|来选取新P。同时改变V的状态。在系统执行算法过程中还要求，网络中的节点执行操作如果是正确诚实的操作，所有执行后结果一致，所有网络中节点前一状态V一致。

1.客户端向P发送请求。

2.P广播至B。

3.B返回执行结果发送给客户端

4.客户端接收3m 1个一致的结果，认为结果被系统确认。

 

 

在现实的分布式系统中，在定义一个时间戳的概念T，在发送消息的时候通过V T 请求 回复信息，客户端同样等待m 1个回复，同时保证签名 时间戳 回复信息来保证一致。这里存在两种情况，一种是客户端请求超时，那就再发送一次，如果是主节点P出故障，那就改变V状态，新选一个P节点。保证第二次的执行过程。

再应用到实际场景，现在PBFT算法定义三阶段任务：预准备（pre-prepare）、准备(prepare)、确认(commit)。

预准备：P分配一个系统序列号ID，发送给所有B节点。发送格式（V、ID、信息摘要、客户端请求）。B节点验证信息摘要和客户端请求一致，验证当前V编号。

准备：B节点在接收信息后加上自己的消息日志，发送至其余节点。P和B节点同时验证消息签名，如果一致，那么就把验证通过写入消息日志。每个节点在准备阶段对每个副本节点验证预准备的消息和准备消息一致性检查完毕。

确认：在前面两个极端一切正常的话，在同一系统环境中，所有请求序号一致，验证消息一致，简单理解就是确认m 1个节点发送了之前发送的序号和消息。每个节点接受确认消息，签名正确；消息的系统环境编号V与节点的环境编号V一致；消息的序号ID满足序列要求。节点通过确认至少m 1个副本信息，保证整个系统中算法的正确性。

通过图形理解下：这个图经常能看到，看文字比较绕，看图其实就比较简单了。

 

结合区块链的角度来说明：

C我们认为是客户端，0、1、2、3是分布式系统中的节点成员，0是主节点、1、2是备份节点，3也是备份节点但已发生故障，默认3发送信息为无效。

1.C发起一笔请求到0号主节点。

2.主节点0开始对请求排序编号，并把请求序号发送到1、2、3节点。

3.1、2节点互相之间和0主节点之间发送消息。

4.0、1、2、之间确认0主节点的分配序号，互相确认。

5.0、1.、2、确认信息回复C。

6.客户端C判断收到确认是否在f 1内，确认结果。

三个阶段达成共识：Pre-Prepare、Prepare 和 Commit，整个流程如下：

1.从全网节点选举出一个主节点（Leader），新区块由主节点负责生成。

2.每个节点把客户端发来的交易向全网广播，主节点将从网络收集到需放在新区块内的多个交易排序后存入列表，并将该列表向全网广播。

3.每个节点接收到交易列表后，根据排序模拟执行这些交易。所有交易执行完后，基于交易结果计算新区块的哈希摘要，并向全网广播。

4.如果一个节点收到的2f（f为可容忍的拜占庭节点数）个其它节点发来的摘要都和自己相等，就向全网广播一条commit消息。

5.如果一个节点收到2f 1条commit消息，即可提交新区块及其交易到本地的区块链和状态数据库。

 

最后说下PBFT模式的垃圾回收机制，在系统中需要将无异议消息记录删除，那么删除这些日志的时候需要确保m 1个节点正常执行证明过，算法中通过对序号整除的模式，周期性进行，在证明过程中请求执行整除后的状态叫做检查点，证明检查点称作稳定检查点。（绕的不行。。。），简单来说：

1.副本生成一个检查点。

2.向其他节点广播这个检查点。这里需要一个序号和状态标识。

3.其余节点接收后检查日志并累计计算到2m 1个记录。这里2m 1就是检查点证明前文说的稳定检查点。

4.然后根据序号，小于序号的前期三阶段日志就可以删除，同时也删除检查点消息。

    PBFT还是挺绕的，有些定理概念解释不清楚，望见谅。有错误说明请及时指正。

笔者初学区块链，很多东西也是慢慢摸索，之所以写下这些基本概念一方面作为自己学习的整理，另一方面也希望更多交流学习的机会。如有兴趣可以直接给我留言或者加笔者微信。