您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

HotStuff算法详解

时间:2021-01-18 12:03:32  来源:  作者:

背景

状态机复制 (State machine Replication, SMR)是人们为了解决分布式系统同步问题提出的一种理论框架。为了让一个系统拥有较强的容错能力,人们通常会部署多个完全相同的副本节点,任意一个节点的崩溃都不会影响整个系统的正常工作。在工程上,这些副本节点通常使用状态机复制理论进行同步。

状态机复制的核心思想是在所有副本上面运行一套相同的状态机,只要所有副本都有相同的初始状态,并且对于初始状态赋予相同的一组操作,那么所有副本的最终状态一定是相同的。

如何确定这一组操作的顺序,就需要系统中所有未出错的节点,对于某一个待提交操作序列达成共识,这就类似于著名的拜占庭将军问题中,军官们面临的困境。在拜占庭问题的诸多解决方案中,都会保证个节点中,只要有个未出错的副本,这些未出错的副本就可以不受其他出错(甚至恶意)的副本影响而达成共识。

HotStuff是尹茂帆等人提出的分布性一致性协议,在该算法中,最多出错节点个数为。该算法有两个优点,第一个优点是,相比于之前的算法,HotStuff是基于leader节点的,拥有线性复杂度,可以极大地降低节点出错时,系统的共识消耗。同时,更替leader的低复杂度,鼓励网络频繁更迭leader节点,对于区块链等领域非常有用。第二个优点是该模型隔离了安全性与活跃性,安全性通过节点投票保证,而活跃性则通过 Pacemaker 保证。

学习HotStuff除了阅读本文,还可以阅读原论文 《HotStuff : BFT Consensus in the Lens of Blockchain》 ,或是原论文的中文翻译。Facebook的Libra数字货币也使用的该算法的变种 LibraBFT 。

算法

原论文提出了HotStuff的三种实现形式,分别为简易的HotStuff算法(Basic HotStuff),链状HotStuff算法(Chained HotStuff)和事件驱动的HotStuff算法(Event-driven HotStuff)。工程上,人们通常使用Event-driven HotStuff算法,但是如果直接去阅读Event-driven HotStuff算法的源代码会不知所云。

Event-driven HotStuff算法之所以比较难以理解,是因为它——

  • 使用了Basic HotStuff算法的共识逻辑,特别的,包括leader如何与replica交互形成共识;
  • 运用了Chained HotStuff提出的流水线优化思想,特别的,如何使用流水线并行优化原算法中相似的阶段;
  • 最后Event-driven HotStuff是Chained HotStuff事件驱动形式,特别的,将原始实现中轮询产生的驱动改为由leader节点发出的事件驱动。

一方面,从论文的结构上来看,先介绍了前两者,最后才在Implementation章节介绍了Event-driven HotStuff。但另一方面,Event-driven HotStuff又是三者中代码最简单的,也是三者中唯一一个可以在网上找到 大量源码 进行对照的实现。因此直接上手阅读源码,在遇到困难时再去查阅简单版本的实现也是一个很好地做法(事实上论文作者也推荐直接阅读Event-driven HotStuff)。

简单HotStuff算法

如果本节下面的内容理解上有困难可以参考原文对应章节。

视图

状态机复制中单次状态转移在HotStuff中以视图(View)的形式出现,leader节点收集网络中其他节点的信息,发送提案并取得共识的整个过程可以看做是一个视图,视图实际上可以类比于状态机的一次转移,其中包含了这次转移需要执行的用户命令。而整个分布式系统,正是通过一次又一次的视图变换(View-Change),得以逐轮推进运作。

分支

直观地看,HotStuff中,每一个副本节点都会在自己的内存中维护一个待提交指令的树状结构。每个树叶子节点都包含了一个待提交的指令,树节点到根节点组成了一个分支。未提交的分支之间互相是竞争关系,一轮中只会有一个分支被节点所共识。

系统中存在一个唯一的leader被其他所有节点所公认,这个leader会尝试将包含“待执行指令”的提议附加到一个已经被个副本投票支持的分支。并尝试就新的分支与其他副本达成共识,共识成功后,整个系统所有节点都会提交并执行这些新的附加操作指令。

【值得注意的是HotStuff并不关心leader的选取过程,因此在后续算法中,我们需要默认leader已经由其他模块指定。】

仲裁证书

HotStuff中的投票使用密码学中的仲裁证书(Quorum Certificate, QC),每一个视图都会关联一个仲裁证书,仲裁证书表明该视图是否获得了足够多副本的认可。仲裁证书本质是副本节点通过自己的私钥签名的一种凭证。

如果一个副本节点认同某一个分支,它会使用自己的私钥对该分支签名,创建一个部分证书发送给leader。leader收集到个部分证书,可以合成一个仲裁证书,一个拥有仲裁证书的视图意味着获得了多数节点的投票支持。

视图的投票总共分为三个步骤,准备阶段prepare, 预提交阶段pre-commit,提交阶段commit。每一次投票都会合成一个仲裁证书,不同阶段的证书从含义上稍微有些区别,在后续章节的阅读时需要注意。

