DAH:Libra 采用的 HotStuff 算法作者亲述:「尤物」诞生记

Facebook公布了Libra白皮书和相关技术文档之后,链闻发现了Libra区块链将使用基于拜占庭容错共识的「LibraBFT」共识算法,而LibraBFT算法则是「HotStuff」的一个变种。之后,链闻又顺藤摸瓜,找到了「HotStuff」论文的第一作者、美国康奈尔大学大学在读博士生尹茂帆,请他讲述了HotStuff的奥妙。

TedYin今年25岁,目前导师是著名计算机科学家EminGünSirer教授和RobbertvanRenesse教授。他同时也是市场颇为瞩目的区块链新项目AvaLabs的联合创始人和首席系统架构师。

2018年暑期期间,他在VMwareResearch实习时提出了「HotStuff」协议中核心算法,并完成了相关论文。

我们邀请TedYin撰文分享了他提出「HotStuff」核心算法前前后后的经历。我们希望通过这篇文章,记录下一个创新性算法被年轻华人研究者提出的背景,一个有可能推动区块链技术发展的基础性研究工作完成的来龙去脉。我们希望以此帮助读者更好理解「HotStuff」,更可以激励区块链行业的研究者和开发者更好地建设。

撰文:TedYin,康奈尔大学博士生,AvaLabs的联合创始人兼首席系统架构师

TedYin,HotStuff论文第一作者,AvaLabs的联合创始人和首席系统架构师。

一入系统深似海

没想到,HotStuff,这个被我中文起名为「尤物」协议的科研成果,或多或少竟源自于我第一个「失败」的研究。请容我细细说来。

2016年,博士之旅伊始,我的导师EminGünSirer教授便拿出几份论文让我细细研读。其中有:

PaxosMadeModeratelyComplex;

ByzantineQuorumSystems;

ImplementingFault-TolerantServicesUsingtheStateMachineApproach。

这些都是共识协议研究经典中的经典。更没想到的是,有一天,我竟有幸与ByzantineQuorumSystems的两位作者合作完成了后来的尤物协议。

声音 | 美联储埃文斯:加密货币Libra可以很快壮大起来 美联储需要理解其意义:美联储埃文斯:Facebook(FB.O)旗下加密货币Libra可以很快壮大起来,美联储需要理解其意义。[2019/9/25]

相较于人工智能的论文,计算机系统相关的研究论文篇幅都较长,一般有十来页。而共识协议算法的论文每一页的难度又令人望而却步。在理解了共识问题的基础以及经典算法以后,一次开会中,Gün教授开始考我了。本来胸有成竹的我,被他连珠炮一般的问题问得说不出话来。

「看来你需要回去重新读一遍啦,Ted!」,他淡然一笑,「不必担心,本来这世界上没多少人懂Paxos。」

在1990年提出的一种基于消息传递且具有高度容错特性的一致性算法,很多大型分布式系统都采用Paxos算法来解决分布式一致性问题,Paxos算法被普遍认为难以理解,难以实现。)

我愧色满面,仓皇逃出了办公室。于是下决心要把其中逻辑理清,以至无懈可击。

「异步」难题

共识协议,或者推广至各种分布式系统的协议,是一类基于时态逻辑的算法描述,其难点在于「异步」。

所谓异步,就是若干个相对独立逻辑可以同时执行,并且它们之间能够依据算法发生交互。这里的「异步」与异步协议中异步所指不同,更接近于并发的概念。

其实在日常生活中,我们也无时无刻不进行这种「异步」的操作:我们不会干等一天别人的消息,也不会在整个项目所有的事情做完后才睡觉休息。我们往往是会「同时」处理若干个不同的事务,尽量不会因为一件事没有做完而被卡住不做后续的所有事情。

这种等待着一件事情完成再处理另一件事情的过程,就可以被称为「同步」;而把事情做一部分丢给别人,接着马上进行其他操作的过程中,则产生了「异步」。

