火星链 火星链
Ctrl+D收藏火星链
首页 > 火必 > 正文

PRO:技术入门 | 探讨BFT的关键细节及Libra的Consensus组件

作者:

时间:1900/1/1 0:00:00

Libra涉及的东西比较多,我们从三条线介绍Libra的设计与实现:

通过分析Node启动并加入到Libra网络的过程,介绍Network组件的设计与实现;

围绕Transaction的生命周期,分析其接收交易、打包区块、运行上链的过程,介绍Libra的Mempool、Executor以及Storage、VM等核心组件;

围绕LibraBFT,介绍Consensus组件以及区块达成共识的过程。

前面我们讲述Libra的第二条主线——Transaction的生命周期,了解了Libra核心组件大概的设计和实现。其中Consensus组件我们只是简单介绍,在实际场景下,Consensus组件需要保证在很多分布在全球不同地区的Validator节点达成共识。在分布式的情况下,保证区块或者说交易的顺序最终一致,可以说,这是整个区块链的灵魂。因此我们单独介绍Consensus流程:

为什么需要Consensus?

目前主流的共识包含哪些?

BFT如何达成共识?

Libra的consensus组件

为什么需要Consensus?

前面介绍账号模型的时候我们提到“按大部分人认可的顺序记录每个Address的变更过程”,这里“大部分人认可的顺序”就是达成共识。但是现实中,要让遍布全球的很多很多互相不信任的节点,对全世界所有人的Transaction的顺序快速达成共识,是一件极具挑战的事情,也是所有公链都在发力的地方。

主流的共识

为了解决全球共识的问题,业内很多能人志士长时间在探索,目前大概形成了3类具有代表性的共识:

这3类共识分别又衍生出各种各样的共识:

POW、POW-DAG、NC-Max等

Pos、PoA、DPos等

PBFT、LibraBFT等

这些共识各有自己的特点,同时相互之间又可能存在一些关联。共识是一个很广阔的话题,感兴趣的可以自己去了解一下。由于BFT本身比较复杂,接下来我们深入讲述BFT,一步一步逼近我们的主题——LibraBFT。

BFT如何达成共识

BFT比较复杂,概念也很多,因此,我们分成多步讲解,从简单的场景开始,逐步扩展:

BFT的安全性与活性

能容忍的拜占庭节点数

同步与异步

PBFT和两阶段确认

币安与格鲁吉亚创新技术署签署合作备忘录:金色财经报道,加密货币交易所币安已与格鲁吉亚创新技术署 (GITA) 签署合作备忘录,双方将在教育和公共区块链倡议,以及共同发展格鲁吉亚加密产业领域展开合作,BNB Chain 将提供本地活动和编程马拉松支持。(cbw)[2023/2/3 11:46:24]

三阶段确认的Hotstuff

链式Hotstuff

BFT的安全性与活性

很多讲BFT或者讲Paxos的文章都会讲拜占庭将军的故事,版本不一,核心思想差不多,这里我们引用百度百科:拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了达到防御目的,每个军队都分隔很远,将军与将军之间只能靠信差传消息。在战争的时候,拜占庭军队内所有将军和副官必须达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,在军队内有可能存有叛徒和敌军的间谍,左右将军们的决定又扰乱整体军队的秩序。在进行共识时,结果并不代表大多数人的意见。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,拜占庭问题就此形成。

以上是百度百科摘取的拜占庭将军的故事,一句话总结,就是要让所有的忠诚将军行动一致,要么实力最强,要么战斗力最强。换句话说,忠诚将军一致行动的安全系数最高。如果出现部分忠诚的将军去进攻,部分忠诚的将军撤退的情况,那么后果不堪设想。

拜占庭容错BFT就是为了解决这个问题。这里有两个很关键的指标:

安全性:allcorrectnodesmustagreeonthesamevalue,就是说所有的忠诚将军达成一致;

活性:allnodesmusteventuallydecideonanoutputvalue,可以理解为,投票一定会产生结果,也就是所有节点达成一致;

安全性是目的,活性是所有造成投票进行不下去的各种异常的一个整体概况。为了同时保证安全性和活性,很容易提出问题:

在一个确定数量的集群里,最多能容忍的拜占庭节点是多少?

在分布式的环境里,消息延迟了怎么办?

能容忍的拜占庭节点数

关于能容忍的最大拜占庭节点数,Lamport大神有数学推导,感兴趣的可以去看看,但是我看了一个更通俗易懂的推导版本。

