强一致共识算法-BFTPAXOS

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

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

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

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

1、PAXOS和RAFT类

有一类算法，仅考虑对错误节点的容错，不考虑恶意节点故意作恶导致的错误，在有节点错误地发布账本信息时，仍旧保证整个系统视图的一致和正确，但不能解决拜占庭问题，代表算法就是PAXOS和RAFT。

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

PAXOS

该算法在一定程度上容忍了信息的丢失、延时、乱序以及重复的可能性,该算法拥有的容错能力是 2 f + 1 2f + 1 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算法是现在分布式系统开发首选的共识算法，容错能力也是 2 f + 1 2f+1 2f+1。从本质上说，Raft算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。Raft算法是强领导者模型，集群中只能有一个"霸道总裁"。

1、节点角色：

1）领导者
负责接收跟从者客户端的消息，将状态共识结果（状态机日志）发送给跟从者，收到多数跟从者的正确性确认后，提交总日志，保证所有跟从者视图一致；会周期性广播心跳消息，通知别的节点自己是领导者，组织别的跟随着发起新的选举来篡权
2）候选者
所有节点都可以成为候选者， 向其他节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。（若获得最多票数的候选人的投票结果相等，则重新投票，直至选出一个领导者为止）
3）跟随者follower
负责从领导者那里获得一致且正确的状态共识结果（日志），当等待领导者心跳信息超时的时候，就主动推荐自己当候选者

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

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

2、BFT拜占庭容错算法

虽说BFT算法的中心化很强，但仍可以运用于区块链这种分布式系统，用中心化换取高效率。

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

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

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

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

(1) PBFT

实用拜占庭容错算法，使得拜占庭协议的运行复杂度从指数级别降低到多项式级别，容错能力 3 f + 1 3f+1 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：广播commit消息，告诉其他节点某个提案n在视图view中已经处于准备状态，即已经集齐了至少2f+1个验证通过的commit消息，此时提案已经通过（各个节点可以将新区块写入本地区块链和状态数据库中）。

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

3、视图切换

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

4、复杂度

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

(2) HotStuff

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

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

1、准备阶段：主节点收到最新的交易，本地执行并打包成区块，发送给从节点；从节点收到最新提案，对其进行验证并签名，返回给主节点

2、预提交阶段：主节点收到Quorum个从节点发送的对当前提案的签名，聚合得到prepareQC，然后广播（预提交）给从节点；从节点收到prepareQC并验证，返回验证成功消息给主节点。至此，所有节点对提案达成共识

3、提交阶段：主节点再次对上一阶段产生的签名进行聚合，得到pre-commitQC，然后广播；从节点再次验证pre-commitQC，然后返回验证结果

4、决定阶段：主节点再次聚合得到commitQC，分发给其他节点，其他节点收到后本地更新状态数据库，提案执行成功，视图切换开始

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

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

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

(3) NoxBFT

是对hotstuff的改进

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

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做的改进：

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

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

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

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

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

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

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

TODO：视图切换复杂度为 O ( n 2 ) 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 2ｆ＋1 2ｆ＋1个签名，共识达成，任意共识节点广播新的区块。

参考资料：
(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