论LibraBFT的广播使用方式

LibraBFT是近期发布的Libra加密货币使用的拜占庭容错（BFT）共识算法。它基于另一种名为HotStuff的BFT共识算法。尽管两者存在相似性，但在关键方面存在差异。本文重点探讨其中一个差异：在LibraBFT中，非领导者节点需要执行广播。这对活性分析、通信复杂性和领导者选举产生了影响。

BFT共识算法的简要历史

拜占庭容错（BFT）一词源自Lamport、Shostak和Pease的论文。作者设想了一个场景：一群拜占庭将军决定是否攻击城市，其中存在叛徒将军。问题在于，在叛徒散布错误信息的情况下，群体何时能达成一致行动？这一场景是分布式系统的隐喻：将军是网络节点，叛徒是故障节点，攻击城市则类似于向数据库提交事务。

Lamport等人的论文提出了解决方案，但假设网络是同步的（消息在固定时间内传递）。Dwork、Lynch和Stockmeyer首次为“部分同步”网络提出确定性算法解决拜占庭将军问题。Castro和Liskov提出的实用拜占庭容错（PBFT）成为许多现代算法的基础（如Tendermint）。PBFT每轮选举领导者，分为三个阶段：领导者提议命令、节点投票、节点确认投票并执行命令。节点通过超时消息协调轮次超时。PBFT在最多⌊(n-1)/3⌋节点故障时仍能工作，优先保证安全性而非活性。

PBFT的广播使用方式值得注意：第一阶段领导者向所有节点广播，但第二和第三阶段所有节点（不仅是领导者）相互广播。

PBFT的变种包括Tendermint和HotStuff。Tendermint将超时机制细化到阶段级别，并有经过充分测试的实现。HotStuff通过流水线设计降低“认证器复杂度”，使用阈值签名使非领导者仅向领导者发送消息，实现线性通信复杂度。

LibraBFT

LibraBFT基于HotStuff，选择原因包括：安全性论证的简洁性、共识与执行的易集成性以及早期实验中的性能表现。LibraBFT保留HotStuff的流水线设计，投票时节点仅向领导者发送投票。

然而，为实现特定目标，LibraBFT以HotStuff未采用的方式使用广播（更接近其远祖PBFT）。具体来说，LibraBFT要求非领导者节点在以下情况下执行广播：

• 节点定期通过广播同步状态。
• 超时发生时（如网络问题或领导者故障），节点向所有其他节点发送超时消息。

状态同步广播使LibraBFT的活性证明更易建立。超时广播的原因未在论文中说明，但推测是为了支持未来自适应领导者选举机制的使用。尽管有这些优势，额外广播增加了算法的通信复杂度，但这种增加可能是不可避免的。

活性分析

在LibraBFT中，“节点至少每段时间（最小广播间隔）𝐼 > 0广播其状态”（第22页）。HotStuff中无类似概念。这使LibraBFT的活性证明更易建立，但两者活性分析在其他方面也存在差异。

HotStuff的活性定理断言，在包括轮次领导者非故障的技术条件下，存在时间边界，所有非故障节点在此时间内执行命令并进入下一轮。该定理参数化两个函数：Leader（确定轮次领导者）和NextView（确定超时中断生成时机）。

LibraBFT的活性定理形式类似，但有两个显著差异：首先，Leader和NextView的类似函数被显式给出而非留作参数；其次，执行命令的时间边界被显式给出而非仅断言存在。值得注意的是，LibraBFT的显式时间边界包含上述最小广播间隔𝐼。𝐼的出现表明LibraBFT的活性分析与HotStuff有根本不同，并非仅由显式给出的Leader和NextView机制导致。

此外，此处存在规范与源代码的不匹配：LibraBFT中节点通过DataSyncNotification消息广播状态（论文附录A.3定义），但Libra源代码中似乎无类似消息处理。例如，Libra的chained_bft模块的start_event_processing函数处理提案、投票等，但无处理DataSyncNotification消息的调用。

总之，LibraBFT活性分析不直接适用于当前形式的源代码。但由于LibraBFT仍在开发中，规范与代码存在差异并不意外。

通信复杂度

如前所述，HotStuff实现线性认证器复杂度（认证器是单轮网络消息中发送的部分签名或签名）。LibraBFT的认证器复杂度如何？不明确且存在歧义。

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

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

状态同步广播如何影响认证器复杂度？状态同步由最小广播间隔𝐼参数化（见活性分析讨论）。论文称“节点至少每段时间𝐼 > 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是一种函数，给定输入产生两个输出：一个随机值，以及该值源自输入的证明。函数应具两属性：首先，随机值如何从输入衍生应不明显；其次，应能说服观察者随机值源自输入（尽管该事实不明显）。后者属性通过证明实现。

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

1

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：

1

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作者引入超时广播专门处理此类场景。

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

LibraBFT和HotStuff是不同算法

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

我们打算密切关注Libra。若您正在开发Libra应用程序，请考虑我们进行安全审查。

2019年7月16日更新。