PBFT
BFT是一类解决拜占庭将军问题的策略/算法：让非拜占庭节点达成一致的算法。在这类论文中，拜占庭节点指“坏”的将军，非拜占庭节点指“好”的将军。
PBFT是实用拜占庭算法（Practical Byzantine Fault Tolerance）的缩写，该论文与1999年发表，另外2001年又发表了一篇Practical Byzantine Fault Tolerance and Proactive Recovery，让PBFT拥有恢复能力。
PBFT作为解决拜占庭问题的策略：非拜占庭节点不知道哪些是拜占庭节点，哪些是非拜占庭节点，PBFT要让非拜占庭节点达成一致。 （这里指先让好节点达成共识，执行请求，形成最长链，之后其他节点的软件会检测当前是不是最长链，若不是，从其他节点要数据，当然数据自己会先检查一边看是否合法。
这里又牵扯到一个点是：为什么有f个恶意节点，最终客户端接收到f+1个相同结果就认为达成共识了呢？ 这是因为在公投的时候，那些没工作，没有正确信息的节点不会投票，只有坏节点会乱投票，所以只要求正常节点比坏节点多就行)
区块链的工作方式是若各节点内容出现不一样（如该节点长时间未联网），则会向其他节点要数据（进行公投，少数服从多数 ），从而达到各节点内容一致。 （本质应该是扫描当前链是否是最长链，从而进行全网投票）
PBFT是Practical Byzantine Fault Tolerance的缩写，即：实用拜占庭容错算法。该算法是Miguel Castro（卡斯特罗）和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，算法的时间复杂度是O(n^2)，使得在实际系统应用中可以解决拜占庭容错问题。以下拜占庭容错问题简称BFT。
BFT是区块链共识算法中，需要解决的一个核心问题，以比特币和以太访为代表的POW，EOS为代表的DPOS，以及今后以太访逐渐替换的共识算法POS，这些都是公链算法，解决的是共识节点众多情况下的BFT。而PBFT是在联盟链共识节点较少的情况下BFT的一种解决方案。
PBFT算法前提，采用密码学算法保证节点之间的消息传送是不可篡改的。
| PBFT容忍无效或者恶意节点数：f，为了保障整个系统可以正常运转，需要有2f+1个正常节点，系统的总节点数为： | R | = 3f + 1。也就是说，PBFT算法可以容忍小于1/3个无效或者恶意节点，该部分的原理证明请参考PBFT论文，下文有链接地址。 |
| PBFT是一种状态机副本复制算法，所有的副本在一个视图（view）轮换的过程中操作，主节点通过视图编号以及节点数集合来确定，即：主节点 p = v mod | R | 。v：视图编号， | R | 节点个数，p：主节点编号。 |
结果: 能够确保Liveness (网络持续运行, 不会卡死) 和 Safety (安全性, 不会被恶意节点主导)
重要概念: View
节点运行过程中, 全网络的配置(configuration)是在不断变化的. 比方说现在的配置是A节点是主节点, 其余节点都是从节点, 那么一段时间后, 这个配置可能改变为B节点为主节点, 其余从节点.
我们将每一次的配置状态称为一个View. 整个网络就是不断在不同的View之间切换的.
记当前View的编号为v, 编号为p = v % n的节点就作为主节点, 其余作为从节点. 当主节点失效时, 进行View的切换.
每一个视图下会处理多个请求，并不是一个视图一个请求
拜占庭节点在网络中的行为
拜占庭问题是在分布式对等网络，对通信容错所提出来的。在真实世界中，拜占庭问题是什么样的？
通常使用拜占庭行为，描述拜占庭节点可能的行为，拜占庭行为有：
- 任何不遵守协议的动作
- 恶意代码、节点
- 代码bug
- 网络故障、数据包损坏
- 磁盘崩掉、重复丢失
- 无权限时加入
- …
PBFT算法流程：
1.REQUEST：
客户端c（注意：客户端并不是节点！节点是服务器，就像VPN，每个客户端会找代理节点，这样多个客户端可能都找1个代理节点。这样的话一个系统就算只有1个客户，但是他能租好几个节点来实现区块链！）向主节点p发送<REQUEST, o, t, c>请求。o: 请求的具体操作，t: 请求时客户端追加的时间戳，c：客户端标识。REQUEST: 包含消息内容m，以及消息摘要d(m)。客户端对请求进行签名。
2.PRE-PREPARE：
主节点收到客户端的请求，需要进行以下交验：
a. 客户端请求消息签名是否正确。
非法请求丢弃。正确请求，分配一个编号n，编号n主要用于对客户端的请求进行排序。然后广播一条«PRE-PREPARE, v, n, d>, m>消息给其他副本节点。v：视图编号，d客户端消息摘要（用来验证这个消息就是客户端的原始消息），m消息内容。<PRE-PREPARE, v, n, d>进行主节点签名。n是要在某一个范围区间内的[h, H]，具体原因参见垃圾回收章节。
为了保持消息较小。请求没有包括在pre-prepare消息（指<PRE-PREPARE, v, n, d>整体）中。这是很重要的因为pre-prepare消息用于作为该请求定义的序列号n在视图v中的证明。
3.PREPARE：
副本节点i收到主节点的PRE-PREPARE消息，需要进行以下校验：
a. 主节点PRE-PREPARE消息签名是否正确。
b. 当前副本节点是否已经收到了一条在同一v下并且编号也是n，但是签名不同的PRE-PREPARE信息（没有收到是合法的 这是为了以防主节点作恶，将不同的请求分到相同的n,从而在其他节点产生请求混乱 因为在短时间会有很多请求，各个请求通过v和n区分，从而相同请求在各个节点一起执行）
c. d与m的摘要是否一致。
d. n是否在区间[h, H]内。 (这是为了避免坏的主节点通过设置一个超大的n来耗尽编号)
非法请求丢弃。正确请求，副本节点i向其他节点包括主节点发送一条<PREPARE, v, n, d, i>消息, v, n, d与上述PRE-PREPARE消息内容相同，i是当前副本节点编号。（不用传m，因为每个节点已经有pre-prepare了，所以有请求m，之后就不用再传m了，只需要传签名d来验证即可，节省流量） <PREPARE, v, n, d, i>进行副本节点i的签名（每一步都要由发送方进行签名，防止伪造）。记录PRE-PREPARE和PREPARE消息到log中，用于View Change过程中恢复未完成的请求操作。
4.COMMIT：
主节点和副本节点收到PREPARE消息，需要进行以下校验：
a. 副本节点PREPARE消息签名是否正确。
b. 当前副本节点是否已经收到了同一视图v下的n。
c. n是否在区间[h, H]内。
d. d是否和当前已收到PRE-PPREPARE中的d相同
非法请求丢弃。如果副本节点i收到了2f+1个验证通过的PREPARE消息（表明至少有f+1个诚实节点在视图v中发送了序列号为n的pre-prepare消息或者是prepare消息），则向其他节点包括主节点发送一条«COMMIT, v, n, d, i>,m>消息，v, n, d, i与上述PREPARE消息内容相同。<COMMIT, v, n, d, i>进行副本节点i的签名。记录COMMIT消息到日志中，用于View Change过程中恢复未完成的请求操作。记录其他副本节点发送的PREPARE消息到log中。
Commit消息的内容和Prepare消息内容相同，但消息类型和数字签名是不同的，所以可以区分。
5.REPLY：
主节点和副本节点收到COMMIT消息，需要进行以下校验：
a. 副本节点COMMIT消息签名是否正确。
b. 当前副本节点是否已经收到了同一视图v下的n。
c. d与m的摘要是否一致。
d. n是否在区间[h, H]内。
非法请求丢弃。如果副本节点i收到了2f+1个验证通过的COMMIT消息（包括自己），说明当前网络中的大部分节点已经达成共识，运行客户端的请求操作o，并返回<REPLY, v, t, c, i, r>给客户端（这只是为了汇报结果，请求已经执行了），r：是请求操作结果，客户端如果收到f+1个相同的REPLY消息，说明客户端发起的请求已经达成全网共识，否则客户端需要判断是否重新发送请求给主节点。记录其他副本节点发送的COMMIT消息到log中。
为什么是f+1个? 坏节点可以无限重放坏消息, 但是无法仿造别人的签名. 所以f个坏节点能产生的带不同签名的坏回复至多f个. 那么f+1个相同的消息就必然是好节点发出的.
结论: 一旦有一个节点进入committed-local(m, v, n, i)状态, 则全网 进入committed(m, v, n)状态.
所以这时3f+1个节点中所有好节点都会达成一致共识，进行上链，不受作恶节点影响。
垃圾回收：
在上述算法流程中，为了确保在View Change的过程中，能够恢复先前的请求，每一个副本节点都记录一些消息到本地的log中，当执行请求后副本节点需要把之前该请求的记录消息清除掉。最简单的做法是在Reply消息后，再执行一次当前状态的共识同步，这样做的成本比较高，因此可以在执行完多条请求K（例如：100条）后执行一次状态同步。这个状态同步消息就是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发生变化，再继续前进。
## checkpoint、stable checkpoint
什么是checkpoint呢？checkpoint就是当前节点处理的最新请求序号。前文已经提到主节点收到请求是会给请求记录编号的。比如一个节点正在共识的一个请求编号是101，那么对于这个节点，它的checkpoint就是101.
那什么是stable checkpoint（稳定检查点）呢？stable checkpoint就是大部分节点（2f+1）已经共识完成的最大请求序号。比如系统有4个节点，三个节点都已经共识完了的请求编号是213.那么这个213就是stable checkpoint了。
那设置这个stable checkpoint有什么作用呢？最大的目的就是减少内存的占用。因为每个节点应该记录下之前曾经共识过什么请求，但如果一直记录下去，数据会越来越大，所以应该有一个机制来实现对数据的删除。那怎么删呢？很简单，比如现在的稳定检查点是213，那么代表213号之前的记录已经共识过的了，所以之前的记录就可以删掉了。
View Change：
只有主节点作恶时，才会change view！
如果主节点作恶，它可能会给不同的请求编上相同的序号，或者不去分配序号，或者让相邻的序号不连续。备份节点应当有职责来主动检查这些序号的合法性。如果主节点掉线或者作恶不广播客户端的请求，客户端 设置超时机制，超时的话，向所有副本节点广播请求消息。副本节点检测出主节点作恶或者下线，发起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消息集合的选取规则： |
\1. 选取V中最小的stable checkpoint编号min-s，选取V中prepare消息的最大编号max-s。
\2. 在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状态，并且开始O中的PRE-PREPARE消息处理流程。
总结：
pre-prepare和prepare消息用于对在同一视图中发送的请求完全排序，即使提出请求排序的primary为虚假节点也是如此。prepare和commit消息用于确保在视图之间对提交的请求进行完全排序
PBFT算法由于每个副本节点都需要和其他节点进行P2P的共识同步，因此随着节点的增多，性能会下降的很快，但是在较少节点的情况下可以有不错的性能，并且分叉的几率很低。PBFT主要用于联盟链，但是如果能够结合类似DPOS这样的节点代表选举规则的话也可以应用于公联，并且可以在一个不可信的网络里解决拜占庭容错问题，TPS应该是远大于POW的。
## 理解3f+1
对于3f+1的理解。需要用2f+1的正常节点。 指挥官 Z，诚实节点A（共f个），诚实节点B（共f个），作恶节点E（共f个） 1 如果Z是诚实的，其实不必需要3f+1，理论上需要2f+1就够了。因为诚实的共f+1个，大于作恶的f个 2 如果Z是作恶的。明显2f+1不够了。这里Z被包含在E里面，作恶节点共f个。假如某诚实节点，收到了所有E的广播，达到了f+1个，>剩下的f个诚实节点。所以作恶成功了。 再来看为什么3f不够。E向A发出进攻指令，E向B发撤退指令。这时进攻节点A+E，共2f个，达成共识了。这时撤退节点B+E，共2f个，也达成共识了。 为什么3f+1够了？E向A发出进攻指令，E向B不发指令或者向个别节点发撤退指令。这时A里面某节点共收到2f个进攻指令（最后阶段），但是还缺少一个，所以还需要等。这个时候，有下面几种情况：（1）E不向B发指令，这样诚实节点共2f+1（包括指挥官Z），互相同步，可以达成进攻共识（2）E向B个别节点发进攻指令，同前，诚实节点大于2f+1，可以达成进攻共识（3）E向B中某节点发出撤退指令，这个时候，该节点立刻识别出来E是作恶节点（因为该节点先收到了A转发的进攻指令），共识失败。（4）E向B个别节点发进攻指令，向个别节点发撤退指令。同前，收到撤退指令的节点立刻识别出来E是作恶节点。
假如 f 个异常节点没有响应，在不知情的情况下，我们一般认为响应的节点里可能有 f 个坏节点，则节点总数 n>3f,所以节点总数最少为3f+1,可以保证最多有 f 节点发生异常。
*为什么至少要2f个prepare (包括自己的pre-prepare共2f+1). 这是因为之前论证的如果有f个fault 节点, 那么节点总数至少是N=3f+1. 简单说一下论证过程, 假设总数N个节点, f个fault节点, 那么必须接收到N-f个消息应答, 就能够判断出结果(因为fault节点可能不发送应答). *N-f个应答中有 f个可能是假的 (从fault节点发出的 ), 那么真实的是N-f-f, 要求真实的应答大于假的应答, 即N-f-f > f ==> N > 3f. **
所以: N_min = 3f + 1
所以在prepare和commit两个阶段必须收到2f+1(包括自己) 的应答消息, 才能证明有f+1非fault节点发送了应答.(注意前提是非fault对于相同的消息, 会产生相同的消息应答) 即2f+1是来限制作恶节点的冒充来使f+1的判断有真实性的
一个节点废除请求，会影响到其他节点收到的消息数！
3阶段消息解决什么问题
前面提到，PBFT解决的是拜占庭问题的一致性，即让非拜占庭节点达成一致。更具体的说：让请求m，在view内使用序号n，并且完成执行m，向客户端发送响应。
为什么不能只有前2个阶段消息
这个问题的等价问题是：为什么Pre-prepare和Prepare消息，不能让非拜占庭节点达成一致？
Pre-prepare消息的目的是，主节点为请求m，分配了视图v和序号n，让至少f+1个非拜占庭节点对这个分配组合达成一致，并且不存在，即不存在有2个消息使用同一个v和n的情况。
Prepared状态可以证明非拜占庭节点在只有请求m使用<v,n>上达成一致。主节点本身是认可<m,v,n>的，所以副本只需要收集2f个Prepare消息，而不是2f+1个Prepare消息，就可以计算出至少f个副本节点是非拜占庭节点，它们认可m使用<v,n>，并且没有另外1个消息可以使用<v,n>。
既然1个<v,n>只能对应1个请求m了，达到Prepared状态后，副本i执行请求m，不就达成一致了么？
并不能。Prepared是一个局部视角，不是全局一致!! 即副本i看到了非拜占庭节点认可了<v,n>，但整个系统包含3f+1个节点，异步的系统中，存在丢包、延时（要时常考虑这些因素！！比如虽然我收到了2f个prepare信息，但是我发出去的包丢了或有延迟，这样其他的节点不一定能收到2f个了），副本i无法确定，其他副本也达到Prepared状态。如果少于f个副本成为Prepared状态，然后执行了请求m，系统就出现了不一致。 (因为每次消息都有签名d，所以坏节点伪造不了请求m，这样的话，唯一的攻击手段就是使<v,n>冲突。所以这也是重点检查目标)
所以，前2个阶段的消息，并不能让非拜占庭节点达成一致。
即达到prepared状态，代表这个节点可以确保
如果你了解2PC或者Paxos，我相信可以更容易理解上面的描述。2PC或Paxos，第一步只是用来锁定资源，第2步才是真正去Do Action。把Pre-prepare和Prepare理解为第一步，资源是<v,n>，只有第一步是达不成一致性的。
2个不变性
PBFT的论文提到了2个不变性，这2个不变性，用来证明PBFT如何让非拜占庭节点达成一致性。
第1个不变性，它是由Pre-prepare和Prepare消息所共同确保的不变性：非拜占庭节点在同一个view内对请求的序号达成共识。关于这个不变性，已经在为什么不能只有前2个阶段消息中论述过。
介绍第2个不变性之前，需要介绍2个定义。
- committed-local：副本i已经是Prepared状态，并且收到了2f+1个Commit消息。
- committed：至少f+1个非拜占庭节点已经是Prepared状态。
第2个不变性，如果副本i是committed-local，那么一定存在committed。
2f+1个Commit消息，去掉最多f个拜占庭节点伪造的消息，得出至少f+1个非拜占庭节点发送了Commit消息，即至少f+1个非拜占庭节点是Prepared状态。所以第2个不变性成立。
为什么3个阶段消息可以达成一致性
committed意味着有f+1个非拜占庭节点可以执行请求，而committed-local意味着，副本i看到了有f+1个非拜占庭节点可以执行请求，f+1个非拜占庭节点执行请求，也就达成了，让非拜占庭节点一致。
虽然我前面使用了2PC和Paxos做类比，但不意味着PBFT的Commit阶段就相当于，2PC和Paxos的第2步。因为2PC和Paxos处理的CFT场景，不存在拜占庭节点，它们的主节点充当了统计功能，统计有多少节点完成了第一步。PBFT中节点是存在拜占庭节点的，主节点并不是可靠(信)的，不能依赖主节点统计是否有f+1个非拜占庭节点达成了Prepared，而是每个节点各自统计，committed-local让节点看到了，系统一定可以达成一致，才去执行请求。
总结
本文介绍了2个阶段消息是无法达成一致的原因，而为什么3阶段消息可以。最核心的还是要理解好，PBFT解决了什么问题，以及它是如何解决的。
流程概述：
pre-prepare将请求从主节点发放到各个备份节点，各个备份节点向所有节点发prepare节点（这就是以防主节点作恶，来看各节点是否统一。 若主节点一直正常，那么其实不用这么麻烦，直接上链就行。但是主节点万一不正常，就要进行验证，能共识就共识，不能共识就超时，客户端再次发送请求） 若节点收到2f+1个一样的prepare，则说明至少有f+1个正常节点拿到请求，那么该结点达到prepared状态（即可以执行请求了），pre-prepare和prepare是来检查这一view中n是否重叠的情况 。其中请求m只发送1次，就是跟着pre_prepare发的，之后只是根据d验证是否是同一个m，这样节省流量，若不是同一个，就等客户端再次发送请求。log也是有记录的。 最后commit信息是来确保有f+1个节点达到prepared状态，避免因为丢包，延迟原因只有少数节点收到了足够的prepare信息。
PBFT解决的是在拜占庭环境下，如何提供一致性，以及如何持续的提供一致性的问题。本文只介绍了如何提供一致性，没有提如何持续提供一致性，即PBFT的可用性。现在，不妨思考一下，View Change是如何保证切换时一致性的，是否也需要2个不变性的支持呢？
参考
BFT-PR
we have developed a recovery mechanism for BFT that makes faulty replicas behave correctly again. BFT with recovery, BFT-PR, can tolerate any number of faults provided fewer than 1/3 of the replicas become faulty within a small window of vulnerability.
A Byzantine-faulty replica may appear to behave properly even when broken.