正如生活中的多任务同时处理一样,带有异步/并发性质的算法设计充满了挑战。以Paxos算法为例,它是一种对宕机有一定容忍度的冗余算法。用通俗的话讲,也就是我们希望有若干个机器去备份同一个系统状态。这个状态可以是用户的信息、银行的交易,或者平台上程序的执行序列。这种「备份」,使得整个系统有一定的抗故障能力——一台带状态副本的机器崩溃之后,我们仍然有别的机器可以使用。

动态 | 三星投资加密货币钱包 ZenGo 已支持 Libra 测试网络:加密货币钱包 ZenGo 已支持由 Facebook 发起的数字货币 Libra 的测试网络,可以进行转账收款操作。由于是测试网络,所以持有的资金是没有任何实际价值的,仅供测试用途。ZenGo 在文章中介绍到,Facebook 自己开发的钱包 Calibra 将会是托管钱包,但 ZenGo 将会是一个非托管钱包。据此前消息,加密货币移动钱包 ZenGo 获得 400 万美元投资,欧洲投行 Benson Oak、三星、Elron 等参投。[2019/8/19]

Paxos作为这类协议的代表已经在业界获得了广泛的使用,比如Google的Spanner系统。毫不客气地说,云服务和大规模数据中心的崛起,重要原因之一就要归功于此。美国计算机科学家莱斯利·兰波特提出了Paxos算法,这成为让他在2013年获得图灵奖的重要原因之一——当然,兰波特有太多的贡献了,包括后文会提到的拜占庭容错算法,这里就不一一展开了。

不过,像Paxos这类算法因为需要保证系统各个机器同时处于一致的状态,以便对外表现为一个不间断的服务,因而十分难以设计和理解。

当然,我的那个故事的结局是:重新来过,认真钻研,自信满满地再次接受也解答了Gün教授提出的若干个刁钻的问题,最终通过了他的考验。

「那么接下来我希望你思考一下能不能基于区块链的结构设计一个CFT算法,打败Paxos。」Gün教授说。

「好的。」我回答到。

虽万难吾往矣

就这么简单的一句话,花去了我整整第一年一个学期的时间。

现在回想,这个过程短暂又漫长,时而枯燥无味,但时而又充满惊奇。我曾经构想出了一些看似正确的算法,但仅仅过了一天,随即便发现无法证明,或者算法本身存在错误。直到在第一个暑假来临前,我向导师提交了一份关于这方面研究的报告。

在报告中我分析了尝试用链式结构打败Paxos的各种大方向。其中主要分为两种:

一种路线是采取类似原中本聪共识中的概率模型,然后通过随机的等待时间来建立起一个可以收敛的共识链;

声音 | 平安集团杨承亮:Libra实际上是一个支付工具:8月8日,在2019SAIF金融论坛上。中国平安保险(集团)资金部副总经理杨承亮在谈论关于libra的话题时称,Libra协会注册在瑞士,Facebook以及很多大佬都在发起成立这个协会。但首先要看它是个公立还是私立的,这涉及到货币是公有还是私有的。在全球而言,法定货币都是由央行发行的,私营机构做货币,这涉及到公共场景的问题,所以,他认同中国行长的观点,如果一个公共服务的产品,背后没有设立公共机构来参与可能会有一些问题,特别是作为全球性的支付货币,还涉及到很多其他的问题。另外,货币具有创造货币的一个功能,但是,Libra实际上是一个支付工具,国家推行货币的过程中应该吸收更多的金融机构来参与设置,这样能够更快激发一些创新的活力。[2019/8/9]

另一种截然不同的思路则是像Paxos那样,使用子集交来把Paxos「编码」在链上。

在报告中,我给出了基于Python快速构建的Raft和第一种路线的性能对比,得出了不成功的结论。而Gün教授对另一个路线并不持乐观态度——因为Paxos/Raft现在已经被优化得很快了,在这种只有宕机的容错场景下是不具备优势的。

我们决定放弃这个CFT相关的研究,我也转而有了一个新项目,也就是后来的Avalanche协议。它是一种概率安全的拜占庭容错协议,这里暂不展开。

有趣的是,报告提到的两条路线中,第一个正好和早期的DPoS思路如初一辙。DPoS是一个备受争议的协议,它在早期并不是拜占庭容错的,而且协议本身没有严格的证明或者性能的测试,主要使用它的EOS虚拟货币,也沦为了一个高度中心化的系统。而第二个路线,如果将问题的领域由宕机容错变为拜占庭容错,Paxos改换成DLS/PBFT,则像极了后来的尤物协议。

