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感到担忧，所有问题解决之前不应启动此类稳定币项目:葡萄牙财政部长Ricardo Mourinho Felix今日对Facebook的数字货币Libra表达了自己的担忧，称在其可能对金融体系构成的风险得到解决之前，不应进行流通。他在一次会议上称：“从一开始就显而易见，Libra是一个具有系统性影响的高风险现象。”“重要的是，在所有问题都得到妥善解决之前，不能启动像Libra这样的‘稳定币’项目。”欧盟周二表示，将提出一项新的法律以覆盖类似Libra这样的加密货币项目，并称它们对更广泛的金融体系构成了风险。Felix强调，葡萄牙和其他欧洲国家一样对Libra怀抱不安。（路透社）[2019/10/12]

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

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

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

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

「异步」难题

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

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

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

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

声音 | 瑞士FINMA主管：FINMA不会阻碍Libra的发展:针对Facebook的加密货币项目Libra，瑞士金融市场监管局（FINMA）主管Mark Branson表示，我们并不会使此类项目成为不可能。我们将以开放的心态回应他们，但对于相同的风险将要求相同的规则。Branson指出瑞士的“规则和标准不可谈判”，并继续说Libra是“正在透明地进行的事情”。他表示对那些在金融系统黑暗角落中发展，通过网络空间传播并且会在有一天规模大到无法阻止的项目感到更加紧张。（coindesk）[2019/10/2]

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

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

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

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

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

「好的。」我回答到。

虽万难吾往矣

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

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

声音 | 赵长鹏：用户数量是选择代币时需考虑的首要因素 币安很可能支持Libra:据Ambcrypto消息，币安首席执行官赵长鹏近日在接受采访时表示，在选择代币投放平台时，他考虑的首要因素是用户数量。当被问及Facebook的加密货币libra是否会投放币安时，他表示，如果你的项目能够吸引大量用户，那么我们很可能会支持你。所以我们很可能会支持Libra。[2019/9/10]

在报告中我分析了尝试用链式结构打败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。

声音 | 法国兴业银行全球解决方案中心副总裁： Libra实际上是 STO，而不是一种货币:法国兴业银行全球解决方案中心副总裁 Prasoon Mukherjee发文称， Libra实际上是证券型代币发行（ STO）。然而与大多数其他 STO不同， Libra是由 Facebook和作为 Libra协会成员的 Uber、 PayPal、 Spotify等大牌公司支持。此外，没有哪一种代表集体投资基金持有单位的证券属于货币，因此 Libra也不是一种货币。 Mukherjee表示，很快 Libra协会将意识到，如果 Libra在法律上被称为通证化资产，而不是货币，那么它将更容易通过复杂的监管迷宫。[2019/6/24]

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

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

太平洋的风

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

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

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

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

动态 | Facebook加密货币项目Libra的核心：去中心化、低波动性、智能合约:Facebook加密货币项目Libra的介绍白皮书今日正式发布。根据白皮书介绍，Libra的使命是建立一个简单的全球货币和金融基础设施，为数十亿人提供动力。该文件概述了我们的计划，一个新的去中心化区块链，低波动性的加密货币，和一个智能合约平台，旨在创造一个新的机会，负责任的金融服务创新。[2019/6/18]

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

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

标签：LIBLIBRADAHAXOAlibabacoinlibra币发行了吗DAH价格Axolotl Finance

SHIB热门资讯