HotStuff 协议的理解

发表于 | 分类于 | 次阅读

HotStuff 协议的理解

简介

HotStuff是继 PBFT 之后 BFT 共识协议中又一里程碑。它具有更低的消息复杂度和更好的扩展性。它的优点如下：

  1. 将共识节点之间完成一轮共识的消息复杂度降低到 O(n)\mathcal{O(n)} 级别，其中 nn 表示消息的数量。与之相比，PBFT中共识节点完成一轮共识的消息复杂度是 O(n2)\mathcal{O(n^2)} 级别。
  2. 将更换主节点的消息复杂度降低到 O(n)\mathcal{O(n)} 级别。与之相比，PBFT中更换主节点的消息复杂度是 O(n3)\mathcal{O(n^3)}。

HotStuff 协议的第一个优点使得它具有更好的扩展性，即当共识组中共识节点数量线性增加时，节点间进行共识的消息复杂度仅仅是线性增加。做过分布式共识实验的都知道，当节点数量增加到 16 以上时，PBFT 协议的每秒处理交易的量（Transaction Per Second，TPS）会由比较明显的衰退，造成这一现象的主要原因是节点间通信消息的复杂度平方级上涨。但是 HotStuff 中节点数量增加时TPS 的衰减的更加缓慢一些。

HotStuff的第二个优点使得能够频繁的切换主节点，带来的好处是使得整个共识组中每个节点都能拥有排序的权力，这能打破主节点对排序权的垄断。与之相比，PBFT 协议中只有主节点出现故障时共识组才会更换主节点。

关键概念和数据结构

关键概念

HotStuff 有 3 个版本，分别使 Basic HotStuff、Chained HotStuff 以及 Event-driven HotStuff，下面分别介绍之。在介绍前，需要介绍一些关键概念。

本文将发起提议的节点称之为主节点，将其他节点称之为从节点，被排序的内容称之为命令。

数据结构

Node

一个 node 对应一个提议（proposal），主要包含如下两部分内容：

  • parent，它的前一个提议的哈希值。
  • cmd，该提议包含的命令。

QC

QC 全称为 quorum certificate，是 HotStuff 中一个重要概念，翻译为足量的证书，QC 主要包含如下数据：

  • type，该 QC 的命令类型。
  • view Number，视图编号，节点本地的视图用 CurView 表示。
  • node，我更愿意称之为提议，每个 node 包含两个内容：一条来自客户端的命令（cmd）以及它的前一个 proposal 的摘要（digest）。摘要实际上是数据的哈希值。
  • sig，由（n-f）个节点签名联合组成的一个门限签名，这个签名证明该证书被绝大多数节点认可。

QC 的主要目的是作为一个可靠证明，表示当前 QC 中包含的命令以及提议被绝大多数节点接收。因为 QC 中的 sig 有 n−fn-f 个节点的签名聚合而成，通过验证 QC 中的签名的合法性，就能知道该 QC 对应的提议是否被其他节点接受。

MSG

主节点向其他节点发送的消息被称之为 MSG，MSG 主要包含如下数据：

  • type，消息类型。
  • viewNumber，消息对应的视图编号。
  • node，消息对应的提议。
  • justify，实际其类型是一个 QC，文中将其称之为 justify。

VoteMSG

从节点向主节点的 MSG 进行投票时发送的消息，主要包含如下数据：

  • MSG，主节点发送的消息内容本身。
  • partialSig，从节点对MSG 中 type、viewNumber 和 node 部分签名。

curView

curView 表示每个节点本地的视图，它是一个局部变量，不同的节点之间的视图编号会有所不同。

⊥

⊥ 符号在 HotStuff 的论文中经常出现，表示空值的含义。

Basic HotStuff

HotStuff的主要运行过程如下图所示。其中 R0 作为 leader，负责发起共识提议，R1、R2和R3负责投票。

HotStuff

New-Veiw

HotStuff 中一轮新的共识开始，都是以主节点收集 n−fn-f 个 NEW-VIEW 消息开始。

