LibraBFT广播机制的使用 - The Trail of Bits博客

Sam Moelius
2019年7月12日
区块链, 论文评审

LibraBFT是最近发布的Libra加密货币使用的拜占庭容错（BFT）共识算法。LibraBFT基于另一种名为HotStuff的BFT共识算法。尽管有人注意到这两种算法之间的相似性，但它们在关键方面存在差异。在本文中，我们重点讨论其中一个差异：在LibraBFT中，非领导者节点执行广播。这对活性分析、通信复杂性和领导者选举都有影响。在简要回顾BFT共识算法及其用途之后，我们将深入探讨这些主题。

BFT共识算法的简要历史

拜占庭容错（BFT）一词源自Lamport、Shostak和Pease的一篇论文。在该论文中，作者考虑了一个虚构场景：一组拜占庭将军正在考虑是否攻击一座城市。问题在于有些将军是叛徒。问题是，如果叛徒传播错误信息，那么在什么条件下，团队可以同意攻击或撤退？注意，攻击或撤退都不被认为比另一方更有利：问题只是就一个行动达成一致！

这个场景是分布式系统中常见情况的隐喻：将军是网络中的节点，叛徒是故障节点，而攻击城市则是向数据库提交交易。

Lamport等人的论文提出了这个问题的解决方案。然而，该解决方案隐含地假设了一个同步网络，这意味着节点之间的消息在固定的、已知的时间范围内传递。相比之下，异步网络中的消息可以任意延迟甚至重新排序。

Dwork、Lynch和Stockmeyer是第一个提出确定性算法来解决“部分同步”网络的拜占庭将军问题的人。（早些时候，Rabin和Ben-Or提出了随机算法。）Dwork等人对网络“部分同步”含义的分析是对BFT算法研究的重要贡献。然而，Dwork等人的算法目的似乎是建立此类解决方案的存在性。因此，它们的算法更具理论意义而非实际意义。

到世纪末，Castro和Liskov提出了一个解决方案，许多当代算法都基于此（例如，下面描述的Tendermint）。Castro和Liskov的算法称为实用拜占庭容错（PBFT），其工作方式如下。每轮有一个从节点中选出的指定领导者，每轮由三个阶段组成。大致上，在第一阶段，领导者提出一个命令供所有节点执行；在第二阶段，节点对该命令进行投票；在第三阶段，节点确认收到彼此的投票并执行命令。当节点认为一轮持续太久时，它会向所有其他节点发送超时消息。节点必须同意一轮应该超时。这个过程有些复杂。整体上，PBFT在最多⌊(n-1)/3⌋个节点故障时工作，这是可能的最佳情况。

为了规避Fischer、Lynch和Paterson的经典不可能结果，PBFT将安全性置于活性之上。这意味着，例如，领导者可能提出一个命令，而该命令可能无法执行，例如由于网络问题。然而，该算法是安全的，因为如果两个非故障节点执行某些命令序列，那么其中一个必然是另一个的前缀。

有趣的是，PBFT如何使用广播。在每轮的第一阶段，领导者向所有节点广播。但在第二和第三阶段，所有节点（不仅仅是领导者）相互广播。

PBFT论文中的图1，将每轮的三个阶段称为“预准备”、“准备”和“提交”。数字代表网络节点，箭头代表消息。注意非领导者节点1和2在第二和第三阶段如何向所有其他节点广播。

已经提出了许多PBFT的变体。一个显著的例子是Tendermint。与PBFT一样，Tendermint按轮进行，每轮分为三个阶段，每个阶段中广播的使用类似。然而，PBFT中的超时是针对整个轮的，而Tendermint中的超时是针对单个阶段的，许多人认为这是一种更简单的策略。（更多讨论请参见此处。）此外，Tendermint有一个经过充分测试且积极开发的实现。因此，Tendermint得到了广泛使用。

HotStuff也可以被视为PBFT的变体。HotStuff算法是“流水线化的”，因此轮中超时与阶段中超时本质上没有区别。但HotStuff对PBFT最显著的改进可能是其降低的“认证器复杂度”。如HotStuff论文中所定义，“认证器是部分签名或签名”（第4页）。论文认为“认证器复杂度是通信复杂度的有用度量……它隐藏了关于传输拓扑的不必要细节……n条携带一个认证器的消息与一条携带n个认证器的消息计数相同。”