一拍即合

17年秋季学期即逝,我向VMwareResearch的首席研究员DahliaMalkhi表达了实习的意向。

当年12月,在清华—康奈尔区块链研讨会期间,Dahlia和VMwareResearch的高级研究员IttaiAbraham飞到深圳,短暂参会并作了学术报告。报告内容是关于BFT协议在区块链时代下的新研究课题。期间,他们宣布发现了2007年获得SOSP最佳论文的ZyzzyvaBFT系统存在的正确性问题,借此说明BFT协议过于复杂和难以理解,以致在业界无数专家审稿的10年以后,仍然可能会发现算法层面的正确性bug。

声音 | 阿布扎比全球市场FSRA CEO:Libra“迫使”各国监管机构认真审视加密货币和区块链:据CNBC消息, 阿布扎比全球市场(ADGM)金融服务监管局(FSRA)首席执行官Richard Teng表示,Facebook的加密货币Libra“迫使”各国央行和监管机构认真审视加密货币和区块链。Richard称:“我认为我们已经拖延太久了。这个行业需要得到适当的监管才能成为主流。” 在谈到阿布扎比全球市场的加密监管规则时,Richard表示:仅去年一年,就有价值10亿美元的代币丢失或被盗,这影响了人们对这个市场的信心。在投资者保护方面,妥善处理风险始终是最重要的。除安全问题外,重要的是要有支持创新的态度。[2019/6/30]

我们在她宣讲的当天吃了早饭,席间她简短地用了30分钟问了一些关于我目前科研的问题作为面试。

Dahlia在业界以一针见血和才思敏捷著称,在挺过了她的一些关于Avalanche协议的一些尖锐问题后,她表达出了对我一开始那个「夭折」CFT项目的浓厚兴趣。在次年的远程交流中,她提到了一个在构想的BFT算法有些类似于我的项目,并且询问我当初放弃的原因。之后我们一拍即合,去VMwareResearch实习的事情也就这么定了下来。

太平洋的风

实习就这么开始了。从东岸的纽约飞到了西岸的加州。美好的湾区,全新的暑假。烈日下,太平洋的风时而拨弄着我手中的纸页,我则低头继续思考着「谁是坏人,谁是好人,谁又背叛了谁」的问题——拜占庭容错。

Dahlia告诉我说,一般世界各地的博士生来这里实习的头一周都不需要做什么,而是应该去尝试摸清自己的能力,以及寻找感兴趣的项目。彼时,她提到希望我能看一下他们于三月份撰写的文稿。

我喜忧参半。「喜」是因为有明确的文稿可以阅读,「忧」则是这个预印稿是不是意味着算法已经设计完毕,而我能做的事所剩无几?

实际上,在「挣扎」着阅读了一周以后,我发现初稿中描述的算法很是模糊,正确性的证明也是一笔带过,其中两个核心引理都是一句话。于是,在商议后,我们做了一个后来觉得极为明智,但对我来说也十分挑战的决定:我不去看那篇预印稿,而是从一张白纸开始,凭着自己受到的启发,结合已有的积累,用我的符号系统来重新描述算法,并且尝试给出严格的证明。

声音 | 美国总统候选人杨安泽:Libra对数以亿计的无银行账户者而言是一次大的迈进:美国总统候选人杨安泽(Andrew Yang)发推称:Facebook的新加密货币Libra对于全球数以亿计的无银行账户者而言是一次大的迈进。(Libra)使用区块链很有意义,甚至可以遏制腐败,因为国际社会为贫困人口提供的大量援助资金从未到达他们手中。[2019/6/19]

整个过程大概又花费了将近一周,最后我将重写的几页稿子交给了Dahlia。令我欣喜的是,得到的反馈非常鼓舞人心。Dahlia说我自己重头设计的算法在本质上和她当初的构想大体相似。

但是不久她就发现了一个很不一样的地方:我的协议里面需要的假设比原本的预印稿的要更少。

