Tendermint共识算法的个人见解

前置知识

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

Tendermint 概括：

Tendermint算法给每个区块赋予一个增量索引或者高度（height），在某一高度中只存在一个有效的区块，区块链从高度为0的创世纪块开始，由一个验证者集合投票产生下一个区块，其中每一个验证者由各自的公钥标识。每一个验证者需要维护一份完整的复制状态的拷贝。每一轮都会通过round robin的方法产生一个提议者（proposer），该提议者在当轮以广播的形式提出一个提议（proposal），提议经过验证者的集体投票，来决定是否最终提交该区块或者进入下一轮次(Round)。在提议的区块真正被提交（commit）之前，验证者们需要进行两轮投票（pre-vote & pre-commit）, 通过一个简单的锁机制用来阻止少于总数1/3的拜占庭节点攻击。由于Tendermint网络的不同时性（asynchrony），当拜占庭节点超过总数的1/3，网络存在瘫痪的可能性。

注意：tendermint的多轮投票机制的核心是共识算法。每一个区块包含一些元数据（metadata），称作区块头（header）。区块头里包含本区块的高度，提议时间，本区块所有交易的梅克尔根哈希值。一个块的最终提交（Commit）可能需要多个Round过程，这是因为有许多原因可能会导致当前Round不成功（比如出块节点Offline，提出的块是无效块，收到的Prevote或者Precommit票数不够 +2/3 等等），出现这些情况的话，解决方案就是移步到下一轮，或者增加 timeout 时间），Round类似但不同于View，新的Round会置为0。

共识流程：

共识算法可以大致分为以下几部分：

•提议（Proposals）：在每一轮（round）中，新区块的提议者必须是有效的，并且告诉（gossiped）其他验证者。如果在一定时间内没有收到当轮提议（proposal），当前提议者将被后面的提议者接替。

•投票（Votes）：两阶段的投票基于优化的拜占庭容错。它们分别被称作预投票（pre-vote）和预提交（pre-commit）。对于同一个区块同一轮如果存在超过2/3的预提交（pre-commit）则对应产生一个提交(commit)。
• 锁(Locks)：在拜占庭节点数少于节点总数的1/3的情况下，Tendermint中的锁机制可以确保没有两个验证者在同一高度提交（commit）了两个不同的区块。锁机制确保了在当前高度验证者的下一轮预投票或者预提交依赖于这一轮的预投票或者预提交。

与其他选举（leader election ）算法不同，Tendermint每一轮都会产生一个新的提议者(proposer)，验证者投票决定是否进入下一轮，这与接受提议的流程类似。
每轮的开始对同步有弱的依赖性。每一轮开始期间，存在一个用来计时的本地同步时钟，如果验证者在TimeoutPropose时间内没有收到提议，会立刻在本机生成一个特殊结构的空块，假装这个空块是从Proposer节点那里收到的，这样，无论如何，在时间T内，都会收到一个proposal区块，要么是一个正常块要么是一个空块。然后接着对这个块进行pre-vote投票和pre-commit投票。如果proposer挂了，绝大部分validator看到的都是一个空块，因此空块会获得多数投票，进入commit阶段。commit空块的时候，不会真的往区块链写入一个空块，而是什么都不写，区块高度不自增，保持不变，这样相当于什么也没有干，这一轮(round)是在空转。下一轮开始的时候会换下一个validator当proposer，这样当前那个挂掉的proposer，就不会卡住整个网络。

每轮收到提议以后，进入完全异步模式。之后验证者的每一个网络决定需要得到2/3验证者以上的同意。这样降低了对同步时钟的依赖或者网络的延迟。但是这也意味着如果得不到1/3以上验证者的响应，整个网络将瘫痪。Tendermint在Liveness方面有所妥协，换取了更强的Finality。
简言之，每轮开始提议弱同步，之后投票完全异步。

一、提议

每轮开始于一个提议（proposal），提议者从内存池（Mempool）选取一批交易进而构成了一个区块，该区块随后被嵌套在ProposalMsg中，最后提议者广播（broadcast）ProposalMsg。如果这个提议者是拜占庭节点，他可能向不同的验证者广播不同的ProposalMsg。

提议者通过一个简单并且相对固定的的round robin轮流坐庄，所以每一轮只有一个有效且被所有验证者公认的提议者。如果验证者收到了之前更低轮次的提议或者提议来自于非法的提议者，该提议将被拒绝。

Tendermint通过投票和锁的机制（voting and locking mechanisms）确保了系统的安全性。如果一个提议者在限定时间内没有处理任何交易，排在其后的提议者将会接替他。如果proposer锁定在上一轮中的block上，那么proposer在本轮中发起的proposal会是锁定的block，并且在proposal中加上proof-of-lock字段。

proposal的数据结构如下：

二、投票 prevote

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

Precommit