HotStuff通过使用阈值签名部分实现了降低的认证器复杂度。这使得非领导者只需将其消息发送给领导者，而不是彼此发送。例如，当对命令进行投票时，HotStuff中的节点将其签名的“份额”发送给领导者。一旦领导者积累了2⌊(n-1)/3⌋ + 1个这样的份额，它就将组合签名广播给所有其他节点。HotStuff算法的其他阶段类似。通过这种方式，HotStuff实现了线性认证器复杂度。

LibraBFT

LibraBFT是Libra加密货币使用的共识算法。LibraBFT基于HotStuff。根据Libra作者的说法，“选择HotStuff协议作为LibraBFT基础有三个原因：(1) 安全性论证的简单性和模块性；(2) 轻松将共识与执行集成；(3) 在早期实验中表现出有前景的性能。”

LibraBFT和HotStuff非常相似。例如，LibraBFT保留了HotStuff的流水线设计。此外，当对命令（或使用LibraBFT术语中的“块”）进行投票时，节点仅将其投票发送给领导者，而不是所有其他节点。

LibraBFT论文中的图3。字母B、V和C分别代表“块”、“投票”和“[法定人数]证书”。注意节点如何仅将其投票发送给领导者（如HotStuff），而不是广播给所有其他节点（如PBFT）。另一方面，注意图注表明“轮同步”未在图中反映。轮同步确实涉及广播。

然而，为了实现某些目标（下面解释），LibraBFT以HotStuff不使用的方式使用广播。（通过这种方式，LibraBFT类似于其远祖PBFT。）具体来说，LibraBFT要求非领导者节点在以下情况下执行广播：

• 节点定期使用广播同步其状态。
• 当达到超时（例如由于网络问题或故障领导者）时，节点向所有其他节点发送超时消息。

使用广播进行状态同步使得更容易为LibraBFT建立活性结果。LibraBFT论文中未给出广播超时的原因。然而，如下所述，我们怀疑这是为了允许未来使用自适应领导者选举机制。尽管有这些优势，额外的广播具有增加算法通信复杂度的不幸副作用。然而，这种通信复杂度的增加可能是不可避免的。（状态同步广播和超时广播都不应影响算法的安全性。）

注意：最近一篇题为“Libra：前进之路”的博客文章明确表示LibraBFT是一个进行中的工作。也许因此，LibraBFT论文中定义的LibraBFT与Libra源代码中实现的LibraBFT之间存在差异。在本文的剩余部分，我们关注前者。我们在下面指出LibraBFT规范与Libra源代码之间的一些差异。（另请注意，虽然LibraBFT论文确实包含代码，但该代码不是Libra本身的一部分，而是模拟器的一部分。LibraBFT作者“打算在报告的后续版本中分享该模拟器的代码并提供实验结果”（第4页）。该版本的报告尚未发布。）

活性分析

在LibraBFT中，“节点每段时间[最小广播间隔]𝐼 > 0至少广播其状态一次”（第22页）。HotStuff中不存在类似概念。不出所料，这使得更容易为LibraBFT建立活性结果。然而，两种算法的活性分析在其他方面有所不同，我们现在解释。

HotStuff的活性定理断言，在包括轮领导者非故障的某些技术条件下，存在一个时间界限，在该时间内所有非故障节点执行命令并进入下一轮。活性定理由两个函数参数化：Leader和NextView。Leader是轮数的函数，决定该轮的领导者。NextView的参数未具体给出，但至少包括轮数。NextView决定何时生成轮超时“中断”。

HotStuff的活性定理

LibraBFT的活性定理具有类似形式。然而，有两个显著差异。首先，LibraBFT的Leader和NextView函数的类似物未留作参数，而是明确给出。其次，执行命令的时间界限不仅被断言存在，而且被明确给出。

LibraBFT的活性定理

值得注意的是，LibraBFT的显式时间界限具有上述提到的最小广播间隔𝐼。𝐼的出现表明LibraBFT的活性分析与HotStuff的活性分析根本不同，而不仅仅是明确给出的Leader和NextView机制的副产品。

我们还要指出，这是LibraBFT规范与Libra源代码不完全匹配的地方。在LibraBFT中，节点使用DataSyncNotification消息（在LibraBFT论文附录A.3中定义）相互广播其状态。Libra源代码中似乎不存在类似于DataSyncNotification消息的内容。例如，如果查看Libra的chained_bft模块中的start_event_processing函数，可以看到处理提案、投票等的函数调用。然而，似乎没有调用处理类似DataSyncNotification消息的内容。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

