区块链新型共识算法：Snowflake to Avalanche

介绍

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

算法流程

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

这里先介绍一下算法的流程，理解了算法流程之后，再来阐述该算法的安全性证明 (Proof of Safty) 和活性证明 (Proof of Liveness)。

下面这张图是 tendermint 状态转换图

算法主要有 NewHeigh -> Propose -> Prevote -> Precommit -> Commit 一共 5 个状态（阶段）。

上述每个状态都被称为一个 Step，首尾的 NewHeigh 和 Commit 这两个 Steps 被称为特殊的 Step，而中间加粗体的三个 Steps 则被称为一个 Round，是共识阶段，也是也是算法的核心原理所在。

需要注意的是，一个块的最终提交（Commit）可能需要多个 Round 过程，这是因为有许多原因可能会导致当前 Round 不成功（比如出块节点 Offline，提出的块是无效块，收到的 Prevote 或者 Precommit 票数不够 +2/3 等等），出现这些情况的话，解决方案就是移步到下一轮，或者增加 timeout 时间）。

这里，还要介绍一个重要概念：PoLC，全称为 Proof of Lock Change，表示在某个特定的高度和轮数(height, round)，对某个块或 nil (空块)超过总结点 2/3 的 Prevote 投票集合，简单来说 PoLC 就是 Prevote 的投票集。

Tendermint 中有两种类型的节点，Validator 节点和 Non-Validator 节点，顾名思义，只有 Validator 节点会参与共识投票，而普通节点作为 Non-Validator 节点，不参与共识投票，只协助传递状态或向 Validator 节点发送交易请求。

初始状态下（创世块），高度为 0， 此时，系统会基于 Round Robin 原则来选出一个 Validator（每个 Validator 都有一定的 Voting Power），由这个 Validator 打包一个新的 Block， 并向所有节点发出 Proposal，剩余的 Validator 节点对该 Proposal 进行投票，最终达成共识。

以下，分阶段来阐述各个阶段:

1. NewHeight

当上一轮 Commit 结束，就会出现新高度，这是就需要进入下一轮共识了，也就是说，这就是新一轮共识过程的开始，这时候需要选出一个 Proposer。选择算法是 Round Robin，基于他们的 Voting Power（上一轮的选中的 Validator 节点会把其 Voting Power 值减去 Total Voting Power，也就是说上一轮的 Validator 在这一轮，其 Voting Power 会变成负数）。

2. Propose

在 Propose 节点开始的时候，该轮指定的 proposer 需要通过 gossip 广播一条 proposal 到所有的 peers。如果此时这个 proposer 被锁在上一轮的某个 block 上，那么它就直接 propose 那个 block，同时包含一条 proof of lock 的信息。

3. Prevote

Validator 节点收到 propose 信息之后就进入 Prevote 投票阶段。投票时，如果 Validator 被锁在之前一个 block 上，那么还是给之前那个 block 投 prevote 票，否则就投当前的 block。同时，它会继续收集对这个 block 的 prevote 投票，等轮到他 propose 的时候打包进 PoLC。

注意：
如果自己有 Lock-Block，这时又收到一个新的针对另外一个块的 PoLC，并且满足LastLockRound < PoLC-Round < 当前 Round，则解锁 Lock-Block。

如果 timeout 期间没收到 proposal，或则收到的 proposal 是无效的，那么就投 nil 票。
在 Prevote 阶段不会锁住任何 block。

4. Precommit

Prevote 超时或则收到的 Prevote 或 nil 票超过 2/3 时，就进入 Precommit 阶段。
如果此时收到了 +2/3 的 prevote 投票，就广播一条 precommit 投票，同时，把自己锁在当前的 block 上（把之前的都释放掉）。一个节点一次只能锁在一个块上。
如果收到 +2/3 的 nil 投票，那么就释放锁。

当一个节点锁在一个 block 上的时候（有 PoLC），它会将 LastLockRound 置为当前 Round，并对这个块投 Precommit 票。

如果有针对 nil 票的 PoLC，则解锁并且对 nil 投 Precommit 票；否则的话保持 Lock-Block 不变，并投 nil 。

