前言

Tendermint是Tendermint公司开源的的一个项目,是一个PBFT算法的变体优化,只需要两轮投票就可以完成共识。
其本质上是POS+BFT结合的算法。

在上篇文章PBFT学习笔记的基础上,本文主要介绍Tendermint共识算法的核心流程和相关证明机制。

算法流程

关于 Tendermint 算法的完整描述在这里

下面这张图是 Tendermint 状态转换图。

Tendermint算法流程

算法主要有 propose -> pre-vote -> pre-commit -> commit 一共4个阶段。

结合图片,先说说外层蓝色箭头的正常流程。

Tendermint算法先随机选出一些节点作为Validators,然后选择其中一个Validator作为Proposer(提议)节点(Tendermint基于POS算法成为提议节点,后面会介绍)。Proposer节点开始监听并收集全网的所有交易,几分钟后,组装一个新块,并向全网广播,这个就是 proposal block。全网所有validator节点收到这个 proposal block后,开始读取这个block里的所有交易,一一进行验证,如果没有问题,就发出一条 pre-vote 投票消息,表示同意这个block,投一个肯定票,如果发现block里有非法交易,则投一个反对票,这些投票消息会被广播到所有validator节点,所以每个validator节点既会发出一个投票消息,又会收集别人的投票消息,当发现收集到的同意投票数量超过 2/3时,就发出一个pre-commit 投票信息,这是第二阶段的投票了,这是每个节点也在监听并收集pre-commit的投票消息。当一个validator节点收集到的 pre-commit 同意票数超过2/3时,说明这个block 是得到了大多数人统同意的,可以放心把这个block写入本地的区块链,追加到末尾,即完成commit阶段。同时区块高度+1,proposer节点索引也+1,进入下一轮(round), 开始提议新块。

异常情况

接下来说一下内圈那个红色箭头表示的小循环。
由于每一轮(round)只有一个proposer有权力出块,如果这个proposer挂了或者网络不好超时了,怎么办?

在proposer节点propose阶段,所有validator节点会启动一个定时器,设置超时时间为T(这个T的值是根据网络情况动态计算出来的),如果在这个时间内还没有收到proposer节点发来的新块,就认为这个proposer节点挂了,所有validator节点不会继续等下去,会立刻在本机生成一个特殊结构的空块,假装这个空块是从Proposer节点那里收到的,这样,无论如何,在时间T内,都会收到一个proposal区块,要么是一个正常块要么是一个空块。然后接着对这个块进行pre-vote投票和pre-commit投票。如果proposer挂了,绝大部分validator看到的都是一个空块,因此空块会获得多数投票,进入commit阶段。commit空块的时候,不会真的往区块链写入一个空块,而是什么都不写,区块高度不自增,保持不变,这样相当于什么也没有干,这一轮(round)是在空转。这一轮转完了,下一轮开始的时候会换下一个validator当proposer,这样当前那个挂掉的proposer,就不会卡住整个网络。

网络假设

Tendermint对网络的要求是,需要网络是半同步的。Tendermint在Propose阶段,有一个超时机制,但是这个超时时间不是一个常量,是动态变化的,因此在这个阶段,要求网络是半同步的。在pre-vote阶段和pre-commit两个投票阶段,对网络没有要求的,即网络是异步的。因此,Tendermint对网络要求是半同步的。

由于在pre-vote和pre-commit的投票阶段,网络是异步的,如果没有收集到超过2/3的投票数,所有validator节点会无限期等待下去,因此,整个系统会卡住。Tendermint在Liveness方面有所妥协,换取了更强的Finality。

举个例子,如果在某一轮中proposer节点广播出了一个新块blockX,某个validator A节点没有按时收到新块,那么该A就会在本机构造一个空块,当做是从proposer收到的,发出一个pre-vote nil投票消息然后进入pre-vote循环,并启动一个超时定时器,这时进入了红色内圈循环,A开始监听网络并收集投票信息,

  • 如果在规定时间内,收集到的投票数,无论是投给空块的还是blockX的,加起来,没有超过2/3,则无限等待,直到投票总数超过2/3

  • 收集到了超过2/3的投票总数后,如果投给空块的票数超过2/3,则发出pre-vote nil投给空块,依旧留在红色内圈;如果投给blockX的票数超过2/3,则发出pre-vote投给blockX,切换到蓝色外圈;如果空块和blockX各自的票数,都没有超过2/3,那么发出pre-vote nil 消息投票给空块,进入pre-commit阶段,依旧在红色内圈。

一旦A发出了pre-commit nil的投票消息,A还是留在红色内圈循环,pre-commit流程与上面类似。总而言之,红色内圈的流程,需要假设网络是半同步的。

