Tendermint共识算法技术实现

Tendermint共识算法技术实现

1. Tendermint共识算法

tendermint共识算法是拜占庭容错算法，也是最多容忍不超过1/3的恶意节点。协议遵循一个简单的状态机，通过消息事件推动状态的改变。tendermint共识主要有一下几个阶段：NewHeight、NewRound、Propose、Prevote、Precommit、Commit。作为一个BFT类的共识算法。tendermint对应的三阶段分别是Proposal，Prevote，Precommit三个阶段：

tendermint共识算法共识步骤

共识节点轮流对交易的区块提议并对提议的区块投票，但区块也有可能提交失败，这种情况下协议将选择下一个validator在相同高度上提议一个新块，重新开始投票。因此tendermint同一个高度可能会经过多个轮次round才能进入下一个高度。成功提交一个区块，必须经过两个阶段的投票，称为pre-vote和pre-commit。当超过 2/3 的验证人在同一轮提议中对同一个块进行了pre-commit投票，那么这个区块才会被提交。

假设少于三分之一的共识节点是拜占庭节点，Tendermint能够保证永远不会在同一高度重复提交区块而造成冲突。为了做到这一点，Tendermint 引入了锁定机制，一旦验证人预投票了一个区块，那么该验证人就会被锁定在这个区块。

2. 共识流程

tendermint共识流程可以通过下面这张经典的图片来描述：

tendermint共识算法流程

下面我们根据这张图片来分析tendermint的共识流程：

1. NewHeight阶段

NewHeight阶段属于特殊阶段，是共识的开始阶段，这个阶段表示上一个高度的区块已经被commit了，开启下一个高度的共识，这个阶段没有太多赘述的必要。

1. NewRound阶段

NewHeight阶段之后，会进入到NewRound阶段，这时候是从round 0开始进行共识流程。但是通过上文的描述，我们知道tendermint达成一个块的共识可能需要多个round，如果在一个round没有达成有效block投票一致的话，共识不会commit block，而是会round+1进入继续到NewRound阶段。NewRound阶段之后我们就会进入到Propose阶段，这个阶段就开始熟悉的BFT三阶段了。

1. Propose阶段

到了这个阶段，就开始生成提案了。tendermint根据Round-robin轮询规则选取主节点。选取主节点的规则较为复杂，简单的可以描述为：

构建一个Validator循环排序数组，从的0位置开始指定Validator为Proposer，然后依次向后指定（选择位置1的Validator为Proposer）, 达到最后时从0重新开始。tendermint是有stake的，validator有一个叫做votingPower的概念，根据这个votingPower来决定数组的顺序，其votingPower越大被选中的概率也就越大，质押的资金stake越多，votingPower就越大。为了防止votingPower很大的Validator选举垄断，初始化后每轮之后都会根据votingPower更新算法都会更新votingPower：

1. 本轮未被选中的Validator本轮后其votingPower增加其初始化的stake，即votingPower = votingPower + stakevotingPower
2. 本轮被选中的Validator本轮后其votingPower减少为Validator循环数组中其他Validator的stake之和。下表显示了Tendermint选取Proposer的Round-robin规则：

根据算法选取的Proposer通过Gossip协议发送Proposal到剩余的每个Validator节点，如果该Proposer被Lock到之前的round的block上，那么该Proposer会直接propose那个block；而如果没有Lock的block则会生成一个新的block，关于lock block的逻辑，在下面的precommit阶段会提到。

生成proposal之后，共识进入到prevote阶段。Propose阶段还会开启一个onProposeTimeout定时器，如果在这个时间之内，如果生成proposal超时，则会超时进入到prevote阶段。

1. Prevote阶段

在Prevote开始阶段，每个Validator会判断自己是否锁定在之前的proposed区块上，如果锁定在之前的proposal区块中，那么在本轮中继续为之前锁定的proposal区块签名并广播prevote投票。否则为当前轮中接收到的proposal区块签名并广播prevote投票。如果由于某些原因当前Validator并没有收到任何proposal区块，那么签名并广播一个空的prevote投票。prevote阶段会不停的收取来自其他节点的prevote投票，这个时候如果收到一个更高轮次的的PoLC，则需要释放掉lock的block。这里介绍一下PoLC：PoLC，全称为 Proof of Lock Change，表示在某个特定的高度和轮数(height, round)，对某个块或 nil (空块)超过总结点 2/3 的Prevote投票集合，简单来说 PoLC 就是2/3+1的 Prevote 的投票集。

如果收到了2/3+1的任何prevote投票(包括自己的prevote投票)，prevote阶段还会开启onPrevoteTimeout定时器，如果在这个时间内，没有收到2/3+1的同一个block的prevote投票，则会超时进入precommit阶段。（注：必须是收到2/3+1的任意prevote投票才开启定时器。）

1. PreCommit阶段

Prevote超时或者收到Prevote（or nil）+2/3的时候，进入Precommit阶段，如果此时节点收到+2/3的Prevote的投票，则会生成并且广播一条Precommit投票，同时将自己锁在这个block上，锁定的区块 会在之后的Propose阶段用到，用于生成新的proposal。

和Prevote阶段一样，如果收到了2/3+1的任何precommit投票(包括自己的precommit投票)，precommit阶段还会开启onPrecommitTimeout定时器，如果在这个时间内，没有收到2/3+1的同一个block的prevote投票，则会超时进入Commit阶段。（注意：必须是收到2/3+1的任意precommit投票才开启定时器。）

1. Commit阶段

Commit阶段是共识流程的最后阶段了，如果收到了针对本轮次的2/3+1个precommit投票，并且之前也收到了对应这个precommit集的proposal，则会commit block，然后进入NewHeight 阶段, 开启新的height；而如果没有收集到这个2/3+1的针对这个proposal的precommit投票集或者没有收到proposal，则进入NewRound 阶段, 开启新的一轮共识。

3. tendermint的安全性和活性

安全性：tendermint由于采取了lock机制，假定有最多小于总结点 1/3 的拜占庭节点。如果一个节点在第 R 轮提交一个块，则表明此节点在第 R 轮收到大于 2/3 的针对此块的 Precommit 投票。这也就意味有大于1/3 的诚实节点在第 R’ (R’ > R)轮仍然锁定在这个块上(因为大于 2/3 的 Precommit 投票必定包含大于 1/3 诚实节点的 Precommit 投票)。只有当遇到针对另一个块的 PoLC 时才会解锁，但是在 R’ 轮是不可能有针对某个块的 PoLC，因为已经有大于 1/3 的诚实节点已经锁定在这个块上，所以就不可能有对另外一个块大于 2/3的 Prevote 投票。

活性：tendermint采用了各阶段的超时机制（采用的2/3+1的任意投票开启计时器），因此就算没有达成某个Round的共识，也会超时进入一个新的Round，并且有lock-unlock保证安全性。

4. Tendermint共识算法和PBFT共识算法的比较：

相同点：

都属于BFT类型的算法，最多容忍不超过1/3的恶意节点。都是三阶段提交，Tendermint的propose->prevote->precommit三个阶段，跟PBFT的三个阶段，pre-prepare, prepare, commit 三阶段是一一对应的都在超时的时候，换掉主节点。

不同点：

Tendermint和PBFT最大的不同点就是Tendermint没有PBFT的View Change阶段。Tendermint很巧妙的把超时的情况跟普通情况融合成了统一的形式，都是 propose->prevote->precommit 三阶段，只是超时的时候通过投空票从而使进入新的轮次来切换主节点。而PBFT是有一个单独的view change过程来触发primary轮换。