共识算法论文阅读笔记1-hotstuff

1.名词解释：

QC：表示一个被<span id="MathJax-Span-8" class="mrow"><span id="MathJax-Span-9" class="mo">(<span id="MathJax-Span-10" class="mi">n<span id="MathJax-Span-11" class="mo">−<span id="MathJax-Span-12" class="mi">f<span id="MathJax-Span-13" class="mo">)个节点签名确认的数据包及viewNumber。比如，对某个区块的<span class="MathJax_Preview"><span id="MathJax-Element-3-Frame" class="MathJax"><span id="MathJax-Span-14" class="math"><span id="MathJax-Span-15" class="mrow"><span id="MathJax-Span-16" class="mo">(<span id="MathJax-Span-17" class="mi">n<span id="MathJax-Span-18" class="mo">−<span id="MathJax-Span-19" class="mi">f<span id="MathJax-Span-20" class="mo">)个投票集合。

prepareQC: 对于某个prepare消息，Leader收集齐<span id="MathJax-Span-22" class="mrow"><span id="MathJax-Span-23" class="mo">(<span id="MathJax-Span-24" class="mi">n<span id="MathJax-Span-25" class="mo">−<span id="MathJax-Span-26" class="mi">f<span id="MathJax-Span-27" class="mo">)个节点签名所生成的证据（聚合签名或者是消息集合），可以视为第一轮投票达成的证据

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">lockedQC: 对于某个precommit消息，Leader收集齐<span class="MathJax_Preview"><span id="MathJax-Span-28" class="math"><span id="MathJax-Span-29" class="mrow"><span id="MathJax-Span-30" class="mo">(<span id="MathJax-Span-31" class="mi">n<span id="MathJax-Span-32" class="mo">−<span id="MathJax-Span-33" class="mi">f<span id="MathJax-Span-34" class="mo">)个节点签名所生成的证据（聚合签名或者是消息集合），可以视为第二轮投票达成的证据

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">2.算法流程

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">四阶段算法，三阶段投票

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">prepare阶段：

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">每个View开始时，新的Leader收集由<span class="MathJax_Preview"><span id="MathJax-Span-41" class="math"><span id="MathJax-Span-42" class="mrow"><span id="MathJax-Span-43" class="mo">(<span id="MathJax-Span-44" class="mi">n<span id="MathJax-Span-45" class="mo">−<span id="MathJax-Span-46" class="mi">f<span id="MathJax-Span-47" class="mo">)个副本节点发送的NEW-VIEW消息，每个NEW-VIEW消息中包含了发送节点上高度最高的prepareQC(如果没有则设为空)。

Leader从收到的NewView消息中，选取高度最高的preparedQC作为highQC。因为highQC是viewNumber最大的，所以不会有比它更高的区块得到确认，该区块所在的分支是安全的。

Leader节点会在highQC所在的安全分支来创建一个新的区块，并广播proposal，proposal中包含了新的区块和highQC，其中highQC作为proposal的安全性验证。

其他节点（replica）一旦收到当前View对应Leader的Proposal消息，Replica会根据会safeNode-predicate规则检查Proposal是否合法。如果Proposal合法，Replica会向Leader发送一个Prepare-vote（根据自己私钥份额对Proposal的签名）。

由于比较的是lockedQC，因此第一轮投票可以反悔（safety判断规则对比的是lockQC，而不是第一轮投票的结果，所以即使在上一轮针对A投了prepare票，假如A没有commit，那么下一轮依然可以对A’投票，所以说第一轮投票可以反悔。）

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">precommit阶段：

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">Leader发出proposal消息以后，等待<span class="MathJax_Preview"><span id="MathJax-Span-55" class="math"><span id="MathJax-Span-56" class="mrow"><span id="MathJax-Span-57" class="mo">(<span id="MathJax-Span-58" class="mi">n<span id="MathJax-Span-59" class="mo">−<span id="MathJax-Span-60" class="mi">f<span id="MathJax-Span-61" class="mo">)个节点对于该proposal的签名，集齐签名后会将这些签名组合成一个新的签名，以生成<em>prepare-QC</em>保存在本地，然后将其放入PRECOMMIT消息中广播给Replica节点。

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo"><span class="MathJax_Preview"><span class="math"><span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">当Replica收到Precommit消息时，会对其签名，然后回复给leader。

• 在HotStuff中，一轮投票的过程，是通过replica与Leader的交互完成

  • replica收到proposal，对其签名后，发送给Leader
  • Leader集齐签名（投票）后，将签名（投票）组装，广播precommit消息
  • replica收到Precommit，验证其中签名，验证通过则表示第一轮投票成功。

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">commit阶段；

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">Leader先收集(n-f)个precommit-vote，然后将其组合为precommit-QC,并将其放在COMMIT消息中广播。

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">当Replica收到COMMIT消息时，会对其签名commit-vote，然后回复给leader。更为重要的是，在此时，replica锁定在precommitQC上，将本地的lockQC更新成收到的precommitQC.

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo"><br data-mce-bogus="1">

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">decide阶段:

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">当Leader收到了（n-f）个commit-vote投票，将他们组合成commitQC，广播DECIDE消息。

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">Replica收到DECIDE消息中的commitQC后，认为当前proposal是一个确定的消息，然后执行已经确定的分支上的tx。Viewnumber加1，开始新的阶段。

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo"><br data-mce-bogus="1">

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo"><br data-mce-bogus="1">

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo"><br data-mce-bogus="1">

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">综上所述：hotstuff之间只有leader和replica之间的信息传递，而PBFT中不同replica之间也是可以进行消息传递的

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo"><br data-mce-bogus="1">

<span class="mrow"><span class="mo"><span class="mi"><span class="mo"><span class="mi"><span class="mo">chained hotstuff流程：

• 非Leader节点
  • 等待来自Leader的Proposal消息
  • 收到Leader的Proposal消息后，检查消息中的QC，更新本地的prepareQC、lockedQC等变量，发出投票
  • 向下一Leader发出NewView消息

• Leader节点
  • 等待NewView消息，然后发出Proposal
  • 发出Proposal后，等待其他节点的投票
  • 向下一个Leader发出NewView消息

正常情况下，每个View中都有一个区块产生并集齐签名，但是情况不会总是这么完美，有时不会有新的区块产生。为了保持区块高度与viewNumber的一致，hotStuff中引入了Dummy block的概念。假如在一个View中，不能达成共识，那么就在为该View添加一个Dummy block。