【异步共识（2）】-“HB-BFT”
果真大家还是喜欢热点，基础原理讲解点击率是真萧条
不过今天这一期是继异步共识基础上，想详细介绍从HB到Dumbo的改进。(Dumbo见下期)
HB-BFT 通过模块化的方式解决了拜占庭环境下的原子广播（Atomic Broadcast，ABC）问题，即如何保证在异步和拜占庭环境下，各个节点按相同顺序收到相同的消息。HB-BFT 首先将 ABC 分解成一个核心模块，异步共同子集（Asynchronous Common Subset，ACS）。之后将 ACS 分解成了 RBC(Reliable Broadcast) + ABA(Asynchronous Binary Agreement)两个子模块，并且分别针对这两个子模块找到了两个比较优化的实现.
假如网络中一共有 10 个节点，每个节点维护了一个交易池作为接收来自客户端交易的缓冲池，每个区块包含 B = 100 个交易。
- 每个节点首先从本地的交易池中选取前 100 个合法的交易，之后再从这 100 个交易中随机选择 100/10=10 笔交易作为自己的 proposal。这里之所以每个节点只选择 B/N 笔交易是为了降低通信复杂度，而之所以采用随机选取的方式，是为了降低每个节点选择重复交易的概率。
- 通过一个共享公钥（阈值签名）将 proposal 加密，交易的内容直到共识结束后（收到了来自 f+1 个 share）才能被解密，从而防止了审查攻击（censorship attacks）。
- 每个节点将加密后的 proposal 作为 ACS 模块的输入，输出就得到了一个“名单”，记录了有哪些节点提交的 proposal 成功得到共识。
- 之后通过一系列的解密操作就得到了最终确认的区块。
ACS (Asynchronous Common Subset)
接下来我们讨论 HB-BFT 的核心——ACS 模块是如何实现的。ACS 可以被分解成 RBC(Reliable Broadcast) 和 ABA(Asynchronous Binary Agreement) 两个子模块。每个节点首先将本地的 proposal 通过 RBC 发送到其它节点，之后每个节点针对每个 RBC 的实例成功与否（0 或 1）执行一次 ABA。也就是说，每个节点都要并行运行 N 个 ABA 的示例（每个节点的 proposal 一个），每个 ABA 的输出 0 或 1 表示是否所有正确节点都认为这个 proposal 最终应该成为区块的一部分。
ACS 的运行流程如下图所示。假如一共有 N=10 个节点（最多容忍 f=3 个拜占庭节点），以节点P1为例。如果 P1 收到来自P2的 proposal（即 RBC2 成功），则 P1将 ABA2 的输入置为 1。当 P1收到 N−f 节点的 proposal 时，将其它所有的 ABA 的输入都置为 0。直到所有 ABA 运行结束，将所有输出为 1 的 ABA 的汇聚成一个集合作为 ACS 的最终输出。例如，针对节点10个p节点 发布的 proposal 对应的 ABA 的结果如果是 1 的话，ACS 的最终输出可以是（1，3，4，5，6，7，9，10）。ACS 保证所有正确节点都得到相同的输出。
下图展示了 ACS 在执行过程中的三种情况。在正常情况下，RBC1 结束比较早，相对应的 ABA1 的输入为 1（yes），其输出也是 1。第二种情况，RBC2 结束的比较慢，在相对应的 ABA2 开始的时候（其它 N-f 个 RBC 成功之后）RBC2 还未结束，ABA2 的输入为 0（No），但由于其它 N-f 个节点对于 ABA2 的输入为 1，最终 ABA2 的输出也是 1，同时保证节点能够最终收到 RBC2 的 proposal。第三种情况，RBC3 失败，当其它 N−f 个 RBC 成功之后，节点对 ABA3 的输入为 0，最终 ABA3 的输出也是 0。
RBC (Reliable Broadcast)
可靠广播 RBC 可以确保源节点能够可靠地将消息发送到网络中的所有节点。具体来说，RBC 主要有以下三个性质：
- 一致性（Agreement）。任意两个正确节点都收到来自源节点的相同的消息。
- 全局性（Totality）。只要有一个节点收到了来自源节点的消息，那么所有正确的节点最终都能收到这个消息。
- 可信性（Validity）。如果源节点是正确的，那么所有正确的节点收到的消息一定与源节点发送的消息一致。
抗拜占庭的 RBC 最早由 Bracha 于1987年首次提出，并得到了广泛应用，其消息传递的示意图如下。RBC 主要分成 Initiate、Echo、Ready 三个阶段，其中后两个阶段各经历一次 all-to-all 的广播。
HB-BFT 中采用了基于(N-2f，N)的纠删码模式，即将一个数据块进行编码后，可以将其分成 N 份，其中只要任意 N-2f 份组合可以恢复整个数据块。消息传递的模式仍然跟传统的 RBC 类似。
ABA (Asynchronous Binary Agreement)
异步二元共识就是要在异步环境下让所有节点对于 0 或 1 达成共识。在 HB-BFT 中，每个节点都会针对其他所有节点的 RBC 是否成功进行一次二元共识，也就是说，每轮共识都要并行地执行 N 个 ABA 的实例。
ABA 主要满足下面几个性质：
- 一致性（Aggreement）。所有节点的输出相同（要么都是 0，要么都是 1）。
- 最终性（Termination）。如果所有正确节点都收到了输入，那么所有正确节点最终都会得到输出。
- 可信性（Validity）。如果任意正确节点的输出是 b（0 或 1），那么至少有一个正确节点的输入是 b。
ABA 的实现原理就是当节点无法达成一致的时候借助一个外部的随机源做决定。这个随机源就是 ABA 的核心组件（Common Coin，CC），我们也可以将 CC 理解成上帝掷骰子，只不过这个骰子只有 0 和 1 两个值。虽然只掷一次骰子可能还是无法达成共识，那么就不停掷，最终会出现所有人都达成一致的结果。Common Coin 有很多实现方案，HB-BFT 针对其模块化的设计，采用了基于阈值签名的 CC 方案。每个节点对一个共同的字符串进行签名并广播给其它节点，当节点收到来自其它 f+1 个节点的签名时，就可以将这些签名聚合成一个签名，并将这个签名作为随机源。
HB-BFT 性能测试
节点部署在广域网，分布在五个大洲，每个交易大小为 250 字节，总结点数 N = 4f，其中 f 为故障节点数，不考虑拜占庭行为。
我们看 HB-BFT 跟 PBFT 吞吐量的对比，如下图所示。我们可以看到在节点数为 8、16 的时候，两者差别不大，但随着节点个数增加，PBFT 的吞吐量有明显下降，而 HB-BFT 则几乎没有什么变化。这是由于 PBFT 是由 leader 将区块发布给其他节点，当节点数增加的时候，leader 的带宽逐渐成为瓶颈，而 HB-BFT 则不存在 leader 的概念，每个节点都贡献区块的一部分，因此吞吐量受网络规模影响不明显。
HB-BFT 的吞吐量-延迟表现情况，可以明显看到，随着网络规模增加，协议的基础延迟明显增加。当网络规模达到 104 个节点的时候，协议的基础延迟增加到 600s。之所以协议的延迟对网络规模这么敏感是因为在每轮共识中，每个节点都要运行 N 个 ABA 的实例，而每个 ABA 的实例都要校验 o(N^2)个阈值签名，因此计算复杂度非常高，随着网络规模增加，首先到达瓶颈的是 CPU，而不是带宽。
而下期的 Dumbo 就是在这个发现的基础上对 HB-BFT 的延迟进行了优化。
参考：[1]https://zhuanlan.zhihu.com/p/362845060
[2] The Honey Badger of BFT Protocols