0%

深入Tendermint---共识算法

分布式一致性算法一般可以分为两类:拜占庭容错和非拜占庭容错。非拜占庭容错算法如 Paxos, Raft 等在当前的分布式系统中已经广泛使用,而拜占庭容错算法的实际应用范围相对来说小很多(特别是在区块链问世之前)。Tendermint 属于拜占庭容错算法,它针对传统的PBFT算法做了优化,只需要有两轮投票即可达成共识,目前Tendermint算法主要应用在区块链系统中,这篇文章就从原理上来介绍 Tendermint的共识机制。

Round-based协议

在Tendermint中一共有三种类型的投票:prevote,precommit和commit。当一个block被全网络commit的话,意味着这个block已经被全网超过2/3的Validator签名并广播了。

vote数据结构如下:

vote

在链达到一个新的Height时候,系统会运行一个round-based协议来决定下一个block。round-based协议由以下三个步骤构成:proposal,prevote,precommit。以及两个特殊步骤:commit,NewHeight。其中propose,prevote和precommit会分别占用整个round 1/3时间。每一round的时间会比上一round的时间长一点,这是为了让网络在部分同步的情况下最终达成一致性共识。

round-based协议运行过程如下:

round

round-based协议是一个状态机,主要有 NewHeigh -> Propose -> Prevote -> Precommit -> Commit 一共 5 个状态。上述每个状态都被称为一个Step,首尾的 NewHeigh和Commit这两个Steps被称为特殊的 Step,而中间循环三个Steps 则被称为一个 Round,是共识阶段,也是也是算法的核心原理所在。一个块的最终提交(Commit)可能需要多个Round过程,这是因为有许多原因可能会导致当前Round不成功(比如出块节点Offline,提出的块是无效块,收到的Prevote或者Precommit票数不够 +2/3 等等),出现这些情况的话,解决方案就是移步到下一轮,或者增加 timeout 时间)。

当区块链达到一个新的高度时进入NewHeight阶段,接下来Propose阶段会提交一个proposal,prevote阶段会对收到的proposal进行prevote投票,在precommit阶段收集到+2/3prevote投票后对block进行precommit投票,如果收集到+2/3precommit投票后进入commit阶段,如果没有收集到+2/3precommit投票会进入再次进入propose阶段。在共识阶段期间如果收到+2/3commit投票那么直接进入commit阶段。

以上就是算法运行的整体过程,接下来分阶段来阐述各个阶段。

Proposal

在每一轮开始前会通过round-robin方式选出一个proposer,选出的proposal会提交这一轮的proposal。proposer的选择规则请查看之前的一篇文章出块节点选择

proposal的数据结构如下:

round

Round-based协议的第一个步骤是Propose,在propose开始阶段,被选中的proposer会给全网络广播一个proposal。如果proposer锁定在上一轮中的block上,那么proposer在本轮中发起的proposal会是锁定的block,并且在proposal中加上proof-of-lock字段。

prevote

在Prevote开始阶段,每个Validator会判断自己是否锁定在上一轮的proposed区块上,如果锁定在之前的proposal区块中,那么在本轮中继续为之前锁定的proposal区块签名并广播prevote投票。否则为当前轮中接收到的proposal区块签名并广播prevote投票。如果由于某些原因当前Validator并没有收到任何proposal区块,那么签名并广播一个空的prevote投票。

Precommit

在precommit开始阶段,每个Validator会判断,如果收集到了超过2/3 prevote投票,那么为这个区块签名并广播precommit投票,并且当前Validator会锁定在这个区块上,同时释放之前锁定的区块,一个Validator一次只能锁定在一个区块上。如果一个Validator收集到超过2/3空区块(nil)的prevote投票,那么释放之前锁定的区块。处于锁定状态的Validator会为锁定的区块收集prevote投票,并把这些投票打成包放入proof-of-lock中,proof-of-lock会在之后的propose阶段用到。如果一个Validator没有收集到超过2/3的prevote投票,那么它不会锁定在任何区块上。这里,介绍一个重要概念:PoLC,全称为 Proof of Lock Change,表示在某个特定的高度和轮数(height, round),对某个块或 nil (空块)超过总结点 2/3 的Prevote投票集合,简单来说 PoLC 就是 Prevote 的投票集。

在precommit阶段后期,如果Validator收集到超过2/3的precommit投票,那么Validator进入到commit阶段。否则进入下一轮的propose阶段。

Commit

commit阶段分为两个并行的步骤: 1. Validator收到了被全网commit的区块,Validator会为这个区块广播一个commit投票。 2. Validator需要为被全网络precommit的区块,收集到超过2/3commit投票。

一旦两个条件全部满足了,节点会将commitTime设置到当前时间上,并且会进入NewHeight阶段。

在整个共识过程的任何阶段,一旦节点收到超过2/3commit投票,那么它会立刻进入到commit阶段。

为什么不会分叉

如果小于1/3节点是拜占庭节点(如果大于等于1/3,那么共识就没法达成了)。当validator commit了区块B,那么表示有大于2/3的节点在R轮投了precommit,这表示至少有大于1/3节点(大于1/3节点哪儿来的呢,就是大于2/3减去小于1/3,为什么是这么算呢,有人说不是有大于2/3的节点投了precommit那么这些人不都是诚实节点吗,当然不是了,拜占庭节点的意思它工作随性,有时候正确有时候失败,假设这个时候所有的拜占庭节点正确的工作了,所以都算在在+2/3节点内,所以这么算了)被lock在了R‘>R。如果这个时候有针对同一区块高度的投票,那么由于这+1/3节点被lock在了R’轮,所以不会有+2/3的节点投prevote,也就不会在同一高度达成一个新的共识区块,所以就不会分叉。

所以Tendermint不分叉是基于它是BFT共识,然后加上LockedBlock共同完成。