fn start_event_processing(
    &self,
    event_processor: ConcurrentEventProcessor,
    executor: TaskExecutor,
    ...
) {
    executor.spawn(Self::process_new_round_events(...)...);
    executor.spawn(Self::process_proposals(...)...);
    executor.spawn(Self::process_winning_proposals(...)...);
    executor.spawn(Self::process_block_retrievals(...)...);
    executor.spawn(Self::process_chunk_retrievals(...)...);
    executor.spawn(Self::process_votes(...)...);
    executor.spawn(Self::process_new_round_msg(...)...);
    executor.spawn(Self::process_outgoing_pacemaker_timeouts(...)...);
}

Libra“chained_bft”模块中“start_event_processing”函数的摘录。注意，似乎没有调用处理类似LibraBFT DataSyncNotification消息的内容。

底线是，LibraBFT活性分析不直接适用于当前形式的LibraBFT源代码。然而，如上所述，LibraBFT是一个进行中的工作。因此，LibraBFT规范与Libra源代码之间存在一些差异并不令人惊讶。

通信复杂度

如上文HotStuff描述中所述，HotStuff实现了线性认证器复杂度，其中“认证器是部分签名或签名”，在单轮网络消息中发送。LibraBFT的认证器复杂度是什么？不清楚且有些模糊。

LibraBFT论文未具体提及“认证器复杂度”，尽管它声称“LibraBFT具有两个理想属性，HotStuff之前的BFT共识协议无法同时支持——线性和响应性……非正式地，线性保证驱动交易提交仅产生线性通信……”（第2页）。该声明在论文后续部分未得到解决。正如我们所论证的，LibraBFT的认证器复杂度至少为O(n²)，其中n是节点数。因此，要么作者未指认证器复杂度，要么该声明是某种疏忽。

当LibraBFT节点认为一轮持续太久时，它向所有其他节点广播超时消息。这些超时消息已签名。因此，LibraBFT的认证器复杂度至少为O(n²)。

LibraBFT在状态同步中使用广播如何影响认证器复杂度？

状态同步由上述活性分析讨论中提到的最小广播间隔𝐼参数化。LibraBFT论文指出“节点每段时间𝐼 > 0至少广播其状态一次”（第22页）。考虑到这一点，LibraBFT的认证器复杂度不应仅是n的函数，还应是𝐼的函数。

然而，论文附录A.3指出“我们假设[数据同步消息]通过认证通道传输，并省略了消息签名”（第36页）。有人可能利用这一事实论证数据同步不影响认证器复杂度（尽管这感觉很像作弊）。

因此，由于使用超时广播，LibraBFT的认证器复杂度至少为O(n²)。根据对网络的假设，可能更多。

需要明确的是，这是最坏情况分析。在常见情况下，超时不会发生。因此，如果𝐼很大，例如是典型轮持续时间的许多倍，那么LibraBFT的性能将接近线性。

最后一点值得提及。HotStuff使用可预测的领导者选举策略。如下一节所述，Libra作者正试图避免使用这种策略。据我们所知，目前不存在次二次自适应领导者选举策略。因此，在比较HotStuff和LibraBFT的通信复杂度时，某些增加可能是不可避免的。

领导者选举

在撰写本文时，Libra源代码的领导者选举策略是轮询。然而，LibraBFT作者指出，这种策略使轮领导者可预测，这便于拒绝服务攻击。在考虑替代方案时，作者指出，以简单方式依赖哈希可能便于“研磨攻击”，例如，攻击者影响哈希以增加特定节点被选为领导者的可能性。

为了解决前一个问题并规避后一个问题，作者表示，“我们打算将来使用可验证随机函数（VRF）。”（事实上，VRF已在Libra源代码中实现，但似乎尚未使用。）在接下来两段中，我们解释VRF是什么。然后，在简要解释LibraBFT块“提交”的含义后，我们解释LibraBFT在领导者选举中提议使用VRF如何由其广播使用启用。

直观上，VRF是一个函数，给定某些输入，产生两个输出：一个看似随机的值，以及一个证明该值源自输入的证明。该函数应具有两个属性。首先，看似随机的值如何从输入派生不应明显。其次，应可能说服观察者看似随机的值源自输入，即使该事实不明显。后一属性通过证明实现。