我们来简化一下问题:假设有一个n个人的部门,准备春游,从A、B两个地方进行选择,哪个地方票数最多,就去哪。其中有f个人很宅,哪都不想去。而剩下的所有h个人都是想去旅行的。这里,不管是诚实还是不诚实节点,都有可能不投票。那么可能会出现这样的结果,A和B的票数一样多,部门行政就不知道该怎么办了,卡住了。而不诚实节点恰恰就希望卡住,为此不诚实的节点可能视情况而投票:

如果A和B的票一样多,那么不诚实节点就不投票

如果A和B的票相差不多,那么不诚实节点会根据自身利益,不约而同选少的一方,最终让A和B的票一样多

总之,不诚实节点希望出现“得不出结论”的尴尬局面。为了避免出现这种“达不成共识”的情况,最多那个的选票最少要达到x,才能形成绝对优势而胜出。

回到拜占庭将军问题上,不管是进攻还是撤退,忠诚的将军只能收取大部分将军传过来的命令之后,统计出一个票数最多的命令,并且执行这个命令。为了让所有忠诚的将军的命令一致,胜出的命令最少应该达到x个,忠诚的将军才能放心大胆的执行这条命令,因为他知道这个命令达到了x个,其他忠诚的将军也是执行同样的命令。

动态 | 京东推出“宙斯盾2.0”系统 运用区块链等技术实现SKU管理:金色财经报道,京东再次升级系统,推出“宙斯盾2.0”系统,进一步优化“商品体验指数”参数,同时运用人工智能、区块链等先进技术,实现对不同SKU的管理,分析用户的意见并反馈给商家,监督和帮助商家进行整改。(36氪)[2019/11/8]

拜占庭将军的例子要比上面部门旅游的例子更复杂一些:部门旅游的选票是给部门行政一个人统计,统一公布;而拜占庭将军的例子是所有将军给其他将军发消息,每个将军自己统计自己收到的消息。那么会存在这样的情况,叛徒将军给A将军发的进攻,给B将军发的撤退。所以做决策的时候,x>n/2+1是不够的,这种情况会有下面表达式3体现出来。

我们用将隐含的重要信息摘出来:

1.总人数

2.最少票数不应该比诚实节点数多,否则不诚实节点只要全部不投票,投票就将进行不下去

3.如果一个结果要代表所有诚实节点,那么起码有一半以上的诚实节点投了这个结果

4.对于不诚实节点,可能给不同的人的投票信息不一样

我们将这些信息转化成表达式:

1=>n=f+h

2=>h>=x

3+4=>x>h/2+f

根据上面的3个不等式,进行推导

=>h>h/2+f

=>1.5h>h+f

=>1.5h>n

=>h>2/3*n=>f<1/3*n

虽然上面的推导是围绕胜出的票数x,但是得出的结论是最多能容忍的拜占庭节点数f。也就是说,要达成共识,拜占庭节点数f必须小于总节点数的n/3,n=3f+1而且x=2f+1。为什么要算这个呢?因为后面会用到。同时,我们也知道了拜占庭节点可能的操作:

不投票

给不同的节点投不同的票

对于第2种操作,可以通过消息签名的方式避免。那只有拜占庭节点不投票或者leader不发起投票的情况了,这种情况被称为弱中止条件下的拜占庭将军问题。

同步与异步

前面我们提到了网络延迟的问题。对分布式系统来说,网络拥塞等异常情况,有可能导致网络延迟非常的大,甚至没有上限。根据协议对延迟依赖情况,将协议分成了3类:

同步:网络延迟有上限且上限是已知的;

异步:消息延迟没有上限;

部分异步:网络延迟有上限但是上限是未知的;

同步模型适合对网络延迟特别敏感的场景;部分异步模型可以理解为覆盖了一般情况下的网络异常,比较接近日常的一般场景,最实用。

部分异步模型下,投票通常会由leader发起,由于leader可能是拜占庭节点,为了保证活性,会对多个节点进行排序,轮流当leader。一旦出现leader为拜占庭节点的情况,导致一定延迟内,不能达成一致,则换下一个leader维持投票过程。Libra实现的LibraBFT共识,使用了Hotstuff作为拜占庭容错算法,属于部分异步模型。

PBFT和两阶段确认

