Facebook Libra 采用的 HotStuff 算法，究竟是怎样一种尤物

来源：链闻ChainNews

Facebook 近日公布的 Libra 白皮书引起各界持续关注，其网站公开的技术文档也被诸多专家审视。文档提到，Libra 区块链将使用基于拜占庭容错共识的「LibraBFT」共识算法，而 LibraBFT 则是「HotStuff」的一个变种。

链闻专访 HotStuff 论文第一作者尹茂帆。

Facebook 近日公布的 Libra 白皮书引起各界持续关注，其网站公开的技术文档也被诸多专家审视。文档提到，Libra 区块链将使用基于拜占庭容错共识的「LibraBFT」共识算法，而 LibraBFT 则是「HotStuff」的一个变种。

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

这个名为 HotStuff 的算法，究竟是怎样一种「尤物」呢？

顺藤摸瓜，我们发现，HotStuff 算法论文由云计算公司 VMWare 的研究团队发表，其安全性及可用性已经过完整的数学证明。论文作者有 5 人，分别为 Maofan Yin、Dahlia Malkhi、Michael K. Reite、Guy Golan Gueta、Ittai Abraham。

HotStuff 算法论文

https://arxiv.org/pdf/1803.05069.pdf

其实「HotStuff」算法论文的第一作者尹茂帆（Ted Yin）是链闻的老朋友。今年仅仅 25 岁的尹茂帆本科毕业于上海交大，目前在美国康奈尔大学（Cornell）大学读博士学位，当前的主攻方向是分布式系统的基础研究，导师是著名计算机科学家 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 翻译成尤物，简直天造地设。

据介绍，HotStuff 已经在一个具有 100 多个副本的网络上进行过部署，超过了 BFT-SMaRt 的吞吐量，同时保持着与之相当的延迟，而在更为实际的测试中性能均超过后者。

和其他分布式系统的共识协议相比，HotStuff 到底有哪些优点呢？以下是链闻记者和尹茂帆的问答：

链闻：关于分布式系统的共识协议，大致可分为两类，一类是以比特币为代表的区块链算法（或者称为中本聪共识），一类是经典的 BFT 算法（如 DLS、PBFT）。两者在应用条件和性能方面，有哪些大的差异和优劣？

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

中本聪共识的优点是，无需提前知道共识的所有参与者，不要求精确的成员信息。因为共识的一部分采用了 PoW （工作量证明），所以天生就对女巫攻击具有一定免疫。而且，中本聪共识的算法十分简单，普通人稍具数学基础，就可以理解。中本聪共识也容易扩容，在 10 个结点和 1000 个结点上受到的性能损失较小（一方面是因为不需要广播投票，另一方面是因为它本来就很慢，见以下解释。）

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

在安全性方面，和传统 BFT 共识相比，中本聪共识只提供概率的安全保证，而 BFT 则是 100% 安全。这里说的安全，或者称为一致性，就是能否避免双花。其实，比特币出六个块能发生双花的概率并不像大家想的那么低，有高达 13% 的概率出现共识失败 (即 BFT 中的 30% 节点的情况)。以此来看，如果要公平比较的话，中本聪共识的效率非常之低。（六个块已经耗时一个小时了。）

再来看经典 BFT 共识，其前提或者说缺点是，需要知道所有参与者，要求 100% 精确的成员信息。另外，经典 BFT 共识相对较难扩容。在 HotStuff 前，大部分经典 BFT 都需要所有结点广播，这带来了平方级别的复杂度（包括 Tendermint 论文里面描述的算法）。增加大量结点会导致网络拥塞。而且，其中的 Leader 结点会承受整个网络的负载（负载极其不均衡），导致难以扩容到成千上万个结点而没有太大性能损失。

BFT 共识的优点则在于，因为共识没有使用无意义的 PoW，所以，经典 BFT 共识的协议速度跟网络发送大量短消息的速度相关，没有中本聪共识那种额外的能源消耗和等待时间。交易延迟非常小，如果不考虑网络延迟，交易在数十至数百毫秒级别，如果考虑网络延迟，就跟网络延迟同数量级。

链闻：你们论文在开篇声称，HotStuff 基于一个新的框架，这个框架在经典 BFT 基础和区块链之间搭建了一座桥梁。如何理解这句话？

尹茂帆：我们的论文名为《尤物协议：透过区块链看拜占庭容错共识》（HotStuff: BFT Consensus in the Lens of Blockchain）。

之所以这么描述，是因为它的算法框架（可以诞生多个衍生算法）采用了树 / 链式结构，十分类似区块链。另外，和传统区块链类似，一个结点当前也有被视作「主链」的一根链，投票只会投给当前认为主链上扩展的新部分。和区块链一样，如果侧链足够「好」，那么它就会变成新的主链。在区块链里面，这个是通过链长度来判定的（长者胜），而在 HotStuff 中，它通过最近一次成功获得大部分投票的块决定。

另一方面，HotStuff 又是传统 BFT 体系下的一员。用此算法框架可以很好地解释 PBFT、DLS、Tendermint、Casper 等协议，达到了一定程度上的归纳和统一。另外，跟之前同类型算法最大区别也是最大贡献的地方是——HotStuff 的核心换届算法没有特殊情况；不像 PBFT 那样有「正常」的执行流程以及「特殊」的换届流程，HotStuff 统一了两者，即没有显式的换届特殊处理，也可以认为是潜在地处处换届。这使得编写一个基于 HotStuff 的共识系统的基础安全部分十分容易。对比 PBFT 的数千行换届代码，HotStuff 只需要几十或百余行即可。

另一个它较同类型算法更优异的特点是，它对工程师们十分友好。它将保证正确性和保证性能的逻辑从算法层面上就进行了解耦合。一旦安全性保证的几十行代码完成，剩下的根据具体应用场景的优化（包括换届机制，政策）都不会再触及这部分，使得系统始终安全。

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

尹茂帆：首先，HotStuff 将换届的代价首次从平方级降低至线性复杂度，这意味着它和 Paxos/Raft 这些在 IT 行业广泛使用的非 BFT 协议一样，拥有一致的复杂度。另外，虽然理论上 Tendermint 等协议可以通过结合数字签名来降低到同样复杂度，但是，这些协议本质上需要在块与块间等待最大的可能网络延迟，使得实际实现出来的系统变成了一个同步系统。而 HotStuff 思路跳出了原有的框架，提出了一个极简的算法体系，使得它可以很容易地打破这个传统 BFT 的魔咒。经过测试，它可以在保证简单代码实现、低理论复杂度的情况下打败现有的最快的传统 BFT 实现，在商用系统方面具有无限潜力。

链闻：Facebook 的 Libra 白皮书提出，Libra 区块链是从"许可型区块链"起步的，未来目标是成为非许可型网络。由许可型转向非许可型，目前有可行的技术路径吗？难点在于扩容（从 100 个节点增加到成千上万个节点）还是在于能否抗女巫攻击？

尹茂帆：理论上来说，任何许可协议都可以转化成非许可型协议。因为传统的共识协议（无论是 BFT 还是非 BFT），都可以通过共识本身来重新配置以增加 / 删除结点。但是因为潜在的女巫攻击，这种基于精确成员信息的协议，需要额外依赖一个 PoS 或者 PoW 的进入机制来开放系统。

• DAG也许是真正的区块链3.0
• 区块链科普深入浅出 | 再也没有比这个更全的区块链知识了！