在precommit开始阶段，每个Validator会判断，如果收集到了超过2/3
prevote投票，那么为这个区块签名并广播precommit投票，并且当前Validator会锁定在这个区块上，同时释放之前锁定的区块，一个Validator一次只能锁定在一个区块上。在任意一轮中，区块具有的超过2/3的预投票被称作一个波尔卡（polka）。超过2/3的空预投票成为空波尔卡（nil-polka）。**如果一个Validator收集到超过2/3空区块（nil)的prevote投票，那么释放之前锁定的区块。处于锁定状态的Validator会为锁定的区块收集prevote投票，并把这些投票打成包放入proof-of-lock中，proof-of-lock会在之后的propose阶段用到。如果一个Validator没有收集到超过2/3的prevote投票，那么它不会锁定在任何区块上。在precommit阶段后期，如果Validator收集到超过2/3的precommit投票，那么Validator进入到commit阶段。否则进入下一轮的propose阶段。

注意：在存在拜占庭节点的异步环境中，单阶投票，即每个验证者对每个提议只投一次，不能足以确保整个系统的安全。一个单阶的投票允许验证者互相沟通他们知道的关于该提议的信息。但是为了容忍拜占庭故障，他们也需要互相告诉对方他们自己了解到的其他验证者声称了解到的关于该提交的信息。换句话说，二阶段提交确保了足够的验证者见证了第一阶段的结果。

三、锁

多轮投票的安全问题是棘手的，必须避免同一高度不同轮数分别提交两个不同区块的情形。在Tendermint中，这个问题可以通过锁机制（locking mechanism）得到解决。

锁定规则：

·
预投票锁（Prevote-the-Lock）：验证者只能预投票(pre-vote)他们被锁定的区块。这样就阻止验证者在上一轮中预提交(pre-commit)一个区块，之后又预投票了下一轮的另一个区块。

· 波尔卡解锁（Unlock-on-Polka
）：验证者只有在看到更高一轮（相对于其当前被锁定区块的轮数）的波尔卡之后才能释放该锁。这样就允许验证者解锁，如果他们预提交了某个区块，但是这个区块网络的剩余节点不想提交，这样就保护了整个网络的运转，并且这样做并没有损害网络安全性。

安全性证明：

假定有最多小于总结点 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 投票。

举例：

举例1：考虑4个验证者，A,B,C,D,假设有一个第R轮关于blockX的提议。现在假设blockX已经有一个波尔卡，但是A看不见它，预提交（pre-commit）为空，然而其他人对blockX进行了预提交。进一步假设只有D看见了所有的预提交，然而其他人并没有看见D的预提交（他们只看见他们的预提交和A的空预提交）。D现在将要提交（commit）这个区块，然而其他人进入到R+1轮。由于任何验证者都可能是新的提议者，如果他们提议并投票了一个新的区块blockY，他们可能提交这个区块。可是D已经提交了bockX，因此损害了系统的安全性。注意，这里并没有任何拜占庭行为，仅仅是不同时性。锁定解决了这个问题通过强迫验证者粘附在他们预提交（pre-commit）的区块，比如新的一轮如果B或者C提议者，他们不会提出新的区块blockY，而是提出上一轮自己已经锁定的区块blockX。因为其他的验证者可能居于这个预提交进行了提交（如上例中的D）。本质上，在任何一个节点一旦存在超过2/3预提交（pre-commit），整个网络被锁定在这个区块上，也就是说在下一轮中无法产生一个不同块的波尔卡。这是预投票锁的直接动机。

举例2：当然这里必须有相应的解锁方式。假设在某一轮中，A和B预提交（pre-commit）了blockX，与此同时C和D的预提交为空。因此所有的验证者进入到下一轮，预提议(pre-vote）blockY。假设A是拜占庭，为blockY也进行了预投票（不考虑其被锁在blockX上），导致了一个波尔卡。假设B并没有看见这个波尔卡，预提交为空，此时A下线，C，D预提交bolckY。他们进入到下一轮，但是B仍然被锁定在blockX上，C和D被锁定在blockY上。这时因为A下线了，他们将永远得不到一个波尔卡。因此即使在拜占庭节点少于1/3的情况下，这里网络的正常运转仍然受到了影响。解锁的条件是1个波尔卡。一旦B看见了blockY的波尔卡（用来为C和D的关于blockY的预提交背书），他应当能够解锁并预提交（pre-commit）blockY。这是波尔卡解锁的动机，其允许验证者在看见更高轮数波尔卡的时候解锁并且提交对应的新区块。

tendermint和传统PBFT的比较

1 优势:
• 用锁的机制代替了PBFT中复杂的viewChange，但是丧失了响应性；
• 工程化成功，可直接基于其开源的框架搭建一条链；
• 联盟链和公有链均可用；
2 不足:
• 丧失响应性：没有“显式”地将polka状态的proposals传到下一个round；
• Safety和Liveness耦合：加锁、解锁机制耦合在一起；

参考：
https://zhuanlan.zhihu.com/p/84962224
中文文档：https://learnblockchain.cn/docs/tendermint/
https://blog.csdn.net/Quilan/article/details/109000255
https://blog.csdn.net/boke14122621/article/details/99291878