一个Byzantine容错的分布式共识协议研究与实现
简单实现了hbbft算法
本设计项目分为两大部分：HoneyBadgerBFT算法实现部分和算法测试部分。由图3-1所示的代码目录结构，hbbft目录下是算法实现部分，test目录下是算法测试部分。HoneyBadgerBFT算法中的各个部分的实现对应于hbbft目录下同名文件，其余部分是各个组件通用结构和存储结构。测试主要是通过修改总节点数、每轮最大提交事务数batchSize来测试算法数据。
HoneyBadgerBFT概述
如果对区块链比较了解，那么蜜獾（平头哥）应该不会陌生，比特币就称为蜜獾的钱，指动物的恢复能力强且无所畏惧。为了纪念蜜獾这种象征，Honey Badger Byzantine Fault Tolerant Protocol诞生了。 假设网络系统的总节点数为N，每个节点都有一个唯一的id。节点接收事务作为输入，它们的目的就是达成某种特定顺序的事务的共识。HoneyBadgerBFT特别适合已许可区块链的部署方案，其中事务可以由任意的客户端提交，但负责执行协议的节点是固定数量的。原子广播语义允许我们抽象出任何特定于应用程序的细节，比如如何对事务进行内部预处理，在实现中，事务只是一个随机值。当一个事务一旦被节点输出的时候，就会被认为该事务是提交的。HoneyBadgerBFT的系统模型会有以下假设：
（1）纯异步网络：假设每个节点都通过可靠的点对点网络通道连接，消息不会丢失，即消息最终都会被传递。由于网络节点中的消息会以任意顺序排列，假设节点会有无限的缓存区且能处理所有接收到的消息。
（2）静态拜占庭错误：恶意节点最多有f个，且总节点数N满足N大于等于3f+1。
（3）受信任的设置：假设节点可以在协议的初始阶段与受信任的处理者交互，这个阶段将用于建立公钥和私钥共享。
异步性是HoneyBadgerBFT最重要的特性之一，传统的PBFT算法会依赖于网络传输的延迟在一定的范围内，所以PBFT算法的实现里面需要一个计时器，类似TCP协议里的超时定时器，当这个定时器超时就会触发超时操作。 HoneyBadgerBFT的每个节点没有像Raft算法那样区分是否是领导节点，即主节点，每个节点都公平地接收事务，并且，每个节点上都会各自维护事务池。每轮开始的时候，随机在事务池里选出一部分事务，用Asynchronous Common Set来发送这些事务。
HoneyBadgerBFT是一个拜占庭容错的共识算法，如图2-1的总体框架图所示，HondyBadger算法由几个组成部分，HoneyBadger、Asynchronous Common Set、Reliable Broadcast和Byzantine Binary Agreement。整个算法大概分为三个步骤：
（1）每个节点从输入的事务中随机选择一批事务，并使用公钥加密，启动N个原子广播的实例（N为系统中节点个数），在某一个原子广播完成以后将该广播对应的节点编号作为输入启动异步公共子集协议ACS。
（2）ACS协议在收集到足够多的节点发来的事务后终止，所有正常节点会达成一个关于事务子集的共识。
（3）解密达成共识的事务子集，提交达成共识的事务。
从算法的大概步骤可以看出，HoneyBadgerBFT的核心部分由两部分组成，分别是原子广播和异步通用子集协议ACS。
HoneyBadgerBFT的总体架构图：
各个部分分别实现的功能如下：
（1）HoneyBadger（HB）：从应用接收交易请求并且将请求放入缓存排队，HB还会管理通过epoch来区别每次共识。每次有一个新的epoch开始，HB都会在这次交易请求中带上一批事务，并传给ACS。
（2）Asynchronous Common Set (ACS)：异步公共子集用RBC和BBA来达成事务子集的共识。
（3）Reliable Broadcast (RBC)：将单个节点的事务分发到网络中的其余节点。RBC的结果是网络中所有节点的事务的总和。RBC保证每个节点得到相同的输出，即使发送方或其他节点尝试向不同节点发送不同的信息。
（4）Byzantine Binary Agreement (BBA)：根据来自网络中所有节点的投票组合来确定该事务子集是否包含在事务集合中。一旦超过2/3的参与节点同意是否将事务子集包含在集合中，BBA就完成。
算法总体流程
在算法实现中，为了简化网络系统，系统中每个节点通过一个公共的通道来进行消息传递，而没有采用实际实现的网络传输。每个节点都有一个唯一的标识和一个存储事务的缓冲区，并且每个节点都会运行一个HoneyBadgerBFT算法的实例。每个节点的事务存储都是基于内存的，生成的事务区块也没用数据库或者文件的形式存储下来，这是因为这些数据对于算法来说是不需要关心的，我关注的点在如何达成共识上，实现的事务也只是用一个随机的数值来表示。
HoneyBadgerBFT算法实现的总体流程如下：
（1）创建N个节点，并初始化节点的HoneyBadger和事务缓存区。
（2）对于每个节点，起三个协程：一个协程每隔一段时间随机产生一批事务，并输入到每个节点的HoneyBadger实例中；一个协程启动HoneyBadger实例，HoneyBadger实例开始运作（详细过程见3.3）；一个协程每隔一段时间拿到HoneyBadger实例的输出，删掉HoneyBadger实例事务缓冲区里已经提交的事务。
（3）接着用一个死循环从公共的消息通道获取消息，触发HoneyBadger的处理函数，如此循环。
（4）当HoneyBadger有输出时，计算已提交的事务数量。
HoneyBadgerBFT算法实现总体流程图：
HoneyBadger
HoneyBadgerBFT算法中，节点接收交易作为输入并且存储在它们的缓冲区中。协议在epoch中执行，在每个epoch之后会有新的一批交易添加到提交日志中。
HoneyBadgerBFT使用的是异步通用子集（Asynchronous Common Subset，ACS），ACS原语允许每个节点提出一个值，并保证每个节点输出一个包含至少N-2f个正确节点的输入值的公共向量。这个会带来两个挑战：
（1）实现审查弹性难度较大。ACS的开销直接依赖于每个节点提出的交易，可以通过每个节点提出不相交集合的交易来提高效率，因此，平均每个交易只会被一个节点提出。但是这样实现会带来审查弹性的损害，因为ACS语义允许敌方选择哪些提出的交易最后会被提交，所以敌方可以选择性地审查交易。HoneyBadgerBFT通过阀值加密来避免，可以防止敌方节点了解哪些节点提出了什么交易。
（2）实际的吞吐量的不确定性。尽管ACS理论上是可行性，但实际的性能方面还没有定论。
在HoneyBadger实例中，包含节点最基本的配置项：节点数、恶意节点数、当前epoch、该节点唯一id、其余节点的id、提出一批事务的数量最大值，每个epoch对应的ACS实例，存储事务的缓存区，记录每个epoch对应的提交的事务，还有一个用于不同协议之间传递的消息列表。
HoneyBadger实现的总体流程如下：
（1）开始运行HoneyBadger之后，在之前就已经输入到事务缓存区的事务里随机选出一批事务，并输入到ACS实例（详细过程见3.4）里。
（2）HoneyBadger的处理函数依赖于ACS的处理函数，如果HoneyBadger当前的epoch（每轮共识的周期数）与请求的epoch相等的话，则取出ACS中的输出并记录，清理掉事务缓存区含结果的部分，然后epoch加一；如果epoch不相等，则清理无效的ACS，不做其它处理。
HoneyBadgerBFT算法中，节点接收交易作为输入并且存储在它们的缓冲区中。协议在epoch中执行，在每个epoch之后会有新的一批交易添加到提交日志中。 HoneyBadgerBFT使用的是异步通用子集（Asynchronous Common Subset，ACS），ACS原语允许每个节点提出一个值，并保证每个节点输出一个包含至少N-2f个正确节点的输入值的公共向量。这个会带来两个挑战：
（1）实现审查弹性难度较大。ACS的开销直接依赖于每个节点提出的交易，可以通过每个节点提出不相交集合的交易来提高效率，因此，平均每个交易只会被一个节点提出。但是这样实现会带来审查弹性的损害，因为ACS语义允许敌方选择哪些提出的交易最后会被提交，所以敌方可以选择性地审查交易。HoneyBadgerBFT通过阀值加密来避免，可以防止敌方节点了解哪些节点提出了什么交易。
（2）实际的吞吐量的不确定性。尽管ACS理论上是可行性，但实际的性能方面还没有定论。
在HoneyBadger实例中，包含节点最基本的配置项：节点数、恶意节点数、当前epoch、该节点唯一id、其余节点的id、提出一批事务的数量最大值，每个epoch对应的ACS实例，存储事务的缓存区，记录每个epoch对应的提交的事务，还有一个用于不同协议之间传递的消息列表。
HoneyBadger实现的总体流程如下：
（1）开始运行HoneyBadger之后，在之前就已经输入到事务缓存区的事务里随机选出一批事务，并输入到ACS实例（详细过程见3.4）里。
（2）HoneyBadger的处理函数依赖于ACS的处理函数，如果HoneyBadger当前的epoch（每轮共识的周期数）与请求的epoch相等的话，则取出ACS中的输出并记录，清理掉事务缓存区含结果的部分，然后epoch加一；如果epoch不相等，则清理无效的ACS，不做其它处理。
HoneyBadger实现大致流程图：
Asynchronous Common Set
Asynchronous Common Set（ACS）算法是HoneyBadgerBFT的基础和核心部分，由上面的算法流程可以看出，HoneyBadger还只是做了消息的加密解密操作，以及事务随机选择的处理，这些处理是为了提高算法的吞吐量，但是达成共识的部分还没有接触到。
ACS满足以下三个特性：
（1）合法性。如果一个诚实节点输出一个集合v，则集合v的元素个数大于等于N-f且集合v包含至少N-2f个诚实节点的输入。
（2）一致性。如果一个诚实节点输出集合v，则每个节点都会输出集合v。
（3）整体性。如果N-f个诚实节点接收一个输入，则所有诚实节点会产生一个输出。
ACS协议由两个协议组成：Reliable Broadcast（RBC）协议和Byzantine Binary Agreement（BBA）协议。ACS协议的主要功能是通过RBC协议广播事务，然后通过BBA协议形成一致的事务集合。在ACS实例中，包含节点基本的配置，每轮对应的RBC实例和BBA实例以及对应的结果，存储结果的缓存区，不同节点消息传递的消息列表，以及一些ACS协议内部消息传递的通道。 ACS实现的总体流程如下：
（1）ACS实例运行时，会起一个协程不断监听通道，有事务输入则处理事务，有消息到达则处理消息。
（2）将输入的事务传给RBC实例广播（详细过程见3.5），如果当前epoch没有给BBA实例提供输入（详细过程见3.6），则向BBA实例输入1。
（3）如果接收到至少N-f个BBA实例输出的1，将其它还没有提供输入的BBA实例输入0，BBA实例的输出都记录下来。
（4）当所有BBA实例都已经完成，将结果是1的节点id记录下来，这些结果是1的节点的RBC输出组成ACS实例的输出。
ACS实现大致流程图：
Reliable Broadcast
Reliable Broadcast（RBC），可靠广播协议，通过使用纠错码算法减少节点之间的传输，RBC需要两次广播：第一次广播ECHO消息，第二次广播READY消息，两次广播后就可以在节点之间达成共识。
PBFT在每一轮共识的时候，领导节点需要把事务块分发给所有其它节点，假如系统节点有10个节点，事务块的大小为100M的话，那么领导节点在这次广播就需要消耗10*100M=1G的带宽，因此领导节点的带宽很容易成为吞吐量的瓶颈，这也是PBFT被人诟病的原因之一。
RBC协议本质上是通过广播发起者先使用纠错码算法将要广播的事务块分成N份，然后广播给N个节点，节点通过各自的网络带宽来广播已经分成小份的事务块。这有点类似于BitTorrent协议，BitTorrent协议通过将资源块分成多份，下载方可以从多个地方下载一个资源的不同部分，既达到加快下载速度的效果，也节省了服务器的资源。因此，RBC协议减少了广播节点的网络带宽，充分利用了所有节点的网络带宽，带宽消耗是PBFT的N分之一。这里有个问题就是如果有的节点没有接收到这些小块或者某些恶意节点故意不广播接收到的小块，那么将无法还原数据。这也是上面需要先用纠错码算法的原因。假设恶意节点个数f=1/3*N，在已经分好的N个小块基础上加多f个纠错码小块，总共N+f个小块，只要节点接收到N+f个小块里的任意N个小块就可以完整地复原出原始事务块。如图3-4所示，给出了大概的RBC协议传递路线，广播者（图中的A节点）将纠错码分好的小份事务块广播给其它节点，其它节点再将收到的小份事务块进行广播，这样所有节点就都会有完整的事务块。
RBC协议图示：
在RBC实例中，包含节点基本的配置，广播节点id，存储其它节点传来的ECHO消息和READY消息，里德所罗门编码器及相关的分片数，存储需要广播的消息，还有一些内部状态值及通道。 RBC实现的总体流程如下：
（1）与ACS类似，RBC运行时会起一个协程不断监听通道，有事务输入则处理事务，有消息到达则处理消息。
（2）将输入的事务块用里德所罗门编码分成N份，且有2f份冗余，分好的数据用默克尔树存储，将不同分支发给不同的节点。
（3）当节点接收到广播节点传来的数据，数据用ECHO消息包装好并广播给其它节点。
（4）当节点接收到ECHO消息，需要验证这份数据是否合法，如果不合法就丢弃。当接收到N-f个合法的ECHO消息时，如果此时还没有发送过READY消息，则广播READY消息，消息里包含默克尔树的根哈希值。
（5）当节点接收到f+1个默克尔树根哈希值相同的READY消息，并且仍未发送过READY消息，则广播READY消息。
（6）当节点接收到2f+1个READY消息后，根据里德所罗门编码恢复数据。
RBC实现大致流程图：
Byzantine Binary Agreement
Byzantine Binary Agreement（BBA）是一种标准的原语，它允许节点就一个位的数据达成一致。BBA算法满足以下三个条件：
（1）一致性。任意一个诚实节点输出一个比特b，那么所有诚实节点都输出b。
（2）最终性。如果所有诚实节点都有输入，那么所有诚实节点的输出都是b。
（3）合法性。任意一个诚实节点输出b，那么至少一个诚实节点的输入是b。
在BBA实例中，包含节点基本配置，存储接收到的二进制值和发送的二进制值，存储需要广播的消息缓存区，还有一些内部状态值及通道。
BBA实现的总体流程如下：
（1）同样的，BBA运行时会起一个协程不断监听通道，有输入值则处理输入值，有其它节点发来的消息则处理消息。
（2）当有输入的二进制值时，记录为estimated，然后向其它节点广播这个二进制值。
（3）当接收到f+1个节点发来的二进制值，如果此时这个节点没有广播过二进制值，那么广播这个二进制值。
（4）当接收到2f+1个节点发来的二进制值，将值记录在binaryValues里，如果之前binaryValues不为空，那么将这个值包装成AuxRequest并广播。
（5）当收到N-f个不同节点发来的AuxRequest，将接收到的AuxRequest包含的二进制值形成集合values，并且values是binaryValues的子集。
（6）最后执行抛硬币算法，有50%的概率将二进制值置为原先的二进制值；若否，则将二进制值置为传来的二进制值。抛硬币算法主要是为了避免在网络分区的情况下，攻击者有机会给不同的用户发送对不同值的投票（或故意不投），使它们对不同区块达成共识。
BBA实现大致流程图：
