Facebook Libra 使用的 HotStuff 算法到底是个什么样的尤物？

连闻采访了 HotStuff 论文的第一作者尹茂帆。

Facebook 近期发布的 Libra 白皮书引起了各界的持续关注，其网站上发布的技术文档也得到了多位专家的审阅。 文件中提到，Libra区块链将采用基于拜占庭容错共识的“LibraBFT”共识算法，而LibraBFT是“HotStuff”的变种。

Libra 区块链使用的 LibraBFT 共识协议的技术论文

这个叫HotStuff的算法到底是个什么样的“尤物”？

循着线索，我们发现HotStuff算法论文是由云计算公司VMWare的研究团队发表的，其安全性和可用性已经得到了完整的数学证明。 该论文共有5位作者，分别是尹茂帆、Dahlia Malkhi、Michael K. Reite、Guy Golan Gueta、Ittai Abraham。

HotStuff算法论文

事实上，《HotStuff》算法论文的第一作者 Ted Yin 是链闻的老朋友。 今年年仅25岁的尹茂帆毕业于上海交通大学，目前正在美国康奈尔大学攻读博士学位。 目前主要从事分布式系统的基础研究。 他的导师是著名的计算机科学家Emin Gun Sirer。 导师是 Robbert van Renesse。

在Facebook正式发布Libra白皮书后，尹茂帆接受了链闻专访，为我们详细解读了HotStuff的奥秘。

初次进入分布式共识算法领域的人很容易被一大堆名词搞糊涂。 而深入挖掘，你会发现这些名词背后有着各种各样的命名故事。 比如DLS算法就是三个作者的缩写：Dwork、Lynch和Stockmeyer。 PBFT算法是“实用拜占庭容错”（Practical Byzantine Fault Tolerance）的首字母缩写，BFT自然就是“拜占庭容错”（下文统一使用BFT）。 那么这个物种的新成员 HotStuff 是如何得名的呢？

尹茂凡解释说，HotStuff这个名字是因为这个词在英文中有三层含义：一是性感的人，二是火辣的东西，三是动画中的小恶魔的名字。 大家都知道以太坊的下一代共识算法Casper的名字也是来源于一个动画人物。 所以，HotStuff 可以与之类比。

在接受联文采访时比特币采用的共识算法，尹茂帆灵机一动，将这个词的中文翻译为尤物。 所以本文标题中的尤物并不是哗众取宠。 殷茂凡说尤物有两个意思，一个是绝世美女，一个是稀世珍宝。 HotStuff 翻译成 stunner，这是天作之合。

据介绍，HotStuff已经部署在超过100个副本的网络上，在保持相当延迟的情况下超过了BFT-SMaRt的吞吐量，并且在更实际的测试中，性能超过了后者。

与分布式系统中的其他共识协议相比，HotStuff 有哪些优势？ 以下是联文记者与尹茂帆的问答：

连文：分布式系统的共识协议大致可以分为两类，一类是以比特币为代表的区块链算法（或者叫中本聪共识），一类是经典的拜占庭算法（比如DLS、PBFT）。 两者在应用条件和性能上的主要区别和优缺点是什么？

尹茂帆：两者的区别大致可以分为五个方面：1）会员信息； 2）性能，包括吞吐量、延迟等； 3）抗女巫攻击（Sybil attack）——中本聪共识自带抗女巫攻击，而经典的BFT则需要额外的PoS或PoW； 4）可扩展性； 5）安全性，即概率与确定性。

中本聪共识的好处是不需要事先知道所有的共识参与者，也不需要精确的成员信息。 因为部分共识使用 PoW（工作量证明），所以它天生就免疫 Sybil 攻击。 而且，中本聪共识的算法非常简单，普通人只要有一点数学基础就可以理解。 Nakamoto 共识也易于扩展，在 10 个节点和 1000 个节点上性能损失较小（一方面因为不需要广播投票，另一方面因为它本身就很慢，见下文解释。 )

中本聪共识的缺点也很明显。 因为 PoW 的难度和等待链的长度关系到安全性，性能从根本上是差的，交易确认延迟无法改变。 现有的所有基于中本聪共识的“魔改”（扩容不换汤）协议只能增加吞吐量。 抛开延迟不谈吞吐量，意义不大。 比如我可以开卡车运一车硬盘来运数据。 虽然是超高吞吐量，但也是超高延迟。