Goldberg、Reyzin、Papadopoulos和Vcelak的草案RFC第4节给出了VRF的一个简单示例。在该示例中，看似随机的值是在输入哈希上计算的RSA签名，证明是哈希。观察者可以通过检查输入具有哈希且签名对应于哈希来验证证明。（注意：对于生产代码，我们建议使用RFC第5节的基于椭圆曲线的VRF，而不是第4节的基于RSA的VRF。）

我们现在简要解释LibraBFT块“提交”的含义。在LibraBFT中，块和法定人数证书交替形成链：

B0 ← C0 ← B1 ← C1 ← B2 ← C2 ← ⋯

这些块（证书）不必在连续轮中提出（组装）；它们之间可能存在任意大的间隙。当满足以下条件时，块被称为“提交”：(1) 它出现在另外两个块下方，(2) 所有三个块都有相关的法定人数证书，以及(3) 这些块在连续轮中提出。

此规则的原因有些技术性。但直观上，“提交”的块被所有非故障节点视为永久性。相比之下，出现在少于两个认证块下方的块被视为非永久性，可能必须被放弃以支持另一个块。

LibraBFT作者打算在领导者选举中使用VRF如下。每个节点将有自己的一些VRF实例（例如，用属于该节点的私钥实例化的VRF）。轮i的领导者将使用最近提交块的轮领导者的VRF实例确定。该VRF实例将确定伪随机函数（PRF）的种子。生成的PRF实例然后将确定轮i及每个后续轮的领导者，直到新块提交。像这样使用两个函数的原因（我们相信）是即使最近提交块的提议者离线，也可以确定轮领导者。

我们现在解释LibraBFT在领导者选举中提议使用VRF如何由其广播使用启用。或者，更具体地说，我们解释为什么如果节点可以仅向一个其他节点发送超时消息（如HotStuff中情况），LibraBFT提议使用VRF将不起作用。超时消息的目的是告诉下一轮领导者开始下一轮。但如下面几段所示，下一领导者是谁可能取决于超时的原因。

假设在连续轮i-2、i-1和i中，提出块Bm-2、Bm-1和Bm。进一步假设轮i的领导者组装法定人数证书Cm并将其广播给所有其他节点。因此，在轮i+1开始时，最近提交的块是Bm-2：

B0 ← C0 ← ⋯ ← Bm-2 ← Cm-2 ← Bm-1 ← Cm-1 ← Bm ← Cm

但假设轮i的领导者在合理时间内未收到轮i+1的块提案。如果轮i的领导者可以仅向一个其他节点发送超时消息，她应该发送给谁？（注意，轮i的领导者在检测或宣布轮i+1超时方面没有特殊作用。）

考虑以下两种解释为什么轮i的领导者未收到轮i+1的块提案。

情况1：轮i+1的领导者故障且从未提出块。在这种情况下，轮i+2时最近提交的块仍然是Bm-2。因此，轮i+2的领导者应由确定轮i+1领导者的相同PRF实例确定。如果轮i的领导者可以仅向一个其他节点发送超时消息，她应将其发送给由此现有PRF实例确定的领导者。

情况2：存在网络延迟。轮i+1的领导者提出了块并组装了法定人数证书，但轮i的领导者未及时收到它们。在这种情况下，轮i+2时最近提交的块是Bm-1。因此，轮i+2的领导者应由新的PRF实例确定，该实例由属于Bm-1提议者的VRF实例播种。如果轮i的领导者可以仅向一个其他节点发送超时消息，她应将其发送给由此新PRF实例确定的领导者。

通过让轮i的领导者将其超时消息发送给所有其他节点，这种歧义得到解决。如果LibraBFT作者引入超时广播 specifically 来解决此类场景，我们不会感到惊讶。

最后，注意HotStuff中不存在类似问题。在HotStuff中，轮领导者由“从视图编号到副本的某种确定性映射确定，最终轮换所有副本”，并且不依赖于最近提交的块。另一方面，轮领导者的可预测性使HotStuff易受拒绝服务攻击，而LibraBFT作者正试图避免。

LibraBFT和HotStuff是不同的算法

LibraBFT和HotStuff非常相似，但两种算法在关键方面存在差异。在LibraBFT中，非领导者执行广播。在状态同步中使用广播使得更容易为LibraBFT建立活性结果。我们怀疑引入超时广播是为了允许未来使用自适应领导者选举机制，例如基于VRF的机制。尽管有这些优势，额外的广播增加了算法的通信复杂度。然而，这种通信复杂度的增加可能是不可避免的。

我们打算密切关注Libra。如果您正在开发