【前言】

之前我了解的都是半同步的共识,现在刚开始接触异步共识,像是发现了新大陆,各种全新复杂的概念突然涌进来,什么FLP定理、异步二元共识等等搞得我晕头转向。这篇文章就来总结一下我在学习HB-BFT算法中遇到的困惑以及我的一些理解(网上很多博客都没有针对性解答,如果有误非常希望能指出来,这对我非常有帮助!!!)

【问题】

问题一:FLP定理通俗易懂一点到底是什么?

    大部分博客的都只是用了原文的核心观点进行解释:“在网络可靠,存在节点失效(即便只有一个)的最小化异步模型系统中,不存在一个可以解决一致性问题的确定性算法”。对于像我这种脑子不太好使的来说,也太难参透了。。

    首先,这里有几个概念要解释清楚:

    1. 异步是什么?异步就是各进程(分布式算法里面就是各节点)之间消息可达,但是传输延迟没有上限

    2. 一致性问题是什么?一致性问题简单来说就是系统的安全性(简单说:不能出错)和活性(简单说:总要有个结果)是否能保证,要理解FLP定理最好的方式就是从系统活性上来理解。

    3. 确定性算法是什么?确定性算法就是指算法的每一步操作都是确定的,对于相同的输入,执行路径和结果总是相同的。

    基于上述概念的解释,FLP算法通俗易懂就可以理解为,异步环境中,如果一个系统里面有很多个进程,大家不管初始状态怎么样(可以称为系统的配置,举个例子,比如4个节点,初始状态认同的信息为0011,或者1010等等都是不同的配置),只要遵循相同的规则,对于某一个的输入和状态,做的事都一样,即使有一个进程被对手(一个全知全能的恶意的敌人,可以无限延迟消息或发送错误消息)攻击了,整个系统最后也能达成一致   这是不存在的

    那原论文的证明用的是反证法,证明过程简单版如下:

    1. 一个确定性算法一定存在一个初始的二值配置(意思就是从这个配置出发运行,下一步结果不会可能是0,也可能是1。举例子,比如4个节点初始值为0011,这是一个二值配置,从这个配置出发,下一步所有节点最终的决定值不会确定性的为0或1,而是两者皆有可能。单值配置就是比如0101下一步无论怎么走就肯定是0000或1111)注意,文章只是用二进制01的一致性来进行证明,该定理也适用于多个值的情况(比如1234等等)

    2. 从任何一个二值配置出发,总存在一个方法(通过延迟消息或者发送错误消息)来避免系统进入一个单值配置,从而使其永远保持二值,无法做出决定。

具体的证明可以看看原文,这里就不赘述了捏

这里我们需要理清楚一个事情,消息可达\neq活性,因为对手可以让系统永远处于二值配置

问题二:异步共识到底解决的是什么问题?

    为了更直观地体现非异步共识在异步环境中的不适用性,在这里用pbft举一个例子,异步环境中没有时间假设,所以节点在没收到其他节点发来的消息时无法区分是普通的延迟还是节点作恶,因此没办法用超时机制来推进系统,假设恶意领导者拒绝发送提案,那整个系统就会发生瘫痪。

    因此,异步共识就是要在没有时间假设的情况下去保证系统的安全性和活性,异步共识算法的设计里不能有任何的时间依赖。但由于消息是可达的,所以现有的算法设计都依赖于消息驱动和公共随机硬币,只要有消息到,就可以推动进程下一步动作,同时通过随机性巧妙绕过FLP不可能性(不追求确定性终止,而是追求概率性终止)。⬅有点抽象,可以这么理解(先假设没有随机性时,算法是确定性的,恶意又无敌对手可以纵观全局并通过某些办法让系统一直处于二值状态,无法达成一致,这时候,大家突然获得了一个相同的、无人能预测的随机数,且算法允许它强制各进程重置并基于这个随机值继续协商,而这个随机数先前无法被恶意对手知晓,因此无法造成干扰

问题三:HB-BFT中的随机硬币解决了什么?

    上述的解释可能还是很抽象,或者有点牵强。下面我会对HB-BFT中的随机硬币进行分析,通过具体的例子来分享我的理解。整个算法的共识过程比较复杂,不懂的可以看看原论文或者这篇博客(Honey Badger BFT共识协议详解_honeybadgerbft-CSDN博客),这里不详细说。

    这部分一定要先看明白算法步骤再来看!!!!!

    简单来说,HB-BFT共识算法通过异步公共子集(ACS,Asynchronous Common Subset)来达成共识。而ACS又分为可靠广播协议(RBC,Reliable broadcast)和异步二元共识(ABA,Asynchronous Binary Agreement)。RBC负责让所有实诚节点都能收到同一个提案集合(注意,这里的RBC本质上是确定性算法),而ABA负责让所有实诚节点都能对提案集中的每个提案都达成共识(比如1就是提交,0就是不提交)。

    ABA的算法流程如下:

    我们举个例子,在4个节点(abcd)的系统中,节点c是恶意对手。对于提案1,ABA阶段初始时,a和b认为是0(也就是est的值,binput是根据RBC结果来初始化est的),d认为是1。a和b广播BVAL(0),d广播BVAL(1)。c向a和b广播BVAL(1),向d广播BVAL(0),此时ab都接收到了f+1个BVAL(1),d接收到了f+1个BVAL(0),于是又进行广播,ab广播BVAL(1),d广播BVAL(0)。这时各节点已经满足2f+1个相同的BVAL,于是广播AUX。于是集合vals就包含了ab的1和d的0。也就是二值状态,没有确定的。而随机硬币可以强行让实诚节点都用同一est重新开始,现在假设abd三个节点初始值est都为0,那么无论c怎么作恶都无法干扰共识。

    那随机硬币的作用就在于:

    1.公共统一的值使得大部分节点(进程)有公共初始值,使系统远离矛盾的配置(个人认为就是类似于0011这种比较极端的,更容易遭受攻击的配置),配合阈值控制保证安全性

    2.随机性使得对手无法预知,从而防止对手提前干扰,降低对手的攻击性

    注意,在这个ABA算法里,2f+1并不能一直保证安全性,比如节点初始值不同的时候(当时博主就是受半同步共识影响太深,一看到2f+1就觉得安全,这是错误的)

【其他小坑】

    1.注意区分一致性广播和可靠性广播:可靠广播确保所有诚实节点接收到所有消息,但不保证消息的顺序(以RBC协议为例,各节点并行提案,最终各实诚节点收到的提案集是一样的)。一致性广播在可靠广播基础上有顺序要求(如pbft,每个提案会有序号以及对上个区块的引用,节点验证时会进行相应的验证)

    2.异步环境中消息最终可达不保证活性,消息阈值控制不保证安全性(由上文分析可得)

有什么问题请指出,这对我的帮助非常大。同时也希望这篇文章能帮助到你,后续我还会在该专栏继续分享,比如小飞象共识、基于DAG的异步共识等等,感谢你的关注!!!

Logo

助力广东及东莞地区开发者,代码托管、在线学习与竞赛、技术交流与分享、资源共享、职业发展,成为松山湖开发者首选的工作与学习平台

更多推荐