共识开始时， R1、R2和R3向新任的主节点发送一个 new-view 消息，NEW-VIEW 消息表示其他节点即将过渡到最新的一个视图中。**NEW-VIEW **中包含一个重要的内容，即 prepared QC。 prepare QC 是节点在执行共识算法过程中生成的，后续的步骤中读者自会知晓。

当主节点至少收到 n−fn-f 个 prepare QC 后，从中选择出具有最高视图编号的 prepare QC，并以该 prepare QC 中的 node 作为父节点，并在该 node 之后创建一个新的 node，新的 node 中包含一条客户端的命令以及它的父 node 的哈希值。随后主节点将 prepare QC、node 等这些信息生成一条 PREPARE 消息中，然后将其广播给其他节点。PREPARE 消息的结构如下所示，分别表示消息的类型、视图编号、提议内容和 prepare QC。

MSG= <PREPARE,CurView, NODE, PREPARE QC>

当从节点收到一条 PREPARE 消息后，开始进行检查，主要检查如下三项内容：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 prepare，并且视图编号正确。
  2. proposal 是 prepare QC 的子节点。
  3. safeNode 检查，内容如下：
    1. proposal 是节点本地 locked QC 的子节点，安全性规则。
    2. prepare QC 的视图编号大于 locked QC 的视图编号，活性规则。

当上述三项检查全部通过时，从节点向主节点发送一条投票消息 （VoteMSG）。

与 prepare QC 相同， locked QC 也是节点在执行共识过程中生成的，后续步骤中读者自会知晓。

PRE-COMMIT

当主节点至少收到 n−fn-f 个 VoteMSG 时，将这些所有消息的 partialSig 部分进行聚合后形成一个门限签名，以此构建一个 QC，它的 type 为 commit，因而称之为 commit QC，随后主节点构建一个 PRE-COMMIT 消息，该消息内容如下：

MSG = <PRE-COMMIT, CurView,NODE = None, commitQC>

主节点将该消息广播给所有节点。

从节点收到该消息后，进行如下检查：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 pre-commit，并且视图编号正确。
  2. 消息中 QC 的类型为 prepare，并且其视图编号为当前视图编号。

当通过上述检查时，从节点本地记录 prepare QC = MSG.QC。

此外，从节点还会生成一个 VoteMsg 并发送给主节点，其内容如下：

VoteMSG=<MSG, partial sig>

COMMIT

当主节点收到至少 n−fn-f 个 VoteMSG 时，将这些所有消息的 partialSig 部分进行聚合后形成一个门限签名，以此构建一个 QC，它的 type为 pre-commit，因而称之为 precommit QC。随后主节点向从节点广播一条 COMMIT 消息，该消息内容如下：

MSG=<COMMIT, CurView, NODE = None, precommit QC>

当从节点收到主节点的 COMMIT 消息后，进行如下检查：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 commit，并且视图编号正确。
  2. 消息中 QC 的类型为 pre-commit，并且其视图编号为当前视图编号。

当通过上述检查时，从节点本地记录 locked QC = MSG.QC。

此外，从节点还会生成一个 VoteMsg 并发送给主节点,其内容如下：

VoteMSG=<MSG, partial sig>

DECIDE

当主节点收到至少 n−fn-f 个 VoteMSG时，将这些所有消息的 partialSig 部分进行聚合后形成一个门限签名，以此构建一个 QC，它的 type 为 commit QC，以内称之为 commit QC。随后主节点向从节点广播一条 DECIDE 消息，该消息内容如下：

MSG=<DECIDE, CurView, NODE = None, commit QC>

当从节点收到主节点的 DECIDE 消息后，进行如下检查：

  1. 该消息发送自当前视图编号对应的主节点，消息类型为 decide，并且视图编号正确。
  2. 消息中 QC 的类型为 commit，并且其视图编号为当前视图编号。

当通过上述检查时，节点开始执行 QC 中对应的 node 的命令。与此同时，节点本地的当前视图编号自增一（++curView），随后向下一任主节点发送 NEW-VIEW 消息以开启下一轮共识，它的消息内容如下：

MSG=<NEW-VIEW, curView，⊥，prepare QC>

Chained-HotStuff

