快捷搜索:  as

基于区块链拜占庭容错共识的Libra共识算法介绍

Facebook 近日公布的 Libra 白皮书引起各界持续关注,其网站公开的技巧文档也被诸多专家核阅。文档提到,Libra 区块链将应用基于拜占庭容错共识的「LibraBFT」共识算法,而 LibraBFT 则是「HotStuff」的一个变种。

Libra 区块链所采纳的 LibraBFT 共识协议的技巧论文

这个名为 HotStuff 的算法,究竟是如何一种「美人」呢?

顺藤摸瓜,我们发明,HotStuff 算法论文由云谋略公司 VMWare 的钻研团队颁发,其安然性及可用性已颠末完备的数学证实。论文作者有 5 人,分手为 Maofan Yin、Dahlia Malkhi、Michael K. Reite、Guy Golan Gueta、Ittai Abraham。

HotStuff 算法论文https://arxiv.org/pdf/1803.05069.pdf

着实「HotStuff」算法论文的第一作者尹茂帆(Ted Yin)是链闻的老同伙。今年仅仅 25 岁的尹茂帆本科卒业于上海交大年夜,今朝在美国康奈尔大年夜学(Cornell)大年夜学读博士学位,当前的主攻偏向是散播式系统的根基钻研,导师是闻名谋略机科学家 Emin Gun Sirer,另一导师是 Robbert van Renesse。尹茂帆也是另一个市场颇为注视的新项目 Ava Labs 的联合开创人和首席系统架构师。

在 Facebook 正式宣布 Libra 白皮书之后,尹茂帆吸收了链闻的专访,他为我们详解了 HotStuff 的玄妙。

首次进入散播式共识算法领域的人,很轻易被一大年夜堆名词绕晕。而深入研究,你会发明这些名词背后有着各类各样的命名故事。比如 DLS 算法便是三位作者的缩写:Dwork、Lynch 和 Stockmeyer。而 PBFT 算法便是「实用拜占庭容错」的首字母缩写(Practical ByzanTIne Fault Tolerance),BFT 自然便是「拜占庭容错」了(下文将统一应用 BFT)。那么,这个物种的新人 HotStuff 的名字到底怎么来的呢?

尹茂帆解释说,之以是取名为 HotStuff,是由于这个单词在英文里有三重意思:一是性感的人,一是炙手可热的好器械,一是某个动画里的小恶魔的名字。大年夜家都知道,以太坊下一代共识算法 Casper 之名,也是来自一个动画角色。以是,HotStuff 可以和它相映成趣了。

在吸收链闻采访时,尹茂帆灵机一动,把这个词的中文翻译为美人。以是本文标题的美人,可不是哗众取宠。尹茂帆说,美人有两层意思,一是绝世美男,一是奇珍奇宝。HotStuff 翻译成美人,的确神工鬼斧。

据先容,HotStuff 已经在一个具有 100 多个副本的收集长进行过支配,跨越了 BFT-SMaRt 的吞吐量,同时维持着与之相称的延迟,而在更为实际的测试中机能均跨越后者。

和其他散播式系统的共识协议比拟,HotStuff 到底有哪些优点呢?以下是链闻记者和尹茂帆的问答:

链闻:关于散播式系统的共识协议,大年夜致可分为两类,一类因此比特币为代表的区块链算法(或者称为中本聪共识),一类是经典的 BFT 算法(如 DLS、PBFT)。两者在利用前提和机能方面,有哪些大年夜的差异和好坏?

尹茂帆:两者的差别大年夜致可以分为五个方面:1)成员信息;2)机能,包括吞吐量,延迟等;3)抗女巫进击 (Sybil attack)——中本聪共识自带抗女巫进击,而经典的 BFT 必要额外的 PoS 或者 PoW;4)可扩容性;5)安然性,即概率 vs 确定性。

中本聪共识的优点是,无需提前知道共识的所有介入者,不要求正确的成员信息。由于共识的一部分采纳了 PoW (事情量证实),以是生造诣对女巫进击具有必然免疫。而且,中本聪共识的算法十分简单,通俗人稍具数学根基,就可以理解。中本聪共识也轻易扩容,在 10 个结点和 1000 个结点上受到的机能丧掉较小(一方面是由于不必要广播投票,另一方面是由于它原先就很慢,见以下解释。)

中本聪共识的毛病也很显着。由于 PoW 的难度和等待链长度跟安然性有关,从根本上说机能很差,买卖营业确认延迟大年夜也无法改变。现有的所有基于中本聪共识的「魔改」(换汤不换药的扩容)协议,着实只能增添吞吐量。而抛开延迟谈吞吐量,意义不大年夜。好比我可以开一个卡车运一车硬盘来输送数据,虽然是超高吞吐量,但也是超高延迟。

在安然性方面,和传统 BFT 共识比拟,中本聪共识只供给概率的安然包管,而 BFT 则是 100% 安然。这里说的安然,或者称为同等性,便是能否避免双花。着实,比特币出六个块能发生双花的概率并不像大年夜家想的那么低,有高达 13% 的概率呈现共识掉败 (即 BFT 中的 30% 节点的环境)。以此来看,假如要公道对照的话,中本聪共识的效率异常之低。(六个块已经耗时一个小时了。)

再来看经典 BFT 共识,其条件或者说毛病是,必要知道所有介入者,要求 100% 正确的成员信息。别的,经典 BFT 共知趣对较难扩容。在 HotStuff 前,大年夜部分经典 BFT 都必要所有结点广播,这带来了平方级其余繁杂度(包括 Tendermint 论文里面描述的算法)。增添大年夜量结点会导致收集拥塞。而且,此中的 Leader 结点会遭遇全部收集的负载(负载极其不均衡),导致难以扩容到成千上万个结点而没有太大年夜机能丧掉。

