Overview

https://medium.com/@crytpol_25852/asynchronous-byzantine-fault-tolerance-a-time-independent-future-proof-byzantine-fault-f6f1a4d1f17a

Nonetheless, all these protocols employ at their core a synchronous (or partially/weak synchronous) BFT consensus algorithm which makes them unsuitable for TRULY permissionless blockchain settings where “network links can be unreliable, network speeds change rapidly, and network delays may even be adversarially induced” ¹⁷. All these BFT variants might be prepared to tolerate malfunction faults due to adversarial collusion or damage in the nodes according to the classical definition of a byzantine attack but the internet has taught us that byzantine behavior can evolve beyond to what a legacy understanding of what is a byzantine attack could have predicted. For instance, Botnetsd¹⁸ and Distributed Denial of Service (DDoS) attacks can easily be used to flood with packets an important node involved heavily in consensus and thus delaying the transmission of packets said node must send/receive for the network to achieve consensus, leading to the halting of the entire network. In this scenario is evident that synchronous consensus algorithms are susceptible to time-delayed attack due to the fact that the transmission of messages needed to achieve consensus are time-bounded. Therefore, synchronous BFT consensus algorithms are not the strongest form BFT because time-assumption are made which makes provably impossible to guarantee liveness in adversarial settings where time-based attacks are constant as can certainly happen when we use the internet¹⁹.

BFT protocols which can run in asynchronous networks are particularly robust against attacks that can be mounted over public networks. Such asynchronous BFT (aBFT) protocols ensure that transactions are processed without timing assumptions.

异步（Asynchronous）环境下只保证消息最终能够到达，但没有对于到达时间的限制。aBFT在设计上需要保证共识系统不会丧失活性。

Honey Badger BFT

核心模块→异步共同子集协议（Asynchronous Common Subset, ACS），且HB-BFT将ACS协议分割为两个子模块：

在第一阶段，每个节点使用RBC协议（Reliable Broadcast）将本地的proposal广播给其他节点；在第二阶段，每个节点都并行执行n个ABA协议（Asynchronous Binary Agreement），来共识一个位向量（用于表示哪些RBC已成功）

门限加密模块↓

Main Procedure

完整的Honey Badger BFT流程如下：

  1. 每个节点从本地交易池（buf）中随机选取$\lfloor B/N\rfloor$个交易，作为$proposed$。并使用门限加密模块Setup后的共享公钥$PK$对$proposed$进行加密→$x$；
  2. 每个节点都并行执行$\{RBC_i\}_N,\{ABA_i\}_N$，组成ACS模块。将$x$作为各自ACS模块的输入（实际上对于节点$\mathcal{P}_j$，即作为本地$RBC_j$的输入，见Figure_4），得到系统共识“YES”后的enc_proposed集合；
  3. 对Step 2输出的enc_proposed集合进行遍历处理：广播自己的秘密份额$e_j$，并通过f+1份share message解密得到明文交易集；
  4. 排序交易集，写入区块（但官方论文中的e.g. lexicographically有点迷惑哈…区块交易可以这么定序的嘛❓）
  5. 从本地交易池中remove已确认交易；

Figure_1

ACS (Asynchronous Common Subset)

Ben-Or等人设计了下述协议，来达成容量至少为$N-f$的子集共识。（$N-f$为最大容错下的诚实节点数）

for party $\mathcal{P}_i$：

  1. 本地输入，作为$RBC_i$的输入；

  2. $RBC_j$执行成功，将$ABA_j$的输入置1；

  3. 至少$N-f$个$ABA$实例执行完成时，将其他$ABA$实例输入均置0；

    上图为官方论文的解释，由此对登链社区https://learnblockchain.cn/article/2494#ACS—Asynchronous-Common-Subset-一文中该点相关的描述作出勘误：

    若在$N-f$个$RBC$实例成功后就将其他$ABA$输入置0，将可能出现以下情况：

      在诚实节点$\mathcal{P}_i$上，有诚实节点$\mathcal{P}_j$对应的$RBC_{j}$还未执行成功，但已有其他$N-f$个诚实节点对应的$RBC$执行成功➡$ABA_j$的输入置0；

      假如存在若干诚实节点本地运行的$RBC_j$出现上述$\mathcal{P}_i$的情况，导致$ABA_j$的共识过程收不到$N-f$条$Aux(1)$➡$ABA_j$的输出为0（本应该为1）；

      由于每个诚实节点本地$N-f$个$RBC$实例执行成功的顺序可能不同，因此考虑最坏情况，可能出现论文中说的”the resulting bit vector could be empty“

    回到Figure_4的实现，若改为在$N-f$个$ABA$实例成功（输出1）后，再将其余未开始执行的$ABA$输入置0，则至少能保证$size(resulting\ bit\ vector)$为$N-f$。且如果不考虑最坏情况（即某个诚实节点对应的$RBC$在很多节点上直到$N-f$个$ABA$均已输出1还未执行成功），则延迟较大的情况下将出现下述情况（仍能output 1）：

  4. 当所有$ABA$实例执行完成后，输出为1的$ABA$下标映射到最终的enc_proposed集合；

Figure_4

RBC (Reliable Broadcast)

RBC协议可保证将消息可靠地发送至网络中的所有节点。

