HoneyBadger-BFT 学习

半同步共识 vs 异步共识

半同步共识协议就是基于第一种方法加强网络假设而设计的。这种方法可以让协议的设计相对简单，协议的关注点可以更多的放在安全性（safety），活性由 failure detector 来保证。比如在 PBFT 中，每个 replica 都要维护一个 timer，一旦 timeout 就会触发 view change 协议选举新的 leader。这里的 timer 就起到了一个 failure detector 的作用。由于半同步网络的假设存在，当网络恢复到同步之后，总能选出一个诚实的 leader，进而保证协议的活性。然而在异步环境下，failure detector 就会失去作用，可能导致无休止的 view change。除此之外，在工程实践中，即使底层网络能满足半同步假设的要求，但如何调节 timer 对协议的实际性能有非常大的影响。如果 timer 时间过短，那么可能导致 view change 频繁发生；如果时间过长，则可能导致网络从 partition 之后恢复较慢。

异步共识协议则完全不需要考虑 timer 的设置。为了保证协议的活性，异步协议需要引入随机源，简单来说就是当协议无法达成共识的时候，借助上帝抛骰子的方式随机选择一个结果作为最终结果。所以，异步共识的核心就是这颗common coin

HoneyBadger BFT

以 HB-BFT 为例，讨论一下异步拜占庭共识所涉及的核心技术。异步拜占庭共识由于协议设计比较复杂、通信复杂度比较高，很长一段时间都只停留在论文中，直到 2016 年 Andrew Miller 在 CCS 上发表 HB-BFT 才意味着异步拜占庭容错正式迈入可实用领域。HB-BFT 通过非常巧妙的设计将整体的通信复杂度降低到了接近于最优的 O(|B|)，前提是区块所占带宽 |B| 足够大。

HB-BFT 通过模块化的方式解决了拜占庭环境下的原子广播（Atomic Broadcast，ABC）问题，即如何保证在异步和拜占庭环境下，各个节点按相同顺序收到相同的消息。HB-BFT 首先将 ABC 分解成一个核心模块，异步共同子集（Asynchronous Common Subset，ACS）。并提出了
ACS = RBC(Reliable Broadcast) + ABA(Asynchronous Binary Agreement)
这两个子模块，并且分别针对这两个子模块找到了两个比较优化的实现，如下图所示。接下来我们讨论每个模块是如何实现的。

HB-BFT Overview

首先，我们看 HB-BFT 是如何利用 ACS 实现 ABC 的。简单来说，每个节点都参与贡献一个区块的一部分,是一个多对多的发送交易，任何对等节点在收到了交易之后都会转发交易，而 ACS 的作用就是决定哪些节点贡献的这一部分最终达成了共识。假如网络中一共有 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 个拜占庭节点），以节点 P1P1为例。如果P1P1 收到来自P2P2的 proposal（即 RBC2 成功），则 P1P1将 ABA2 的输入置为 1。当P1P1收到 N−f 节点的 proposal 时，将其它所有的 ABA 的输入都置为 0。直到所有 ABA 运行结束，将所有输出为 1 的 ABA 的汇聚成一个集合作为 ACS 的最终输出。例如，针对节点P1,P3,P4,P6,P7,P9,P10发布的 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 个节点已经收到RBC2，对于 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 的广播，因此 Bracha 的 RBC 协议的通信复杂度是$O(N2∣v∣)$ 。

在这之后，Cachin 等人在 2005 年提出了基于纠删码的 RBC 实现，将通信复杂度降低到了$O(N∣v∣+λN2log⁡N)$。HB-BFT 就是采用了这种优化的 RBC。当$∣v∣ $远大于$λNlog⁡N$ 的时候，其通信复杂度可以近似表示为$O(N∣v∣) $ 。由于$∣v∣=∣B∣/N$ ，则 HB-BFT 整体的通信复杂度可以表示为$O(∣B∣) $（|B|为整个区块的大小），也就是渐进于理论最优。

HB-BFT 中采用了基于(N-2f，N)的纠删码模式，即将一个数据块进行编码后，可以将其分成 N 份，其中只要任意 N-2f 份组合可以恢复整个数据块。消息传递的模式仍然跟传统的 RBC 类似。

ABA (Asynchronous Binary Agreement)

异步二元共识就是要在异步环境下让所有节点对于 0 或 1 达成共识。在 HB-BFT 中，每个节点都会针对其他所有节点的 RBC 是否成功进行一次二元共识，也就是说，在系统中每轮Epoch都要并行地执行 N 个 ABA 的实例。

ABA 主要满足下面几个性质：

一致性（Aggreement）。所有节点的输出相同（要么都是 0，要么都是 1）。
最终性（Termination）。如果所有正确节点都收到了输入，那么所有正确节点最终都会得到输出。
可信性（Validity）。如果任意正确节点的输出是 b（0 或 1），那么至少有一个正确节点的输入是 b。

ABA 的实现原理就是当节点无法达成一致的时候借助一个外部的随机源做决定。这个随机源就是 ABA 的核心组件（Common Coin，CC），我们也可以将 CC 理解成上帝掷骰子，只不过这个骰子只有 0 和 1 两个值。虽然只掷一次骰子可能还是无法达成共识，那么就不停掷，最终会出现所有人都达成一致的结果，所以common coin是最大的瓶颈，因为common coin是概率性的，而且common coin的多方安全计算，要求每个节点参与，在异步环境下太慢了。Common Coin 有很多实现方案，HB-BFT 针对其模块化的设计，采用了基于阈值签名的 CC 方案。每个节点对一个共同的字符串进行签名并广播给其它节点，当节点收到来自其它 f+1 个节点的签名时，就可以将这些签名聚合成一个签名，并将这个签名作为随机源。

HB-BFT vs PBFT

PBFT是部分同步版的RBC, 如果都在同步场景下，二者性能应该差不多，因为ABA一轮就结束了，大家的结果是一样的。但是，在异步场景下，HB-BFT的性能会碾压PBFT，因为在异步情况下PBFT会一直换主，始终无法推进共识，但是HB-BFT运用Common Coin,利用概率，最后收敛。