强一致共识算法-BFT/CFT

区块链中共识机制的目的：使所有节点获得一致的区块链视图。

一致性视图包含两个含义：1、一致性：区块链的每次更新后，每个节点都能获得相同的视图；2、有效性（可审查特性）：由任一诚实节点在区块链发布的信息都最终被其它节点承认并记录。（如果一笔交易被发送到$N-f$个诚实节点了，那么最终每个诚实节点都会确认这笔交易。这就是可审查特性。）

在区块链系统中达成以上两个特性的算法就是一致性算法。

分布式系统一般通过状态复制机原理来实现一致性。其核心思想是系统中所有副本运行着相同的状态机，只要所有副本都以相同的初始状态开始，并基于相同的初始状态执行一组相同顺序的操作，那么所有的状态最终会收敛一致，即整个系统对外表现出一致性。所以状态复制的时候，不再来回地传递系统状态，而是传递导致系统状态变化的事件（区块链系统中就是交易）。

1、CFT类共识算法Crush Fault Tolerance

这类算法，仅考虑对错误节点的容错，不考虑恶意节点故意作恶导致的错误。在有少数节点故障或掉线的情况下，仍旧保证整个系统视图的一致和正确，但不能解决拜占庭问题，代表算法就是PAXOS和RAFT。

Zookeeper的ZAB, Viewstamped Replication（VR）, raft, multi-paxos都可以被称为Leader-based一致性协议

PAXOS

该算法在一定程度上容忍了信息的丢失、延时、乱序以及重复的可能性，该算法拥有的容错能力是$2f+1$，下面介绍经典paxos：

1、节点角色：

1）提议者Proposer（多个）：负责提出Proposal，每个提案包括唯一标识ID+值value
2）决策者Acceptor（多个）：获得多数Acceptor同意的proposal，才被允许给决策学习者接收
3）决策学习者Learner（多个）：只会被动接收已经通过的proposal

2、共识过程：

1）准备阶段
所有Proposer向所有Acceptor发送“准备请求”（不包含共识结果，只包含proposal的编号），Acceptor响应“准备响应”（包含未来可以接受的最小proposal编号）。Acceptor先后接收到多个proposal，这些proposal的编号可能不同，各个Acceptor就在“准备响应”中设置阈值，表明之后只接受编号大于等于已经接收到的编号的最大值。
2）接受阶段
Proposer收到大多数Acceptor的”准备响应“后，根据“准备响应”中的编号阈值，向所有Acceptor发送”接受请求“（包含提案编号和共识结果），所有Acceptor接受最新版本的proposal，达成共识；

3、PAXOS解决了两个问题：

1）所有节点都可以区分当前提议者和过期提议者，从而避免过期的共识消息搞破坏；
2）一旦达成一个新共识，所有节点必须接受它，以达成一致性。

4、PAXOS存在的问题：Proposor获得大多数Acceptor的准备响应以后，才会继续发送真正的状态共识结果，那么当由于某些原因，所有Proposor都没有收到足够多的响应，就无法继续开展共识，所以只能多次重复执行上述步骤直至成功。但是Proposor和Acceptor之间的通讯是rpc远程调用，多次执行Basic Paxos实例，就会导致往返消息多、耗性能、延迟大。

如何解决？比如：选择一个leader，来决定共识结果，于是有了下面Raft算法

实际上multi-paxos也是通过选择一个leader，来减少proposal冲突的次数

RAFT

Raft算法是现在分布式系统开发首选的共识算法，容错能力也是$2f+1$。从本质上说，Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。Raft算法是强领导者模型，集群中只能有一个”霸道总裁”，通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

1、节点角色：

1）领导者
负责接收跟从者客户端的消息，将状态共识结果（状态机日志）发送给跟从者，收到多数跟从者的正确性确认后，提交总日志，保证所有跟从者视图一致；会周期性广播心跳消息，通知别的节点自己是领导者，阻止别的跟随着发起新的选举来篡权

2）候选者
所有节点都可以成为候选者， 向其他节点发送请求投票RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。（若获得最多票数的候选人的投票结果相等，则重新投票，直至选出一个领导者为止）

3）跟随者follower
负责从领导者那里获得一致且正确的状态共识结果（日志），当等待领导者心跳信息超时的时候，就主动推荐自己当候选者

