从零开始设计一个共识算法——一场没有硝烟的战争

目录

1. 拜占庭容错算法

1.1 前言

1.2 概念澄清

1.3 假设

1.4 安全性

1.5 活性

2. 隐藏锁问题

2.1 收集锁

2.2 广播所有锁

2.3 引入固定时延

2.4 增加一个阶段

2.5 方案总结

3. 现有算法对比

3.1 PBFT

3.2 Tendermint

3.3 Hotstuff

4. 总结

5. 附录

5.1 情况分析

5.2 隐藏锁问题

参考文献

1. 拜占庭容错算法

1.1 前言

在本文中，我们尝试从零开始设计一个拜占庭容错的共识算法。但由于本文是在阅读大量文献之后，思考整理得出的，难免会有“事后诸葛亮”的嫌疑，但这不要紧，我们的目的也不是真的为了设计一个全新的共识算法，而是站在设计者的角度，思考一个共识算法是如何一步步得出的。当然，在推理过程中，我们也会使用尽可能少的已知条件，让“从零开始”不那么“哗众取宠”。相信本文会让你对共识算法有一个较为全面的理解，以后如果遇到新的共识算法，也可以使用本文的思路分析，快速拿下。

1.2 概念澄清

在开始之前，我们先理清一些基本概念。

分布式一致性算法（共识算法）：使集群中多个节点保持数据状态一致的通信算法。

拜占庭错误：节点除了宕机（不发送消息），还可能出现随机的恶意行为（发送假消息）。

拜占庭容错算法：能够容忍拜占庭错误的共识算法。设集群中拜占庭节点（错误节点）数为 f，当总结点数 N < 3f 1 时，不存在一个拜占庭容错算法。即总节点的最小数量为 3f 1，本文我们使用这个数量作为总节点的数量。

共识算法的正确性可以分为以下两个性质：

1. 安全性 (safety)，也叫一致性 (agreement)，表示 所有正确节点执行的请求（包括顺序）一致。
2. 活性 (liveness)，也叫可终止性 (termination)，表示 共识总能在有限时间内达成。

换句话说，如果没有安全性，不同节点就可能执行了不同请求，使系统失去了一致性，这是不可容忍的；如果没有活性，那么系统会永远“卡住”，无法处理请求。下面我们从这两个特性出发，尝试站在设计者的角度看一个拜占庭容错的共识算法是如何诞生的。

1.3 假设

为了让算法在可证明正确性的同时可被实际应用，我们需要在特定的网络下设计算法。存在以下几个网络模型：

1. 同步（asynchrony）：网络延迟存在一个已知的固定上限 Δ。即消息总能在 Δ 时间内传输到目标节点。
2. 异步（synchrony）：网络延迟不存在固定上限 Δ。即消息不一定能在固定时间内传输到目标节点。
3. 部分同步（partially synchrony）：网络延迟固定上限 Δ 已知，但仅在一个未知的时间 GST（global stabilization time） 后成立。也就是在 GST 之后，网络为同步网络。当然，同步网络不会永远保持，只会保持一定时间，所以部分同步可以看成是异步网络和同步网络交替进行的网络模型。

实际的网络可能存在丢包、分区等情况，所以不是一个同步的网络；而在异步网络下，无法保证活性；部分同步网络最符合实际，因此我们算法的设计将会基于这个假设。

我们需要设计一个这样的共识算法：即使是在异步网络下，也要保证安全性；在同步网络下，保证活性。这样，在部分同步网络下，就能保证算法的安全性和活性。

分布式一致性算法早在上个世纪就被广泛研究，但随着区块链的兴起，再次进入人们的视野。为了方便讨论，同时使共识算法更贴近于区块链的场景，我们把算法的一些参数对应到区块链中，把“请求”称为“区块”，请求的执行顺序称为“高度”，区块按照高度顺序串联起来就成了区块链。但请记住，共识算法并不关心请求是什么，不同系统可以有不同的请求结构。

同时，我们假设共识为单线程的，即只有完成上一个区块的共识，才能开始下一个区块的共识。并且我们假设存在某个机制，当节点发现自身区块落后于其他节点时，会自动从其他节点同步，本文不对这个机制做具体描述，并简单使用“快速恢复机制”来指代这个过程。