可以发现，Basic HotStuff 中主节点在提议阶段主要作用是构建新的提议并选择最新的 QC，其他阶段主要作用是组合新的 QC 并广播给其他节点，那么为什么不令主节点在每个阶段都做出一个新的提议呢？基于这个思路，就产生了链式的 HotStuff，即文中的 Chained-HotStuff。在 Chained-HotStuff 中不再区分每个阶段的 QC ，而是统一称之为 Generic QC。主要运行过程按照角色划分，主要过程如下：

主节点

根据从节点的投票信息，从中选择出视图编号最大的 QC，在此 QC 之后创建一个新的提议消息并广播给其他节点，消息类型如下：

MSG=<GENERIC, CurView, NODE, GENERIC QC>

从节点

从节点收到 GENERIC 消息之后，检查如下信息：

  1. 消息类型为 GENERIC ，并且其视图编号和本地视图编号一致并且来自于对应的主节点。
  2. 使用 SAFENode 规则验证当前提议NODE 和 NODE 的父节点的正确性，如果通过，则向下一个视图的主节点发送投票消息 VOTEMSG=<MSG, partialSig>。
  3. 沿着其中的链式规则，找到一系列的提议 b->b’->b‘’->b*，进行如下验证和处理：
    1. 如果 b* 的父节点是 b“，那么记录 prepare QC = b*.justify
    2. 如果 b* 的父节点是 b“ 并且 b’‘ 是 b‘ 的父节点，那么记录 locked QC = b’.justify
    3. 如果 b* 的父节点是 b“ 并且 b’‘ 是 b‘ 的父节点并且 b 是 b‘ 的父节点，那么执行 b.justify 中的提议，并且向客户端返回执行结果。

View-Change

在等待消息期间，如果发生超时，节点本地视图 curView 自增，随后向对应的主节点发送 NEXT-VIEW 消息，内容如下：

MSG=<GENERIC, CurView, NODE=none, GENERIC QC>

说明

  1. 每个特定的视图编号下最多确认一个提议。因为当一个提议被确认时视图编号就会加一，当某个视图下没有达成共识时引起超时，此时视图继续增加一。
  2. prepare QC 表示一条命令处于准备状态，并且这个准备状态已经被绝大多数节点承认。它的主要作用在发生 view-change 时，令新任的主节点在最新的处于准备状态的命令的基础上进行提议，这样能最大化利用前任主节点的共识工作。但是由于处于准备状态，这条命令也可能会被新任主节点作废。locked QC 表示指令处于锁定状态。锁定状态表示该指令已经被锁定为下一个需要执行的指令，它一定会绝大多数节点执行。