锁机制

在上面的图中,其实还隐含有一个锁机制,没有在图中表现出来。举个例子,有四个validator 节点,A,B,C,D, 在某个R轮,

1.在propose阶段,proposer节点广播出了新块blockX

2.A的超时时间内没有收到这个新块,向外广播pre-vote nil,B,C,D都收到了,向外广播pre-vote投给blockX

3.现在四个节点进入了pre-commit阶段,A处于红色内圈,B,C,D处于蓝色外圈

4.假设A由于自身网络不好,又没有在规定时间内收到超过2/3个对blockX的投票,于是只能发出 pre-commit nil投票消息投给空块

5.D收到了B和C的pre-vote消息,加上自己的,就超过了2/3了,于是D在本机区块链里commit了blockX

6.B和C网络出现问题,收不到D在pre-commit消息,这是B和C只能看到2票投给了blockX,一票投给了空块,全部不足2/3,于是B和C都只能 commit空块,高度不变,进人R+1轮,A也只能看到2票投给了blockX,一票投给了空块,也只能commit空块,高度不变,进人R+1轮

7.在R+1轮,由于新换了一个proposer, 提议了新的区块blockY,A,B,C 三个可能会在达成共识,提交blockY,于是在同样的高度,就有blockX和blockY两个块,产生了分叉。

为此,Tendermint加上了锁的机制,具体就是,在第7步,即使proposer出了新块blockY,A,B,C只能被锁定在第6步他们的pre-commit块上,即A在第6步投给了空块,那么在第R+1轮,只能继续投给空块,B在第6步投给了blockX,那么在新一轮,永远只能投给blockX,C也是类似。这样在R+1轮,就会有1票投给空块,两票投给blockX,最终达成共识blockX,A,B,C三人都会commit blockX(commit阶段进行解锁),与D一致,没有产生冲突。

如何选择验证节点

首先,在创始区块里,可以静态设置一组validator节点 其次,当链启动后,可以发送 ValidatorUpdate消息,更新validator列表。见 Validator Updates
这个地方文档里没有讲太多,看起来还是比较原始的,没有 Algorand 那种密码抽签类似的随机抽样算法。不过这个地方应该是可以随时拓展的。

出块人顺序的选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 验证人集合结构体
type ValidatorSet struct {

Validators []*Validator `json:"validators"` //无序保存所有验证人
Proposer *Validator `json:"proposer"` //出块人
totalVotingPower int64 //总投票力
}
// 验证人结构体
type Validator struct {
Address data.Bytes `json:"address"`
PubKey crypto.PubKey `json:"pub_key"`
VotingPower int64 `json:"voting_power"`

Accum int64 `json:"accum"`
}

出块人的顺序与验证人的Accum参数相关,谁的Accum大,谁先出块,而Accum的值与VotingPower(投票力)又紧密相连。
在节点运行起来之前,会进行初始化,初始化的时候每个验证人的Accum与验证人的VotingPower一样。0高度第一轮的出块人是Accum值最大的那个验证人。
Accum每轮都会进行改变,每轮的出块人也会改变。
选出来了一组validator节点后,全网所有validator节点都会存一份,比如放在一个循环数组里。
一般一个区块大部分情况下只需要一轮(round)就能产生,网络不好的时候可能要多轮才能出一个块。无论如何,每一轮都会有一个新的validator作为proposer, 轮换规则就是很简单的依次递增,第一轮,会选择数组中第0个validator作为proposer, 第二轮选择第1个validator,一次类推,到达最后一个后,重置为0,这样无限循环。

然后开始共识算法,第0轮回选择位置为0的validator 作为proposer节点,第1轮选择位置为1的validator, 第2轮选择位置为2的validator作为proposer, 到达最后一个后在重置为0,无限循环。
这种round-robin 策略,能有效的略过超时的proposer节点。如果一个proposer节点挂了或者所在网络很差,大部分节点都不能按时收到一个新快,于是超时后每个验证节点会在本机构造出一个空块,并广播投票消息出去,经过pre-vote和pre-commit两轮投票之后,最后commit一个空块,等价于什么不做,高度不变,开始新一轮。由于每开始新一轮,都会按顺序换成下一个proposer,这样就自然跳过了挂掉的proposer节点,算法能自动进行下去。

模拟出块人顺序(假设两个节点都在高度0的位置开始运行)

  • 每轮验证人Accum值更新公式:(round代表跳跃的轮数,上面也说了,可以直接从第1轮跳到第3轮)
    Val.Accum = Val.Accum + Val.VotingPower * round

  • 被选为出块人之后,出块人的Accum值更新公式:
    Proposer.Accum = Proposer.Accum - ValSet.totalVotingPower