1.4 安全性

如何共识？

系统如何对一个高度的区块达成共识呢？这可以类比一个民主的组织如何达成一个决策，往往会有一个提案者（proposer，为了便于讨论，我们暂且称为 leader）提出一个方案，其他成员进行投票表决。对应到共识算法中，我们需要选出一个 leader，对于某个高度，（收集交易并）组装区块（这个过程我们简称为“出块”，组装好的含高度的区块我们称为“提案”）并广播，其它节点收到的提案后广播投票，收集其他节点的投票，当收集到足够多的相同投票时，确定该提案。

收集多少投票？

由于有 f 个拜占庭可能不投票，所以收集到 2f 1 个投票就该停止，否则系统将失去活性。由此我们给节点引入一个行为：

行为1：节点收集到 2f 1 个相同投票（含提案）时，提交该提案，执行区块并存储，最后向客户端响应。

加锁

另外，由于 leader 可能为错误节点，可能故意向不同节点发送不同提案（同一高度的不同区块），所以为了保证安全性，正确节点只会对某个高度投一票，即当高度 H 已经给区块 A 投过票时，不会再对该高度的其他区块投票，我们称这个行为为“加锁”，并且说节点对于高度 H “锁定”在了区块 A。

由此，我们引入第二个行为限制：

行为2：对于某个高度，正确节点发起或收到一个提案时，会锁定该区块，并坚持对已锁定的区块进行提案或投票，而会忽略该高度下的其他区块提案。

QC 性质

有了加锁机制之后，不同节点还有没有可能在同一高度提交不同区块呢？

稍加推理，我们会发现这是不可能的：假设在高度 H 上，节点 1 提交了区块 A，节点 2 提交了区块 B。那么说明有 2f 1 个节点对区块 A 投了票，有 2f 1 个节点对区块 B 投了票，由于总节点数为 3f 1，所以这两部分节点的交集为 (2f 1)*2 - (3f 1) = f 1，其中错误节点数为 f，所以交集一定有一个正确节点，这个节点对区块 A 和区块 B 都投了票，这与行为 2 产生了矛盾，所以假设不成立。

可见 2f 1 既是我们为了保证活性只能收集的最大数量，同时也是投票的最小数量（为了保证交集至少有一个正确节点），这个投票对应的节点集合称为 Quorum（委员会），投票集合称为 Quorum Certificate（委员会证书，简称 QC）。正如我们上面分析的，QC 具有一个非常重要的性质：任何两个 Quorum 至少有一个共同的正确节点。我们把这个性质称为 QC 性质。因为一个 Quorum 的节点数量为 2f 1，而错误节点数为 f，因此 Quorum 中至少有 f 1 个正确节点，所以 QC 性质也可以表述成 任何两个 f 1 个正确节点的集合至少有一个共同节点。关于 QC 性质的更多讨论，可以参考我的另一篇文章：深入理解PBFT算法——提交阶段的作用。

1.5 活性

上文我们讨论了安全性，接下来我们重点关注下活性。

视图切换

共识算法活性丢失的最直接来源是 leader 出错。当 leader 为错误节点时（宕机或发送任意消息等），可能完全不发提案，也可能给其他节点发送任意不同的提案，使得每个节点都无法收集够 2f 1 个正确投票，共识无法正常进行。所以当检测到 leader 为错误节点时，需要更换 leader，我们称 leader 的一个任期为视图（view），更换 leader 的过程为 “视图切换”，每个视图有一个唯一的编号，称为视图号，并且每次视图切换时视图号都递增 1。至此，提案除了高度和区块之外，还多了一个视图号。

那么如何检测 leader 出错呢？最简单的办法是设定超时时间，如果超过某个时间还没有对某个高度的提案达成共识，就认为 leader 为错误节点，触发视图切换。

如何选举下一任的 leader 呢？最简单的办法是轮流法，即当前 leader 节点编号 = 视图号%节点数。其中“%”表示取余。