我的解释是,原稿里面维护的变量和隐含条件过多,而且有的好像也不是必要。我相信「简单即是优美」的原则,于是去掉了一些觉得冗余的不变量。

瞬间,Dahlia变得严肃认真了起来,直截了当地说,「不,这个简化会直接破坏协议的正确性」。

好在我已早有准备,向她解释了这个「重要」条件其实是不必要的。但是她依然坚持。

讨论变得逐渐激烈,于是我壮了胆,带着十足底气的口吻「挑战」道:「Ifso,couldyoupleaseshowmeacounterexample?」她立即开始在眼前的白板上写写画画,我全神贯注,准备迎接对我思维以及口语表达的挑战。

在她数次尝试失败之后,我再次耐心地解释了一遍无需那个条件的原因。我说,听上去确实挺反直觉的,我一开始也觉得困惑,但是后来发现证明正确性并不需要它。最后,她将马克笔缓缓放下,笑着长出了一口气说,「目前我想不到反对的理由。Ted,你赢了。哈哈。」

证明不是一笔挥就的。我一开始自鸣得意的证明很快就被Dahlia发现了一个致命问题:有一个条件从来没有用过。和之前我们所争论的冗余条件不同,我们都意识到这是一个极为关键的条件,奈何找遍了整个证明都没有!

这种感觉就像是修好一个机器后发现手头多了一些零件,又或是做完手术发现金属盘里多出了一些器官一般。所幸的是,很快我们发现了其中一句话其实暗含了条件,但欣慰之余又感叹就算是专业人士,做这种BFT协议也是十分棘手。

随后,我们计划将旧稿替换成现在重写的新稿。

高手过招

Dahlia一直是我最敬重的学者之一,因为她平易近人,跟年轻人打成一片,而在讨论学术问题时又有着渊博的知识储备和学者的严肃威严,讨论细致入微,不让毫厘。

老实说,在讨论中,大多数时候还是她取得了「胜利」。跟高手「过招」,我不得不叹服她思维的深度、广度和速度。这也是跟她合作的乐趣:就像是一场赛车比赛,稍一不留神,她就在弯道直接超车,一骑绝尘了;或是在你飞速狂奔而不知其所往时将其横刀拦下,使之冷静下来解释清楚。

不久,坐在旁桌的MikeReiter也加入了我们的讨论。我对计算机安全领域的大佬知之甚少,自然也是不知道这位Mike的来头。只是当时觉得他特别友善,还经常来问我需不需要来看一眼我的稿子,或者讨论一下算法问题。

MikeReiter,现为北卡罗来纳大学教堂山分校计算机系教授

他也对HotStuff感兴趣,于是我们便有了三人的开会小组。再后来我才意识到,原来最早读的那篇于1998年发表的著名论文「拜占庭仲裁系统ByzantineQuorumSystems」,正是Dahlia和Mike在AT&T实验室工作时期所合著的成果。那时的我还在幼儿园留着口水,咬着手指。

1998年发表在学术期刊「分布式计算」上的论文「Byzantinequorumsystems」

相比Dahlia,Mike更像是那种深藏不露的扫地僧。他时常会在你作报告加速时打断,慢条斯理道:「恕我愚钝,但是我不理解你刚刚说的东西,你能再解释一遍吗?」而我逐渐察觉到他懂的其实远比看上去的多,总能在关键的地方提出非常好的问题。一旦他和Dahlia争论起来,我几乎无法插嘴,只好在一旁以崇敬的目光看着两位「神仙大战」。

犹物之生

Dahlia提起了最初的论文稿其实投了2018年的PODC会议,结果被拒。原因有二:审稿人觉得这论文写得太笼统,他们没能理解算法的具体过程,以及证明过于简陋;另一方面则是他们认为实用拜占庭容错算法的期刊版本已经在其中「暗示」了可能存在线性复杂度的换届,所以论文号称的线性换届并不是新东西。

Dahlia对第一点心服口服——这也是让我不看原文重头写过的原因之一。但她对第二点不以为然,因为她去找来了那个期刊论文,所谓「暗示」并不可行。

