共识算法-PBFT(实用拜占庭容错系统) 区块链

title: 共识算法-PBFT(实用拜占庭容错系统)
tags: 区块链,共识算法
拜占庭容错系统区块链网络的记账共识和拜占庭将军问题是相似的。参与共识记账的每一个记账节点相当于将军，节点之间的消息传递相当于信使，某些节点可能由于各种原因而产生错误的信息并传达给其他节点。通常，这些发生故障节点被称为拜占庭节点，而正常的节点即为非拜占庭节点。
拜占庭容错系统是一个拥有n台节点的系统，整个系统对于每一个请求，满足以下条件：

1.所有非拜占庭节点使用相同的输入信息，产生同样的结果；
2.如果输入的信息正确，那么所有非拜占庭节点必须接收这个信息，并计算相应的结果。

与此同时，在拜占庭系统的实际运行过程中，还需要假设整个系统中拜占庭节点(坏节点)不超过m（3m

安全性：任何已经完成的请求都不会被更改，它可以在以后请求到；
活性：可以接受并且执行非拜占庭客户端的请求，不会被任何因素而导致非拜占庭客户端的请求不能执行。

拜占庭系统普遍采用的假设条件包括：
1.拜占庭节点的行为可以是任意的，拜占庭节点之间可以共谋；
2.节点之间的错误是不相关的；
3.节点之间通过异步网络连接，网络中的消息可能丢失、乱序并延时到达，但大部分协议假设消息在有限的时间里能传达到目的地；
4.服务器之间传递的信息，第三方可以嗅探到，但是不能篡改、伪造信息的内容和验证信息的完整性。

原始的拜占庭容错系统由于需要展示其理论上的可行性而缺乏实用性。另外，还需要额外的时钟同步机制支持，算法的复杂度也是随节点增加而指数级增加。

实用的拜占庭容错系统实用拜占庭容错系统（ PBFT），降低了拜占庭协议的运行复杂度，从指数级别降低到多项式级别（ Polynomial），使拜占庭协议在分布式系统中应用成为可能。
PBFT是一类状态机拜占庭系统，要求共同维护一个状态，所有节点采取的行动一致。为此，需要运行三类基本协议，包括一致性协议、 检查点协议和视图更换协议。

一致性协议：解决如何达成共识
检查点协议：类似于操作系统的还原点
视图更换协议：系统的每个服务器节点在同样的配置信息下工作，该配置信息被称为“视图”。配置信息由主节点确定，主节点更换，视图也随之变化

我们主要关注支持系统日常运行的一致性协议。一致性协议要求来自客户端的请求在每个服务节点上都按照一个确定的顺序执行。这个协议把服务器节点分为两类：主节点和从节点，其中主节点仅一个。在协议中，主节点负责将客户端的请求排序；从节点按照主节点提供的顺序执行请求。每个服务器节点在同样的配置信息下工作，该配置信息被称为视图，主节点更换，视图也随之变化。
PBFT的一致性协议
一致性协议至少包含若干个阶段：请求（ request）、序号分配（ pre-prepare）和响应（ reply）。根据协议设计的不同，可能包含相互交互（ prepare） ,序号确认（ commit）等阶段。
PBFT系统通常假设故障节点数为m个，而整个服务节点数为3m+1个。每一个客户端的请求需要经过5个阶段，通过采用两次两两交互的方式
在服务器达成一致之后再执行客户端的请求。
C为客户端，N0~N3表示服务节点，特别的，N0为主节点，N3为故障节点。整个协议的基本过程如下：

1.客户端发送请求，激活主节点的服务操作。
2.当主节点接收请求后，启动三阶段的协议以向各从节点广播请求。
- 1.序号分配阶段，主节点给请求赋值一个序列号n，广播序号分配消息和客户端的请求消息m，并将构造PRE-PREPARE消息给各从节点；
- 2.交互阶段，从节点接收PRE-PREPARE消息，向其他服务节点广播PREPARE消息；
- 3.序号确认阶段，各节点对视图内的请求和次序进行验证后，广播COMMIT消息，执行收到的客户端的请求并给客户端以响应。
3.客户端等待来自不同节点的响应，若有m+1个响应相同，则该响应即为运算的结果。

PBFT演示在 n ≥ 3m + 1 的情況下一致性是可能解決的，其中， n 为总节点数， m为恶意节点总数
n = 4, m = 0 （接下图）

总结 【共识算法-PBFT(实用拜占庭容错系统)】PBFT在很多场景都有应用，在区块链场景中，一般适合于对强一致性有要求的私有链和联盟链场景。例如，在IBM主导的区块链超级账本项目中，PBFT是一个可选的共识协议。在Hyperledger的Fabric项目中，共识模块被设计成可插拔的模块，支持像PBFT、Raft等共识算法。