假设有验证人ValA,ValB,ValC,且
ValA.VotingPower = 1000

ValB.VotingPower = 2000

ValC.VotingPower = 3000

初始化验证人集合:

ValSet.Validators = {ValA,ValB,ValC}

ValSet.totalVotingPower = ValA.VotingPower + ValB.VotingPower + ValC.VotingPower = 6000

此时根据每个验证人的Accum值将ValSet.Validators里面的所有验证人插入到优先级队列中,

顺序为ValC > ValB > ValA,取出队列中的第一个元素,即ValC,它就是本轮的出块人。那么此时:

ValSet.Proposer = ValC

ValC.Accum = ValC.Accum - ValSet.totalVotingPower = 3000 - 6000 = -3000

注:这些初始化动作是在节点运行起来之前完成的。

在0高度出块过程中始终不变的值是:

ValA.VotingPower = 1000

ValB.VotingPower = 2000

ValC.VotingPower = 3000

ValSet.Validators = {ValA,ValB,ValC}

ValSet.totalVotingPower = 6000

假设0高度出块需要三轮才能成功完成。

节点N出块人顺序

在第一轮各值分别为:

ValSet.ProPoser = ValC,即此时验证人是ValC。

ValA.Accum = 1000

ValB.Accum = 2000

ValC.Accum = -3000

这一轮由ValC进行出块。如果节点N就是验证人C,那么该节点从自己的内存池开始打包交易,进行proposal,如果不是,那么节点N等着就行。假设这一轮出块失败(没有在规定时间内收到proposal,或者没有在规定时间内收集齐 +2/3 的prevote票或precommit票),开始进行第二轮出块。

从第一轮跳到第二轮,跳跃轮数为1,即 round= 2-1 = 1

此时更新验证人的Accum值:

ValA.Accum = ValA.Accum + ValA.VotingPower*round = 1000 + 1000*1 = 2000

ValB.Accum = ValB.Accum + ValB.VotingPower*round = 2000 + 2000*1 = 4000

ValC.Accum = ValC.Accum + ValC.VotingPower*round = -3000 + 3000*1 = 0

此时根据每个验证人的Accum值将ValSet.Validators里面的所有验证人插入到优先级队列中,

顺序为ValB > ValA > ValC,跳了一轮,所以选择队列中第一个元素,即ValB,它就是本轮的出块人。

那么此时:

ValSet.Proposer = ValB

ValB.Accum = ValB.Accum - ValSet.totalVotingPower = 4000 - 6000 = -2000

这一轮由ValB进行出块。如果节点N就是验证人B,那么该节点从自己的内存池开始打包交易,进行proposal,如果不是,那么节点N等着就行。假设这一轮出块失败(没有在规定时间内收到proposal,或者没有在规定时间内收集齐 +2/3 的prevote票或precommit票),开始进行第三轮出块。

从第二轮跳到第三轮,跳跃轮数为1,即round = 3-2 = 1

此时更新验证人的Accum值:

ValA.Accum = ValA.Accum + ValA.VotingPower*round = 2000 + 1000*1 = 3000

ValB.Accum = ValB.Accum + ValB.VotingPower*round = -2000 + 2000*1 = 0

ValC.Accum = ValC.Accum + ValC.VotingPower*round = 0 + 3000*1 = 3000

此时根据每个验证人的Accum值将ValSet.Validators里面的所有验证人插入到优先级队列中,

顺序为ValA > ValC > ValB ,跳了一轮,所以选择队列中第一个元素,即ValA,它就是本轮的出块人。

那么此时:

ValSet.Proposer = ValA

ValA.Accum = ValA.Accum - ValSet.totalVotingPower = 3000 - 6000 = -3000

【A与C的Accum值一样,但是为什么A会在前面?这个跟优先队列数据结构有关,首先A压入队列中,然后B压入队列,但是B比A要小,那么B加入队列后面,再将C压入队列中,C与A相等,也会往队列后面添加,如果压入的值要大,那么就会往队列前面加,其他数据往后移动。】

这一轮由ValA进行出块。如果节点N就是验证人A,那么该节点开始从自己的内存池开始打包交易,进行proposal,如果不是,那么节点N等着就行。假设这轮出块成功,成功的收集到了足够多的票数,那么下个步骤就是commit,将块添加到区块上。添加完成之后,会更新共识状态,并更新所有验证人信息,假设此时加入了一个新的验证人ValD,其中ValD.VotingPower = 2000。那么更新信息如下:

现在更新的验证人信息用于下一个高度出块,round = 1(从一个高度调到下一个高度)