声音 | 比特币安全专家:对在物联网设备中使用区块链技术持怀疑态度:据ambcrypto.com消息,比特币安全专家Andreas Antonopoulos最近表示,对在物联网设备中使用区块链技术持怀疑态度,因为不知道这么做有什么好处,认为这与使用专用的IOT数据库没有不同。他表示,很多人使用区块链这个术语来解决实际上是数字签名数据库的问题,大多情况是将IOT和区块链这两个术语混合在一起产生一些新的解决方案。[2019/5/18]

BFT是围绕投票进行的,其中PBFT最常见。

下面是PBFT算法的大概流程,我们先看一下每个阶段所代表的意思:

request:触发leader发起提案

pre-prepare:leader准备提案,并把提案广播给所有节点

prepare:节点要把自己的vote广播给其他节点,所以消息复杂度是O(N^2),同时会对收到的所有vote进行统计

commit:当这个提案达到2f+1的vote时,节点会认为这个提案取得了认可,这时候,当前节点会通知所有其他节点他打算提交这个提案,commit消息不但要表明自己接收提案,还必须包含自己收集到的2f+1个vote。如果当前节点收到了2f+1个针对这个提案的commit,这时候才表示这个结果达成了一致。这个阶段比较复杂,下面会重点讲。

上面等于发起了两轮投票,为什么要进行两轮投票才能最终达成一致呢?

我们来设想一下只有一轮投票的场景:

正好有那么一个时刻,3节点给1节点发送了投票消息之后,成为了拜占庭节点。2节点虽然是非拜占庭节点,但是还没发起投票。这时候,1节点收到了3票,分别是0、1、3,所以1节点有理由觉得所有诚实节点达成了共识。但实际上并没有达成一致,这时候2节点可能会由于超时,发起要求重新投票的请求,并且0和3有可能同意这个请求。所以,只有一轮投票有可能没有达成一致。

为了解决上面的问题,所以PBFT协议设计中又进行了一轮投票,解决第一轮投票不能达成一致的情况,这就是commit阶段。但是细想一下,第二轮投票也会出现达不成一致的情况:

虽然解决了第一轮投票的问题,但是好像第二轮投票又出现了第一轮同样的问题?实际上PBFT对第二轮投票进行了优化:

动态 | 延安上线以区块链等技术打造的新型城市管理平台:据新华网消息,1月25日上午,延安市宝塔区携手腾讯、百度、阿里等互联网公司,打造的智慧乡村、掌上社区、数字宝塔、信用街区、全民城管的“宝您满意”智慧民生系列数字应用平台上线。“宝您满意”系列数字应用平台是通过融合运用云计算、大数据、物联网、人工智能、区块链等信息化技术打造的新型城市管理平台。[2019/1/26]

所有节点在发送确认消息的时候,不但要告诉其他节点自己的状态,还需要带上证明,也就是需要带上其他节点发给自己的2f+1个vote的签名消息。

在区块链的应用场景里,后一个块是基于前一个块的。如果以BFT作为共识,那么出块顺序是确定的,后面出块的节点不仅要构建新的区块,还需要在提案中给出前一个区块的证明,要么2f+1签名的commit,要么2f+1的超时签名,否则,该出块节点就是拜占庭节点,将发起超时投票给下一个出块节点。

以上是对PBFT以及两阶段确认的一个大概讲述。非拜占庭节点通过两轮投票达成共识,通过多leader和超时等机制保证了协议的活性,但是,需要O(N^3)的消息复杂度。

三阶段确认的Hotstuff

PBFT是一个非常经典的拜占庭容错算法。在两阶段确认的commit阶段,由于要带上其他节点签名的vote消息以证明自己的状态不是说谎来的,这导致了O(N^3)的消息复杂度,因此也有明显的瓶颈。有没有算法能解决这个问题呢?Libra的LibraBFT共识协议选用的?

Hotstuff?拜占庭容错算法通过“门限签名+三阶段确认”很巧妙的解决了这个问题。

Hotstuff的第一作者是康奈尔大学的在读博士生尹茂帆老师。对比前面的两阶段确认,我们看到,Hotstuff在prepare和commit中间多了一个pre-commit阶段,为什么多一轮投票就能解决消息复杂度的问题呢?

首先,我们简单的说明一下门限签名的作用,感兴趣的可以自己去研究一下。n个节点通过某种方式给每个节点生成了一个私钥,但是只有一个公共的公钥。接下来,所有的投票信息都由属于自己的这把私钥进行(k,n)签名。同一条消息,只有集齐了k个节点的签名,才能构造出一个能通过公共的公钥验证成功的总签名。这样的话,节点的提案要想达成共识,必须收集2f+1个节点对同一条“同意该提案”的消息的签名,才能构造出一个能使用公共的公钥验证成功的总签名,否则就进入了超时流程。