视图切换成功之后，假如上一个视图的共识没有遗留，即所有节点处于一致状态，那么新 leader 可以重新发起提案，继续推动共识的进行。

由于我们是用超时来触发视图切换的，所以不能断定上一个 leader 为错误节点，同时也无法保证旧视图中的共识已经全部完成，可能存在部分节点已经提交了某个区块，但其他节点还没收到该区块的情况，此时新 leader 必须保证这些区块能被所有正确节点提交。下面我们列举下进入新视图时各种可能的异常情况，同时一起思考新 leader 应该如何处理这些异常。

1. 只有部分正确节点（大于等于 f 1）锁定了某个区块（该区块可能已被部分正确节点提交），其他正确节点未锁定任何区块。
2. 只有部分正确节点（小于 f 1）锁定了某个区块（该区块一定没有被任何节点提交），其他正确节点未锁定任何区块。
3. 正确节点锁定在了不同区块。

造成以上情况的原因是不难推测的，若有疑问可以参考附录的【情况分析】。在新视图中，我们来看看节点可以怎么做：

情况 1：假如新 leader 为正确节点，且在上一个视图中锁定该区块了，那么本次继续使用该区块发起提案，其他节点对该区块投票，可以正常达成共识。 假如新 leader 为错误节点（或者新 leader 为正确节点，但在上一个视图中没有锁定该区块），那么如果发起一个不同的提案，是不可能收集到足够投票的（行为 1 和行为 2 保证了安全性），并且可能使得其他节点锁定在这个区块，演变成了情况3；若没有使得其它节点锁定在不同区块，那么多次视图切换之后总能轮到锁定该区块的正确节点出块（活性）。

情况 2：假如新 leader 为正确节点，且在上一个视图中锁定该区块了，那么本次继续使用该区块发起提案，其他节点对该区块投票，可以正常达成共识。 假如新 leader 为错误节点（或者新 leader 为正确节点，但在上一个视图中没有锁定该区块），那么如果发起一个不同的提案，可能使得其他节点锁定在这个区块，演变成了情况3；若没有使得其它节点锁定在不同区块，那么多次视图切换之后总能轮到锁定该区块的正确节点出块。

情况 3：假如错误节点配合投票，且存在大于等于 f 1 的正确节点锁定在同一区块，轮到这里面的其中一个节点出块时，是可能达成共识的，但要想办法把其他锁解开，否则后续可能无法共识。如何说服节点解锁？道理很简单，就是给他们证据让他们相信该高度已有另一个区块提交了，可以放心解锁。最直接的证据就是 QC。由此，我们引入另一个行为限制：

行为3：leader 发起新提案时，携带本节点最近提交的提案的 QC，其他节点收到 QC 时会解锁在该高度下锁定的区块，并提交该 QC 对应的提案，继续新提案的共识。

假如此时发生了视图切换，新 leader 没有该高度的最新 QC，那么无法解锁其他节点，共识无法进行，但多轮视图切换之后总能轮到携带了最新 QC 的节点出块。

如果错误节点不配合投票，或者不存在大于等于 f 1 的正确节点锁定在同一区块，无论由谁发起提案，都是不可能收集到足够投票的，并且由于该高度下还没有形成一个 QC，后续也无法形成一个 QC，所以无法解锁，无法达成共识，我们称这种现象为“死锁”，死锁使得系统失去了活性。

死锁问题

为了避免死锁，我们要保证当一个新锁产生时，旧锁一定有机会能被解开。QC 解锁机制明显不具备这个特性，因为新旧锁的同时存在可能使得 QC 永远无法生成。

那么，如果新锁能解锁旧锁不就好了？如果要做到新锁能安全解锁旧锁，那么必须具备这样的特性：若新锁能够产生，那么旧锁对应的区块一定没有被提交，这样才能安全地解锁，换句话说，如果旧锁对应的区块被提交了，那么不可能产生新锁。