Q&&A 环节

  1. 为什么 new-view 中使用 prepare QC 作为切换视图的依据，locked QC 可以吗？

    locked QC 是完全可以的，因为当一个 node 具有 locked QC 时，那么必然有 prepare QC，因此，使用 locked QC 也可以作为 new-view 中的根据。

  2. 在切换视图时，为什么使用 prepare QC 而没有使用 locked QC 呢？

    使用 prepare QC 能够最大化利用被替换的主节点在共识过程中做的工作。节点本地存储的locked QC 和 prepare QC 有两种可能的情况：

    1. locked QC 和 prepare QC 指向同一个提议。
    2. locked QC 指向提议 A，prepare QC 指向提议 B。此时提议 B 必然是提议A 的一个子孙提议，区别是 A已经被共识锁定，但是 B 没有被共识锁定。如果在 new-view 消息中使用 locked QC，那么新任主节点的新提议会废掉提议 A。实际上，因为 A 已经获得 prepare QC，那么在 B 的基础上继续提议是更好的选择。需要说明的是，实际上，如果主节点执意选择在 locked QC，即 A 处进行新的提议 B‘，其他节点也会接受这一提议，因为新的提议也能通过 safeNode 函数的检查。因为新的提议 B’ 也是绝大多数节点 locked QC（也就是A）的子节点。

    综上，使用 prepare QC 能够最大化利用前任主节点的共识工作。

  3. 为什么 HotStuff 中 commit 步骤之后可以达到和 PBFT 中 commit 步骤相同的作用，那么为什么 HotStuff 中还会额外增加 decide 步骤呢？

    这一步骤的作用是降低 HotStuff 中 new-view 消息的复杂度，也正是这一步骤，将 HotStuff 中更换主节点的消息复杂度降低到了 O(n) 级别。

    假设我们去掉 decide 阶段，并且令节点在 commit 阶段收到主节点的 commit 消息之后，不再继续向主节点发送 commit-vote 消息，而是直接执行该命令。

    现在考虑一种场景，假设视图编号为 v 的主节点是拜占庭节点，它将 commit 消息只发送给 f−1f-1 个节点，这 ff 个节点（主节点和 f−1f-1个节点）更新了 locked QC，并且执行 commit 消息对应的命令。

    随后出现超时， HotStuff 中节点向下一任主节点发送 NEW-VIEW 消息，每个节点发送最新的 prepare QC，其中ff个节点发送视图编号为 v 的prepare QC，n−fn-f 个节点发送视图编号为 v-1 的 prepare QC。

    新任主节点在收到 n−fn-f 个 new-view 消息后从中选择出 prepare QC 中视图编号最大的一个 QC，随后在这个 QC 后生成新的 proposal，并将其放入 PREPARE 消息广播给其他节点。需要注意的是，PREPARE 消息只包含主节点挑选的视图编号最大的 QC而并非 n−fn-f 个 QC。PREPARE消息中的 QC 到底是不是 n−fn-f 个 new-view 消息中视图编号最大的 QC 是没有办法证明的。

    从全局视角看，视图编号最大的 prepare QC 的视图编号为 v，但是主节点可以选择视图编号为 v-1 的一个 prepare QC。此时该主节点在视图编号为 v-1的QC后面提出一个新的提议，然后构建一个 PREPARE 消息（该消息的视图编号是 v+1）后广播给其他节点。其中最大prepare QC 的视图编号为 v 的ff 个节点会拒绝投票（safeNode 函数中安全规则无法通过），但是剩余的 n−fn-f 个最大视图编号为 v-1 的节点会接收这一提议。这就造成不一致，即 HotStuff 更换主节点的方法会导致 commit 阶段执行命令时会出现系统安全性问题。

    因此，解决办法有两种（任选其一）：

    1. 增加一个 decide 阶段，保证一个命令被执行前，绝大多数节点都会锁定该命令，即绝大多数的节点的 locked QC 都是该命令。在 HotStuff 中的 decide 阶段，节点收到 commit QC 时，可以确认绝大多数节点的 locked QC 都是该命令，那么就可以安全的执行该命令,这种方法的弊端是，一条命令的确认时间增加了一个round tripe。
    2. 在主节点的 PREPARE 中附带上 n−fn-f 个 prepare QC 以方便从节点验证主节点挑选出来的视图编号最大的 QC 确实是全局视角下视图编号最大的 QC，但是这种方法带来的弊端就是 PREPARE 消息的复杂度直接变为 O(n2)\mathcal{O(n^2)} 。

    在 HotStuff 中选择了第一种解决办法，因为命令确认额外增加的时间延迟，可以通过chained-HotStuff 比较好的解决。

  4. HotStuff 中的 pacemaker 具体是如何工作的？

参考资料

  1. HotStuff arxive 论文

共识协议需要确定的若干个步骤

  1. 确定新提议是什么?

  2. 发现有足够节点确定了新提议后,预先提交下一个提议(局部)

  3. 有足够多的节点预先提交了新提议,正式提交新提议(局部)

  4. 有足够多的节点正式提交新提议,确定新协议被确认(全局)

  5. L-BFT 协议为什么需要view-change?

    1. 主节点出现故障时,必须从已有的节点中选择出最新的 主节点以保证共识能够继续。

  6. view-change 时最新的 leader 应该在哪个状态的基础上再次进行共识？

    1. 假设通过投票确定最新的 leader，那么应该以投票信息中所有节点的最新状态为准，这样能够避免最新 leader 推翻前任 leader 的共识结果。
    2. 最新状态应该是可验证的，例如每个节点投票新 leader 时，将本地最新的 2f+1 个 prepare 消息发送给新的 leader。

  7. view-change 时需要注意的点

    1. view-change 的时候，一定不能回滚已经确认的共识消息。