论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决定何时生成轮超时“中断”。

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

值得注意的是，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的机制。尽管有这些优势，额外的广播增加了算法的通信复杂度。然而，这种通信复杂性的增加可能是不可避免的