Honey Badger BFT中的RBC协议设计如下：

  1. 本地输入，基于$(N-2f,N)$纠删码进行分割，并计算N份叶节点$\{s_j\}_N$对应的Merkle Root $h$，向节点$\mathcal{P}_j$发送$VAL(h,b_j,s_j)$

    其中$VAL$是消息类型名，$b_j$为Merkle Tree从根到$s_j$的对应分支，示例如下：

    If we would receive the block L4, we would only need Hash 1–0 and Hash 0 to verify that block L4 is valid for the root hash.

  2. 收到$VAL$包后广播对应$ECHO$包；

  3. 收到$ECHO$包后校验Merkle Tree的分支，不合法则丢弃；

  4. 当收集满$N-f$（i.e. $2f+1$）个合法$ECHO$包后，从任意$f+1$个恢复出完整的$N$个叶节点$\{s_j^{‘}\}$，并验证Merkle Root是否一致，若一致则广播$READY$包；

    Q: 为什么纠删码采用$f+1$（i.e. $N-2f$），论文中暂未找到说明

  5. 对于延迟较大的节点，若在收到$N-f$个合法$ECHO$包前，先收到了$f+1$个$READY$包，则说明至少由一个诚实节点发出，将同样广播$READY$包；

  6. 等待收到$2f+1$个$READY$包，若已收到$N-2f$个合法$ECHO$包，则恢复出对应完整输入，否则继续等待足够的$ECHO$包；

Figure_2

ABA (Asynchronous Binary Agreement)

$ABA$协议（如图示）对单个bit作出共识（r means the round number）

HB-BFT使用的ABA协议参考自

A. Mostefaoui, H. Moumen, and M. Raynal. Signature-free asynchronous byzantine consensus with t< n/3 and o (n 2) messages. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 2–9. ACM, 2014.

初始化$est_{0}$为该$ABA$实例的输入，进入下面的循环：

  1. 广播$BVAL_{r}(est_r)$；

    $BVAL$ probably means BIT_VALUE

  2. 令$bin_values_r$为空集；

  3. 当收到来自$f+1$个节点的$BVAL_r(b)$时，证明至少由一个诚实节点发出，若未发送过$BVAL_r(b)$，则广播该消息；

  4. 当收到来自$2f+1$个节点的$BVAL_r(b)$时，将$b$加入集合$bin_values_r$；

  5. 当$bin_values_r$不为空集时：

    • 广播$AUX_r(w)$，$w\in bin_values_r$；

    • 等待，直到收到$n-f$(i.e. $2f+1$)条$AUX_r$消息（其中包含的值构成集合$vals$），需要满足$vals\sub bin_values_r$；

    注意(5)在监听等待时，(3)(4)仍在运行，因此$bin_values_r$可能变化（存在部分$AUX_r$消息携带的值满足$\in bin_values_r$，被加入计数）⬅ 解释了原文为何说”this condition may be triggered upon arrival of either an AUX or an BVAL”；

    但(5)不会随着$bin_values_r$的变化再次广播 ⬅ 每个诚实节点只会选择一个$w$，广播$AUX_r(w)$；

    • 获取随机源s（见Figure_12）

    • 若$\mid vals\mid=2$，令下一轮的$est_{r+1}=s$；

      若$\mid vals\mid=1,vals=\{v\}$，令$est_{r+1}=v$，若$v=s\%2$，输出$v$，否则继续循环；

Figure_11

ABA的正确性证明可以移步https://zhuanlan.zhihu.com/p/46274211

PBFT等弱同步共识算法中若无法收到相同VOTE的$2f+1$条信息（假设$f$个拜占庭节点均不发消息，而$2f+1$个诚实节点间存在不一致VOTE👈下面解释），则引入定时器timer来解决无法达成共识的问题；

这里解释一下为什么存在诚实节点分歧👉e.g. PBFT中leader本身作恶，发给一部分节点能通过校验的区块，而发给另一部分节点不能通过校验的区块

而Honey Badger BFT异步共识算法不存在timer，并引入了随机源来解决上述问题，使得共识不会停滞（失去活性）；

HB-BFT中随机源采用的方案是对Coins’ sid的(n, f+1)阈值签名（➡ f个拜占庭节点不可能得到合法签名）；

Figure_12

Reference

Hashgraph

Hashgraph - a data structure that records who gossiped to whom, and in what order.

  • Hashgraph基础数据单元为event（包含TransactionSet、Timestamp和两个父event的HashValue）

  • Hashgraph网络下使用gossip协议进行通信，每个节点不停随机选择其他节点sync“己方已知但对方未知”的events，receiver收到sync后则创建自己的最新event（父hash分别指向self-parent和sender的最新event），并同样向随机节点sync

    因此实际上传输的是hashgraph itself，即gossip about gossip协议：

  • Hashgraph将event按round划分，首先引入前置概念：

    • See: 如果event w存在到event x的通路（有向边），则称w see x
    • Strongly see: 如果网络节点总数为n，event w可见超过2n/3个不同节点的event（且这些event均可见event x），则称w strongly see x

    对于Hashgraph下的节点，每一round中其创建的第一个event被记作witness（见证人）

    每一个event都存在对应的round created number：

    若event w的父event中最大round为r，则其round created number相应的为r或r+1（r+1当且仅当w能strongly see超过2n/3个不同节点下round r的witness➡成为新一轮witness）

Reference

  • THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE (paper)

Dumbo BFT