我们目前的机制明显无法做到这一点，因为加锁的动作是在收到区块时进行的，即使一个区块已经被提交了，该高度下仍然可能有另一个区块被提出来（可能是错误节点，也可能是正确节点没有锁定或提交那个区块）。简而言之，就是加锁的条件太宽松，所以我们可以尝试增加加锁的条件。一个比较直接的办法就是，在加锁前增加一轮投票（我们称为准备消息），收集到 2f 1 个准备消息时（我们称这个 QC 为“锁定 QC”，简称“QC 锁”），再进行加锁，加锁之后再进行第二轮投票（我们称为提交消息），收集第二轮的 QC（对应我们上面一直讨论的 QC，为了跟锁定 QC 区分，我们称这个 QC 为提交 QC）。至此，我们的行为 1 和行为 2 升级为：

行为1'：节点收集到提交 QC 时，提交该提案，执行区块并存储，最后向客户端响应。

行为2'：在一个视图中，对于某个高度，正确节点只会对一个区块发送准备消息，而会忽略该高度下的其他区块提案；对于某个高度（不关注视图号），正确节点收到一个锁定 QC 时，会锁定该区块，并坚持对已锁定的区块进行提案或投票，而会忽略该高度下的其他区块提案。

有了这样的机制，我们再重新审视是否能够满足刚刚提到的那个特性。先看同一个视图的情况，根据行为 2' 和 QC 性质，节点不可能收到冲突的锁定 QC，所以不会锁定在互斥的区块，两个互斥的 QC 锁只可能出现在不同视图中，视图号越大，表示锁越新；对于不同视图的情况，如果旧锁对应的区块被提交了，根据行为 1'，已经有 2f 1 个节点有了旧锁；根据行为2'，不可能有 2f 1 个节点对该高度的另一个区块发送准备消息，所以不可能形成新锁。可见这个解锁机制满足以上特性。

另外，根据快速恢复机制，假如节点收到了一个比本地 QC 锁的高度更大的 QC 锁时，会快速同步落后的区块，并从该高度继续共识，所以从这个意义上看，高度更大的 QC 锁也可以“解锁”高度小的 QC 锁。因此，高度越大，锁越新；高度相同时，视图号越大，锁越新。

因此，行为 3 升级为：

行为3'：leader 基于最新锁定的区块发起新提案，并携带本节点最新的 QC 锁，其他节点收到 QC 锁时会解锁更旧的 QC 锁，并继续新提案的共识。

值得一提的是，假如最新锁定的区块已经提交，那么显然新提案是基于该区块出的一个新的区块，但是假如最新锁定的区块还未提交，那么 leader 可以选择继续使用该区块构造新提案，也可以选择基于该区块出一个新块，对于后者，需要增加一个设定：如果某个区块提交了，那么高度更低的区块也该提交。

2. 隐藏锁问题

使用以上的解锁机制，可以解决死锁问题。但是假如发生视图切换时，新 leader 没有最新 QC 锁，那么无法解锁其他节点，共识可能无法进行，并且，不像提交 QC，最新的 QC 锁是会动态变化的，也就是可能每次 leader 在视图切换之前都可能形成一个最新的 QC 锁，导致下一个 leader 的锁永远不是最新的，永远轮不到最新锁的节点出块，从而使系统失去活性。最新 QC 锁仿佛被“隐藏”了，所以这个问题被称为“隐藏锁”问题，具体例子可以阅读附录。

2.1 收集锁

在讨论如何解决隐藏锁问题之前，我们先回看一下上面分析的几种情况，会发现存在一个问题，很多情况可能需要等待多轮视图切换才能达成共识，这大大影响了共识效率。

我们等待的目的都是为了轮到一个拥有最新 QC 锁的正确节点。那么有没有可能，切换新 leader 时，想办法把最新 QC 锁发送给新 leader，新 leader 再从中选出一个最新的 QC 锁，这样就可以直接在一轮共识中完成。

新 leader 应该收集多少个节点的消息呢？同样的，由于错误节点可能会故意不发送消息，所以为了保证活性，leader 最多在收集到 2f 1 个消息时就该停止。这也导致了最新的 QC 锁不一定能被 leader 收到，隐藏锁问题仍然存在。

2.2 广播所有锁