2、流程：当领导者处于稳定状态时，省略掉准备阶段，直接进入接受提案阶段

3、任期

英文单词是 term，领导者是有任期的。

1）自动增加：跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会增加自己的任期号。比如A、B、C最早term都为0，A的计时器最早超时，就将自己的任期+1，置为1，自己给自己投一票，然后向其他节点发送请求选举的消息。

2）更新为较大值：当节点发现自己的任期编号比其他节点小时，会更新到较大的编号值。比如节点 A 的任期为 1，请求投票，投票消息中包含了节点 A 的任期编号 1，节点 B 和 C 收到消息后，会将自己的任期编号更新为 1。

3）恢复为跟随者：如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。例如任期为 3 的领导者收到任期编号为 4 的心跳消息，那么前者将立即恢复成跟随者状态。这里的任期为3的领导者可能是因为网络等因素导致同步状态落后。

4）拒绝消息：如果一个节点接收到较小的任期编号值的请求，那么它会直接拒绝这个请求，比如任期编号为 6 的节点 A，收到任期编号为 5 的节点 B 的请求投票 RPC 消息，那么节点 A 会拒绝这个消息。

选举规则：
1）一个任期内，领导者一直都会是领导者，直到自身出现问题（如宕机），或者网络问题（延迟），其他节点发起一轮新的选举。
2）在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，投完了就没了。

超时时间设置：
为了防止多个节点同时发起投票，会给每个节点分配一个随机的选举超时时间。这个时间内，节点不能成为候选者，只能等到超时。比如上述例子，节点 A 先超时，先成为了候选者。这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。

4、优点：由于只有一个领导者，所以没有提案冲突的问题，省略掉准备阶段，减少了网络通信数量，提升了性能，降低了延迟；raft比paxos容易的地方在于流程清晰，描述更清晰，关键之处都给出了伪代码级别的描述，可以直接用于实现，而paxos最初的描述是针对非常理论的一致性问题，真正能应用于工程实现的mulit-paxos，Lamport老爷爷就提了个大概，之后也有人尝试对multi-paxos做出更为完整详细的描述，但各不相同。

2、BFT拜占庭容错算法Byzantine Fault Tolerance

BFT算法和区块链的概率性共识算法相比，中心化较强，但仍可以运用于区块链这种分布式系统，用中心化换取高效率。拜占庭将军问题最早是由 Leslie Lamport 与另外两人在 1982 年发表的论文《The Byzantine Generals Problem 》提出的， 他证明了在将军总数大于$ 3f$ ，背叛者为$f $或者更少时，忠诚的将军可以达成命令上的一致，即$3f+1<=n$。Miguel Castro (卡斯特罗)和 Barbara Liskov （利斯科夫）在1999年发表的论文《 Practical Byzantine Fault Tolerance 》中首次提出 pbft 算法，该算法容错数量也满足$3f+1<=n$，算法复杂度为 o ( n2)o(n^2)o(n2)。

其实PoW也不是完全中心化的，因为全网算力的大头集中在少数人手中

一个拜占庭共识算法需要保证两个性质：

• 安全性：所有诚实节点都认为某一时刻系统状态为s
• 活性：所有诚实节点最终能确定s为系统状态

上述的s可以理解为状态变量的某个值

(1) PBFT

实用拜占庭容错算法，使得拜占庭协议的运行复杂度从指数级别降低到多项式级别，容错能力$3f+1$

1、节点角色：所有节点都是Replica，其中包括一个Primary和剩余的Backup

2、共识步骤：
客户端请求–主节点生成提案–从节点准备同步–主从节点提交同步–回复客户端同步结果

1）请求Request：客户端向主节点发送开启共识的请求（主节点收集各个replica节点发送的交易）

2）预准备Pre-Prepare：主节点为客户端的请求分配提案编号（排序并执行交易，得到最新状态或区块），然后发出预准备消息<,message>给各副本节点，其中message是客户端的请求消息，digest是消息的摘要，n是提案编号，view是视图编号。

3）准备Prepare：从节点收到预准备消息后，检查消息合法性（本地执行区块内的交易），检查通过，则向其他节点发送准备消息<>，id是发送节点的身份信息，同时接收来自其他节点的准备消息，收到准备消息的节点对消息同样进行消息合法性检查，验证通过后，则把这个准备消息写入消息日志中，每个从节点集齐至少2f+1个验证过的消息才算完成准备步骤。