在安全性方面，与传统的BFT共识相比，中本聪共识只提供概率性的安全保障，而BFT是100%安全的。 这里说的安全性，或者说一致性，就是能不能避免双花。 事实上，比特币六个区块的双花概率并没有大家想象的那么低。 共识失败的概率高达 13%（即 BFT 中 30% 节点的情况）。 从这个角度来看，如果要进行公平的比较，中本聪共识的效率是非常低的。 （六个街区已经花了一个小时。）

再看经典的 BFT 共识，它的前提或缺点是需要知道所有参与者，要求 100% 准确的成员信息。 此外，经典的 BFT 共识相对难以扩展。 在 HotStuff 之前，大多数经典的 BFT 都需要广播所有节点，这带来了平方级的复杂度（包括 Tendermint 论文中描述的算法）。 添加大量节点会导致网络拥塞。 而且Leader节点会承担整个网络的负载（负载极不平衡），很难扩展到数千个节点而不会有太大的性能损失。

BFT共识的优势在于，由于共识没有使用无意义的PoW，经典BFT共识的协议速度与网络发送大量短消息的速度有关，没有额外的能源消耗和等待时间中本聪共识。 事务延迟很小。 如果不考虑网络延迟，交易在几十到几百毫秒级别。 如果考虑网络延迟，则与网络延迟是同一个数量级。

练文：你的论文一开始就声称HotStuff是基于一个新的框架，在经典的BFT基金会和区块链之间架起了一座桥梁。 怎么理解这句话？

尹茂帆：我们的论文题目是《HotStuff：区块链视角下的 BFT 共识》。

之所以这样描述，是因为它的算法框架（可以诞生多种衍生算法）采用了树/链结构，非常类似于区块链。 此外，与传统区块链类似，节点当前有一条链被视为“主链”，只会对当前被认为在主链上扩展的新部分进行投票。 与区块链一样，如果侧链足够“好”，它就会成为新的主链。 在区块链中，这是由链长决定的（长者获胜），而在 HotStuff 中，它是由最近获得多数选票的区块决定的。

另一方面，HotStuff 是传统拜占庭容错系统的成员。 使用该算法框架可以很好地解释PBFT、DLS、Tendermint、Casper等协议，实现一定程度的归纳和统一。 另外，与以往同类算法最大的区别和最大的贡献在于HotStuff的核心选举算法没有特殊情况； 不同于PBFT有“正常”的执行过程和“特殊”的选举过程，HotStuff统一了两者，即对连任没有明确的特殊处理，也可以认为是潜在的连任到处。 这使得编写基于 HotStuff 的共识系统的基本安全部分变得非常容易。 相比于PBFT的几千行代码，HotStuff只需要几十、几百行。

另一个优于同类算法的特点是对工程师非常友好。 它将保证正确性和性能的逻辑从算法层面解耦。 安全保障的几十行代码一旦完成，剩下的基于具体应用场景的优化（包括选举机制和策略）就不会触及这部分，让系统始终安全。

连文：PBFT算法可以在互联网等异步环境中运行，一些优化也使其比以往的共识算法更快。 但它也存在一些问题，比如检测坏主节点和重新选择新主节点（视图更改）的过程非常低效。 例如，为了达成共识，PBFT 需要方级消息交换，这意味着每台计算机都必须与网络中的所有其他计算机进行通信。 总之，PBFT 的可扩展性明显不够。 对于这些问题，HotStuff 有哪些解决方案呢？

尹茂帆：首先，HotStuff首次将重选成本从平方级降低到线性复杂度，这意味着它具有与Paxos/Raft等IT行业广泛使用的非BFT协议相同的复杂度。 此外，虽然Tendermint等协议通过组合数字签名理论上可以降低到同样的复杂度，但这些协议本质上需要等待区块间最大可能的网络延迟比特币采用的共识算法，使得实际实现的系统成为同步系统。 HotStuff的思想跳出了原有的框架，提出了极简的算法体系，轻而易举地打破了这种传统BFT的魔咒。 经测试，在保证代码实现简单、理论复杂度低的情况下，可以击败现有最快的传统BFT实现，在商业系统中具有无限潜力。

链闻：Facebook 的 Libra 白皮书提出，Libra 区块链一开始是一个“许可的区块链”，未来的目标是成为一个非许可的网络。 从授权到非授权，目前是否有可行的技术路径？ 是扩展困难（从 100 个节点到数万个节点）还是抵抗 Sybil 攻击？

尹茂帆：理论上，任何许可协议都可以转化为非许可协议。 因为传统的共识协议（无论是拜占庭容错还是非拜占庭容错），都可以通过共识本身重新配置来添加/删除节点。 但由于潜在的女巫攻击，这种基于精确成员信息的协议需要额外依赖PoS或PoW入口机制来打开系统。