如何解决隐藏锁问题呢？实际上，对于收集了 2f 1 个节点的最新 QC 锁的新 leader 来说，隐藏锁并不构成一个问题。回想一下，我们说如果新锁能够产生，那么旧锁对应的区块一定没有被提交，所以新锁可以安全地解锁旧锁。但是，其实新锁对应的区块也是可能没有被提交的，假如我们能找到新锁一定没被提交的证据，那么新锁也可以被安全地解锁。

如果某个节点本地的最新 QC 锁对应的提案已经被提交了，那么至少有 2f 1 个节点拥有该提案的相同 QC 锁，并且这 2f 1 个节点的最新 QC 锁要么等于该 QC 锁，要么为更大高度的 QC 锁，我们记这个集合为 C，根据 QC 性质，如果新 leader 收集 2f 1 个节点的最新 QC 锁，那么其中一定有一个正确节点在集合 C 中，所以一定能收集到已经提交的提案对应的 QC 锁或者更大高度的 QC 锁。也就是说，如果有一个节点拥有一个 QC 锁（不管视图号多大），但 leader 没有从任何节点收集到与之相同的 QC 锁或更大高度的 QC 锁，那么可以断定该 QC 锁对应的提案一定没有被提交，所以可以安全地解锁。于是，我们找到了另一个解锁的方法，leader 不一定非得获得最新的 QC 锁，只需要把这 2f 1 个 QC 锁作为证据广播给其他节点即可，其他节点根据上面提到的规则解锁，然后可以继续后面的共识，从而不存在隐藏锁问题。

值得一提的是，收集并广播 QC 锁的过程只需要在视图切换开始时执行一次，一旦完成了一次全体的解锁，在该视图中就不再需要关心此问题，因为在一个视图中不可能有节点锁定在不同区块。

2.3 引入固定时延

广播所有 QC 锁无疑增大了视图切换的消息复杂度，有没有其他办法呢？我们前面提到最新锁可能无法被 leader 收集，所以会导致部分节点无法解锁，我们尝试直面问题，有没有办法保证最新的锁能被 leader 收集到呢？这样 leader 只需要广播最新的 QC 锁，就能让所有正确节点解锁，并且这个操作同样只需要在视图切换时进行一次。

我们在最开始有一个同步假设，节点的最大时延是有固定上限的，所以如果新 leader 在收集 QC 锁时，等待一个固定时间，如果这个时间大于时延上限的话，那么一定能够收集到最新的 QC 锁；如果小于时延上限，那么本次可能无法达成共识，下次视图切换时增加这个时延上限，这样轮了多次之后，总能超过时延上限。

以上方法可以减少视图切换的消息复杂度，但由于引入了一个固定时延，一旦出现视图切换（错误节点为 leader 时，总有机会能触发视图切换），不管网络有多好，共识都要等待一个固定的时间，从而失去了响应性。

响应性：系统达成共识的时间只依赖于网络的实际时延，而不依赖于已知的最大时延。通俗来说就是说当系统处于异步网络时，共识慢一些甚至无法达成都没关系，但只要系统切换到同步网络，且当前 leader 为正确节点，不管错误节点做出什么行为，都能在实际的网络延时下达成共识，网络好就快一些，网络不好就慢一些，而不是不管网络好坏，共识都要等待预设的网络最大时延。

2.4 增加一个阶段

难道就没有两全的办法吗？能否不要通过等待固定时延来确保收集到最新的 QC 锁呢？实际上，上面“广播所有锁”利用到的 QC 原理同样可以应用在我们遇到的这个问题上，也就是，我们在准备阶段之前再加一轮投票，收集到的 QC 称为预备 QC，收集到预备 QC 时才可以广播准备消息，那么当收集到 QC 锁时，一定有 2f 1 个节点拥有对应的预备 QC。假设某个节点的最新 QC 锁为 A，那么一定有 2f 1 个节点拥有对应的预备 QC，且这些节点的最新预备 QC 一定不旧于该预备 QC，我们记这些节点构成集合 C，当 leader 收集 2f 1 个节点的最新预备 QC 时，其中一定有一个正确节点位于集合 C 中，所以一定能收到不比 QC 锁 A 旧的预备 QC。因此，最终收集到的最新预备 QC，一定不旧于任意节点的最新锁定 QC。同时，预备 QC 也具备 QC 锁的基本性质，所以我们可以使用预备 QC 来解锁 QC 锁。从而解决了隐藏锁问题。