4）提交Commit：每个replica节点都广播commit消息，告诉其他节点某个提案n在视图view中已经处于准备状态，即已经集齐了至少2f+1个验证通过的commit消息，此时提案已经通过（各个节点可以将新区块写入本地区块链和状态数据库中）。

5）回复Reply：主节点给发出交易的客户端回应最新区块

3、视图切换

当Primary节点故障或有错误的时候，启动视图转换过程（View-change），即更换Primary节点，通信复杂度为 O ( n3)O(n^3)O(n3)，复杂度过高，导致PBFT无法在大规模真实网络应用，Hotstuff设计了线性复杂度的视图切换过程，复杂度为$O(n)$，同时也能保证安全性和活性。

4、复杂度

通信复杂度的瓶颈在于准备阶段，replica节点之间进行的一致性和正确性检查，需要花费大量通信资源，复杂度为 O ( N2)O(N^2)O(N2)

5、对比一下CFT类算法

对于CFT类算法，从节点无条件相信主节点的提案，默认主节点发送的共识消息无误，并且给所有从节点发送的都一样，所以无需进行可信验证和同步过程，从节点直接将主节点发送的消息保存到本地数据库即可。

对于BFT类算法，从节点可以拒绝主节点的提案，也就是可以怀疑主节点发送的消息可能是错误的，也可能发给所有从节点的消息不完全一样，所以需要从节点收到消息以后进行验证，并且要和别的从节点同步，这就是prepare和commit阶段做的事。prepare时，从节点将验证结果发给别人。commit时，从节点将从别的从节点收到的同步消息进行验证（具体要验证的主要是是否超过2f+1个消息是完全一样的），并把验证结果发送给别的从节点。对于单个从节点来说，如果commit阶段结束时，收到了2f+1个验证通过的消息，就认为本次状态共识结束，将状态共识结果更新到本地数据库。

(2) HotStuff

容错能力为$3f+1$，在 PBFT 的基础上做了较多改进：1、将 PBFT 的网状通信网络拓扑换成星形，降低了系统通信的复杂度，以主节点为网络中心，只依靠主节点进行消息的发送和处理，再把结果传送给其他节点。2、线性视图转换(Linear View Change,LVC)降低切换视图的复杂度。3、引入门限签名，将Quorum个replica结点的签名结合成一个证书QC，避免了多节点之间的相互转发签名消息，减少通信复杂度，相当于用门限签名+2轮通信代替了PBFT的一轮通信。

共识步骤：准备阶段（PREPARE）、预提交阶段（PRE-COMMIT）、提交阶段（COMMIT）、决定阶段（DECIDE）

1、准备阶段：主节点生成提案，发送给从节点；从节点收到提案，认为这单个提案符合自己的交易记录，验证并签名，返回给主节点

2、预提交阶段：主节点收到从节点发送的对单个提案的签名，聚合这些签名，然后广播（这是为了让每个从节点验证一下：主节点发给所有从节点的消息是一样的）；对于某一个从节点，会验证聚合签名，确认聚合签名无误，也就是认为主节点发给所有从节点的消息是一样的，返回主节点验证成功消息

3、提交阶段：主节点收到从节点对聚合签名的验证结果，若收到了2f+1个，就认为同步成功，开始正式提交，需要告诉所有从节点，别的从节点也认为消息已经同步，具体做法是：聚合从节点们对聚合签名的签名（好绕），然后广播；从节点再次验证，然后返回验证结果

4、决定阶段：主节点再次聚合上一步的验证结果，然后广播，目的是告诉从节点：主节点我成功在本地执行了状态更新，本次状态共识正式结束！

因为不再需要多个节点之间的同步通信，而是依赖一个主节点来通信，所以复杂度为$O(N)$

添加了流水化处理的hotstuff叫做Chained Hotstuff

每个阶段都会切换视图，因此每个提案都有自己的视图，节点对于不同的提案来说处在不同的视图上。

对比PBFT：

hotstuff将同步的过程变成了3阶段，但从节点之间不再有消息发送，而是依赖聚合签名，只从主节点拿消息，来验证全局已经同步。实际上减少了通信量。

(3) NoxBFT

是对hotstuff的改进

