hotstuff共识算法总结

本文分为两个部分，第一部分给出hotstuff的总结，第二部分详细谈hotstuff的细节。

第一部分

我们首先聊一下HotStuff共识算法，该算法总结了PBFT、Tendermint等共识算法的特点，实现了一个既有安全性（safety）、活性(liveness)，又有响应性(responsiveness)的共识算法。

为了更好的理解HotStuff的创新点，我们先简要回顾一下PBFT和Tendermint的短板。

PBFT是最早的可以实用的拜占庭容错共识算法，该算法最大的短板是ViewChange时的消息复杂性，每当需要在共识节点中切换Leader时，都需要大量的消息O(n^3)，这是很复杂的。

Tendermint是17年提出的共识算法，该算法采用了锁定、解锁机制，简化了Leader切换过程。但是该算法却损失了响应性，在该算法中即使某个节点集齐了各个共识节点的投票消息，依然需要等待一段时间，以保证大多数节点都能集齐消息。这会带来什么影响呢？在网络情况很好的时候，依然需要等待固定时间，才能出块。比如说，在目前的Cosmos主网中，出块间隔相当稳定，大约是6秒左右。

如何才能让区块的确认只与网络的实际延迟有关呢，也就是说网络状况好的时候，区块更快确认；网络状态差的时候，可以多等点时间确认。这样的特性就是所谓的响应性，Responsiveness。

HotStuff给出了这样一个算法，Leader切换只需要线性复杂度，同时保证了响应性。那么它是怎么做到的呢？

首先，HotStuff引入了门限签名，每一轮的共识投票消息，都是各个共识节点发送给Leader节点，由Leader将这些消息签名组合成一个，再广播给大家。这样极大的较少了系统中消息量，从O(n^2)减到了O(n)。

然后，相比于PBFT和Tendermint的两轮投票，HotStuff采用了三轮投票，多了一轮投票，各个节点集齐投票就可以进入下一个共识，而不需要等待固定的时间。

除了响应性，HotStuff还采用了链式确认，我们认可一个区块，实际上也是对于该区块父区块的认可。在链式的HotStuff中，可以将区块的确认放在下一个区块中，只要一个区块后面产生了三个连续区块，那么就说明该区块经过了三轮投票确认，就可以最终敲定了。

还有一个比较大的创新是，HotStuff提出了安全性和活性的解耦，安全性和活性可以分开独立的设计。共识算法的安全性经过严格的数学证明，同时其活性可以更加灵活，可以定制。比如说，一个系统想要采用HotStuff，安全性的部分不用担心，对于活性的部分，比如Leader怎么切换、超时时间如何定义等等可以灵活的留给使用者定义。

总结一下HotStuff的特点:

消息复杂度是线性的，O(n)， Leader切换时也是线性的；
具备响应性，Responsiveness
链式的确认规则，出块更快；
安全性规则和活性规则解耦，更加灵活。

第二部分

basic hotstuff三阶段流程图

首先明白为什么需要三个阶段？：
某个好节点i达到committed-local可以执行交易了，说明其至少接收了2f+1个节点的commit消息，所以至少有f+1个好节点的commit消息。好节点发送commit需要保证是已经进入prepared状态才行。这样就至少有f+1个好节点进入了prepared状态。如果发生视图转换的时候，新的主节点需要收到2f个来自其他不同节点的view-change消息（加上自己就是2f+1个消息）。网络中总有3f+1个节点，所以f+1个好节点肯定至少有一个会把已经prepared的消息发送到下一个视图中继续达成共识。pbft的视图切换复杂度很高，导致效率低。在hotstuff中，Replica收到DECIDE消息中的commitQC后，认为当前proposal是一个确定的消息，然后执行已经确定的分支上的tx。hotstuff多出来的一个阶段（也就是副本节点拿到commitQC之后），相当于是保证pbft中最终每一个节点都达到了commit-local状态，这样就可以去进行提交了。当然如果这里有部分节点没有收到commitQc，在后续会跟上来，如果很多节点收不到commitQC就会发生试图轮换，看上去好像又和pbft的复杂度一样高，但是我们采用了流水线之后，就可以降低viewchange的复杂度。

chained hotStuff

图片解读：view1的leader提出了新块叶子节点b*，并且附带了上一个视图传下来的genericQC，等待收集对b*的投票形成下一个QC，然后继续传给下一个视图的leader2。
注意：这里的genericQC相当于是对b’'的证书。

参考链接：
http://t.zoukankan.com/gexin-p-12107826.html
https://www.cnblogs.com/gexin/p/12031954.html