就这一点,我们两人在一次讨论中对PBFT期刊版本的算法进行了剖析,最终得出了一个好消息和一个坏消息:好消息是PBFT的换届做不到线性,也就是审稿人的说法有误;但坏消息是,Dahlia的旧稿里面的算法并不符合标题所说的完全线性,而是有更深层次的微妙之处。

就在这次和Dahlia对PBFT期刊版本的讨论中,我们得到了新的思路

实际上,为了保证响应度,不得不变成平方复杂度;或者为了线性复杂度而放弃响应度。无论何种取舍,皆使我们的贡献度大幅缩水——这朵乌云不幸地于周五飘在了头顶,在这沦为「incrementalwork」的阴霾下我们若有所思地开始了周末。

柳暗花明

山重水复后,我席间提到的一个思路给了Dahlia新的启发。于是,在那个周日的下午,当我还在家慵懒地用笔记本看新闻时,突然收到了一封她上千字的邮件。

果然,在我们的HotStuff体系中,尽管最初的算法跟Tendermint本质相仿,但还有别的变种可以打破这种壁垒:在保证与PBFT类似响应度的同时,达到线性的消息复杂度下界,即理论最优。值得一提的是,前面提到的Paxos同样也是线性复杂度。

主要思路就是那天讨论中我突发奇想提到的:「如果我们增加一个阶段呢?两个阶段的协议变三个阶段,但是好像我们可以用中间阶段维护的不变量来避免Liveness的问题,从而完全保证响应度。」

于是,便有了第三版的「尤物」,也是Facebook的LibraBFT所基于的那个。

尽管在最终发表的论文中,我被列为第一作者,但是这个算法的提出,与Dahlia和Mike等经验丰富学者的紧密协作及相互间激发出的灵感密切相关。我也很开心,能够在VMwareResearch短暂的暑假实习期间完成「尤物」的主体部分算法。

在实习结束之后的半年间,我们坚持不懈地完善理论和代码,并且也尝试向业界推广该成果。我们都对创造可以用于实际系统的协议充满热情,也都对理论和系统实践有着一定经验。Dahlia显然比我拥有更多的经验和更深刻的认识,我从她身上学到了很多。令人感动的是,她对我的思考和每一个建议都认真加以考虑,并且也充分信任我的一些观点——这使得我凭借自己对系统和这个行业的理解能有所施展。

例如Facebook的Libra技术文档中反复提到的「起搏器」,就是由我提出并取的名字。当时我看到HotStuff框架提供了一次从算法层面对共识安全和性能的机会,然后在第一次描述算法时就将保证系统安全的部分抽离出来,然后将与具体应用相关的heuristics部分分离成为一个「起搏器」,来拯救Liveness。

这一点,毫无疑问,是谈论HotStuff无法避开的有趣话题。

我真心期待这个「尤物」,能够让无论是国外还是国内的巨头,抑或是创业公司,能够真正构建实际的拜占庭容错系统。毫无疑问,Facebook首先尝了鲜。

我们在2018年向他们推荐了「尤物」,而后如技术文档中所说,在考虑了市面上诸多其他算法后,他们作出了决定。

与此同时,我也向一些国内的创业公司宣传了算法。遗憾的是我跟国内大公司并没有机会接触,只听说他们在共识上栽了不少跟头。

讽刺的是,如今的市场上,极大一部分区块链公司并没有实现所谓的区块链,遑论拜占庭容错。残酷的现实就是,就算从Google、Facebook或是阿里、腾讯等公司抓出最优秀的程序员,其中能够熟练掌握Paxos、且知晓如何从头构建这样高效系统的人屈指可数。

但是我们不要感到灰心丧气,因为这反而是对国内产业的一个前所未有的,赶超世界最领先水平的机遇。除比特币和以太坊之外,一个合格的、成熟的新BFT容错系统尚未诞生,谁将摘取这个王冠——更确切的是,哪些公司将弯道超车,这尚未可知。

我希望「尤物」能够抛砖引玉,为此铺平道路。

郑重声明: 本文版权归原作者所有, 转载文章仅为传播更多信息之目的, 如作者信息标记有误, 请第一时间联系我们修改或删除, 多谢。

链链资讯

[0:0ms0-3:650ms