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

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和Ｍike在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容错系统尚未诞生，谁将摘取这个王冠——更确切的是，哪些公司将弯道超车，这尚未可知。

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

标签：DAHAXOTUFUFFDAH币AXO币TUF TokenBuffedShiba

区块链热门资讯