一、区块链共识算法

因为hotstuff是一种被用于区块链的共识算法，所以先讲一下区块链的共识。
大家都知道，比特币的出现，尤其是比特币价格的夸张涨幅，带动了整个区块链行业的发展。用的人多了，自然讨论就多了。大家就发现比特币的很多的不足，其中一个非常让人诟病的，就是其所采用的pow共识机制。pow带来了几个很大的问题，比如能源消耗大（如果当作一个国家，排名20多位，当然是好是坏其实是有争议的），比如tps非常低（6-7笔）、交易确认时间长（概率性、最好de等待1小时以上）。
这些问题，如果要改进，一个很有效的方法就是要改进其共识算法。而关于此，也有个所谓的不可能三角问题（类比CAP定理），即安全性、去中心化、性能(可称做scalability, speed…)。

个人觉得，大部分共识算法，其实就是围绕这三个特性，根据自身需求、认识做不同的取舍。当然，解决比特币的上述问题除了在共识算法下功夫，还有其它方案，比如分片、分层等等，这里就先不讲了。
有需求、就有解决方案，伴随者区块链的发展，比特币、以太坊暴露了越来越多的问题。有段时间，学术界和工业界关于共识的研究、讨论非常的火热，也衍生出了非常多的共识算法，比如POS、DPOS、POA、POSA、POH等等。这一类算法，个人觉得，可以算作是跟着区块链而诞生的，没有区块链、加密货币，就没有它们。
然而，共识其实是分布式系统的固有问题，原本就存在很多解决方案，比如著名的paxos、raft等等。所以，自然就有人翻翻旧书堆，然后就发现BFT类算法，貌似有点意思，貌似有点用。这个和AI领域的神经网络有点类似，指不定啥时候就发扬光大了（也可能永远没人用…）。

二、BFT类算法

那什么叫BFT呢，BFT是拜占庭容错（Byzantium Fault Tolerance）的缩写，意味着系统的每个节点的行为是任意（好意、恶意、断网、崩溃…）的，具体可以网上查阅拜占庭将军。是不是发现和公链的使用场景，或者说有点类似呢？

1、早期历史

• lamport 1982 就提出了拜占庭将军问题，并给出了解决方案
• Barbara Liskov、Miguel Castro 1999 提出了PBFT，大幅提高了算法的效率
  可以发现，这两个算法距今少则20年，长则40年，确实称得上历史尘埃中的金子。
  大家可以想想pow是不是bft，虽然我这里把两者区分了。

2、优点

• 确定性，commit的块不会回滚，无需等待足够长的块
• 高性能，轻松达到数千tps，有些联盟链号称几万tps，比如百度超级链、FiscoBcos…

3、缺点

• 中心化，要求提前确定节点
• 性能仍然不够高（针对pbft），尤其是节点数量（几百几千甚至更多）过多的时候

4、pbft基本流程

可以忽略request和reply阶段

• pre-prepare：所有节点收到请求，验证请求合法后，广播自己的vote
• prepare：所有节点收集2f+1签名形成prepareQC，并广播
  QC是quorum certificate的缩写，代表法定人数证明
• commit 所有节点收集2f+1 prepareQC后，回复给客户端
  便于理解的话，可以记住：每个阶段每个节点都会先收集信息，然后再广播信息。
  可以发现，通信复杂度为O（N*N），N为节点数量。

5、区块链

区块链的爆发也带来了bft类算法的爆发式发展，上图是一个示例，还有很多其它的优秀算法。

6、优化

a、基于leader

大家首先发现，让一个节点负责消息的分发和收集，会使得整个流程简化不少。每轮流程和原始pbft类似，只是都先把消息发给leader，再由leader广播给所有节点。
可以发现网络消息数从O(NN)下降到O(N)，但因为每个prepareQC包含2f + 1 签名，所以通信量复杂度还是O(NＮ)。
同样的，每个阶段，每个节点也是收集一轮信息，在发送一轮信息，leader和follower都类似。
缺点是如果leader作恶，那么共识无法达成，需要切换leader。

b、门限签名

密码学的进步：包含2f + 1 签名信息的prepareQC，占用空间降至O(1)，整个通信量复杂度下降到O(N)。