2.5 方案总结

我们来总结一下我们最终的方案。

提案阶段：leader 使用已锁定但未提交的区块（若没有，则使用新区块）发起提案。

锁定阶段：节点收到 leader 的提案时，判断是否满足 a. 在该视图内没有对该高度的不同区块投过票，且 b. 没有锁定该高度下的另一个区块 或 提案携带的 QC 锁比本地的锁新（注意如果 QC 锁的高度远大于本地已知的高度时，节点会通过快速恢复机制补齐缺失的区块），若满足则广播对该提案的准备消息；节点收集到 2f 1 个准备消息（锁定 QC）之后，对该高度加锁，并广播提交消息。

提交阶段：节点收集到提交 QC 后，执行该区块并向客户端响应。

计时器：每次完成一个区块的提交、开始等待下一个区块时，设定一个超时时间，若在该时间内下一个区块没有完成提交，则触发视图的切换。

视图切换：上面提到的三种方式选择一种，若选用第三种，则需要在锁定阶段前加一个预备阶段，预备阶段逻辑与锁定阶段类似。

3. 现有算法对比

其实说到这里，我们基本上已经把我们即将介绍的几个共识算法——PBFT、Tendermint、Hotstuff——的核心思想讲完了。网上关于这些共识算法的描述有很多，本文并不打算对算法过程进行罗列，而只强调它们共同解决的问题、不同的解决办法、各自的优缺点。如果对算法细节感兴趣，建议阅读论文原文，特别是论文的证明部分。

正如我们上文讨论的，其实不管什么共识算法，无非就是要保证两个性质：安全性 和 活性。对于活性，则包含 leader 出错、死锁和典型的隐藏锁问题。

在安全性方面，这几个算法如出一辙，都是利用了我们上文提到的 QC 性质；对于 leader 出错，则都是使用了 leader 切换机制；对于死锁，基本上也都是通过增加一轮投票阶段来解决；但对于隐藏锁问题的解决却各有千秋，分别使用了我们上文提到的三个基本思想，下文我们会一一分析。

3.1 PBFT

对于 PBFT，我们经常会看到类似这样的一张图：

上面的三个阶段其实就对应我们上面提到的提案阶段、锁定阶段、提交阶段。

准备阶段收集的准备证书就对应我们的 QC 锁；提交阶段收集的提交证书就对应我们的提交 QC。

在隐藏锁问题的解决上，PBFT 选用的是 “广播所有锁” 的方法，所以视图切换过程如下：

所有节点广播 View-Change 消息，该消息包含本节点的准备证书，新 leader 收集到 2f 1 个 View-Change 消息之后，将所有 View-Change 消息打包进 New-View 消息并广播给其他节点。不同的是，节点发送的准备证书并不只是最新的，还包含了其他的较近的准备证书，这可以看成是“快速恢复机制”的一部分；同时， New-View 消息中也不仅包含准备证书，还包含基于这些准备证书发起的新提案，这是为了在解锁的同时，进行新提案的发起，推进未完成共识的区块更快完成。

PBFT 最常被诟病的就是视图切换复杂度高，N 个 New-View，每个 New-View 含 2f 1个 View-Change，每个 View-Change 含若干个准备证书，每个准备证书有 2f 1 个签名，所以消息复杂度为 O(n^3)。这也是后来其他共识算法想方设法要解决的问题。

3.2 Tendermint

Tendermint 最大的改进就是降低了视图切换的消息复杂度。