1、原HotStuff论文中的活性机制（视图切换）使用了一个全局超时时间来判断视图超时。NoxBFT设计了更灵活的机制应对网络环境的不稳定。具体：每个节点进入新的视图后，等待超时时间，如果本视图未超时，则定时器时长不变。若超时，则不断广播TimeoutMsg，直到收到quorum个TimeoutMsg，然后进入下一视图，此时定时器置为原配置时间的k倍，连续超时n次则置超时器为原配置的 kn k^nkn倍。以此类推，这样可以避免在网络不稳定时频繁切换视图。

2、交易缓存池

为避免交易丢失，设计了交易缓存池来缓存客户端交易。共识模块会主动拉取池中交易进行打包。交易池也可以减轻共识工作量，进行交易去重，通过交易内容的hash来标识交易，将已经执行的交易写入布隆过滤器，防止双花攻击，提升共识算法的稳定性。

3、快速恢复机制

不稳定的网络环境可能导致节点落后。在HotStuff原论文中，作者将此部分具体实现留给了开发者。NoxBFT实现了工程可用的同步算法，让落后共识节点能快速恢复最新状态，分为两步：
1）节点落后较多，直接向其他节点拉取区块，恢复到最新检查点（若干个视图后会来到一个检查点，普遍认为最新检查点之前的所有区块回滚的概率极低）
2）最新检查点之后的共识进度落后，则向其他节点拉取最新的CommitQC快速恢复共识进度

4、聚合签名

NoxBFT中实现并改进了Ed25519聚合签名算法。改进：1）通过编译预先计算的数据来加速签名生成；2）实现大数类型专用的加速Ed25519的计算过程，压缩大数的存储。最终Ed25519算法要比官方快2.5倍，签名算法也实现了更高的性能。

(4) LibraBFT

是一种Chained Hotstuff，LibraBFT 最初会选择一些在不同地理上分布的创始成员做共识节点，以后逐渐的，共识节点会对外开放，并基于 libra 稳定币的多少来选择共识节点，也就是转变成 PoS 机制。

LibraBFT 在 HotStuff 基础上的改进主要在于提供一个详细的参与不同视图的 Pacemaker 设计和实现。LibraBFT 提供对共识节点投票权力的动态配置机制，并给出了对主节点和从节点的激励机制。除此之外，还有检测拜占庭节点的具体实现，是惩罚机制的基础。

(5) SBFT可扩展拜占庭容错

是对拜占庭容错算法(PBFT)的一种扩展，可以支持世界范围内的209个replicas（其中64个拜占庭错误replica）正常运行，并且吞吐量可以达到PBFT的两倍，延迟也更低。

基于PBFT做的改进：

1. 类似hotstuff的主节点作为收集者来生成聚合签名方式，进行共识
2. 快速共识模式fast path和正常共识模式slow path灵活切换：当所有replica都没有错误并且状态已经同步时，SBFT允许使用快速共识机制。实现了第一个正确且实用的双模式view change，允许快速共识模式和正常共识模式之间的无缝切换
3. 聚合签名的引入减少了通信复杂度（类似hotstuff），使得瘦客户端能被大量应用
4. 增加冗余服务节点来提升性能和自适应能力：只有当所有的节点都没有错误且系统是同步的时候才可以进行快速共识，因此即使一个节点的故障都会使系统从fast path切换到slow path。SBFT借鉴了single-shot consensus algorithm（？）中提出的理论，使得fast path可以在$3f+2c+1$个replicas的系统中容忍$c$个故障replicas

节点角色：每一个视图中都会有$c + 1 $个Commit collectors和Execution collectors用来收集并组合门限签名和传播结果签名。为了liveness，至少需要一个正确的collector，论文中在fast path情况下用了c+1个collector实现冗余。

fast path是SBFT的默认共识模式，包含三阶段：

1. Pre-Prepare：主节点将客户端请求打包并广播
2. Sign-share：所有节点对提案投票，签名发送给C-collector
3. Commit-proof：C-Collector聚合签名并广播

之后的两阶段是提交阶段，包含sign-state和execute-proof

1. Sign-State：收到Commited块及投票后，replica节点验证并签名，发送给E-Collector
2. Execute-proof：E-Collector收集签名并聚合，再次广播

slow path使用的共识是线性化的PBFT，其实类似hotstuff（其实hotstuff是晚于SBFT发表的，我理解hotstuff的描述更加清晰了）

