2023年7月27日发(作者：)

HoneyBadgerBFT（异步共识算法）笔记最近⼀直在看Honey Badger BFT共识协议，看了很多博客和⼀些相关的论⽂，但是发现有些博客存在着部分理解错误的地⽅，或者就是直接翻译2016年的那⼀篇论⽂，在经过半个多⽉的细读之后，打算整理出这篇博客，⽅便给学习这个共识协议的⼈学习，同时⾃⼰也留存⼀份笔记，以下仅是笔者通过阅读论⽂和博客等⽅式，描述⾃⼰对Honey Badger的理解。如有错误，还请指正。Miller等⼈提出的Honey Badger BFT是⼀种在异步⽹络环境下可以正常运⾏的BFT协议。异步，⽐PBFT的吞吐量和延迟性能好仅⽀持封闭⽹络，即主机个数已知，协议执⾏过程中没有新的主机接⼊⽹络。⽆Leader，每个节点都可作为共识的发起者。Honey Badger BFT使⽤了两个⽅法来提升共识效率：通过纠删码分割交易来环节单节点带宽瓶颈。通过在批量交易中选择随机交易块，并配合门限加密来提升交易的吞吐量。基础知识纠删码（我是在⼀篇博客上⾯看到的关于RS纠删码的介绍，这⾥只是粗略的介绍⼀个概念，让⼤家知道是⽤来⼲什么的，以及是⼀个什么原理。纠删码技术在后⾯的RBC阶段会使⽤到，主要是⽤于均分带宽，缓解提出共识交易节点的带宽瓶颈。）纠删码⼯作原理简介：RS（Reed-solomom）码是⼀种⽐较常见的纠删码，它的两个参数m和n分别代表校验块个数和原始数据块个数（课容忍m个数据块的丢失，拜占庭共识中，设m = 2f，原始数据块为f+1），我们可以使⽤n数据块就恢复出原始的数据块。纠删码编码过程：C代表校验块，D代表原始的数据块。假设我丢失了D1、D4、C2数据块：解码过程：（⼀共三步）Step1：在编码矩阵中去掉求实数据块以及该数据块对应的⾏。即B矩阵变为了n*n维度的⽅阵，C和D组合的矩阵由（n+m）⾏变为n⾏，在上诉假设过程中，我们得到新的矩阵以及对应的矩阵运算关系式，其中在丢失了部分数据块后，D所代表的原始数据块成为了要求的⽬标。step2：求B’的逆矩阵：如下图所⽰：step3:可以采⽤对等式两边同时乘上B’的逆矩阵，于是得到所求解。如果⼤家没太看懂，我贴上关于纠删码部分原作者的博客链接：随机交易块为了降低各个节点之间提交交易的重复性，Honey Badger BFT算法使⽤随机选择交易块的⽅法来选择需要共识的交易集，具体选择条件如下：假设⽹络中共有N个节点，每个节点进⾏共识的交易⼤⼩为B。每个节点收集交易数据，放到⾃⾝的交易缓冲池中，每⼀轮共识之前，节点从交易缓冲池的第⼀个B⼤⼩的交易池中随机选取 B/N 个交易进⾏共识。（提问：为什么节点只选择B/N个交易进⾏共识？答：因为不⽌⼀个节点提交共识交易集，是所有节点都会进⾏提交，当前节点 Pi 会从其他N-1个节点处收到他们提交的交易集，然⽽每个节点能够共识的交易⼤⼩为B，N * B/N = B，所以知道了么？）门限加密第三⽅可信机构（2016年的论⽂提出：如果可信机构不可信了，可以使⽤分布式密钥⽣成协议替代）会将私钥分⽚放给所有参与共识的节点，在解密的时候，只要节点收集到⼀定门限数量的解密分⽚，则该节点可以恢复出密⽂。使⽤门限加密还可以实现审查弹性，避免了敌⼿知道哪个交易由哪个节点发起⽽阻挠共识的达成。默克尔树默克尔树会在后⾯的RBC协议阶段使⽤到。默克尔树（或者哈希树）是⼀棵能够存储哈希值的树，树的叶⼦节点是数据块（例如交易集、⽂件等）的哈希值，内部节点则是其对应⼦节点串联字符串的哈希值。这⾥以RBC中的交易块 sj 为例。如何校验数据块的叶⼦节点 sj 和路径 bj 校验是否等于 h，假设 j = 2，交易分块 s2，b2 以及 h，b2 = {h1, h8, h11}Honey Badger BFT算法总流程总体的算法主要包括三个步骤：随机选取交易集并对交易集加密交易的可靠⼴播（采⽤RBC实现）。共识（采⽤ABA实现）算法流程如下节点 Pi 先根据随机选择交易块的选择规则选取要进⾏共识的交易集合（B/N个交易），第三⽅可信机构分发私钥分⽚给每个节点。节点 Pi 使⽤公钥PK对交易集进⾏加密，加密的交易⽤ x 表⽰。将 x 作为ACS（后⾯会详细讲解）的输⼊，ACS结束后，会收到N个（包括⾃⼰的那⼀个，其余为其他节点发起的交易共识）交易集vj ，以及交易对应的01⽐特串，每个⽐特对应⼀个节点发起的共识交易集合（1表⽰该交易集最终会被提交，0表⽰该交易集不会被提交）。将⼆进制共识结果为 1 的交易块收集起来，并对它进⾏解密，当 Pi 收到 f + 1个解密分⽚的时候 Pi 就可以解密得到 vj 的明⽂交易集合。交易被解密之后，会进⾏赛重、校验交易正确性、和排序等环节。交易被提交之后，就会从待提交的交易缓冲池中删除。下图为Honey Badger BFT算法总流程图（运⾏于Pi）。ACS（异步公共⼦集协议）Hoeny Badger BFT是第⼀个实现最佳渐近效率的⼀步原⼦⼴播协议。Honey Badger BFT算法采⽤ACS（Asynchronous Common Subset）协议实现了原⼦⼴播（Atomic Broadcast）。ACS协议由两个协议组成：⼀个是可靠⼴播协议RBC（Reliable Broadcast），⼀个是异步⼆进制协议ABA（Asynchronous BinaryAgreement）。RBC协议：⼴播交易。ABA协议：形成⼀致的⼆进制交易列表。下图为RBC和ABA协议具体执⾏过程：这只是在 Pi 为发起共识交易者的⾓度进⾏解释，其实其他的节点也是相同的步骤，并且并发执⾏。RBC协议论⽂采⽤基于纠删码的RBC协议来⼴播每个节点提交的交易集。RBC的协议包括如下步骤（这⾥只是针对 Pi 为消息的发送者，其实其他的节点也在同时进⾏与 Pi 相同的步骤）：Pi 将加密后的交易块 v 作为RBC的输⼊，使⽤纠删码技术⽣成N个数据块 {sj}， j∈N。将所有的 sj 计算出默克尔根 h， bj 是 sj 到 h 的路径，并将 VAL(h, bi, si) 消息⼴播给其他节点。（关于默克尔树部分的理解，可以参考前⾯基础知识关于其的介绍）如果其他节点收到来⾃Pi的VAL信息，则⼴播 ECHO(h, bi, si) 消息。当其他节点收到EHCO消息之后，他⾸先会校验根据 si 和 bi 是否能算出h（对 Pi 来说，就是校验 ECHO(h, bj, sj)），检查这个ECHO是否有效，如果能够正确推算，就表⽰此ECHO有效，如果⽆效则直接丢弃这个ECHO。当节点收到 2f+1 个ECHO消息（h相同）之后，则选取其中 f+1 个ECHO，根据其sj 和 bj计算出 h’。然后对⽐ h’ 和 h 是否相等。如果相等则⼴播 REDAY(h) 消息。当节点收到 2f+1 个 READY(h) 消息，则使⽤前⾯收到的 f+1 个ECHO消息恢复出原始的密⽂ v（纠删码技术）。（注释：下图中算法的倒数第⼆个⼩圆点的部分。我没有在流程中叙述出来，肯定有⼈会有疑惑，根据我⾃⼰的理解，我认为这⼀部分是为那些⽹络情况不好的正确节点准备的，或许他们在收到了 f+1 个别的节点发出的READY(h)消息的时候，还没有收到⾜够多的ECHO消息，所以他⾃⼰本⾝还不能触发发送READY的契机。但是收到了那么多⼈已经发了READY消息，那么他就知道这个答案是对的，那么他就抄作业。直接发送READY消息，这也就解释了最后⼀个点为什么有wait for N-2f ECHO messages）。ABA协议如果节点能够根据 f+1 个ECHO消息重构出交易密⽂ v，则对对应的实例ABA发送⼀个1，如果当前节点已经重构出了 2f+1 个节点提交的交易块（指已经输⼊了2f+1个1），那么就会对后⾯所有的ABA实例都输⼊0，表⽰在收到 2f+1个交易块之后，后⾯的我都不要了。（为啥这么任性？因为这是在拜占庭共识中，会有 f 个是拜占庭节点，如果我要等到全部节点的交易块都收到再进⾏下⼀步，其实是不太可能的，万⼀有拜占庭节点故意不发，那样我们的等待很可能会阻塞共识的达成，所以我们就假设排除掉 f 个个节点的交易，只收到2f+1个就⾏啦）。其实这⾥会有⼀个情况2（当然接下来只是我的理解，如ACS的第⼀个图中我标注的情况2这个阶段所⽰）。⼀个节点已经对2f+1个ABA实例输⼊1，对剩下的 ABA 实例都为0，但是这时候所有节点输⼊为 1 的ABA实例的集合其实并不相同，所以需要⼀次交互，当节点对某个ABA 实例设置为0，但是他⼜收到了 f+1 个其他节点发来将该实例设置为1的消息，那么他就会把⾃⼰设置为0的ABA实例重新设置为1，并且他还需要等待该实例对应的交易集从RBC中重构出来。如果没有收到那么多1，那就不更新。假设节点P1经过前⼀轮的交互，已经将⾃⼰拥有的ABA实例对应的⼆进制序列更新，此时我们以ABA2为例。节点对应的其他ABA实例也是相同的步骤，其他节点也与P1并⾏执⾏。r表⽰轮次，会根据循环的轮次⽽不断⾃增。1. est1初始化为12. ⼴播BVAL1(1)3. bin_values1 = ∅4. 在节点P1接收 2f+1个到BVAL1(1)，则bin_values1= bin_values1∪{1} = {1}5. 当bin_values1 不为空集的时候：※ ⼴播AUX1(w)，w是属于集合bin_values1⾥⾯的元素，这时候bin_values1⾥⾯只有⼀个元素——1，所以所有节点在bin_values1⾥⾯选的的元素w必然相同。※ vals表⽰所有节点选取的w的集合，当前为第⼀轮，vals集合⾥⾯也只会有元素1※ s 可以看做是⼀个随机数，其实它就是所有节点将轮次 r 进⾏门限签名再聚合之后形成的聚合签名。※ 这时vals集合是与{b} = {1}相等的，那么他会进⼊下⾯的那个if语句，est2 = 1，如何当前的1与随机抛硬币算法选取出的结果相等，那么表⽰已经对这个交易块的提交达成了共识，输⼊当前的共识结果1。（s%2 ∈{0,1}）※ 如果不凑巧与抛硬币算法没有相等，那会在进⼊⼀次上⾯的循环。随着循环的次数越多，会更容易达成共识。其实这⼀部分给我的感觉就是：节点之间选出⼀个结果，然后还需要⽼天爷（随机数）来决定你这个结果要不要被采纳。相同就采纳，不相同就不采纳。但是这个2016年那篇论⽂中提到了已经证明了在常数轮次可以达成最终的共识。最后经过ABA协议之后，得到⼀串共识后的⼆进制列表（假设⼆进制列表是存储在数组中，⽂中没有提及，只是我的猜想）。再对收到的交易序列按照⼆进制列表的结果进⾏处理，下图中第⼀排为⼆进制列表，第⼆排位对应的节点下标。将为1的交易集提取出来，使⽤门限解密密钥进⾏解密，当收到 f+1个对应同⼀个交易集的解密分⽚的时候，就可以解密出当前的交易集。在进⾏⼀系列的交易去重、验证交易正确性的⼿段。然后将最终的交易集进⾏提交。并从每个节点的待提交交易缓存池中将提交成功的交易删除。以上只是我这段时间⾃⼰学习和理解的Honey Badger BFT，如有不对之处，还望指出。附上的2016年的Honey Badger BFT原⽂，以及门限加密原⽂，以及参考的ABA算法的原⽂可以在我的博客主页找到。