Tendermint 与 PBFT 具有非常相似的两阶段投票协议，文末总结部分也有各个共识算法的阶段名称对应，这里不再赘述。值得一提的是，如上图所示，进入新一轮的 Propose 之前，可能是 New Round，也可能是 New Height，后者仅在共识成功时出现。也就是说，当某个高度的区块共识成功时（图中蓝色箭头组成的循环），会进入新的高度，否则，会进入新的 Round，直到该高度共识成功。这里的 Round 其实就对应 PBFT 中的视图（View），共识超时触发切换 Round，更换 leader。不同之处在于 Tendermint 即使共识成功进入 New Height 也会更换 leader，但这对于保证活性不是必要的，更多是为了保证各个节点能够按照正确的权重轮流出块，以达到激励分配的公平性，同时有研究表明在区块链的环境下频繁更换 leader 有助于提高链的质量。后文将提到的 Hotstuff 也是每个区块都会更换 leader。

不过以上的区别无关痛痒，隐藏锁的解决机制才是我们要重点讨论的话题。实际上，Tendermint 使用了我们上文提到的“引入固定时延”的机制。

首先，它使用了一个 Gossip 协议，节点间会互相同步收集到的消息（提案、投票等），网络模型遵循部分同步假设。也就是说，如果某个正确节点发送/接收到了消息 A，那么在某个时间间隔 Δ 之后，所有正确节点都会收到消息 A。

在这个基础上，Precommit 阶段引入超时时间 timeoutPrecommit，在这个超时时间内，节点可以（通过 Gossip 协议）向其他节点同步最新的锁。可证明当 timeoutPrecommit 大于某个值时，可以保证最新的 QC 锁一定能在进入下一个 round 前发送给所有正确节点（严谨证明参见论文 Lemma 6），即下一个 round 的 leader 一定含有最大的 QC 锁。因为使用了 Gossip 协议，所以它进入 New Round 时表面上并没有额外的消息传输。另外，Propose 和 Prevote 阶段也含有超时时间，当这些超时满足一定要求时，可证明活性（参见论文 Lemma 5）。

3.3 Hotstuff

Hotstuff 的算法思想与 PBFT 和 Tendermint 是类似的，但使用了“增加一个阶段”的方式来解决隐藏锁问题。非流水线版本的 Hotstuff 共识流程如下图：

看起来感觉跟 PBFT 差别很大？实际上，如果我们把他画成下面全广播的网状形式，就好理解了：

这个图和 PBFT 很像，区别是图中红色框的部分。第二个框实际上就是为了解决隐藏锁问题而增加的阶段，而第一个框则是所有节点在视图切换时向主节点发送本地的最新 QC 锁（因为 Hotstuff 没有像 Tendermint 一样的 Gossip 机制）。其他阶段可以与 PBFT 一一对应进行理解。

Hotstuff 的一个改进点是使用了聚合签名，所有节点不直接广播已签名的投票消息，而是先将投票发送给 leader，再由 leader 将所有签名进行聚合之后，再广播给其他节点，这样可以减少验签时间，并且将网状通信变成了复杂度更低的星型通信。

将全广播的共识流程中的网状通信替换为星型通信，就有了一开始的那个共识流程图。

既然有非流水线版本，那就有流水线版本，这是 Hotstuff 的另一个重要改进。

 由于每个投票阶段的消息非常类似，所以可以将他们的消息类型进行统一，并且不同提案的共识可以流水线化。具体来说，所有节点在 PREPARE 阶段收集足够的投票组成 genericQC，然后 genericQC 转发到下一个视图的 leader，新 leader 负责下一个 PRE-COMMIT 阶段。但新 leader 并不是真正地执行 PRE-COMMIT 阶段，而是重新进入一个新的 PREPARE 阶段，并提出新的提案。视图 v 1 的 PREPARE 阶段同时作为视图 v 的 PRE-COMMIT 阶段，视图 v 2 的 PREPARE 阶段同时作为视图 v 1 的 PRE-COMMIT 阶段和视图 v 的 COMMIT 阶段，以此类推。视图 v 的提案会在视图 v 4 的 PREPARE 阶段结束时提交。

因此，在 Hotstuff 的流水线的版本中，只有 NEW-VIEW 和 GENERIC 两种消息类型，前者包含上一个视图的 genericQC 和当前视图的提案，后者包含对当前视图提案的投票，足够的 GENERIC 消息进行聚合签名后组成 genericQC。