接下来,我们看一下使用了门限签名之后,三阶段确认大概的过程。我们来重点看一下由leader发起的4条消息:

①prepare阶段:leader将包含自己的“提案+前一个commitQC”的消息msg1广播给所有节点

②pre-commit阶段:leader收到了2f+1个节点“通过msg1提案”的签名消息,然后使用这些签名构造一个“prepareQC总签名”的消息msg2,并将msg2广播给所有节点,让他们对自己构造的prepareQC进行验证

③commit阶段:leader收到了2f+1个节点“msg2的prepareQC验证通过”的签名消息,然后使用这些签名又构造成一个“pre-commitQC总签名+提交提案”的消息msg3,并广播给所有节点pre-commitQC进行验证

富士通技术解决方案有限公司执行董事会成员加入IOTA基金会:根据thebitcoinnews报道,几个小时前IOTA在博客上宣布,Rolf Werner博士正式加盟IOTA基金会。Werner目前负责富士通的欧洲市场以及德意志地区的所有业务活动,同时还是富士通技术解决方案有限公司执行董事会成员。Werner是继Bosch与VW后又一位加入IOTA基金会的知名专家。[2018/4/9]

④decide阶段:leader收到了2f+1个节点“msg3的pre-commitQC验证通过”的签名消息,这个时候等于leader收到共识达成一致的证明,然后使用这些签名正式构造一个commitQC总签名的消息msg4,广播给所有节点

以上是三阶段确认的大概过程,有点绕口,从图可以看出,与两阶段对比,主要有两点不同:

三阶段确认比两阶段确认多了一个pre-commit阶段。实际上三阶段确认的pre-commit阶段+commit阶段,就等于两阶段确认的commit阶段。换句话说,两阶段确认的commit阶段里包含了2f+1个节点的vote用于证明自己没有说谎,这个证明在三阶段确认中被独立拿出来进行了一轮投票,就是上图中的pre-commit阶段。这是两阶段确认模型与三阶段确认模型的主要区别,这么理解,上面的过程就不饶了。

所有节点只跟leader打交道:三阶段确认巧妙的通过门限签名,将本应该是所有节点都要收集的消息,优化成“leader统一收集,其他节点只需要对总签名进行校验”的过程,将消息复杂度降到了O(N)。当然,超时机制差不多,需要收集2f+1的超时签名构造一个总签名,替换掉commitQC。

以上就是我认为的三阶段确认与两阶段确认最主要的区别,其中QC是法定节点数证书,可以理解为总的签名。

链式Hotstuff

前面我们讲述了三阶段确认其实是BasicHotStuff,在区块链的应用场景下,整个过程概括起来大概是这样的:

总的来说就是“prepareQC->pre-commitQC->commitQC”这3个门限签名的QC不断的转换,hotstuff作者们在三阶段确认的基础上,又对算法做了进一步优化,这就是ChainedHotStuff:

投票轮次和网络消息都得到了很好的优化,将原本需要进行3轮的投票,合并到1轮了。最终的结果就成了这样:

这是链式hotstuff设计巧妙的地方。

Libra的consensus组件

前面我们深入介绍了BFT的背景知识,包括拜占庭将军的故事、拜占庭容错算法最多能容忍的拜占庭节点数、部分同步模型;接着,我们详细讲述了两阶段确认的拜占庭容错算法;最后,我们讲述了巧妙的结合了门限签名和三阶段确认的Hotstuff,以及进一步优化后的链式Hotstuff。

LibraBFT共识是基于Hotstuff实现的,我们先看一下Libra的Block结构:

是不是跟链式Hotstuff很像?Libra在每一轮投票中,既会校验当前Proposal的Block,同时也会对爷爷Block达成共识。这样,爷爷Block就会被commit,并把Block包含的Transaction以及涉及的用户状态存储到DB中。

所以Libra的Ledger存储看上去总是比Block存储低两个高度,因为后来两个高度的Block还没有达成共识,分别处于pre-commitQC阶段和prepareQC阶段。Libra实现的共识流程大概是这样的:

上图有两个需要注意的地方:

round代表了一轮投票,round的event由Pacemaker维护,Pacemaker组件主要负责算法活性,维护超时时间;

