# 共识算法
## 共识算法简介
共识算法是指在分布式场景中,多个节点为了达成相同的数据状态而运行的一种分布式算法。
在分布式场景中,可能出现网络丢包、时钟漂移、节点宕机、节点作恶等等故障情况,共识算法需要能够容忍这些错误,保证多个节点取得相同的数据状态。
根据可容忍的故障类型的不同,可以将共识算法分为两类:
- 容忍宕机错误类算法(crash fault tolerant consensus algorithm),可以容忍网络丢包、时钟漂移、部分节点宕机这种节点为良性的错误。常见算法有 Paxos、Raft。
- 容忍拜占庭错误类算法(byzantine fault tolerant consensus algorithm),可以容忍部分节点任意类型错误,包括节点作恶的情况。常见算法有 PBFT、PoW、PoS等。
根据使用场景的不同,又可将共识算法分为公链共识、联盟链共识两类。
### 公链共识
公链的特点是节点数量多且节点分布分散,主要使用的共识算法有PoW和PoS,这两种共识的优点是可以支持的节点数量多,缺点是TPS较低和交易确认时间长。
### 联盟链共识
联盟链的特点是节点之间网络较为稳定且节点有准入要求,根据需要容忍的错误类型可以选择Raft和PBFT类算法,这类算法的优点是TPS较高且交易可以在毫秒级确认,缺点是支持的节点数量有限,通常不多于100个节点。
### 公链共识和联盟链共识的对比
| 共识 | 支持的节点数量 | TPS | 交易时延 |
| --- | --- | --- | --- |
| 公有链共识 | 10000+ | 10+ | 10min+ |
| 联盟链共识 | 100+ | 1000+ | 1s+ |
## 长安链中的共识
长安链v1.1.0开源版本目前支持Solo,Raft,TBFT,HotStuff 四种共识类型。四种共识对比如下:
| 共识类型 | 故障节点数为n(n>=0)时,网络中最少节点数 | 使用场景 |
| -------- | --------------------------------------- | ------------------------------------------------ |
| Solo | Solo只支持1个节点 | 主要用于测试及搭建demo |
| Raft | 2n+1 | 联盟链中不需要考虑恶意节点,且需要性能较高的场景 |
| TBFT | 3n+1 | 联盟链中需要考虑恶意节点的场景 |
| HotStuff | 3n+1 | 联盟链中需要考虑恶意节点的场景 |
### Solo
#### 算法简介
SOLO是单节点无共识投票过程的“共识算法”。
#### 算法用途
1. 快速部署单节点运行,降低试用门槛;
2. 供开发人员进行除网络和共识模块的全流程测试。
#### 如何使用算法
部署一个长安链节点,将链配置的共识算法进行如下修改,清除数据启动即可:
```sh
#共识配置
consensus:
# 共识类型(0-SOLO,1-TBFT,2-MBFT,3-HOTSTUFF,4-RAFT,10-POW)
type: 0
```
### Raft
#### 算法简介
[Raft算法](https://en.wikipedia.org/wiki/Raft_(algorithm))是目前使用最广泛的非拜占庭容错类共识算法。
Raft算法主要依靠投票机制和日志复制机制来实现节点间的共识。节点通过投票选出一个leader,由leader负责处理所有请求,再将请求以日志的方式复制到其他节点。
#### 算法用途
1. 不考虑恶意节点的多节点环境;
2. 需要支持高TPS的环境。
#### 共识接口说明
Raft 实现了长安链的ConsensusEngine接口。
Start 方法用来初始化Raft内部状态及启动Raft实例。
Stop 方法用来停止Raft实例。
```go
type ConsensusEngine interface {
// Init starts the consensus engine.
Start() error
// Stop stops the consensus engine.
Stop() error
}
```
#### Raft共识与核心引擎交互图
流程图如下:
#### 如何使用算法
Raft共识建议配置节点数为2n+1(n>=0),将链配置(参见配置模块,链配置章节)的共识算法进行如下修改,清除数据启动即可:
```sh
#共识配置
consensus:
# 共识类型(0-SOLO,1-TBFT,2-MBFT,3-HOTSTUFF,4-RAFT,10-POW)
type: 4
nodes:
- org_id: "wx-org1.chainmaker.org"
node_id:
- "QmcQHCuAXaFkbcsPUj7e37hXXfZ9DdN7bozseo5oX4qiC4"
- org_id: "wx-org2.chainmaker.org"
node_id:
- "QmeyNRs2DwWjcHTpcVHoUSaDAAif4VQZ2wQDQAUNDP33gH"
- org_id: "wx-org3.chainmaker.org"
node_id:
- "QmXf6mnQDBR9aHauRmViKzSuZgpumkn7x6rNxw1oqqRr45"
```
### TBFT
#### 算法简述
TBFT 是一种拜占庭容错的共识算法,可以在拜占庭节点数小于总数1/3的情况下,保证系统的安全运行。
TBFT 的每轮共识可以分为5个步骤:
1. NewRound: 共识投票的准备阶段,会初始化共识相关状态;
2. Proposal: 提案阶段,leader节点会打包区块,并广播给follwer节点;
3. Prevote: 预投票阶段,follower节点在收到proposal并验证proposal合法后,广播自己的prevote投票到其他节点;
4. Precommit: 预提交阶段,节点收到 >2/3 针对proposal的prevote投票后,广播自己的precommit投票到其他节点;
5. Commit: 提交阶段,节点收到 >2/3 针对proposal的precommit投票后,提交proposal中的区块到账本。
其中共识投票是指其中的Proposal,Prevote,Precommit三个阶段。 阶段图示如下:
流程图如下:
#### 与PBFT的区别
TBFT基于Tendermint算法,与PBFT的最大区别在于:PBFT有一个固定的leader节点打包交易,当leader节点故障的时候会
使用view-change子协议更换leader;而在TBFT中,leader是轮换的,每提交n个块(可以配置)leader会轮换成下一个节点。
因此,TBFT比PBFT有更好的公平性。
#### 与msgbus交互流程
`ProposaState`: TBFT发送给核心引擎本节点在当前高度是否是leader节点,核心引擎判断是否需要打包区块
`Proposal`: 核心引擎打包区块并发送给TBFT
`Verify`: 当本节点收到主节点发来的区块后,向核心引擎验证区块读写集等信息
`VerifyResult`: 核心引擎返回给TBFT Verify的结果,当区块合法时,本节点将会投票给区块
`Commit`: TBFT完成共识后,向核心引擎发送提交区块的信号,核心引擎提交区块到账本
`BlockInfo`: 核心引擎告知TBFT已提交区块的高度等信息,TBFT进入下一个高度
#### 接口说明
TBFT 实现了长安链的`ConsensusEngine`接口。
`Start` 方法用来初始化TBFT内部状态及启动TBFT实例。
`Stop` 方法用来停止TBFT实例。
```go
type ConsensusEngine interface {
// Init starts the consensus engine.
Start() error
// Stop stops the consensus engine.
Stop() error
}
```
#### 数据结构
```protobuf
// TBFTMsgType defines different type message in tbft
enum TBFTMsgType {
propose = 0;
prevote = 1;
precommit = 2;
state = 3;
}
message TBFTMsg {
TBFTMsgType type = 1;
bytes msg = 2;
}
// Proposal defined a consesensus proposal which can
// be gossiped to other node and can be serilized
// for persistent store.
message Proposal {
string voter = 1;
int64 height = 2;
int32 round = 3;
int32 pol_round = 4;
Block block = 5;
EndorsementEntry endorsement = 6;
}
// VoteType represents the type of vote
enum VoteType {
VotePrevote = 0;
VotePrecommit = 1;
}
// Vote represents a tbft vote
message Vote {
VoteType type = 1;
string voter = 2;
int64 height = 3;
int32 round = 4;
bytes hash = 5;
EndorsementEntry endorsement = 6;
}
// Step represents the step in a round
enum Step {
NewHeight = 0;
NewRound = 1;
Propose = 2;
Prevote = 3;
PrevoteWait = 4;
Precommit = 5;
PrecommitWait = 6;
Commit = 7;
}
```
#### 配置参数
TBFT 可以通过在配置块中的`ext_config`字段配置相关参数:
1. "TBFT_propose_timeout": 提案的超时时间,如`10s`, `1m`;
2. "TBFT_propose_delta_timeout": 每轮提案超时增加的时间,如`10s`, `1m`;
3. "TBFT_blocks_per_proposer": 每个节点连续出块数,如 `3`。
### HotStuff
chainedbft模块实现了流水线hotstuff共识,是一种优化后的三阶段bft算法,在拜占庭节点数小于总数1/3时,保证系统的安全运行,同时提供更加高效的运行效率;在如下方面进行了优化:
* 优化投票流程,使用星型网络减少网络通信量至O(n)
* 简化共识消息类型为 proposalMsg、voteMsg
* liveness和safty解耦,方便拓展实现
hotstuff是一种基于view的共识算法,每个view又称为level,每次进行level切换时,可以更新下一个level的proposer,且具有如下特性;
* 共识算法运转过程中,存在两个全局累加的变量:区块高度、共识level,指定高度的区块可能经历多轮共识才达成一致,当节点生成有效区块或当前共识level被投超时票后,共识level都会递增
* 流水线的hotstuff共识算法中,对当前共识level区块的投票会发送下一个共识level的proposer节点,由下一个level的proposer收集投票信息组成QC,包含在新生成的区块中
* hotstuff共识算法为三阶段协议:prepareQC、precommitQC、commitQC
* 在流水线模式的实现中,当前区块的QC是由下一个view的leader节点收集,包含在下一个区块中;且由于每一阶段都是对指定消息的投票收集,因为对协议进行了如下优化
* prepareQC:链上验证者集合对当前view提案的第一轮共识投票,包含在下一轮共识view+1的提案中,当节点收到view+1提案消息时,表示对view的第一轮共识达成
* precommitQC/lockedQC:共识view的precommitQC是由view+1的prepareQC间接确认的,即当view+2的leader将验证者集合对view+1的共识投票包含在新提案中,其它节点收到view+2提案时,表示对view+1的prepareQC达成,对view的precommitQC达成
* commitQC:与precommitQC的达成类似,view的commitQC是通过对view+2的prepareQC间接达成的;当节点收到view+3的提案时,表示链上验证集合对view的commitQC达成,此时会将view的提案在链上提交
* 因此流水线的hotstuff实现中,节点会缓存三个共识view(view、view+1、view+2)待提交的提案信息,直到收到view+3提案时,将view的提案进行提交
* 经过流水线hotstutff的共识优化,投票类型仅包含对于接收的**proposal**消息的投票或共识超时后的**NewView**消息投票
**名字解释**
* QC(quorum certificate):(n−f)个节点对指定proposal消息的签名投票集合。
* TC(timeout quorum certificate):(n−f)个节点对共识view的超时消息的签名投票集合。
#### 模块设计
共识模块主要由几个组件组成,分别是:状态机`chainedbftSMR`、安全服务`SafetyRules`、活性服务`Pacemaker`、信息同步`syncManager`、定时器服务`TimerService`,互相配合在`ConsensusChainedBftImpl`中实现了Hotstuff协议。
* chainedbftSMR:用来管理节点的状态,保存节点的投票、QC信息等
* SafetyRules:验证节点接收的proposal消息的有效性
* Pacemaker:共识活性服务,使用接收到的QC/TC信息,推进节点的共识状态
* syncManager:在共识过程中,如果负责落后节点的信息同步,将其更新至最新链上最新状态
* TimerService: 定时器服务,当共识切换或生成区块时,添加定时任务,执行超时监测
* ConsensusChainedBftImpl:将各个模块组合起来,实现流水线hotstuff共识
#### 配置参数
1. HOTSTUFF_round_timeout_milli:共识view切换的基础超时时间
2. HOTSTUFF_round_timeout_delta_milli:相同区块高度下,每次共识超时后增加的delta时间
3. HOTSTUFF_proposer_timeout_milli:proposer生成区块时基础的超时时间
4. HOTSTUFF_proposer_timeout_delta_milli:proposer生成区块时,每次超时后增加的delta时间