流水线化之后由于只有一种 QC，所以锁定和提交逻辑依赖于视图间的数量关系，有兴趣的话可以阅读原论文了解更多。

4. 总结

1. 共识算法的正确性包含：安全性和活性。活性主要需要解决 leader 出错、 死锁 和 隐藏锁 问题。
2. QC 性质：任何两个 Quorum 至少有一个共同的正确节点。
3. 安全性：加锁机制 QC 性质。
4. leader 出错：是活性丢失的直接来源，使用视图切换解决该问题。
5. 死锁：增加一轮投票 解锁机制。
6. 隐藏锁：三种解决方法，广播所有锁、引入固定时延、增加一个阶段。
7. 提及的三个共识算法对安全性、leader 出错、死锁的解决思想基本相同，对于隐藏锁则分别使用了以上三个方法。
8. Hotstuff 的其他改进：聚合签名减少消息复杂度；流水线化。
9. 各个共识算法的联系和区别整理到了如下表格，可以对照着理解。

5. 附录

5.1 情况分析

1.5 节的情况造成原因分别如下：

1. 上一个视图的 leader 为正确节点，由于网络原因，部分节点还未收到提案；或者上一个视图的 leader 为错误节点，只给部分节点发送提案和投票。
2. 同上。
3. 上一个视图的 leader 为错误节点，给不同节点发送了不同提案；或者在情况 1 或 2 的前提下，新 leader 发送了新提案，使得其他节点锁定在其他区块。

5.2 隐藏锁问题

假设有 4 个节点，编号 0~3，节点 3 为错误节点。开始时，所有节点都没有锁。

1. view 0 时，节点 0 为 leader，发起一个提案，并收集到了 QC 锁，在本地锁定了该提案，记该锁为 v0。但由于网络原因，其他节点都没有收集到 v0，并且超时触发视图切换；
2. view 1 时，节点 1 为 leader，发起一个提案，由于此时节点 0 有最新的锁，所以节点 0 不会投票，假如错误节点不投票，那么是无法收集到足够投票的，假如此时错误节点在合适的时间点将投票只发给节点 1，使节点 1 锁定在 v1。
3. view 2 时，节点 2 为 leader，发起一个提案，此时节点 0 和节点 1 有更新的锁，所以他们不会投票，此时只剩下 2 个节点无法形成锁。
4. view 3 时，节点 3 为 leader，同上，无法形成锁。
5. view 4 时，节点 0 为 leader，发起一个提案，由于此时节点 1 有最新的锁，所以节点 1 不会投票，假如错误节点不投票，那么是无法收集到足够投票的，假如此时错误节点在合适的时间点将投票只发给节点 0，使节点 0 锁定在 v4。
6. view 5 时，节点 1 为 leader，发起一个提案，由于此时节点 0 有最新的锁，所以节点 0 不会投票，假如错误节点不投票，那么是无法收集到足够投票的，假如此时错误节点在合适的时间点将投票只发给节点 1，使节点 1 锁定在 v5。
7. view 6 时，节点 2 为 leader，发起一个提案，此时节点 0 和节点 1 有更新的锁，所以他们不会投票，此时只剩下 2 个节点无法形成锁。
8. view 7 时，节点 3 为 leader，同上，无法形成锁。
9. view 8 时，又回到步骤 5，节点 0 锁定在 v8，如此循环，永远无法达成共识。

参考文献

1. 拜占庭错误维基百科描述：Byzantine fault
2. PBFT 论文原文：Practical Byzantine Fault Tolerance
3. Tendermint 论文原文 1（建议阅读）：The latest gossip on BFT consensus
4. Tendermint 论文原文 2：Tendermint: Byzantine Fault Tolerance in the Age of Blockchains
5. Tendermint 官方 Github 描述共识过程
6. 关于 Tendermint 各个阶段超时时间的描述
7. Hotstuff 论文原文：HotStuff: BFT Consensus in the Lens of Blockchain
8. HotStuff 图片来源：HotStuff: the Consensus Protocol Behind Facebook’s LibraBFT
9. HotStuff共识算法详解
10. 部分同步网络相关论文：Consensus in the presence of partial synchrony