绿色表示当前round的leader,负责生成Block并发起proposal;黄色表示其他Validator节点,负责验证和投票;红色表示下一个round的leader,负责收集统计投票、处理commit,然后在下一个round构造Block、发起proposal;

这里有几个关键的问题,在流程中没有体现出来:

如何确定proposer

如何更新一组proposer

下面我们来逐个讨论。

如何确定proposer

Libra的实现中有3种proposer策略:FixedProposer、MultipleOrderedProposers、RotatingProposer。

FixedProposer:表示指定固定节点当Proposer,一般用于测试;

RotatingProposer:表示一批节点轮流当Proposer,每个round返回一个Proposer;

MultipleOrderedProposers:复杂一些,见下图,其中还使用了随机数VRF算法,保障每个round所有节点得到一组相同顺序的Proposer,但是每个round之间的Proposer顺序不同;

所以在使用MultipleOrderedProposers的情况下,每轮投票都有一组Proposer,Proposer存在优先级,非拜占庭节点会根据Proposer的优先级,给优先级最高的Proposer投票。这样减少了Proposer为拜占庭节点的风险,如果一组Proposer均为拜占庭节点,那么Validator投超时的票TC。

如何更新一组proposer

前面我们讲述了Proposer大概的确定过程,多个round的Proposer组虽然顺序不同,但是一直是相同的几个Proposer在不停的变换顺序。那如果要换掉这些Proposer呢?尤其是需要在这么多节点之间要同一时间对同一结果达成共识。

实际上,更新Proposer组需要通过transaction调用add_validator或者remove_validator的合约,transaction在打包的时候会被执行,如果存在validator更新,会把更新放到Block的block_info中,同时也会把transaction打包进Block。最后,随着这个Block被commit,所有的Validator会根据block_info的信息更新本地的proposer组。这样,所有的节点在同一个round把proposer组更新了,整个过程在libra中叫Reconfiguration。

总结

在Libra的第3条主线中,概念和内容比较多,我们先后介绍了这些内容:

为了保证所有账号的数据正确,所以需要在全球范围对transaction的顺序快速达成共识;

当下主流的共识协议,例如Pow、Pos、BFT等;

Libra使用了Hotstuff算法,属于BFT的一种,因此我们了解了很多跟BFT相关的背景知识,主要包括两阶段确认、三阶段确认以及链式Hotstuff;

最后,我们了解了Libra的consensus组件,包括投票流程、确定proposer的流程、Reconfiguration流程等等,基本上覆盖了LIbraBFT共识协议的主要过程。

本文作者Westar实验室技术专家邓启明。这是Westar实验室官网,欢迎大家关注?http://westar.io/

标签:POSPROPPROSERpos币种PROP币PROMISEVeriumReserve

火必热门资讯
GER:全民消费码、国家数字货币、40万亿新基建与ABCDE五种武器救经济

这次新冠肺炎,对中国和世界经济的伤害是巨大的。一开始还有人隔岸观火,但如今确诊病例已经遍及除南极洲之外所有大洲.

1900/1/1 0:00:00
COIN:大户开始进入新的积累阶段,ETH上涨信号来了?

一些最大的以太坊钱包正在囤币,这标志着一个新的积累阶段开始了。这些利益相关者可能会在将资产抵押到ETH2.0中之前尽量避免出售ETH.

1900/1/1 0:00:00
比特币:走出疫情阴影,矿圈备战减半

文:凯尔来源:蜂巢财经编者注:本文作了不改变作者原意的删减。由于新冠肺炎疫情的爆发,挖矿业的上下游在年初受到短暂影响。随着各端口正式复工,矿业逐渐回归正轨.

1900/1/1 0:00:00
STE:少了中国的 Voice,还说要「game changing」吗?

在这个冷清到连朋友圈都没有人晒转账的情人节,EOS创始人DanielLarimar成了加密货币行业这一天的主角.

1900/1/1 0:00:00
GRAM:亿万富翁、前政府高官和乔布斯遗孀,Telegram投资者阵容豪华

据知情人士称,史蒂夫·乔布斯的遗孀劳伦·鲍威尔·乔布斯投资了Telegram的Gram代币,参与了TelegramOpenNetwork项目的ICO.

1900/1/1 0:00:00
GAU:中国日报:疫情防控或加快推进数字货币的发行

原文:中国日报网随着新型冠状病肺炎疫情防控工作进入关键阶段,社会公众关心的使用现金支付是否安全的问题近期得到了相关的权威解释.

1900/1/1 0:00:00