算法

下面是HotStuff的伪代码,其中算法1是重要函数的伪代码,涉及到到消息创建、投票创建、叶节点创建、仲裁证书创建、消息验证、仲裁证书验证、节点安全性判断这些功能。算法2则是HotStuff的运行流程,在每一个阶段,领导节点leader和所有副本replica(包括leader)都会等待特定类型的消息,并进行处理。下面,我会依次讲解每一个阶段究竟做了什么事情。

HotStuff算法详解

 

简单HotStuff涉及函数

HotStuff算法详解

 

简单HotStuff算法流程

prepare阶段

在视图编号增加时,所有节点都会发送New-View类别的消息给leader节点,消息中捎带当前节点的prepareQC值(这里伪代码没写),leader节点在接收到个New-View消息即可以默认已经有足够多的副本等待接收新的提案。

prepareQC是一个仲裁证书,记录了一个最后获得了个节点投票的已提交分支,leader节点从所有New-View消息捎带的仲裁证书中,选择了一个拥有视图编号最大的仲裁证书highQC,基于highQC对应的节点,创建叶节点拓展待提交的指令curProposal,这样对于leader来说是最安全的。

最后leader节点会将curProposal、highQC封装到prepare类型的消息中发送给副本节点,而副本节点对于接收到的prepare类型消息,进行安全性检测safeNode。

从算法1中,我们可以看到,安全性判定分为两个规则,安全性规则和活跃性规则。安全性规则检测消息对应的节点是否是仲裁证书的直接子节点,如果是的话,说明副本节点的待提交节点和leader的待提交节点都是同步,中间没有任何步骤缺失。活跃性规则则检测自身的lockedQC的视图编号是否小于仲裁证书的的视图编号,如果小于的话,就说明自己被卡在了一个其他节点早已达成共识的视图,因此可以忽略自身的lockedQC,直接尝试与leader重新同步。

pre-commit预提交阶段

当leader节点收到个为当前提案curProposal投票时,将他们合并为prepareQC,此时的prepareQC已经获得了这个副本的投票。而对于副本节点,prepareQC则被赋值为prepare阶段中leader节点的highQC,即最近已提交分支。

commit提交阶段

commit阶段类似于pre-commit阶段。当leader接收到个pre-commit投票时,它将它们组合成一个precommitQC,并在commit类型消息中广播它;副本用commit投票来响应它。重要的是,此时通过将副本的lockedQC设置为precommitQC(算法2的第25行),副本将被锁定在precommitQC上。这对于保护提案的安全至关重要,以防提案成为一项协商一致的决定。

decide决定阶段

当leader节点收到个commit的选票时,它将它们合并成一个commitQC。一旦leader节点获得了commitQC,它就会以decide消息的形式将其发送给所有其他副本。在接收到decide消息时,副本将commitQC中包含的提案视图视为已提交的决策,并在已提交的分支中执行命令。副本将增加viewNumber并启动下一个视图。

下一个视图(nextView)中断

在所有阶段中,副本都会在viewNumber视图处等待由函数确定的超时时间段。如果中断等待,副本也会增加viewNumber并开始下一个视图。

理解

正如代码中蓝色部分所强调的,系统的replica在每一阶段都会维护一个量:

  • prepareQC,表示该仲裁证书曾经获得过一次majority投票
  • lockedQC,是一个用于保证安全性的中间量
  • commitQC,是个表示决策已经成了的凭证,不论之后发生什么样的问题(网络延迟、节点崩溃),只要有个正确节点,这个决定都是会被继续尊重

为什么上述算法是安全的,核心就是证明下面的命题:

如果和是冲突的节点,那么他们不能够同时被某个正确的副本所提交(commit)。

该命题的证明在文末附录1,如果想要搞清楚lockedQC具体的含义,可以尝试阅读一下证明。 接着证明上述算法的活跃性,活跃性的核心是证明下面的命题:

我们首先定义全局稳定时间GST之后,存在一个有界的持续时间,满足如果所有副本在期间仍然在视图中,且视图的leader节点正常运行,那么决定(decision)可以到达。

该命题的证明在文末附录2.

链状HotStuff算法

如果本节对应的内容理解有难度,可以参考 原文对应章节

。 在Basic HotStuff中,不难发现每个阶段都是极其同构且独立的,因此可以进行流水线优化。

HotStuff算法详解

 

图1 Chained HotStuff是Basic HotStuff的流水线版本,QC可以同时处于多个阶段。 对于节点b,单箭头表示b.parent字段,双箭头表示b.justify.node。

更具体地说,在Chained HotStuff协议中,prepare阶段的副本的投票由leader节点加以收集,并且储存在状态变量genericQC里。接下来,genericQC被转发给下一个视图的leader,实质上是将下一阶段的职责(这曾经由pre-commit阶段负责的)委托给下一个leader节点。然而,下一位leader实际上并不单独进行pre-commit阶段,而是启动一个新的prepare阶段,添加自己的提议。视图的prepare阶段同时充当视图的pre-commit阶段。视图的prepare阶段同时充当视图的pre-commit阶段和视图

