EN
Libra 采用的 HotStuff 算法作者亲述：「尤物」诞生记
Facebook 公布了 Libra 白皮书和相关技术文档之后，链闻发现了 Libra 区块链将使用基于拜占庭容错共识的「 LibraBFT 」共识算法，而 LibraBFT 算法则是「 HotStuff 」的一个变种。之后，链闻又顺藤摸瓜，找到了「HotStuff」论文的第一作者、美国康奈尔大学（Cornell）大学在读博士生 尹茂帆（Ted Yin） ，请他讲述了 HotStuff 的奥妙。撰文： Ted Yin，康奈尔大学博士生，Ava Labs 的联合创始人兼首席系统架构师Ted Yin 今年 25 岁，目前导师是著名计算机科学家 Emin Gün Sirer 教授和 Robbert van Renesse 教授。他同时也是市场颇为瞩目的区块链新项目 Ava Labs 的联合创始人和首席系统架构师。
2018 年暑期期间，他在 VMware Research 实习时提出了「HotStuff」协议中核心算法，并完成了相关论文。
我们邀请 Ted Yin 撰文分享了他提出 「HotStuff」核心算法前前后后的经历。我们希望通过这篇文章，记录下一个创新性算法被年轻华人研究者提出的背景，一个有可能推动区块链技术发展的基础性研究工作完成的来龙去脉。我们希望以此帮助读者更好理解 「HotStuff」，更可以激励区块链行业的研究者和开发者更好地建设。
Ted Yin，HotStuff 论文第一作者， Ava Labs 的联合创始人和首席系统架构师。
一入系统深似海
没想到，HotStuff ，这个被我中文起名为「尤物」协议的科研成果，或多或少竟源自于我第一个「失败」的研究。请容我细细说来。
2016 年，博士之旅伊始，我的导师 Emin Gün Sirer 教授便拿出几份论文让我细细研读。其中有：
- Paxos Made Moderately Complex；
- Byzantine Quorum Systems；
- Implementing Fault-Tolerant Services Using the State Machine Approach。
相较于人工智能 （AI） 的论文，计算机系统相关的研究论文篇幅都较长，一般有十来页。而共识协议算法的论文每一页的难度又令人望而却步。在理解了共识问题的基础以及经典算法以后，一次开会中，Gün 教授开始考我了。本来胸有成竹的我，被他连珠炮一般的问题问得说不出话来。
「看来你需要回去重新读一遍啦，Ted！」，他淡然一笑，「不必担心，本来这世界上没多少人懂 Paxos。」
（链闻注： 「Paxos」指 Paxos 算法，Paxos 算法是莱斯利·兰伯特（Leslie Lamport）在 1990 年提出的一种基于消息传递且具有高度容错特性的一致性算法，很多大型分布式系统都采用 Paxos 算法来解决分布式一致性问题，Paxos 算法被普遍认为难以理解，难以实现。 ）
我愧色满面，仓皇逃出了办公室。于是下决心要把其中逻辑理清，以至无懈可击。
「异 步」难题
共识协议，或者推广至各种分布式系统的协议，是一类基于时态逻辑的算法描述，其难点在于「异步」 （asynchrony） 。
所谓异步，就是若干个相对独立逻辑可以同时执行，并且它们之间能够依据算法发生交互。这里的「异步」与异步协议中异步所指不同，更接近于并发 （concurrency） 的概念。
其实在日常生活中，我们也无时无刻不进行这种「异步」的操作：我们不会干等一天别人的消息，也不会在整个项目所有的事情做完后才睡觉休息。我们往往是会「同时」处理若干个不同的事务，尽量不会因为一件事没有做完而被卡住不做后续的所有事情。
这种等待着一件事情完成再处理另一件事情的过程，就可以被称为「同步」；而把事情做一部分丢给别人，接着马上进行其他操作的过程中，则产生了「异步」。
正如生活中的多任务同时处理一样，带有异步 / 并发性质的算法设计充满了挑战。以 Paxos 算法为例，它是一种对宕机有一定容忍度的冗余算法 （Crash Fault Tolerance，下称 CFT） 。用通俗的话讲，也就是我们希望有若干个机器去备份同一个系统状态。这个状态可以是用户的信息、银行的交易，或者平台上程序的执行序列。这种「备份」 （replication） ，使得整个系统有一定的抗故障能力——一台带状态副本的机器崩溃之后，我们仍然有别的机器可以使用。
Paxos 作为这类协议的代表已经在业界获得了广泛的使用，比如 Google 的 Spanner 系统 。毫不客气地说，云服务和大规模数据中心的崛起，重要原因之一就要归功于此。美国计算机科学家 莱斯利·兰波特 （Leslie Lamport） 提出了 Paxos 算法，这成为让他在 2013 年获得图灵奖的重要原因之一——当然，兰波特有太多的贡献了，包括后文会提到的拜占庭容错算法 （BFT） ，这里就不一一展开了。
不过，像 Paxos 这类算法因为需要保证系统各个机器同时处于一致的状态，以便对外表现为一个不间断的服务，因而十分难以设计和理解。
当然，我的那个故事的结局是：重新来过，认真钻研，自信满满地再次接受也解答了 Gün 教授提出的若干个刁钻的问题，最终通过了他的考验。
「那么接下来我希望你思考一下能不能基于区块链的结构设计一个 CFT 算法，打败 Paxos。」Gün 教授说。
「好的。」我回答到。
虽万难吾往矣
就这么简单的一句话，花去了我整整第一年一个学期的时间。
现在回想，这个过程短暂又漫长，时而枯燥无味，但时而又充满惊奇。我曾经构想出了一些看似正确的算法，但仅仅过了一天，随即便发现无法证明，或者算法本身存在错误。直到在第一个暑假来临前，我向导师提交了一份关于这方面研究的报告。
在报告中我分析了尝试用链式结构打败 Paxos 的各种大方向。其中主要分为两种：
- 一种路线是采取类似原中本聪共识中的概率模型，然后通过随机的等待时间来建立起一个可以收敛的共识链；
- 另一种截然不同的思路则是像 Paxos 那样，使用子集 （Quorum） 交来把 Paxos「编码」在链上。
我们决定放弃这个 CFT 相关的研究，我也转而有了一个新项目，也就是后来的 Avalanche 协议 。它是一种概率安全的拜占庭容错协议，这里暂不展开。
有趣的是，报告提到的两条路线中，第一个正好和早期的 DPoS 思路如初一辙。DPoS 是一个备受争议的协议，它在早期并不是拜占庭容错的，而且协议本身没有严格的证明或者性能的测试，主要使用它的 EOS 虚拟货币，也沦为了一个高度中心化的系统。而第二个路线，如果将问题的领域由宕机容错 （CFT） 变为拜占庭容错 （BFT） ，Paxos 改换成 DLS/PBFT，则像极了后来的尤物协议 （即 HotStuff） 。
一拍即合
17 年秋季学期即逝，我向 VMware Research 的首席研究员 Dahlia Malkhi 表达了实习的意向。
（链闻注： Dahlia 毕业于希伯来大学，曾在 AT&T 研究室工作多年，后自 1999 年到 2007 年在希伯来大学计算机系执教，之后又曾担任微软研究院在硅谷 (MSR Silicon Valley) 的首席研究员，并在 2014 年 MSR 硅谷被微软解散后参与创立了云基础架构和移动商务解决方案厂商威睿 (VMware) 的研究机构 VMware Research，担任首席研究员。 她在分布式系统稳定性和安全性领域研究颇深。 ）
当年 12 月，在清华—康奈尔区块链研讨会期间，Dahlia 和 VMware Research 的高级研究员 Ittai Abraham 飞到深圳，短暂参会并作了学术报告。报告内容是关于 BFT 协议在区块链时代下的新研究课题。期间，他们宣布发现了 2007 年获得 SOSP 最佳论文的 Zyzzyva BFT 系统存在的正确性问题，借此说明 BFT 协议过于复杂和难以理解，以致在业界无数专家审稿的 10 年以后，仍然可能会发现算法层面的正确性 bug。
我们在她宣讲的当天吃了早饭，席间她简短地用了 30 分钟问了一些关于我目前科研的问题作为面试。
Dahlia 在业界以一针见血和才思敏捷著称，在挺过了她的一些关于 Avalanche 协议的一些尖锐问题后，她表达出了对我一开始那个「夭折」 CFT 项目的浓厚兴趣。在次年的远程交流中，她提到了一个在构想的 BFT 算法有些类似于我的项目，并且询问我当初放弃的原因。之后我们一拍即合，去 VMware Research 实习的事情也就这么定了下来。
太平洋的风
实习就这么开始了。从东岸的纽约飞到了西岸的加州。美好的湾区，全新的暑假。烈日下，太平洋的风时而拨弄着我手中的纸页，我则低头继续思考着「谁是坏人，谁是好人，谁又背叛了谁」的问题——拜占庭容错。
Dahlia 告诉我说，一般世界各地的博士生来这里实习的头一周都不需要做什么，而是应该去尝试摸清自己的能力，以及寻找感兴趣的项目。彼时，她提到希望我能看一下他们于三月份撰写的文稿。
我喜忧参半。「喜」是因为有明确的文稿可以阅读，「忧」则是这个预印稿是不是意味着算法已经设计完毕，而我能做的事所剩无几？
实际上，在「挣扎」着阅读了一周以后，我发现初稿中描述的算法很是模糊，正确性的证明也是一笔带过，其中两个核心引理都是一句话。于是，在商议后，我们做了一个后来觉得极为明智，但对我来说也十分挑战的决定：我不去看那篇预印稿，而是从一张白纸开始，凭着自己受到的启发，结合已有的积累，用我的符号系统来重新描述算法，并且尝试给出严格的证明。
整个过程大概又花费了将近一周，最后我将重写的几页稿子交给了 Dahlia。令我欣喜的是，得到的反馈非常鼓舞人心。Dahlia 说我自己重头设计的算法在本质上和她当初的构想大体相似。
但是不久她就发现了一个很不一样的地方：我的协议里面需要的假设比原本的预印稿的要更少。
我的解释是，原稿里面维护的变量和隐含条件过多，而且有的好像也不是必要。我相信「简单即是优美」的原则，于是去掉了一些觉得冗余的不变量。
瞬间，Dahlia 变得严肃认真了起来，直截了当地说，「不，这个简化会直接破坏协议的正确性」。
好在我已早有准备，向她解释了这个「重要」条件其实是不必要的。但是她依然坚持。
讨论变得逐渐激烈，于是我壮了胆，带着十足底气的口吻「挑战」道：「If so, could you please show me a counterexample? （如果真是这样，你能给我构造一个反例吗？ ） 」她立即开始在眼前的白板上写写画画，我全神贯注，准备迎接对我思维以及口语表达的挑战。
在她数次尝试失败之后，我再次耐心地解释了一遍无需那个条件的原因。我说，听上去确实挺反直觉的，我一开始也觉得困惑，但是后来发现证明正确性并不需要它。最后，她将马克笔缓缓放下，笑着长出了一口气说，「目前我想不到反对的理由。Ted，你赢了。哈哈。」
证明不是一笔挥就的。我一开始自鸣得意的证明很快就被 Dahlia 发现了一个致命问题：有一个条件从来没有用过。和之前我们所争论的冗余条件不同，我们都意识到这是一个极为关键的条件，奈何找遍了整个证明都没有！
这种感觉就像是修好一个机器后发现手头多了一些零件，又或是做完手术发现金属盘里多出了一些器官一般。所幸的是，很快我们发现了其中一句话其实暗含了条件，但欣慰之余又感叹就算是专业人士，做这种 BFT 协议也是十分棘手。
随后，我们计划将旧稿替换成现在重写的新稿。
高手过招
Dahlia 一直是我最敬重的学者之一，因为她平易近人，跟年轻人打成一片，而在讨论学术问题时又有着渊博的知识储备和学者的严肃威严，讨论细致入微，不让毫厘。
老实说，在讨论中，大多数时候还是她取得了「胜利」。跟高手「过招」，我不得不叹服她思维的深度、广度和速度。这也是跟她合作的乐趣：就像是一场赛车比赛，稍一不留神，她就在弯道直接超车，一骑绝尘了；或是在你飞速狂奔而不知其所往时将其横刀拦下，使之冷静下来解释清楚。
不久，坐在旁桌的 Mike Reiter 也加入了我们的讨论。我对计算机安全领域的大佬知之甚少，自然也是不知道这位 Mike 的来头。只是当时觉得他特别友善，还经常来问我需不需要来看一眼我的稿子，或者讨论一下算法问题。
Mike Reiter，现为北卡罗来纳大学教堂山分校计算机系教授
他也对 HotStuff 感兴趣，于是我们便有了三人的开会小组。再后来我才意识到，原来最早读的那篇于 1998 年发表的著名论文「拜占庭仲裁系统 Byzantine Quorum Systems」，正是 Dahlia 和Ｍike 在 AT&T 实验室工作时期所合著的成果。那时的我还在幼儿园留着口水，咬着手指。
1998 年发表在学术期刊「分布式计算」上的论文「Byzantine quorum systems」
相比 Dahlia，Mike 更像是那种深藏不露的扫地僧。他时常会在你作报告加速时打断，慢条斯理道：「恕我愚钝，但是我不理解你刚刚说的东西，你能再解释一遍吗？」而我逐渐察觉到他懂的其实远比看上去的多，总能在关键的地方提出非常好的问题。一旦他和 Dahlia 争论起来，我几乎无法插嘴，只好在一旁以崇敬的目光看着两位「神仙大战」。
尤物之生
Dahlia 提起了最初的论文稿其实投了 2018 年的 PODC 会议 （分布式系统理论顶会） ，结果被拒。原因有二：审稿人觉得这论文写得太笼统，他们没能理解算法的具体过程，以及证明过于简陋；另一方面则是他们认为实用拜占庭容错算法 （PBFT） 的期刊版本已经在其中「暗示」了可能存在线性复杂度的换届 （view change） ，所以论文号称的线性换届并不是新东西。Dahlia 对第一点心服口服——这也是让我不看原文重头写过的原因之一。但她对第二点不以为然，因为她去找来了那个期刊论文，所谓「暗示」并不可行。
就这一点，我们两人在一次讨论中对 PBFT 期刊版本的算法进行了剖析，最终得出了一个好消息和一个坏消息：好消息是 PBFT 的换届做不到线性，也就是审稿人的说法有误；但坏消息是，Dahlia 的旧稿里面的算法并不符合标题所说的完全线性，而是有更深层次的微妙之处。
就在这次和 Dahlia 对 PBFT 期刊版本的讨论中，我们得到了新的思路
实际上，为了保证响应度 （responsiveness, 即在正常运行中不需要让每个共识等待最大的网络延迟，从而沦为「同步协议」） ，不得不变成平方复杂度；或者为了线性复杂度而放弃响应度。无论何种取舍， 皆使我们的贡献度大幅缩水——这朵乌云不幸地于周五飘在了头顶，在这沦为「incremental work」的阴霾下我们若有所思地开始了周末。
柳暗花明
山重水复后，我席间提到的一个思路给了 Dahlia 新的启发。于是，在那个周日的下午，当我还在家慵懒地用笔记本看新闻时，突然收到了一封她上千字的邮件。
果然，在我们的 HotStuff 体系中，尽管最初的算法跟 Tendermint 本质相仿 （抛开我们更简洁优美不谈） ，但还有别的变种可以打破这种壁垒：在保证与 PBFT 类似响应度的同时，达到线性的消息复杂度下界，即理论最优。值得一提的是，前面提到的 Paxos （非拜 占庭容错） 同样也是线性复杂度。
主要思路就是那天讨论中我突发奇想提到的：「如果我们增加一个阶段呢？两个阶段的协议变三个阶段，但是好像我们可以用中间阶段维护的不变量 （Invariant） 来避免 Liveness 的问题，从而完全保证响应度。」
于是，便有了第三版的「尤物」，也是 Facebook 的 LibraBFT 所基于的那个。
尽管在最终发表的论文中，我被列为第一作者，但是这个算法的提出，与 Dahlia 和 Mike 等经验丰富学者的紧密协作及相互间激发出的灵感密切相关。我也很开心，能够在 VMware Research 短暂的暑假实习期间完成「尤物」的主体部分算法。
在实习结束之后的半年间，我们坚持不懈地完善理论和代码，并且也尝试向业界推广该成果。我们都对创造可以用于实际系统的协议充满热情，也都对理论和系统实践有着一定经验。Dahlia 显然比我拥有更多的经验和更深刻的认识，我从她身上学到了很多。令人感动的是，她对我的思考和每一个建议都认真加以考虑，并且也充分信任我的一些观点——这使得我凭借自己对系统和这个行业的理解能有所施展。
例如 Facebook 的 Libra 技术文档中反复提到的「起搏器」 （Pacemaker） ，就是由我提出并取的名字。当时我看到 HotStuff 框架提供了一次从算法层面对共识安全 （safety） 和性能 （Liveness) 进行解耦合 （decouple） 的机会，然后在第一次描述算法时就将保证系统安全的部分抽离出来，然后将与具体应用相关的 heuristics 部分分离成为一个「起搏器」，来拯救 Liveness。
这一点，毫无疑问，是谈论 HotStuff 无法避开的有趣话题。
我真心期待这个「尤物」，能够让无论是国外还是国内的巨头，抑或是创业公司，能够真正构建实际的拜占庭容错系统。毫无疑问，Facebook 首先尝了鲜。
我们在 2018 年向他们推荐了「尤物」，而后如技术文档中所说，在考虑了市面上诸多其他算法后，他们作出了决定。
与此同时，我也向一些国内的创业公司宣传了算法。遗憾的是我跟国内大公司并没有机会接触，只听说他们在共识上栽了不少跟头。
讽刺的是，如今的市场上，极大一部分区块链公司并没有实现所谓的区块链，遑论拜占庭容错。残酷的现实就是，就算从 Google、Facebook 或是阿里、腾讯等公司抓出最优秀的程序员，其中能够熟练掌握 Paxos （CFT 容错非 BFT 容错） 、且知晓如何从头构建这样高效系统的人屈指可数。
但是我们不要感到灰心丧气，因为这反而是对国内产业的一个前所未有的，赶超世界最领先水平的机遇。除比特币和以太坊之外，一个合格的、成熟的新 BFT 容错系统尚未诞生，谁将摘取这个王冠——更确切的是，哪些公司将弯道超车，这尚未可知。
我希望「尤物」能够抛砖引玉，为此铺平道路。
来源：链闻