如果在 timeout 期间内，没有收到对某个块的足够的 +2/3 投票（prevote 或者 nil 都行），那么就什么也不干。

最终，如果一个节点收到了 +2/3 的 precommit 投票，就进入 Commit 阶段。否则，继续进入下一轮的 Propose 阶段。

5. Commit

Commit 阶段是一个特殊阶段，有两个并行的条件必须满足：

1. 节点必须收到该 block
2. 节点必须等待，直到收到 2/3 的 节点 commit 信息。

At any time during the consensus process if a node receives more than 2/3 of commits for a particular block, it immediately enters the Commit step if it hadn’t already. Thus there are two ways to enter the Commit step. A commit-vote for a block at round R counts as prevotes and precommits for all rounds R0 where R < R0 . Commit-votes are gossipped to neighboring peers in the background re-gardless of the current round or step。

At any time during the consensus process if a node is locked on a block from round R but receives a proof-of-lock for a round R0 where R < R0 , the node unlocks.

证明

1. 安全性证明

Tendermint 的安全性就是说，在对高度为 H 的块达成共识之后，不可能会出现新的高度为 H 的块，也就是说 Tendermint 保证不会分叉，保证不会分叉的主要角色就是 Lock-Block。

先看下wiki对于安全性证明的描述：

Assume that at most -1/3 of the voting power of validators is byzantine. If a validator commits block B at
round R, it’s because it saw +2/3 of precommits at round R. This implies that 1/3+ of honest nodes are still
locked at round R’ > R. These locked validators will remain locked until they see a PoLC at R’ > R, but this
won’t happen because 1/3+ are locked and honest, so at most -2/3 are available to vote for anything other
than B.

翻译：

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

下面给出较为详细的证明过程，假设高度为 H 的块 b 在第 R 轮达成共识。给出如下条件：

• x 表示在第 R 轮已经 Commit 的节点，均为诚实节点，x < 1/3。
• y 表示拜占庭节点，可以做任意事情，y < 1/3。
• z 表示剩余节点，z > 1/3，因为已经有 x 个节点 Commit，则肯定有 z0 个节点对 b 投了 precommit 票，z0 < z。

需要证明，当 x 个节点 commit 之后，剩余(也就是 y + z)的没有 Commit 块 b 的节点不会对另外一个块达成共识。

也就是说需要证明：y + z - z0 < 2/3，假设所有的拜占庭节点都对 b 投了 Precommit，则满足：x + y + z0 > 2/3。

简而言之，要从 x + y + z0 > 2/3 证明 y + z - z0 < 2/3。

我们通过反证法来证明：
假设 y + z - z0 > 2/3，也就是在第 r 轮之后有可能造成分叉，则：
x + y + z - z0 > 2/3 + x => 1 - z0 > 2/3 + x => x + z0 < 1/3。

而上面我们提到了，因为x节点已经 Commit 块 b，则 x + y + z0 > 2/3，且 y < 1/3，则说明 x + z0 必须大于1/3。由此证明，y + z - z0 < 1/3 成立，在第 R 轮之后无法对另一个块达成共识，也就不可能出现分叉。

活性证明

活性证明相对来说就要简单一些，假设多于 1/3 的节点分别 Lock 在不同的块上，则在 Prevote 阶段的条件保证最终 round 较小的会 unlock，而且 proposal 的超时时间会随着轮数的提高而提高。

其他

在证明安全性的过程中提到，有可能会有部分节点由于没有收到足够的 Precommit 投票导致无法 commit，这个时候可以通过同步来使各个节点的状态尽量保持一致，在wiki中提到一个 JSet 和 VSet 的概念，当节点已经 commit 时，就可以广播一条消息携带 VSet 给其他节点，其他节点验证对于块的 commit 是否有效。这一点其实和 bft-raft （另外一个拜占庭容错算法，Raft 算法的变种）的做法类似。

全文完！

如果你对我的文章感兴趣，欢迎留言或者关注我的专栏。

微信公众号：“知辉”

搜索“deliverit”或

扫描二维码