的commit阶段。 在实际的实现中,还有一些细节,比如说,当一个leader没有成功获得足够的仲裁证书,那么就可能出现一个节点的justify的视图编号并不连续,如图2所示,这种情况需要通过添加哑结点补齐。

HotStuff算法详解

 

图2 v8的父节点没有成功获得仲裁证书

我们按照节点的依次向上访问,可以获得流水线中各个阶段的节点。令,,

  • 如果,说明的prepare阶段成功完成,当副本投票给时,还需要执行。需要注意的是,即使,执行上述赋值也是安全的,我们在下一节Event-driven HotStuff中会使用后者。
  • 如果,说明的pre-commit阶段成功完成,需要同步更新。
  • 如果,说明的commit阶段完成,就变成一个已提交的决策。

下面是Chained HotStuff的伪代码,其中略去了很多特殊情况的判断。

HotStuff算法详解

 

事件驱动的HotStuff

从Chained HotStuff到Event-driven HotStuff也并不困难。最终伪代码涉及了如下的数据结构——

  • 将节点映射到投票
  • 最近投票节点的高度
  • 被锁定的节点(和lockedQC相似)
  • 最后执行的节点
  • 由Pacemaker维护的最高的已知QC(与genericQC相似)
  • 由Pacemaker维护的叶节点

下面两个代码共同组成了一个工程上实现高效的Event-driven HotStuff算法,他们分别描述了安全性相关模块和活跃性相关模块。和Chained HotStuff源码进行对比,不难理解其中各个函数的功能,同时,读者也可以结合 网络上公开的实现

进行理解。

HotStuff算法详解

 


HotStuff算法详解

 

上述的HotStuff是三阶段的,而论文中还介绍了一个两阶段的HotStuff变种算法,其优势是更少的阶段,更快的效率,而劣势则是乐观响应性的损失。

HotStuff算法详解

 

附录1. 证明HotStuff安全性

证明: 如果和是冲突的节点,那么他们不能够同时被某个正确的副本所提交(commit) .

先证明一个特殊情况,假设和的高度相同,上述命题不成立。这其实是很显然的,毕竟副本的提交需要多数节点的投票,而每个副本每个阶段只会投一个提案,不可能出现两个同样深度树节点得票数同时过半的情况。

HotStuff算法详解

 

w和b高度不同的情况

假设和高度不同,不妨设,,是高度 大于 且与 冲突 的, 高度最小 的那个 合法的 prepareQC仲裁证书。 即

HotStuff算法详解

 


HotStuff算法详解

 

和都是合法的commitQC仲裁证书,是一个合法的prepareQC证书。算法29行说明一个commitQC是由个lockedQC组成,而算法13行则说明一个prepareQC需要个副本同时通过safeNode检验。 而一个commitQC需要由个lockedQC组成,和一个prepareQC需要的次safeNode检验,一定存在一个公有的,在视图的时候,会设置lockedQC为precommitQC(),当尝试检验safeNode谓词时,就会发现既不满足“extends from”,也不满足“”。这意味着

甚至根本无法生成,与假设矛盾。 反证法的结论就是不可能存在两个冲突的commitQC。

附录2. 活跃性证明

我们首先定义全局稳定时间GST之后,存在一个有界的持续时间,满足如果所有副本在期间仍然在视图中,且视图的leader节点正常运行,那么决定(decision)可以到达。 引理 如果一个正常运行的副本已经锁定了,且锁定在了,那么至少个副本投票了与匹配的。 引理证明 如果一些副本锁定了,那么在prepare阶段一定获得了个投票(算法2的第10行),由于,所以其中至少个是正常运行的副本。 活跃性证明 从一个新的视图开始,leader节点收集个newView消息,并计算出他们的highQC,最后广播prepare消息。假设在所有副本中(包括leader本身),最高的锁定QC是,通过引理, 我们知道了,至少有个正确的副本曾经向一个匹配的投票,并且该值已经被附在NewView消息中,传送给leader节点。在这些New-View消息中,至少有一个会被leader接受,并赋值到highQC中。基于假设条件,所有正确的副本在该视图中处于同步状态(synchronized),且leader节点是无缺陷的。因此,所有正确的副本都会在prepare阶段投票,由于在函数里面,算法1第27行的条件被满足了(即使节点的消息和副本的冲突,即26行条件不满足)。然后,在leader为这个视图聚合出有效的prepareQC之后,所有副本将在接下来的所有阶段进行投票,从而产生一个新的决策。在GST之后,这些阶段完成的持续时间是有界的。



Tags:HotStuff算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
背景状态机复制 (State Machine Replication, SMR)是人们为了解决分布式系统同步问题提出的一种理论框架。为了让一个系统拥有较强的容错能力,人们通常会部署多个完全相同的...【详细内容】
2021-01-18  Tags: HotStuff算法  点击:(158)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条