TODO：视图切换复杂度为 O ( n2)O(n^2)O(n2)

(6) Honey Badger BFT

使用了两个方法来提升共识效率：
1、分割交易，缓解主节点的带宽瓶颈

被主节点分发的提案包括一整个新区快，HBBFT则将一个区块分成n份，每一份包含若干比不同的交易，发给一个replica节点，这些replica节点之间再去交换剩下的n-1份，这样就充分利用了replica节点之间的带宽，还缓解了主节点的广播压力

2、replica随机选择交易去广播，并配合门限加密来提升交易吞吐量

由于 HoneyBadge BFT 是一种异步共识协议，每个replica节点收到的交易是非同步的，随机的，这些交易可以是不同的，交易到达各个节点的时间顺序也是不定的。各节点收到交易信息之后，会将其放入本地缓存池，然后在一个视图中随机选取若干交易进行验证+签名并广播出去。那么最终所有节点都会收到各个不同的交易子集，取并集就可得到本视图的区块包含的所有交易。

最终确认哪些交易还需要一个叫做 Binary Byzantine Agreement 的过程，简单来说就是，在所有节点之间进行一轮共识，得到一个最终确认的二进制数值value，由这个二进制的对应的位来决定哪个交易会被最终确认。在根据value剔除无效交易和重复交易之后，每个节点就可以立刻确认剩余的交易集（Asynchronous Common Subset ）。

这一策略的好处：一是可以防止敌手了解交易选取策略，而可以进行干扰或攻击；二是各节点虽然收到的交易顺序不一定一致，但在网络条件差不多的情况下，大部分交易顺序可能是相同的，随机选取而不是都按顺序选取可以避免大量的重复。

(7) DBFT算法

授权拜占庭容错，是一种在NEO区块链内部实现的保证容错的共识算法。此算法中有两种节点角色：记账节点+普通节点

记账节点由持币节点选举出来。记账节点又划为议长与议员，议长负责广播新的提案， 议员负责验证提案与投票。

在 pre-prepare 阶段，议长负责向其他议员广播新的 prepare- request提案；prepare 阶段，议员检查签名与验证视图编号等信息是否正确，如果正确则广播 prepare-response，并发起投票，当收到至少$2ｆ＋1$个签名，共识达成，任意共识节点广播新的区块。

3、用于区块链的共识算法分类

1）概率性共识算法

属于弱一致共识算法，区块数据以一定概率达成共识，随时间推移概率提高，但不能保证区块数据一定不可更改。代表有PoW、PoS，大多用在公链中，参与共识的节点通过求解难题、质押权益等方式竞争出块权，并依据最长链、GHOST等规则根据节点本地的数据确定主链（而不是强一致共识根据网络中传播的状态确定最长链/最新状态），通信复杂度为线性，开销小。对DDos、日食攻击有抵抗能力。

交易处理性能低，计算开销大。出块归属权的确定依赖计算能力竞争，导致出块间隔不够稳定，且有中心化的风险。

Bitcoin-NG 通过“关键区块+微块”的方式将出块权和排序过程分开，提升共识算法性能。委托权益证明算法 DPoS 通过投票机制缩小共识节点范围，提升交易处理性能。

2）确定性共识

区块数据一旦达成共识就不能再改，代表有 PBFT、Algorand等。大多基于PBFT进行改进，基本都用在联盟链，共识过程开始后，链内交易暂停，所有共识节点基于固定规则获取出块权，通过“节点通信+数字签名”的方式确定共识结果。这里的固定规则基于相对固定的节点准入权限设置，所以便于设置超时投票等机制进行出块间隔的稳定，或引入随机函数来分配出块权，使得出块权的归属不可预测且具有公平性。

交易处理性能高，计算开销小，但通信复杂度高，需要在网络同步环境下进行，扩展性差，限制了公式规模的扩大和场景扩展。

参考资料：
(1) 姜义,吕荣镇. 区块链共识算法综述[J]. 佳木斯大学学报（自然科学版）,2021,39(2):132-137,161. DOI:10.3969/j.issn.1008-1402.2021.02.035.
(2) https://blog.csdn.net/nzyjava/article/details/122296011
(3) https://blog.csdn.net/yijiull/article/details/94775459
(4) https://zhuanlan.zhihu.com/p/54626185