最近Facebook公布了发行稳定币Libra的计划和相应的技术白皮书。用天秤座取名，不言而喻意在公平、和谐、普惠。古罗马诗人，《地理学》作者马尼利鸟斯（Manilius）曾说，天秤座的季节是平衡的，白天的时间和晚上时间一样多；而罗马的法官都必须是天秤座出生。
Libra平台的技术核心点有两个，一个是智能合约编程语言MOVE，另一个是共识算法LibraBFT。
本文将从Libra共识协议、PBFT共识协议、HotStuff共识协议、LibraBFT共识协议及结论五个部分对LibraBFT做一个详细的评述，整篇文章将分为以下4篇连载文章进行发布：
连载文章
连载(1): Libra共识协议介绍
连载(2): PBFT共识协议回顾
连载(3): HotStuff共识协议介绍
连载(4): libraBFT共识协议及结论
连载(3): HotStuff共识协议介绍
HotStuff的基本假设是系统有固定的节点数n = 3f+1，其中f是系统能容忍的最大拜占庭节点数。系统通信是点对点的认证和可靠通信。网络通信的假设是半同步，也就是说，网络有一个知道的延迟D，以及一个不知道的全网稳定时间（Global Stabilization Time，简称GST），当GST过后，任意两个节点之间的通信都将在D时间内完成。HotStuff能总保证正确性（safety），在GST后的消息时延在一定限度（D）内能保证活性（liveness）。
HotStuff采用门限签名机制【7】，门限设置是（k, n）。n个节点中所有的节点共用一个公钥，但每一个节点有自己的私钥。每个节点用自己的私钥签名消息m，叫部分签名消息，多个节点的部分签名消息可以用来生成一个联合签名消息，当至少有k = 2f+1个节点提供部分签名消息时，其它任何一个节点能用公钥验证该联合签名消息。其中f是系统能容忍的拜占庭节点总数，n = 3f+1。
HotStuff【1, 2】论文中提出一个“认证复杂度”的概念。认证复杂度简单来说，统计协议交互时通信的认证消息数，也就是部分签名或联合签名消息的个数。以这个角度出发，HotStuff作者们对一些BFT协议作了分析，把主要BFT协议的通信认证复杂度列出如表3-1：
表3-1：BFT协议认证复杂度对比
从表3-1可看到，在正常情况下，PBFT的认证复杂度是O(n平方)，在视图更换时一般情况是O(n立方)，当视图更换时出现最坏情况，也就是连续f个Leader都出故障时，PBFT的认证复杂度是O(n四次方)。而HotStuff则是O(n)线性复杂度。即使在有f个leader出故障时，仍能保持O(fn)的线性认证复杂度。
在HotStuff中，每个视图有一个所有共识节点都知道的唯一的Leader，视图的序号是递增的。每个共识节点保存有一个树形结构，该树形结构里的每一个node（简称图节点），保存有该共识节点接收到的命令请求，以及相应的元数据，还有指向父图节点的哈希指针。HotStuff协议的进程就是不断确认树形结构里的分支。
Leader在提议分支时，必须收到（n-f）个节点的投票才能确认该分支。这个（n-f）的投票叫法定节点数证书（quorum certificate，简称QC）。QC是与特定图节点以及视图序号相关联。
HotStuff协议分为基本HotStuff（Basic HotStuff）和链式HotStuff（Chained HotStuff）协议。我们下面分别介绍这两种协议。
3.1 基本HotStuff协议
我们先来看基本HotStuff（Basic HotStuff）的共识流程。图3-2是HotStuff的一个正常情况的流程。流程分为四阶段：prepare，pre-commit，commit和decide阶段。
图3-2：HotStuff 基本流程
1、Prepare阶段
首先一个新的Leader需要收集（n-f）个共识节点发出的new-view消息。共识节点在转到新的视图时，会发new-view消息，包含该节点所有的最高prepareQC。Leader处理这些收到的消息，在其中选择最高视图的prepareQC，称为highQC，它可以断定没有比这个更高的视图能达到确认状态。因此，在highQC图节点所在的分支状态是正确的（safe）。这个时候，Leader用createLeaf方法来在highQC.node的尾部延伸分支，建立一个新的图子节点，并嵌入指向父图子节点的哈希指针。然后向各节点发出prepare消息，包含highQC作为正确性的证明。
当其它共识节点收到prepare消息后，每个共识节点用safeNode判断方法来判断是否接受它。在每个共识节点的本地树形结构中，有自己的一个锁定图节点（lockedNode）。它首先判断接收到的新的图子节点是否是从锁定图节点后延伸的，另外就是接收到的视图号码是否比锁定图节点的视图号要高。如果两者都满足，该共识节点将接受提议，并返回给主节点一个投票，并用自己的私钥给投票消息签名。
2、Pre-commit 阶段
当Leader接收到（n-f）个prepare vote 投票消息后，他会把投票放进prepareQC, 然后Leader会广播包含prepareQC的pre-commit消息。副本会回复对pre-commit的投票消息pre-commit vote并将消息的摘要上签名。
3、Commit 阶段
该阶段和pre-commit阶段类似，当Leader 接收到（n-f）pre-commit vote投票消息后，它会将消息放进precommitQC, 然后Leader连同commit message广播给所有副本。特别重要的是，副本在收到precommitQC时把它的LockedQC置为precommitQC。这个对保证正确性至为重要。副本节点会返回commit vote签名消息给Leader。
4、Decide阶段
当Leader收到（n-f）个共识节点的commit vote消息后，它将这些消息联合起来放在commitQC中，然后广播给所有共识副本节点。副本节点收到commitQC后，会认定在commitQC中的命令进入确认状态，并开始执行确认分支中的命令。最后递增viewNumber，并开始下一个视图。
在以上阶段中，副本节点会有一个定时器，如果在一个视图中超时，将递增viewNumber，开启一个新的视图更换。
对比PBFT，可以看到，HotStuff的通信是由Leader主节点广播，副本节点之间并不广播消息，而是由副本节点直接回复给主节点，主节点利用门限签名把各副本节点的签名信息联合成一个签名信息，再在下个阶段作为证据发给所有副本节点。因此，HotStuff在消息往返里避免了副本之间的广播消息，在Leader不出故障情况下，把复杂度从PBFT的O(n平方)降低到O(n)。而最为重要的是，HotStuff将视图转换融入正常流程，大大简化了视图转换的复杂度。在PBFT中，视图转换需要把从检查点以后的所有消息集合重传，认证消息复杂度升到O(n立方)，特别是在最坏情况下（f个Leader连续出故障），复杂度升到O(n四次方)。而HotStuff即使在最坏情况下，能始终保持线性复杂度。
3.2 链式HotStuff
在基本HotStuff中，Leader主节点需要三个阶段来确认一个请求提交。这些阶段都非常相似，除了收集其它副本节点的投票外，大部分没有做多少实际工作。
链式HotStuff （Chained HotStuff）提升基本HotStuff的效用并同时并大大简化其流程。方法是在每个Prepare阶段，都主动的转换视图。具体说来，在链式HotStuff，对Prepare阶段的投票，由下一个在prepareQC的视图的Leader来收集。同样，依此类推，pre-commit和commit阶段的投票也由与之相应的下一个视图的leader来收集。这样，新Leader在视图v+1的prepare提议阶段，同时作为视图v的pre-commit阶段。而新的Leader在视图v+2的prepare提议阶段，同时可以作为视图v+1的pre-commit阶段，以及视图v的commit阶段。因为所有阶段的数据结构都一样，因此可以用流水线的方式来提升共识的效率。图3-3展示了链式HotStuff的基于Basic HotStuff的流水线形式。
图3-3: 链式HotStuff_基础HotStuff流水线
视图 v1, v2, v3作为v1提交的命令cmd1的prepare，pre-commit和commit阶段。cmd1命令在v4里确认。视图v2,v3,v4作为v2提交的cmd2的三个基础HotStuff的阶段，cmd2在v5里得到确认。依此类推。
因此链式HotStuff中，只有两类型的消息，一种是new-view，一种是generic-phase的generic消息。genericQC实现所有不同阶段的功能。
链式HotStuff中，如果图节点b’中的QC直接对应父图节点b，这样形成了One-Chain; 如果在One-Chain的基础上，下一个图节点b‘’中的QC直接对应b’，这样就形成了Two-Chain，在这个基础上，下一个图节点b*中的QC直接对应b’’, 这样就形成了Three-Chain。图3-4显示视图v4，v5，v6形成了一个Three-Chain。
图3-4:Three-Chain示意图
如果图节点b*形成Three-Chain,那么图节点b的确认已完成。
3.3 PaceMaker
在HotStuff中，Pacemaker是用来保证共识流程的活性。
Pacemaker通过两方面来实现。一方面是“同步”，也就是在一个足够长的时间内，把所有正确的副本节点和主节点的本地树结构更新到一致的高度。主节点的选择一般是从一个预先制定的表中轮流选出主节点。Pacemaker的另一方面是主节点需要能选择让正确的副本节点接受的提议。HotStuff的new-view消息正是让主节点能选择正确的提议的方法。
（未完待续）