BFT 共识的优点则在于,由于共识没有应用无意义的 PoW,以是,经典 BFT 共识的协议速率跟收集发送大年夜量短消息的速率相关,没有中本聪共识那种额外的能源耗损和等待光阴。买卖营业延迟异常小,假如不斟酌收集延迟,买卖营业在数十至数百毫秒级别,假如斟酌收集延迟,就跟收集延迟同数量级。

链闻:你们论文在开篇声称,HotStuff 基于一个新的框架,这个框架在经典 BFT 根基和区块链之间搭建了一座桥梁。若何理解这句话?

尹茂帆:我们的论文名为《美人协议:透过区块链看拜占庭容错共识》(HotStuff: BFT Consensus in the Lens of Blockchain)。

之以是这么描述,是由于它的算法框架(可以出生多个衍生算法)采纳了树 / 链式布局,十分类似区块链。别的,和传统区块链类似,一个结点当前也有被视作「主链」的一根链,投票只会投给当前觉得主链上扩展的新部分。和区块链一样,假如侧链足够「好」,那么它就会变成新的主链。在区块链里面,这个是经由过程链长度来鉴定的(尊长胜),而在 HotStuff 中,它经由过程近来一次成功得到大年夜部分投票的块抉择。

另一方面,HotStuff 又是传统 BFT 体系下的一员。用此算法框架可以很好地解释 PBFT、DLS、Tendermint、Casper 等协议,达到了必然程度上的归纳和统一。别的,跟之前同类型算法最大年夜差别也是最大年夜供献的地方是——HotStuff 的核心换届算法没有特殊环境;不像 PBFT 那样有「正常」的履行流程以及「特殊」的换届流程,HotStuff 统一了两者,即没有显式的换届特殊处置惩罚,也可以觉得是潜在地处处换届。这使得编写一个基于 HotStuff 的共识系统的根基安然部分十分轻易。比较 PBFT 的数千行换届代码,HotStuff 只必要几十或百余行即可。

另一个它较同类型算法更优良的特征是,它对工程师们十分友好。它将包管精确性和包管机能的逻辑从算法层面上就进行懂得耦合。一旦安然性包管的几十行代码完成,剩下的根据详细利用处景的优化(包括换届机制,政策)都不会再触及这部分,使得系统始终安然。

链闻:PBFT 算法可以在互联网等异步情况中运行,一些优化也使它较曩昔的共识算法更快。但它也有一些问题,比如检测不良主要节点和从新选择新主要节点(view change)的历程异常低效。比如为了杀青共识,PBFT 必要平方级其余消息互换,这意味着每台谋略机都必须与收集中其他所有谋略机进行通信。总之,PBFT 的扩容性显然不敷。HotStuff 对这些问题有哪些办理规划?

尹茂帆:首先,HotStuff 将换届的价值首次从平方级低落至线性繁杂度,这意味着它和 Paxos/Raft 这些在 IT 行业广泛应用的非 BFT 协议一样,拥有同等的繁杂度。别的,虽然理论上 Tendermint 等协议可以经由过程结合数字署名来低落到同样繁杂度,然则,这些协议本色上必要在块与块间等待最大年夜的可能收集延迟,使得实际实现出来的系统变成了一个同步系统。而 HotStuff 思路跳出了原有的框架,提出了一个极简的算法体系,使得它可以很轻易地突破这个传统 BFT 的魔咒。颠末测试,它可以在包管简单代码实现、低理论繁杂度的环境下打败现有的最快的传统 BFT 实现,在商用系统方面具有无限潜力。

链闻:Facebook 的 Libra 白皮书提出,Libra 区块链是从“许可型区块链”起步的,未来目标是成为非许可型收集。由许可型转向非许可型,今朝有可行的技巧路径吗?难点在于扩容(从 100 个节点增添到成千上万个节点)照样在于能否抗女巫进击?

尹茂帆:理论上来说,任何许可协议都可以转化成非许可型协议。由于传统的共识协议(无论是 BFT 照样非 BFT),都可以经由过程共识本身来从新设置设置设备摆设摆设以增添 / 删除结点。然则由于潜在的女巫进击,这种基于正确成员信息的协议,必要额外依附一个 PoS 或者 PoW 的进入机制来开放系统。

HotStuff 共识的其他实施

除了 Facebook,其他一些区块链项目也已经抉择应用 HotStuff 共识。此中一个是公链项目 Cypherium(cypherium.io)。有趣的是,Cypherium 项目声称可以实现非许可型的扩展——假如这个考试测验成真,意味着这可以为 Facebook 提出的转型路线图,供给了一种办理规划。

Cypherium 首席履行官 Sky Guo 吸收链闻采访中说清楚明了这里面的要点:

他说,与 Libra 未来计划转型为 PoS 不合的是,Cypherium 的主网将设计成 PoW+HotStuff 的混杂共识机制。

平日来讲,区块链共识分为两个历程:选举引导者、打包与验证区块。传统项目里这两个历程由同一种共识机制实现。而 Cypherium 在第一个历程中选用了 PoW 共识,用于选择引导者节点。任何谋略设备均可以经由过程挖矿的要领成为 Cypherium 的验证节点而不依附于受相信的第三方。每当有矿工成功挖到 PoW 时,验证委员会傍边光阴最老的节点脱离委员会,新的矿工成为验证委员,实现永远性的动态轮换。而第二个历程,则选用了效率较高的 HotStuff 共识来打包和验证区块。响应地,Cypherium 设计了选举链+买卖营业链的双链架构。Sky Guo 声称,Cypherium 共识 CypherBFT 可以做到完全去中间化、买卖营业顺时终极确认、支持亿级用户的利用处景。

您可能还会对下面的文章感兴趣: