LibraBFT 算法的美妙之处

文章标题：《LibraBFT 算法简述》
文章来源：知乎专栏
作者：任之劼

首先，不熟悉 BFT 的人可以看看我之前的三篇文章：

《区块链时代的拜占庭将军们（上）》
《区块链时代的拜占庭将军们（中）》
《区块链时代的拜占庭将军（下）—— 区块链共识算法的发展趋势》

其实我是在发完第三篇之后就看到了 Hotstuff，当时非常犹豫要不要把这个算法加进共识算法的发展趋势里面，后来放弃了，因为我觉得新算法层出不穷是加不完的，当然，我现在有点后悔这个决定 —— 要不然现在就可以拿出来吹一吹了。另外一点，也是好巧不巧的，用 BLS 来降低 BFT 的消息复杂度这个事，正好是我扩容那一系列下一篇的内容。不过那些内容在这里我准备简述一下，然后细节可以继续关注我的专栏。

Hotstuff BFT

Hotstuff 这篇论文我记得是年初的时候发在 arxiv 上的，一作是一位康奈尔的中国博士，然后论文会正式发表在今年的 PODC 上。不过，在正式发表之前，就已经被 LibraBFT 用了而大火了一把。

这篇我们不具体说 Hotstuff 的细节，而是更说一些 Hotstuff 的思路和贡献。当然，我觉得对于许多区块链的从业者而言，具体的细节可能并没有这些来的有趣，同时，直接看论文的时候，其实不如这样的思路来的清晰。

大网络中的 BFT

这个其实不算是 Hotstuff 的贡献，而是其实就像我在 BFT 第一篇就说的，是区块链为 BFT 算法这个问题带来的一个新的场景和挑战。而这其中的第一个挑战，就是把 O(n^2) 的消息复杂度降到 O(n)。但是，本身这件事并不是 Hotstuff 的创新，因为基本上所有目前的 BFT 都有了 O(n) 的消息复杂度。

Hotstuff 达到 O(n) 消息复杂度的方法其实已经是一个比较经典的方法了，就是采用聚合签名，然后假定 leader 是诚实的让 leader 去收集签名。采用聚合签名的方法其实从 Byzcoin 就有了，然后其实很多共识算法，不仅限于 BFT 算法，例如 Dfinity，也在采用这类方法。这个方法我在后面的一篇扩容的部分会详细写到，在这里就不赘述了。

BFT 与链的结合

传统 BFT 达成共识的方法是两轮共识，其中第一轮定序（prepare），第二轮 commit。很多将 BFT 用于区块链的项目仍旧采取「先做两轮通信，然后达成共识，最后上链」的模式，而 Hotstuff 采用的是「先上链，在区块中加入聚合签名，于是，在 n 个区块之后就可以视为通过了 n 轮的通信达成共识」。

于是，其实根本就不需要再去区分所谓 prepare，commit 这两轮通信的区别了，只需要简单地把每一轮节点的行为定义成「leader 负责出块和收集签名」，然后「其他节点负责对 leader 出的块进行签名」，然后，只要收集到了 2f+1 个签名，leader 就可以出一个块，然后后面有 n 个块就相当于达成了共识。

这点的好处在于，O(n) 的通信复杂度可以让诚实节点知道「我知道消息 m 将成为共识」，但是必须要 O(n^2) 的通信才能让每个诚实节点都确信「我还知道所有诚实节点也知道消息 m 是共识」，而通过 leader 收集签名并出块这种方法，当所有人看到区块 b 的时候，诚实节点会知道「我知道 b 是共识」，而在看到 b 后一块 b' 的时候，诚实节点等于知道了「所有签名的人也都知道了 b 是共识」。于是，每次出块的时候都只需要 O(n) 的消息复杂度，但是，在一个诚实 leader 和聚合签名的帮助下，通过两轮的 O(n) 消息复杂度，我们达到了之前 O(n^2) 的效果。

并且，这个事情和 b' 的共识的第一轮是同步进行的。换句话说，就是把每一轮 BFT 的过程也链起来之后，还把通信复杂度减少了一半。这一点，虽然之前也有类似的想法，但是我个人觉得 Hotstuff 是第一个把这个思路确切地落在算法里的，这点我觉得非常有趣，同时，也是未来的一个方向。

其实这个方法是从两个方向逐渐靠拢的——第一是从 BFT 的方向，大家逐渐意识到其实链式结构可以省掉 BFT 中的很多事情，例如其实我们不需要定序，而且对于后面一个区块达成共识实际上就相当于对于前面的区块进行了共识，而很多 BFT 算法，例如：avalanche （Hotstuff 作者的另一篇）都开始注意到了这个事；而从区块链共识算法，尤其是追求 finality 的方向来看，人们发现其实一个区块后面跟上 2f+1 个节点的出块，就相当于达成了 BFT，而如果通过多个人对于这些区块签名可以加速这个过程，像这一点，也在例如 Polkadots 这类的算法中有所体现。而 Hotstuff 可以说是这两种思路到了这个阶段最简洁的融合。

BFT 的快速响应

大网络 BFT 算法在实际应用中最复杂的问题实际上是 view change （一个在 leader 不响应的时候大家提议换 leader 的机制），这点我听不止一个采用 PBFT 算法的人说过了。这是因为实际上在 PBFT 以及所有传统 BFT 其实都是基于传统的拜占庭将军问题的（见我之前的文章），也就是说，我们会先假设 leader 是诚实的，然后以他为主导达成共识。

于是，view change 是个不得已的事情，需要所有的诚实节点先 time out，然后对于 view change 这件事达成共识，然后，他们把这个共识（以及已经达成了共识这件事）告诉新的 leader，新的 leader 还要把这个消息广播出去宣布 view change，于是，这个 view change 的 cost 是 O(n^3)（采用了聚合签名之后是 O(n^2)）。

这其中有两个问题：一个是 view change 的消息复杂度，一个是 view change 必须要等到诚实节点对于 view change 达成共识之后才会发生。

Hotstuff 的一个非常有趣的新意在于把传统 BFT 的两轮共识变成了三轮，然后借此把 view change 的 cost 变成了 O(n)。这个可以这么理解：传统的 view change 是 O(n^2) 消息复杂度，也就是说，所有的诚实节点在 view change 之前会确认所有的诚实节点确实都进行到下一个 view，而在 Hotstuff 中，view change 不需要等「我知道其他人也知道 view change 了」这件事就可以进行，于是，消息复杂度就降到了 O(n)，也就是说，只要诚实节点的内置 time out 到了，那么就可以发 view change 给新的 leader 开始 view change。

为什么需要把两轮变成三轮呢？因为之前 BFT+链式结构的简化中，严格来说这两个通信复杂度为 O(n) 的区块和 PBFT O(n^2) 消息复杂度的 prepare 和 commit 还是有区别的 —— 当有两个区块连起来的时候，两边是相当的，但是其实每一个区块的消息复杂度都只有 O(n)，并不说明所有诚实节点都知道「所有诚实节点都会达成共识」。

而同样，view change 的消息复杂度也只有 O(n)，于是如果一条消息刚有第一个区块的时候 view change 了，那么诚实节点会对于第一个区块是否达成了共识产生不一致，因为 prepare 和 view change 看起来都很有道理。

而把两轮变成三轮之后我们就解决了这个问题。因为我们可以规定任何两轮之后的东西才是共识，而如果没有到两轮就不算——对于 prepare 和 view change 都是如此。

于是，如果 view change 发生在第一轮之后，那么我们不认为之前 prepare 的是正确的，而 view change 也同理。相反，如果在第二轮之后发生 view change，那么由于已经经过了两轮，所以这条消息已经经过了定序，即便在 view change 之后也会最终达成共识。

所以总体来说，Hotstuff 的核心思路如下：

1. 采用聚合签名的结构把每一轮的消息复杂度变成 O(n)；

2. 用链式结构把 O(n^2) 的共识变成了两轮 O(n) 消息复杂度的区块提交；

3. 在这种结构下，把 view change 的消息复杂度降到 O(n)，然后为了防止 view change 造成的不一致，把两轮区块提交变成了三轮；

整体下来，虽然前两条也很有趣，但是最核心的优点是 view change 变得更容易了，无论是时长，消息复杂度，还是对于下一任 leader 的工作压力。虽然代价是需要多一轮通信，但是这样的延迟，无论是对于世纪中 view change 的可能延迟，还是对于习惯了区块链共识算法延迟的我们而言，其实都不值一提。

LibraBFT

LibraBFT 基本上就是 Hotstuff，只不过在这之上做了两点改动。

其中一点是将 Hotstuff 用于区块链时候加上了现实考量的机制，例如引入了 epoch （代）的概念，允许共识节点替换，同时加上激励机制和惩罚机制…

另外一点是同步性上的改进（也许也算不上改进）：

Hotstuff 是在 partial synchrony 网络中生效的（网络中消息延迟有上限，但是这个上限未知），这已经算是一个非常强的异步假设了，它和 PBFT 一样，但是现在很多的区块链算法都已经在用同步假设了。

而 Hotstuff 里的轮其实概念更像是 PBFT 的几个步骤，也就是说实际上这个轮不是一个时间概念，而是和 PBFT 一样，是上一个步骤（收集签名，发布区块）结束之后自动进入的。换句话说，一个区块出现有可能很快，但也有可能在 View Change 的时候要等很久。于是呢，LibraBFT 使用了 Pacemaker 机制，让每一轮的时间尽量有一个上限。

以上就是关于 LibraBFT 的简介了。在我看来，Hotstuff 是一个非常有趣，甚至有可能是最近对于未来区块链的共识算法最有启发性的一个算法。而 Libra 采用这个算法其实也很有道理，因为 Hotstuff 不仅有现在大部分 BFT 的高输出，而且解决了大部分通行 BFT 的 view change 的问题，而在实践中这却是是非常影响 BFT 算法在区块链环境中使用的问题。

当然，对于 Libra 本身，我的意见都在这个答案里了： 《如何评价 Facebook 发布的数字货币 Libra?》

反正，对于 Facebook 而言，这是个进可威胁金融业，统治区块链领域，甚至和主流货币扳手腕；退可造噱头，蹭热点，涨股价，最后搞个 Facebook 版支付宝或者微信支付的项目，甚至，即便它被相关机构叫停，它还是能洗白之前隐私盗窃犯的形象，摇身一变变成强权和守旧的挑战者，对于 Facebook 而言，它几乎一定会成功，只不过是程度问题。

但是，无论如何，它都会对于区块链领域造成深远的影响，不是因为它做的事，不是因为它的技术，不是因为它可能的成就，而是因为它是 Facebook。

因此，在以上这个意见里我没有提到的是，我觉得无论成功与否，它对于区块链整个行业造成的影响，都未必是正面的 —— 如果它取得了巨大的成功了，以现在的路线，我们可以看到的是区块链对于互联网巨头挑战的失败，以及区块链领域再次被大鳄占领；如果它没有取得巨大的成功而只是一个成功的噱头，我们会看到其他的大鳄们站台的无数跟风的噱头出现，再割完一圈韭菜后翩翩离场，留下一个不再有任何生机的区块链行业。