三、基本概念

1、网络通信模型

• 同步模型：假定最大的网络延时T，得设置比较大（min级别？）。因为实际情况，网络可以出问题，而解决问题可能几分钟，也可能几小时，甚至几天。
• 异步模型: 网络时延无保证
  网络是无法保证达成共识的，著名的FLP定理
• 半异步模型: partial synchronous model，上面两个模型的折中
  也叫部分同步，网络可能处于异步状态，但是GST（global stable time）后会进入同步状态
  大部分共识算法都是基于半同步模型，这也符合实际情况，可以参考下文。
  https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/

2、响应性（Responsiveness）

一旦网络进入同步状态，好的leader以实际网络延时的速度，达成共识。
也叫做(Optimistic) Responsiveness乐观响应性，我觉得也比较直观。就是网络达到同步状态（GST）后，即解决了所有网络问题后，真正干完活所需的时间和实际网络延迟一致。类似于要搬1000块砖，现在砖也准备好了，人也吃饱喝足了，那么假定一分钟搬10块砖，100分钟就能搬完。
(Optimistic) Responsiveness After GST, any correct leader, once designated, needs to wait just for the first (n−f) responses to guarantee that it can create a proposal that will make progress. “As fast as the network propagates, on a good day”

3、安全性（safety）

坏事情永远不发生，即所有的好节点不可能提交(commit)相冲突的数据
注意区别密码学的security，这个概念其实和共识算法无关，区块链中的security是通过密码学保证。

4、活性（liveness）

只要系统网络进入同步状态，系统最终都能达成新共识。
区块链中就是链的高度会增长，不断出新块。

5、两阶段提交

假设节点收到prepareQC即提交（如上图称作commitQC），
再假设除了leader之外，其它节点都未收到prepareQC，如何保证被leader提交的数据将来被其它节点提交呢？
只能要求其它节点记录所有的proposal，并保证后续的共识与此不分叉。而在有的情况下，proposal可能只被少数节点收到，如果每次都有一个好节点出现此类问题，那么系统的好且工作的节点将不断减少，直至无法共识（无活性）。

6、鸽笼（抽屉）原理

如果把n+1个东西放进n个盒子里，有一些盒子必须包含最少2个东西。

7、3f + 1

假定总节点为n, 坏节点（作恶节点）为f。 那么在每轮共识的时候，最多只能收集n-f个签名，否则就极有可能永远没法共识了。
容易得到：
每轮共识的票数不能大于N - f，否则可能永远打不成共识(坏节点一直不干活)。
每轮共识的最少好节点票数： （N – f）– f
相邻轮次共识的好节点数量： 2 * (n – 2f）
好节点永不作恶，那么只要保证这2 * (n – 2f）节点中有重复节点，就安全了。根据鸽笼原理，可得：
2 * （n – 2f）> n – f =》n > 3f，即n >= 3f + 1

鸽笼原理中的盒子，其实就是好节点，相当于有n-f盒子，要放2*(n – 2f）个东西。
两阶段以及切换leader的过程，为了保证安全性，都应用了这个原理。

四、hotstuff

1、基本情况

第一个实现Linear view change且拥有(Optimistic)Responsiveness的共识算法。
应用：知名的Facebook Libra

2、比较

可以发现从大的主要维度看，hotstuff基本实现了最优。

3、基本流程

4、关键点

相比其它共识，之所以能达到这个目标，得益于下几点：

• 增加一轮共识
• 新节点的替换规则
  if m.node extends from m.justify.node ∧ safeNode(m.node, m.justify)
function safeNode(node, qc)
return (node extends from lockedQC.node) // safety rule
∨ (qc.viewNumber > lockedQC .viewNumber ) // liveness rule
• Viewchange，leader切换与共识流程融合

5、优化

链式共识，n高度的commit, n+1高度的lock，n+2高度的prepare，可以同时验证。
提高了系统的吞吐量，但是latency还是没变。

6、tradeoff

• 增加了共识的阶段，增加了一个分叉块，latency延长50%。
• 增加了分叉的可能性，增加了实现的复杂度