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

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的两位作者合作完成了后来的尤物协议。

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

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

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

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

「异步」难题

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

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

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

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

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

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

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

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

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

「好的。」我回答到。

虽万难吾往矣

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

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

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

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

另一种截然不同的思路则是像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。

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

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

太平洋的风

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

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

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

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

整个过程大概又花费了将近一周,最后我将重写的几页稿子交给了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容错系统尚未诞生,谁将摘取这个王冠——更确切的是,哪些公司将弯道超车,这尚未可知。

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

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

金智博客

NEAR大饼再次下探 瑞波或延续低迷_COIN:ORT

不知道大家有没有一种感觉,今年以来,随着币价的不断上涨,币圈人气越来越高,伴随资金盘、局和维权事件时有发生,按常理ZF应该出台比较严格的政策规范一下市场行为,然而到目前为止还没有相关动静.

[0:0ms0-3:754ms