ValA.Accum = ValA.Accum + ValA.VotingPower * round = -3000 + 1000 * 1 = -2000

ValB.Accum = ValB.Accum + ValB.VotingPower * round = 0 + 2000 * 1 = 2000

ValC.Accum = ValC.Accum + ValC.VotingPower * round = 3000 + 3000 * 1 = 6000

ValD.Accum = ValD.Accum + ValD.VotingPower * round = 0 + 2000 * 1 = 2000

此时根据每个验证人的Accum值将ValSet.Validators里面的所有验证人插入到优先级队列中,

顺序为ValC > ValB > ValA > ValD,取出队列中的第一个元素,即ValC,它就是下以高度的出块人。

那么此时:

ValSet.totalVotingPower = ValSet.totalVotingPower + ValD.VotingPower = 6000 + 2000 = 8000

ValSet.Proposer = ValC

ValC.Accum = ValC.Accum - ValSet.totalVotingPower = 6000 - 8000 = -2000

以此一直循环下去,节点N就包含了从一个高度出块成功到下个高度出块,包括其中投票力改变的情况下,所有出块人的顺序。

节点M出块人顺序
节点M与节点N一样,在高度0的位置开始出块,那么第一轮的值都是相同的。

在第一轮各值分别为:

ValSet.ProPoser = ValC,即此时验证人是ValC。

ValA.Accum = 1000

ValB.Accum = 2000

ValC.Accum = -3000

这一轮由ValC进行出块。如果节点M就是验证人C,那么该节点开始从自己的内存池开始打包交易,进行proposal,如果不是,那么节点M等着就行。此时节点M记录的轮数为1。假设在等待期间,接收到节点N第三轮的prevote信息,节点M发现自己处理落后,第1轮和第2轮投票都已经失败,那么直接调到第三轮进行处理。

从第一轮跳到第三轮,跳跃轮数为round = 3-1 = 2

此时更新验证人的Accum值:

ValA.Accum = ValA.Accum + ValA.VotingPower*round = 1000 + 1000*2 = 3000

ValB.Accum = ValB.Accum + ValB.VotingPower*round = 2000 + 2000*2 = 6000

ValC.Accum = ValC.Accum + ValC.VotingPower*round = -3000 + 3000*2 = 3000

此时根据每个验证人的Accum值将ValSet.Validators里面的所有验证人插入到优先级队列中,

顺序为ValB > ValA > ValC ,因为这次跳跃了2次,那么会选择优先队列的第二个人为出块人。

ValSet.Proposer = ValA

ValB.Accum = ValB.Accum - ValSet.totalVotingPower = 6000 - 6000 = 0

ValA.Accum = ValA.Accum - ValSet.totalVotingPower = 3000 - 6000 = -3000

跳入到第三轮之后,如上述更新每个验证人的相关信息,然后判断收到的pre-vote信息中的块是否已经收集到 +2/3 的pre-vote,如果已经收集到了,那么可以直接进入第3步骤,进行pre-commit投票,如果还没有收集到足够的pre-vote,那么进入第2步骤,进行pre-vote投票。

这里假设第三轮出块成功,剩下的与节点N步骤会一致。

出块人的顺序是一定的,每个节点同一高度同一轮的出块人都是同一个人。根据上面的模拟可以发现,投票力越大,随着循环,它的出块次数会比投票力小的出块人次数要多,因为它的Accum会增加的很快。
还有一点上文中未提到,就是在收集到 + 2/3 的pre-vote票之后,节点会锁定在这个块,这是为了防止给多个块投票,到了pre-commit之后,只能给锁定的块进行pre-commit块进行投票。如果在需要多轮才能成功的出块的情况下,那么收集到下一轮的拥有 +2/3 的pre-vote的块之后,会将上一轮进行解锁,会锁定在下一轮的块中。

Tendermint与PBFT比较

Tendermint和PBFT看起来非常类似,例如:

  • 都属于BFT类型的算法,最多容忍不超过1/3的恶意节点

  • 都是三阶段提交,Tendermint的propose->pre-vote->pre-commit三个阶段,跟PBFT的三个阶段,pre-prepare->prepare->commit三阶段是一一对应的

  • 都在超时的时候,换掉proposer/primary

不过,Tendermint相对于PBFT有简化。

Tendermint没有PBFT那种ViewChange阶段,Tendermint很巧妙的把超时的情况,跟普通情况融合成了统一的形式,都是 propose->pre-vote->pre-commit 三阶段,只是超时的时候新块是一个特殊的空块。切换proposer是通过提交commit空块来触发的,而PBFT是有一个单独的view change过程来触发primary轮换。