摘要。本报告介绍了LibraBFT，这是一个针对Libra Blockchain设计的强大而高效的状态机复制系统。 LibraBFT基于HotStuff，这是最近的一项协议，利用拜占庭容错（BFT）数十年的科学进步，实现了互联网设置所需的强大的可扩展性和安全性。 LibraBFT进一步完善了HotStuff协议，引入了明确的活跃度机制，并提供了具体的延迟分析。为了推动与Libra Blockchain的集成，本文档提供了从全功能模拟器中提取的规范。这些规范包括状态复制接口和用于参与者之间的数据传输和状态同步的通信框架。最后，本报告提供了一个正式的安全证明，它引出了检测BFT节点不良行为的标准，同时还有一个简单的奖励和惩罚机制。

1 介绍

互联网和移动宽带的出现使全球数十亿人接触，提供知识，免费通信和各种低成本，更便捷的服务。这种连接还使更多人能够访问金融生态系统。然而，尽管取得了这些进展，但对于那些最需要金融服务的人来说，获得金融服务仍然有限。

区块链和加密货币表明，计算机科学，密码学和经济学的最新进展有可能在金融基础设施方面创造创新，但现有系统尚未达到主流应用。作为实现这一目标的下一步，我们设计了Libra Blockchain [1]，[2]，目的是建立一个简单的全球货币和金融基础设施，为数十亿人提供支持。

这个新区块链的核心是一个名为LibraBFT的共识协议 - 本报告的重点 - 通过该协议对区块链交易进行排序和最终确定。 LibraBFT在参与共识协议的一组验证器中分散信任。 LibraBFT保证就诚实验证者之间的交易历史达成共识，即使参与者的门槛是拜占庭（即有缺陷或腐败[3]），它仍然是安全的。通过采用经典的拜占庭容错方法，LibraBFT建立在分布式计算中坚实且经过严格验证的基础之上。此外，科学界已经在LibraBFT的基础上取得了稳步进展，在扩展共识技术方面，并使其在互联网环境中保持稳健。

最初，参与的验证者将被允许进入共识网络，该协会由地理上分布的和不同的创始成员组成，这些成员是根据客观成员标准选择的组织，具有引导Libra生态系统的既得利益[2]。随着时间的推移，会员资格将变为开放，仅基于组织持有Libra[4]。

LibraBFT的共识基于一种名为HotStuff的前沿技术[5]，[6]，它在BFT共识和区块链的世界之间架起了桥梁。这种选择反映了丰富的专业知识和各种替代方案的探索，并为LibraBFT提供了以下关键属性，这些属性对于分散信任至关重要：

安全性： LibraBFT保持诚实验证者之间的一致性，即使多达三分之一的验证者作恶。
异步： 即使在网络异步的情况下（即，在无限制的通信延迟或网络中断期间），也保证一致性。这反映了我们的信念，即构建互联网规模的共识协议，其安全性依赖于同步，本质上既复杂又容易受到网络上的拒绝服务（DoS）攻击。
不可改变性： LibraBFT支持不可改变性概念，即交易变得不可逆转。它提供了简明的承诺，用于向最终用户验证分类帐查询的结果。
线性和响应性： LibraBFT有两个理想的属性，HotStuff之前的BFT共识协议无法同时支持 - 线性和响应性。这两个技术概念与领导者的概念相关联，这是推动部分同步进展的关键方法。非正式地，线性保证即使领导者轮换，推动交易提交也只会产生线性通信（这是最优的）; 响应性意味着领导者在收集来自验证者的响应时没有内置的延迟步骤和进展。
简单性和模块性： LibraBFT的核心逻辑允许简单而强大的实现，与基于Nakamoto共识的公共区块链相似[7]。值得注意的是，该协议围绕单个通信阶段进行组织，并允许简明的安全性参数。
可持续性： 据报道，信任基于计算能力的当前公共区块链消耗大量能量[8]，可能需要集中化[9]。 LibraBFT被设计为股权证明系统，其中参与特权基于其财务参与被授予已知成员。 LibraBFT可以支持经济激励措施，以奖励良好行为和/或惩罚利益相关者的错误行为。 LibraBFT中的计算成本主要包括加密签名，这是一种具有高效实现的标准概念。

关键技术方法 LibraBFT是一个共识协议，在轮次中进行，在每轮中，在验证者中选择领导者。如上所述，需要这种关键方法来推动部分同步的进展。领导者提出一个由事务组成的新块，并将其发送给其他验证者，如果新块都是由有效事务组成，则验证者验证新块。一旦领导者收集了大多数选票，她就会将其发送给其他验证人。如果领导者未能提出有效的区块或者没有聚集足够的选票，则超时机制将强制进行新一轮，并且将从验证器中选择新的领导者。这样，新块扩展了区块链。最终，一个块将满足LibraBFT的提交规则，一旦发生这种情况，就会提交此块和任何先前的块。

相关工作 全面的调查超出了本手稿的范围（例如参见[10] - [12]）。在这里，我们提到影响我们工作的关键概念和机制。经典设置中的共识算法。拜占庭共识问题由Lamport等人开创。 [3]，他还创造了拜占庭一词来模拟任意的，可能是恶意腐败的行为。 Lamport等人提出的解决方案的安全性。依赖于同步，实际系统希望避免由于复杂性而导致的依赖性，并且因为它使系统暴露于DoS对安全的攻击。

代替同步假设，由Ben-Or [13]开创的随机算法保证了高概率的进步。一系列研究逐渐提高了此类算法的可扩展性，包括[14] - [17]。但是，大多数实际系统尚未纳入随机化。在未来，LibraBFT可能会采用某些随机化来阻止自适应攻击。

Dwork等人介绍了一种不同的异步设置方法[18]，将安全（在任何时候）从活性（在同步期间）分开。Dwork等人引入了一个轮逐轮的范例，每一轮都由指定的领导者驱动。一旦诚实的领导者出现，就会在同步期间保证进展，并且在此之前，轮次会因超时而退役。 Dwork等人的方法（DLS）是迄今为止大多数实际BFT工作的基础，并且其性能得到了稳定的改进。具体而言，它是Castro和Liskov [19]引入的第一个实用解决方案的基础，称为PBFT。在PBFT中，一个诚实的领导者在两个all-to-all的通信轮次中做出决定。除了最初的PBFT开源实现之外，该协议已经集成到BFT-SMaRt [20]中，最近已集成到FaB [21]中。Zyzzyva [22]为PBFT增加了一条乐观快速的轨道，当没有失败时，它可以在一轮中做出决定。Zyzzyva [22]为PBFT增加了一条乐观快速的轨道，当没有失败时，它可以在一轮中做出决定。Cachin [24]和Reiter [25]在共识协议中使用了使用门限加密的响应聚合，以all-to-collector和collector-to-all模式替换all-to-all通信模式，这种模式仅产生线性通信成本。门限签名聚合已被纳入几个基于PBFT的系统，包括Byzcoin [26]和SBFT [27]。同样，LibraBFT结合了消息收集和快速签名聚合[28]。与门限签名相比，LibraBFT中的签名聚合不需要分布式设置，并且以每个签名的每个节点一个额外比特的价格为选民提供经济激励。

两个区块链系统，Tendermint [29]和Casper [30]提出了一种新的PBFT变体，它简化了PBFT的领导者替换协议，使其仅具有线性通信成本（线性）。这些变体放弃了称为响应性的实用解决方案的标志性特征。非正式地，（乐观的）响应性允许当领导者在收到固定数量的消息时提出新的块而不是等待固定的延迟时。因此，Tendermint和Casper在实际的BFT解决方案中引入了一个权衡 - 它们具有线性或响应性，但不是两者兼而有之。LibraBFT所基于的HotStuff解决方案（以及其他最近的区块链，特别是具有名为PaLa [31]的变体的ThunderCore）解决了这种权衡，并提出了第一个具有两者的BFT共识协议。

在无权限的环境中达成共识。上面提到的所有作品都采用了允许的设置，即参与的玩家是事先知道的。不同的是，在无权限的环境中，任何一方都可以加入并参与协议 - 这就是Nakamoto Consensus（NC）[7]旨在解决的问题 - 导致完全不同的协议结构。在NC中，交易（以块为单位）被链接并简单地通过工作证明传播到网络。确认是以概率方式定义的 - 块在历史中保留的概率与区块链中后续块的计算成本成正比。扩展现有供应链的奖励机制足以激励矿工接受当前的实际存在的链并迅速收敛于一个最长的分叉。Casper和HotStuff表现出类似的协议结构简单性。他们将协议轮次嵌入到（可能是分支的）链中，并通过链的简单离线分析推断出提交决策。

几个区块链类似地基于直接非循环图（DAG）形式的块图，允许在将块发布到图中时具有更大的并发性，例如GHOST [32]，Conflux [33]，Blockmania [34]和Hashgraph [35]。我们对这些范例中的一些范例的经验表明，恢复图形信息并在参与者暂时失去连接后进行验证可能具有挑战性。在LibraBFT中，只有领导者才能扩展链条; 因此，传播，恢复和验证图形信息很简单，基本上是线性的。

重温LibraBFT。 LibraBFT利用HotStuff（ArXiv版本[5]，出现在PODC’19 [6]中）并拥有上面四十年的工作所取得的许多好处。具体来说，LibraBFT采用DLS和PBFT循环方法，具有签名聚合，并具有线性和响应性。我们还发现Casper和HotStuff的链结构导致了强大的实现和简洁的安全性参数。

与HotStuff本身相比，LibraBFT进行了许多增强。 LibraBFT提供了起搏器机制的详细规范和实现，参与者通过该机制同步轮次。这与活跃度分析相结合，该分析包含对交易承诺的具体约束。 LibraBFT包括验证者投票权（时期）的重新配置机制。它还描述了奖励提议者和选民的机制。该规范允许导出安全和完整的标准来检测试图破坏安全性的验证者，从而使惩罚能够在将来纳入协议。我们还详细阐述了验证者之间的数据传播协议，以同步其状态。

组织： 本报告的其余部分结构如下：我们首先介绍重要的概念和定义（第2节）以及如何在Libra区块链中使用LibraBFT（第3节）。本报告的其余部分结构如下：我们首先介绍重要的概念和定义（第2节）以及如何在Libra区块链中使用LibraBFT（第3节）。然后，我们描述了LibraBFT及其网络通信层的核心数据类型（第4节）。接下来，我们将协议本身（第5节）提供足够的细节来准备安全证明（第6节）。然后我们描述起搏器模块（第7节）并证明活力（第8节）。最后，我们讨论了LibraBFT的经济激励（第9节），并在第10节中得出结论。

在这个初始报告中，需要代码的地方，我们选择使用Rust的最小子集作为协议的规范语言。我们提供在离散事件模拟环境中直接从我们的参考实现中提取的代码片段。我们打算共享此模拟器的代码，并在后续版本的报告中提供实验结果。

2 概述和定义

我们首先描述LibraBFT的所需属性以及我们的状态机复制协议如何集成到Libra Blockchain中。

2.1 复制状态机

复制状态机（SMR） 协议[36]旨在提供分布在网络上并在许多进程（也称为节点）之间复制的抽象状态机。

具体地，以一些初始执行状态启动SMR协议。每个进程都可以提交命令并观察一系列提交。每个提交都包含执行状态，该执行状态是在先前提交之上执行特定命令的结果。在执行期间可能会拒绝命令：在这种情况下，它们被称为无效命令。

假设命令执行是确定性的，我们希望保证以下属性：

安全性 所有诚实的节点都遵循相同的提交顺序。
活性只要提交了有效命令，就会生成新提交。

请注意，节点应以相同的顺序观察提交，但不一定要同时观察。第2.3节中详细说明了诚实节点的概念。

2.2 时代（Epochs）

对于实际应用，参与协议的节点集可以随着时间的推移而发展。在LibraBFT中，通过epoch的概念解决了这个问题：

每个时代开始时使用上一个纪元的最后执行状态 - 或者使用系统范围的第一个时代的初始参数。
我们假设每个执行状态都包含一个标识当前时期的值epoch_id。
当提交递增epoch_id的命令时，当前时代在该提交之后停止，并且下一个时代开始。

2.3 拜占庭容错

从历史上看，容错协议旨在解决常见故障，例如崩溃。在区块链的上下文中，SMR共识协议用于限制系统中各个节点的权力。为此，即使某些节点与协议任意偏离，我们也必须保证安全和活跃。

在本报告的其余部分，我们假设每个时代都有一个固定的，未知的恶意节点子集，称为拜占庭节点[3]。假定所有其他节点（称为诚实节点）严格遵循协议规范。在给定的时代内，我们假设每个SMR节点α具有固定的投票权，表示为𝑉（α）≥0。我们为所有节点的总投票权写𝑁，并假设一个安全阈值𝑓作为𝑁的函数，使得𝑁>3𝑓。例如，我们可以定义𝑓=（𝑁-1）/ 3。对于本报告中的符号简单性，我们将𝑥的投票权称为𝑥节点。

我们在以下BFT假设的背景下分析所有共识属性：

bft假设 任何时期内拜占庭节点的组合投票权不得超过安全阈值𝑓。

组合投票权𝑀满足𝑀≥𝑁-𝑓的节点子集称为法定集合（法定人数）。以下经典引理[37]证明了法定集合的概念：

引理B1： 在BFT假设下，对于同一时代中两个法定集合的每个节点，存在一个诚实节点同时属于两个法定集合。

我们在6.1节中回顾引理B1的证明。

2.4 加密假设

我们假设散列函数和数字签名方案对计算有限的攻击者是安全的，并要求每个诚实节点对其私有签名密钥保密。

由于我们的协议只散列和签名公共值，我们可以假设所有数字签名都是强烈的非概率意义上的不可伪造的，这意味着任何有效的签名必须来自私钥的所有者。类似地，我们可以假设哈希函数永远不会发生哈希冲突，因此hash（𝑚1）=hash（𝑚2）意味着𝑚1=𝑚2。

2.5 网络假设和忠实者崩溃

虽然LibraBFT的安全性仅在BFT假设下得到保证，但活跃性需要对网络和流程进行额外的假设。具体来说，我们假设网络在坏连接和良好连接的时段之间交替，分别称为异步和同步的时段。只有在足够长的同步期间才能保证活力。

在异步期间，我们允许消息丢失或占用任意长的时间。我们还允许诚实的节点崩溃并重新启动。在同步期间，我们假设在诚实节点之间的任何消息所采用的传输延迟存在上限δ𝑀; 此外，诚实的流程必须响应，不能崩溃。

我们必须强调，即使在同步期间，受到最大延迟δ𝑀的影响，攻击者也会控制恶意节点和网络消息的调度。

该模型的参数 - 例如δ𝑀的值或网络当前是否同步 - 对系统内的参与者不可用。为了简化分析，文献中通常只考虑两个时期：在某个未知的全球稳定时间（称为GST）之前和GST之后。我们的活性证明（第8节）将给出系统在GST之后产生提交所需时间的具体上限。

更正式地说，关于网络和崩溃的假设写成如下：

最终同步网络: GST之后，在一些（未知的）延时δ𝑀> 0内，网络在诚实节点之间传递所有消息。
最终没有崩溃：GST之后，诚实的节点完全响应，永不崩溃。

我们注意到GST模型没有考虑与消息处理相关的CPU时间。此外，LibraBFT中的消息大小不受限制，因此，固定的δ𝑀可以说是过度简化的。在将来的工作中，我们可以对消息大小实施严格限制，或者将每条消息的网络延迟视为固定延迟，传输延迟与消息大小成比例的组合。

2.6 领导者，投票，法定认证

LibraBFT属于基于领导者的共识协议系列。在基于领导者的协议中，验证者轮流取得进展，每轮都有一个称为领导者的指定验证者。领导者负责提出新的区块并获得验证人对其提案的签名投票。LibraBFT遵循HotStuff [5]的链式变体，其中每轮是一个单个指定领导者的通信阶段，并且领导者的提议使用加密哈希组织成链。在一轮中，领导者提出了一个扩展其知道的最长链的块。如果提案有效且及时，则每个诚实节点都会签名并向领导发回投票。在领导者获得足够的投票以达到法定人数之后，它将投票聚合成法定人数证书（QC），再次延伸相同的链。QC广播到每个节点。如果领导者未能组装QC，参与者将超时并进入下一轮。最终，足够的块和QC将及时扩展链，并且块将匹配协议的提交规则。当发生这种情况，链上向上匹配的未提交块将变为提交。

3 与Libra区块链整合

3.1 共识协议

我们预计LibraBFT将用于Libra区块链[2]，如下所示：

Libra的验证者参与LibraBFT协议，以便安全地复制Libra区块链的状态。我们将每个验证器运行的LibraBFT节点的软件实现称为SMR模块。从这里开始，我们将LibraBFT的参与者称为验证者节点，或简称为节点。
发送到SMR模块的命令是Libra事务的序列。从SMR模块的角度来看，命令和执行状态是不透明的数据结构。 SMR模块将命令的执行完全委托给Libra的执行模块（参见附录A.1中的可能API）。我们从执行状态中读取了epoch_id。（回想一下，当提交对epoch_id的更改时，当前时代会停止。）
重要的是，，SMR模块还委托系统的剩余部分计算给定时代内的投票权。使用与执行层相同的回调（附录A.1）作为管理时代的回调来完成。为了获得更好的灵活性和透明度，我们希望这个逻辑能够在Move [38]中编写，这是Libra中可编程事务的语言。
每次需要执行命令时，执行引擎都会获得一个用于Move智能合约的时间值。保证该值在执行相同命令的每个SMR节点上一致。
SMR模块看到的执行状态不必是实际的区块链数据。实际上，在本报告中我们称之为“执行状态”的是轻量级数据结构（例如，散列值），其指的是存储在验证者的本地存储器中的具体执行状态。提交的每个命令必须由每个验证器至少在本地执行一次。将来，LibraBFT还可以包括一个附加机制，用于验证者通过本地存储与另一验证者相应的最近执行状态同步。

3.2 Libra 客户端

LibraBFT在验证者节点如何与Libra客户端交互的设计上是基本独立的。但是，我们可以提出以下意见：

Libra客户端提交的事务首先使用内存池协议在验证者节点之间共享。当需要提出提案时，共识领导者会从内存池中提取交易。
为了验证与Libra客户端相关的区块链状态，在协议期间，LibraBFT节点签署了简短的承诺，以保证特定的执行状态正在提交。这导致加密提交证书可以独立于LibraBFT的共识协议的细节进行验证，前提是Libra客户端知道相应时代的验证者密钥集。我们将在章节（第4.1节）中描述如何与共识数据一起创建承诺。
关于这最后的假设，目前，我们将考虑Libra客户端可以从与一个或多个可信验证者的传统交互中学习验证者密钥集。将来，我们将为此目的提供安全协议。

3.3 安全

区块链应用程序还需要额外的安全注意事项：

协议的参与者应该能够限制他们分配给其他节点的资源量（例如，CPU，内存，存储等），以确保尽管有拜占庭行为的实际活跃度。我们将在下一节（第4节）中看到，我们的数据通信层提供了让接收者控制它们消耗多少数据（即背压）的机制。对本报告的未来版本进行更彻底的分析。
理性节点的经济激励应与SMR协议的安全性和性能保持一致。我们在章节（第9节）中描绘了能够奖励和惩罚的低级机制。
领导者可能会受到针对性的拒绝服务攻击。我们的起搏器规范（第7节）概述了如何引入可验证的随机函数（VRF）[39]，以一种较不可预测的方式将领导者分配给轮数。在未来，我们还可能影响领导者选择，以便更频繁地选择健全的领导者。在系统级别保护节点超出了本报告的范围。

关于公平的说明： 除了安全性和活性之外，SMR系统中经常讨论的另一个抽象属性是公平性。传统上，这个概念被定义为诚实节点提交的每个有效命令最终都被提交的事实。然而，这个经典的定义与诸如Libra之类的区块链应用程序的相关性较低，其中交易首先通过共享的内存池进行，并且需要进行交易费拍卖。在未来工作中，我们在讨论公平性。

4 共识数据和网络

在本节中，我们将介绍LibraBFT的核心数据类型，称为记录，并讨论用于通过网络同步节点状态的通信框架。

4.1 记录

LibraBFT节点的核心状态由一组记录组成。我们定义了四种记录：

区块： 由领导者在给定的轮数中提出并包含要执行的命令
投票： 节点为一个块及其执行状态投票
法定认证（QCs）： 其中包含对于给定块及其执行状态的法定数量的投票 - 以及可选的对Libra客户的承诺。
超时： 节点通过它来证明其当前轮次已达到超时。

Rust中的精确数据结构将在下一段中提供。最重要的是：

记录由作者签名。
块被链接（图2）：它们必须包括较低轮的块的QC的哈希 - 或者在时代的开始处，在时期的初始化期间设置的固定散列值ℎinit。
投票和QCs包括作为投票对象的块哈希和执行状态。

根据当前时代的投票权，通过收集相同执行状态的足够法定票数（第2.3节）来形成QC。法定认证由其作者签署的事实对协议来说并不重要：这仅仅是为了限制下一位领导人对选民奖励的影响（见第9节关于经济激励）。

投票和QCs包括为Libra客户端准备的可选承诺值。当投票人检测到在已投票块上收集QC将触发链中较早块的提交时，它必须使用该较早块的执行状态填充字段commitment（另请参见下面第5.3节中的提交规则）。通过这种方式，具有非空字段commitment的QC充当提交证书 - 即，提交特定状态的简短加密证明。由于我们在QC中包含了时代标识符，因此只要知道该时代的验证者集，就可以单独验证这种提交证书。

由于与数据同步消息相关的技术原因，我们在投票和QC中包括冗余的轮数（附录A.3）。

必要时，我们将区分网络记录 - 刚刚从网络接收的记录 - 来自经过验证的记录，这些记录已经过彻底验证，以确保在下一节中定义的强不变量（第4.2节）。但是，当上下文清楚时，我们通常会使用记录来验证记录。

重要的是，由记录验证（例如，链接规则）强制执行的不变量和初始条件保证一个给定时代的记录形成树 - 除了超时没有上链的。对于每个节点，保存时代记录的数据结构称为记录存储。如果一条记录存在于节点当前时代的记录存储中，我们说节点知道这条记录。我们在附录A.2中描绘了记录存储对象的可能接口。我们将明确节点何时可以从其记录存储中删除（清理）记录，以最小化存储，作为5.7节中协议描述的一部分。

Rust中的数据结构。 我们假设以下原始数据类型：

EpochId (整型).
Round (整型).
NodeTime (节点的系统时间).
BlockHash and QuorumCertificateHash (哈希值).
Author (共识节点的标识).
Signature (数字签名).

LibraBFT的网络记录使用如下的Rust语法指定。

/// A record read from the network.
enum Record {
    /// Proposed block, containing a command, e.g. a set of Libra transactions.
    Block(Block),
    /// A single vote on a proposed block and its execution state.
    Vote(Vote),
    /// A quorum of votes related to a given block and execution state.
    QuorumCertificate(QuorumCertificate),
    /// A signal that a particular round of an epoch has reached a timeout.
    Timeout(Timeout),
}
struct Block {
    /// User-defined command to execute in the state machine.
    command: Command,
    /// Time proposed for command execution.
    time: NodeTime,
    /// Hash of the quorum certificate of the previous block.
    previous_quorum_certificate_hash: QuorumCertificateHash,
    /// Number used to identify repeated attempts to propose a block.
    round: Round,
    /// Creator of the block.
    author: Author,
    /// Signs the hash of the block, that is, all the fields above.
    signature: Signature,
}
struct Vote {
    /// The current epoch.
    epoch_id: EpochId,
    /// The round of the voted block.
    round: Round,
    /// Hash of the certified block.
    certified_block_hash: BlockHash,
    /// Execution state.
    state: State,
    /// Execution state of the ancestor block (if any) that will match
    /// the commit rule when a QC is formed at this round.
    commitment: Option<State>,
    /// Creator of the vote.
    author: Author,
    /// Signs the hash of the vote, that is, all the fields above.
    signature: Signature,
}
struct QuorumCertificate {
    /// The current epoch.
    epoch_id: EpochId,
    /// The round of the certified block.
    round: Round,
    /// Hash of the certified block.
    certified_block_hash: BlockHash,
    /// Execution state
    state: State,
    /// Execution state of the ancestor block (if any) that matches
    /// the commit rule thanks to this QC.
    commitment: Option<State>,
    /// A collections of votes sharing the fields above.
    votes: Vec<(Author, Signature)>,
    /// The leader who proposed the certified block should also sign the QC.
    author: Author,
    /// Signs the hash of the QC, that is, all the fields above.
    signature: Signature,
}
struct Timeout {
    /// The current epoch.
    epoch_id: EpochId,
    /// The round that has timed out.
    round: Round,
    /// Creator of the timeout object.
    author: Author,
    /// Signs the hash of the timeout, that is, all the fields above.
    signature: Signature,
}

哈希和签名: 我们假设可以对记录的数据字段进行哈希以产生确定性哈希值。通过确定性哈希，我们的意思是当且仅当数据结构的内容相等时，两个数据结构的哈希值应相等（另请参见第2.4节关于加密假设）。

记录的哈希应包括与类型相关的标记，后跟记录中的所有字段，但字段签名除外。记录的签名适用于其哈希值。

QC中投票向量的签名是从QC作者选择的原始投票记录中复制的。

4.2 网络记录验证

在时代初始时，共识节点就QuorumCertificateHash类型的初始值ℎinit达成一致。例如，我们可以用某些固定值的种子定义$ ℎ_{init}= hash（seed \parallel epoch\_id）$。

每个共识节点都会顺序验证它从网络接收的所有记录：

所有签名都应该是来自当前时期节点的有效签名。
BlockHash值应引用先前验证的块。
QuorumCertificateHash值应引用已验证的法定认证或初始散列ℎinit。
对于块链和法定认证中的连续块，应严格增加轮次值。建议块中的轮次值在每个时代从第1轮重新开始。
QC的作者应该是前一个块的作者。
超时，投票和QC中的时代标识符必须与当前时代匹配。
投票和QC中的轮次值必须与认证区块的轮次相匹配。
投票或法定认证中的承诺值应与提交规则一致（第5.3节）。如果承诺值存在，则应由与认证块相同的作者集签名。
应跳过验证失败的网络记录。

鉴于块和QC的散列的约束，除了超时之外，节点已知的已验证记录形成树，其根是值ℎinit（引理S1）。

4.3 通讯框架

在LibraBFT中，通信框架构建了一个点对点的覆盖，用于在验证者之间可靠地传播协议记录（第4.1节）。框架API由两个原语动作组成：（i）发送，节点用它拥有的记录更新一个节点; （ii）广播，节点向所有同伴传播更新。

为了向诚实的节点提供可靠的传输保证，LibraBFT在点对点同步协议之上构建了gossip覆盖。简而言之，对于某个固定值𝐾（0 <𝐾≤𝑁），希望广播的节点将其数据发送到至少𝐾个节点的随机子集。接收节点以相同的方式转发相关数据。

在网络操作期间发送和转发的“相关”数据的确切性质是LibraBFT协议描述的一部分（第7.11节）。在第一次阅读中，可以简单地认为，节点在每次更新其记录存储时都会转发它所知道的每个有效记录。

从以下意义上说，转发数据对于广播行为的可靠[24]非常重要：如果诚实节点接收（相关）数据，那么 - 很可能 - 其他所有诚实节点将在不久之后知道这些数据。重要的是，即使数据的来源是恶意节点，这也成立。

随机八卦（gossip）提供以下广播保证：

概率-可靠-广播: 在GST之后，如果一个诚实的节点接收或拥有需要闲聊的数据，那么-在很高的概率-在（未知）时间延迟δ𝐺> 0之前，每个其他诚实节点都将接收到这些数据。

我们从广义上解释了这一要求，允许在此过程中更新数据。我们还允许几个发送人在一段时间[𝑡1; 𝑡2]内并行启动相同数据的闲聊，并假设所有诚实节点在时间𝑡2+δ𝐺时都会收到数据。

选择扇出系数的注意事项 作为网络延迟和可扩展性之间的权衡，扇出因子𝐾的选择通常远小于节点数。我们将如何选择一个𝐾值的工作留给以后，以便单个消息在GST之后遵循经典假设（最终同步网络）。现在，我们可以简单地选择𝐾=𝑁（节点数），并让δ𝐺=δ𝑀。

4.4 数据同步

由于转发和崩溃的可能性，一种天真的方法，即发送者将他们的记录直接推送到接收者，将导致多次接收和重传相同的数据。一般而言，我们希望让发件人启动通信，但是让接收者更多地控制他们如何使用数据。在LibraBFT中，通过引入称为数据同步的交换协议来解决这个问题。

从一个发送方向其他节点发送数据的过程分为多个步骤：

使新数据可用（即，被动地发布）作为发送者的数据同步服务的一部分。
根据通信的性质向每个接收者发送一个称为DataSyncNotification消息的通知：用于点对点通信的单个接收者，否则为随机子集。
让接收方使用DataSyncRequest消息连接回发送方，并纠正DataSyncResponse消息中包含的数据。

交换完成后，接收方应立即验证收到的数据，然后将所有有效和相关的数据作为服务器提供。如前所述，新数据可能需要通知其他多个节点才能完成可靠的广播。

4.5 运行环境

为了指定和模拟LibraBFT，我们抽象出有关流程，网络，定时器以及通常在通用术语运行时环境下的节点操作系统的详细信息。我们将LibraBFT节点的行为指定为私有本地状态和少量称为处理程序的算法的组合。处理程序通常会改变当前节点的本地状态并返回一个值。规范将要求运行时环境在特定时间调用处理程序并立即解释返回的值。

4.6 数据同步处理程序

我们现在指定数据同步的处理程序。我们要求运行时环境将第4.4节中描述的消息（即DataSyncNotification，DataSyncRequest和DataSyncResponse）传送到经过身份验证的预期接收者通道中，速度取决于当前的网络条件。我们创建了三个相应的处理程序，以便在收到消息时调用并返回可能的答案。当节点的主处理程序（第5.6节）请求环境向特定发件人发送通知时，将使用附加处理程序create_notification。

Rust接口： 我们将数据同步处理程序用Rust表示，如下所示：

trait DataSyncNode {
    /// Sender role: what to send to initiate a data-synchronization exchange.
    /// We only include our current vote when notifying a proposer.
    fn create_notification(&self, include_vote: bool) -> DataSyncNotification;
    /// Sender role: handle a request from a receiver.
    fn handle_request(&mut self, request: DataSyncRequest) -> DataSyncResponse;
    /// Receiver role: accept or refuse a notification from an authenticated sender.
    fn handle_notification(
        &mut self,
        authenticated_sender: Author,
        notification: DataSyncNotification,
        smr_context: &mut SMRContext,
    ) -> Option<DataSyncRequest>;
    /// Receiver role: receive data from an authenticated sender.
    fn handle_response(
        &mut self,
        authenticated_sender: Author,
        response: DataSyncResponse,
        smr_context: &mut SMRContext,
    );
}

数据同步处理程序连续查询和更新节点的记录存储，独立于协议的主处理程序，将在第5节中介绍。这三种消息类型的可能定义见附录A.3。

4.7 数学符号表示

我们已经看到，验证失败的记录将被接收节点拒绝。除非另有说明，否则从现在开始考虑的所有记录都是经过验证。

我们使用字母α来表示协议的节点。我们在给定时间为α的记录存储记为record_store（α）。我们使用符号$ \parallel $ 表示位串的连接。

我们在记录中引入以下符号：

我们用字母𝐵表示区块值; 𝐶表示法定证书; 𝑉投票; 𝑇超时; 最后，𝑅表示区块或证书。
我们使用ℎ，ℎ1等来表示QuorumCertificateHash或BlockHash类型的哈希值。我们使用字母𝑛，𝑛1等表示轮次。
我们将一个块的字段轮次写为round（𝐵），对于记录𝑅的任何字段foo，记为foo（𝑅）。
如果ℎ=certified_block_hash（𝐶），我们记为ℎ←𝐶。同样，在单票𝑉的情况下，我们写ℎ←𝑉。如果ℎ=previous_quorum_certificate_hash（𝐵），我们写为 ℎ←𝐵。
更一般地说，我们将 ← 视为哈希，块，投票和法定证书之间的关系。我们可以用 𝐵←𝐶 代替 hash(𝐵)←𝐶，𝐵←𝑉 代替 hash(𝐵)←𝑉 和 𝐶←𝐵 代替 hash(𝐶)←𝐵。
最后，我们用 ←* 表示 ← 的传递和反身闭合，即：𝑅0←*𝑅𝑛 当且仅当 𝑅0←𝑅1…←𝑅𝑛，𝑛≥0。

5 LibraBFT协议

5.1 协议概述

每个共识节点α维护当前时代的本地记录树，先前记录为record_store（α）。树的初始根，QC哈希ℎinit，作为共识时代设置的一部分达成一致。树中的每个分支都是一系列记录，在块𝐵𝑖和法定认证𝐶𝑖之间交替。形式上，如链表示：ℎinit←𝐵1←𝐶1…←𝐵𝑛[←𝐶𝑛]。

当节点充当领导者时（图3），它必须提出一个新的事务块𝐵𝑛+ 1，通常扩展（一个）其最长分支（1）的尾部法定认证𝐶𝑛。假设提议𝐵𝑛+1成功广播，诚实节点将验证数据，执行新块，并向领导发回投票（2）。在没有执行错误的情况下，诚实节点应该在𝐵𝑛+1之后就执行状态达成一致。在收到足够的同意该执行状态的投票后，提议者将为该块创建一个法定人数证书𝐶𝑛+1并广播它（3）。链长现在增加了一个：ℎinit←←1←𝐶1…←𝐵𝑛+ 1←𝐶𝑛+ 1。此时，领导者被认为已经完成，并且另一位领导者应该使用新提案扩展该树。

由于网络延迟和恶意节点，诚实的节点可能并不总是同意“最佳”分支以扩展和投票的块。在BFT假设（第2.3节）下，诚实节点观察到的投票约束保证当分支增长到足以包含满足提交规则的块𝐵时，𝐵及其前任不再受冲突提议的挑战。因此这些块被顺序提交以推进复制状态机。

为了保证恶意节点或反应迟钝的领导者的进度，每个提案都包含一个轮数。一轮将在一段时间后超时。当下一轮变得活跃时，预计会有一个新的领导者提出一个区块。起搏器抽象（第7.3节）旨在使诚实的节点在足够长的时间内就一个唯一，有效的轮次达成一致。

我们现在可以重新描述LibraBFT协议的主要目标如下：

安全性： 新提交总是扩展包含所有先前所有提交的链。
活性： 如果网络同步足够长的时间，最终会产生新的提交。

LibraBFT设计描述： 在本节的其余部分，我们精确地提出了提交规则（第5.3节）和投票约束（第5.4节和第5.5节）。然后，使用前面第4节中描述的通信框架，我们继续描述LibraBFT协议中的本地状态和节点行为（第5.6节和第5.7节）。

本节提供了第6节中给出的安全证明的先决条件。活性机制将在第7节中介绍，然后是第8节中的活性证明。

5.2 链

𝑘链是𝑘个块和𝑘个QC的序列：

1	`𝐵0 ← 𝐶0 ← … ← 𝐵𝑘−1 ← 𝐶𝑘−1`

𝐵0被称为这个链的头。 𝐶𝑘-1称为尾巴。

回想一下，根据区块轮次概念的定义，轮次必须沿着链严格增加：round（𝐵𝑖）<round（𝐵𝑖+ 1）。

当轮数精确增加1 - 即round（𝐵𝑖）+ 1 =round（𝐵𝑖+ 1） - 我们说链条有连续的轮数。

实际上，由于许多原因，链的轮数可能不连续。例如，不诚实的领导者可能会提出无效的区块，或者由于网络问题，领导者可能无法及时收集法定数量的选票。如果未在一轮中产生法定人数证书，则较高轮次的领导者最终将提出一个破坏链中邻接的块。

5.3 提交规则

一个块𝐵0被认为与节点的记录存储中的HotStuff的提交规则匹配，当且仅当它是具有连续轮次的3链的头部，即存在𝐶0，𝐵1，𝐶1，𝐵2，𝐶2，如下:

𝐵0 ← 𝐶0 ← 𝐵1 ← 𝐶1 ← 𝐵2 ← 𝐶2 并且 round(𝐵2) = round(𝐵1) + 1 = round(𝐵0) + 2

当节点α观察到这样的提交规则时，α的记录存储器中的𝐵0和𝐵0之前的块将变为提交。

根据我们之前关于承诺的讨论（第4.1节），位于𝐶2位置的有效法定认证充当提交证书：它必须包含非空字段值承诺（commitment），以验证在当前时代中已执行执行状态（𝐶0）。请注意，如果承诺为空，则𝐶2不是有效记录，应忽略它（第4.2节）。

5.4 第一次投票限制：增加轮次

提交规则的安全性依赖于两个投票约束。第一个涉及投票块的轮次：

增加轮次：如果round(𝐵)<round(𝐵')，过去曾经投票给𝐵的诚实节点可能只投票给𝐵'。

此投票约束对法定认证很重要（请参阅第6节）。在实践中，一个节点α将在标记为latest_voted_round（α）的局部变量中跟踪其最新投票的轮次，并且如果round（𝐵）> latest_voted_round（α）则仅投票给块𝐵。

5.5 第二个投票限制：锁定轮次

锁定的节点α的轮次，写为locked_round（α），是节点α所知的2-chain的头部的最高轮次，如果有的话，否则为零。实际上，我们可以初始化locked_round（α）的值为0，每当一个新的 2-chain 𝐵0 ← 𝐶0 ← 𝐵1 ← 𝐶1 中round（𝐵0）> locked_round（α）时，则record_store（α）更新为round（𝐵0）。

我们还定义了前一轮的块𝐵如下：如果存在𝐵’和𝐶’使得𝐵’←𝐶’←𝐵，我们让previous_round（𝐵）= round（𝐵’）; 否则，previous_round（𝐵）= 0。

我们现在可以制定第二个投票约束：

锁定轮次：如果诚实节点α当前持有previous_round（𝐵）≥locked_round（α）,则它只能投票给块𝐵。

5.6 共识节点的本地状态和主处理程序API

我们现在可以根据本地状态和运行时环境调用的处理程序来描述LibraBFT节点所遵循的协议（第4.5节）。

本地状态： 如前所述，节点α的状态的核心组件由当前记录存储（第4.2节）组成 - 写为record_store（α） - 其中包含α知道的其当前时代的所有已验证记录。

节点状态还包括与领导者选举相关的许多变量。我们将它们分组为一个称为起搏器的特殊对象，并在7.3节中对它们进行描述。

协议实例所需的其他状态变量包括：

当前时代标识符epoch_id（α），用于检测当前时代的结束;
作为记录作者的α的标识符，写成local_author（α）;
最新投票块的轮次latest_voted_round（α），（初始值：0）;
锁定轮次locked_round(𝛼), (初始值：0);
与我们同步的最新节点的标识和活动轮次，表示为latest_senders（初始值：空列表）;
最后一次广播的系统时间latest_broadcast（α），（初始值：时代的开始时间）。

节点的状态还包括一个称为数据跟踪器的对象，负责跟踪主处理程序已经处理的数据，特别是提交，并决定是否需要转发新数据。我们在第7.11节中提供了有关数据跟踪器的更多详细信息。

最后，节点的状态包括所有先前时代的记录存储。那些时代现在已经停止，这意味着不能插入新的记录。

主处理程序API： 在LibraBFT中，共识节点的主处理程序由单个算法update_node组成，必须由运行时环境在三种情况下调用：

无论何时节点在启动或崩溃后重新启动;
每当数据同步交换完成时（第4.6节）;
定期，在给定时间由处理器本身的最后一次运行调度。

主处理程序通过返回运行时环境要携带的操作项列表来响应记录存储或时钟中观察到的更改。特别：

主处理程序可能要求在将来的给定时间调度对update_node的新调用;
它可以指定应该将数据通知发送给特定的领导者;
它可能会要求广播数据通知。

主处理程序的实现是LibraBFT协议的核心。它在5.7节中有详细描述。

Rust定义 在Rust中，节点的本地状态编写如下：

struct NodeState {
    /// Module dedicated to storing records for the current epoch.
    record_store: RecordStoreState,
    /// Module dedicated to leader election.
    pacemaker: PacemakerState,
    /// Current epoch.
    epoch_id: EpochId,
    /// Identity of this node.
    local_author: Author,
    /// Highest round voted so far.
    latest_voted_round: Round,
    /// Current locked round.
    locked_round: Round,
    /// Time of latest broadcast.
    latest_broadcast: NodeTime,
    /// Names and rounds of the latest senders during network communication.
    latest_senders: Vec<(Author, Round)>,
    /// Track data to which the main handler has already reacted.
    tracker: DataTracker,
    /// Record stores from previous epochs.
    past_record_stores: HashMap<EpochId, RecordStoreState>,
}

主处理程序API，update_node，写成：

trait ConsensusNode {
    fn update_node(&mut self, clock: NodeTime, smr_context: &mut SMRContext) -> NodeUpdateActions;
}

此定义假定运行时环境提供以下输入：

当前节点状态（当前用Rust）;
当前系统时间（clock）
SMR操作的上下文，例如命令执行（smr_context）

回想一下，ConsensusNode除了涉及DataSyncNode（第4.6节）之外还提供了数据同步的处理程序。 SMRContext在附录A.1中精确定义。

函数update_node返回的操作项保存在以下数据结构中：

struct NodeUpdateActions {
    /// Time at which to call `update_node` again, at the latest.
    should_schedule_update: Option<NodeTime>,
    /// Whether we need to send a notification to a leader.
    should_notify_leader: Option<Author>,
    /// Whether we need to send notifications to a random subset of nodes.
    should_broadcast: bool,
}

5.7 主处理程序实现

我们现在用Rust描述LibraBFT节点的主处理程序的实现，具体实现如下：

impl ConsensusNode for NodeState {
    fn update_node(&mut self, clock: NodeTime, smr_context: &mut SMRContext) -> NodeUpdateActions {
    // Update pacemaker state and process pacemaker actions (e.g., creating a timeout, proposing a block).
    let latest_senders = self.read_and_reset_latest_senders();
    let pacemaker_actions = self.pacemaker.update_pacemaker(
        self.local_author,
        &self.record_store,
        self.latest_broadcast,
        latest_senders,
        clock,
    );
    let mut actions = self.process_pacemaker_actions(pacemaker_actions, smr_context);
    // Update locked round.
    self.locked_round = std::cmp::max(self.locked_round, self.record_store.highest_2chain_head_round());
    // Vote on a valid proposal block designated by the pacemaker, if any.
    if let Some((block_hash, block_round, proposer)) = self.record_store.proposed_block(&self.pacemaker) {
        // Enforce voting constraints.
        if block_round > self.latest_voted_round
        && self.record_store.previous_round(block_hash) >= self.locked_round
        {
            // Update latest voted round.
            self.latest_voted_round = block_round;
            // Try to execute the command contained the a block and create a vote.
            if self.record_store.create_vote(self.local_author, block_hash, smr_context) {
                // Ask that we reshare the proposal.
                actions.should_broadcast = true;
                // Ask to notify and send our vote to the author of the block.
                actions.should_notify_leader = Some(proposer);
            }
        }
    }
    // Check if our last proposal has reached a quorum of votes and create a QC.
    if self.record_store.check_for_new_quorum_certificate(self.local_author, smr_context) {
        // The new QC may cause a change in the pacemaker state: schedule a new run of this handler now.
        actions.should_schedule_update = Some(clock);
    }
    // Check for new commits and verify if we should start a new epoch.
    for commit_qc in self
        .record_store
        .chain_between_quorum_certificates(
            self.tracker.highest_committed_round,
            self.record_store.highest_committed_round(),
        )
        .cloned()
    {
        // Deliver the new committed state, together with a short certificate (if any).
        smr_context.commit(&commit_qc.state, self.record_store.commit_certificate(&commit_qc));
        // If the current epoch ended..
        let epoch_id = smr_context.read_epoch_id(&commit_qc.state);
        if self.epoch_id != epoch_id {
            // .. create a new record store and switch to the new epoch.
            self.start_new_epoch(epoch_id, commit_qc, smr_context);
            // .. stop delivering commits after an epoch change.
            break;
        }
    }
    // Update the data tracker and ask that we reshare data if needed.
    if self.tracker.update_and_decide_resharing(self.epoch_id, &self.record_store) {
        actions.should_broadcast = true;
    }
    // Return desired node actions to environment.
    actions
    }
}

在高级别，该算法实现以下操作：

运行起搏器模块并执行请求的起搏器操作，例如创建超时或提议区块。
执行并投票选出有效的提议区块，如果有的话，同时遵守有关最新投票轮次（第5.4节）和锁定轮次（第5.5节）的两个投票限制。
如果节点提出了一个区块，并且收到了同一状态的法定数量的投票，则创建一个法定认证。
检查记录存储中新发行的提交，并将它们传递到状态机复制上下文。
检查将终止的当前时代的提交，并在需要时启动新时代。
确定节点是否应该转发（即八卦gossip）其数据。

该算法依赖于节点的记录存储来计算已知双链（2-chain）的最高头的轮次（highest_2chain_head_round），最高提交规则的头部（highest_committed_round），以及提交规则的尾部QC（commit_certificate）。

方法chain_between_quorum_certificates采用两轮𝑚和𝑛（𝑚≤𝑛）作为输入。如果记录存储包含round(𝐵0) = 𝑚 和 round(𝐵𝑘) = 𝑛的链 𝐵0 ← 𝐶0 ← 𝐵1 ← 𝐶1 ← … ← 𝐵𝑘 ← 𝐶𝑘 ，那么它将返回一个顺序QCs 𝐶1, … , 𝐶𝑘的迭代器（有关详细接口，请参阅附录A.2）。

主处理程序还使用与活性相关的其他接口，并在后面的部分中进行了描述：

起搏器Pacemaker提供了一个函数update_pacemaker来控制领导者选举，超时和提议;返回的操作项由process_ pacemaker_actions方法处理; 并且RecordStore的propoed_block方法也使用起搏器来选择一个节点可以投票的有效提议（如果有的话）（第7.3节）。
DataTracker对象提供了迄今为止处理的最新提交，以及方法update_and_decide_resharing以更新最新提交值（以及其他）和控制八卦gossiping（第7.11节）。

时代变更： 一旦节点提交结束当前时代的提交QC，它就会停止该时代的提交，存档其当前记录存储，并为新时代创建一个记录存储。节点必须保留前一个时期的记录存储以确保活性：在数据同步期间，节点必须能够追随提交链并执行命令，直到任何发送方的最新时代的最新提交规则（另请参见第3.1节和第7.11节）。

链上包含时代变化的块与触发提交规则的块之间的提交可以任意长，这取决于网络条件。为了避免持久化未提交的数据，我们可能要求提议者在分支上检测到时期更改后仅提出空命令。

6 安全证明

在安全证明中，我们考虑当前时代中诚实节点所见到的所有记录的集合，并证明提交的块必须形成一个线性链ℎinit ← 𝐵1 ← 𝐶1 ← 𝐵2 … ← 𝐵𝑛，始于初始QC哈希为ℎinit的时代。

6.1 预备知识

我们首先回顾一下经典BFT引理的证明：

引理B1： 在BFT假设下，对于同一时代中两个法定集合的每个节点，存在一个诚实节点同时属于两个法定集合。

证明： 设$ 𝑀_𝑖≥𝑁-𝑓（𝑖= 1,2）$是每个法定集合的综合投票权。每个法定集合的投票权$ 𝑀’_𝑖 $，不包括拜占庭节点，满足$ 𝑀’_𝑖 ≥ 𝑀_𝑖-𝑓 ≥ 𝑁-2𝑓。我们注意到，如果两组不相交，总的投票权$ 𝑀’_1 + 𝑀’_2 ≥ 2𝑁-4𝑓 > 𝑁-𝑓 $ 将超过所有诚实节点的投票权。因此，在两个法定人数中都存在诚实的节点。

接下来，我们证明了两个新的引理。第一个涉及记录的链接。

引理S1： 对于任何记录𝑅，𝑅0，𝑅1，𝑅2：

$ ℎ_init ←∗ 𝑅 $
如果𝑅0←𝑅2且𝑅1←𝑅2，则𝑅0=𝑅1;
如果𝑅0←𝑅2，𝑅1←𝑅2并且round（𝑅0）<round（𝑅1）, 则𝑅0←*𝑅1

证明：

根据经验证的记录定义（第4.2节）
根据链的定义，假设哈希是完全抗冲突的
使用前一项和轮数不能在链中减少的事实，通过归纳推导得出𝑅1←*𝑅2。

第二个引理涉及第一个投票规则和法定认证的概念。

引理S2： 考虑两个带有QC的块：𝐵←𝐶和𝐵’←𝐶’。在BFT假设下，如果round（𝐵）= round（𝐵’），则𝐵=𝐵’和state（𝐶）= state（𝐶’）。

特别是，对于每个𝑘>0，存在一个唯一的块，其在节点已知的𝑘链的头部中具有最高的轮次。

证明： 在BFT假设下，必须存在一个诚实的节点，该节点同时为获胜提议𝐶中的state（𝐶）和𝐶’中的state（𝐶’）进行投票。通过投票规则（增加轮次），我们必须有𝐵=𝐵’和state（𝐶）= state（𝐶’）。

6.2 主要安全论据

我们说两个（不同的）记录𝑅，𝑅’是冲突的，当既不能𝑅←𝑅’也不能𝑅’←𝑅时。

引理S3： 假设一个3链（3-chain）从round 𝑛0开始到round 𝑛2结束。对于每个认证区块𝐵←𝐶，round（𝐵）>𝑛2，在BFT假设下，我们有previous_round（𝐵）≥𝑛0。

证明： 让𝐵0←𝐶0←𝐵1←𝐶1←𝐵2←𝐶2是round(𝐵0)=𝑛0开始到round(𝐵2)=𝑛2结束的3链(3-chain)。

在BFT假设下，存在一个诚实的节点α，其投票包括在𝐶2（投票给𝐵2）和𝐶（投票给𝐵）中。由于round（𝐵）>𝑛2，根据投票规则（增加轮次），α必须首先投票给𝐵2。那时，α已经看到了以𝐵0开始的2链(2-chain)。由于锁定轮次永不减少，其锁定轮次至少为round（𝐵0）=𝑛0。在给𝐵的投票后，节点α锁定的轮次至少为𝑛0。因此，投票规则（锁定轮次）意味着previous_round（𝐵）≥𝑛0。

命题S4： 假设一个3链，其连续轮次以round 𝑛0处的块𝐵0开始。对于每个认证区块𝐵←𝐶，round（𝐵）≥𝑛0，在BFT假设下，我们有𝐵0←*𝐵。

证明： 通过归纳 round（𝐵）≥𝑛0。设𝐵0←𝐶0←𝐵1←𝐶1←𝐵2←𝐶2是一个以𝐵0开头且连续轮数的3链：round（𝐵0）+2 =round（𝐵1）+ 1 =round（𝐵2）=𝑛0+ 2。

如果round（𝐵）≤𝑛0+ 2，则round（𝐵）是值𝑛0，𝑛0+ 1，𝑛0+ 2之一。通过引理S2，𝐵是值𝐵0，𝐵1，𝐵2之一; 因此，𝐵0←*𝐵。

否则，假设为round（𝐵）>𝑛0+ 2，即round（𝐵）> round（𝐵2）。通过引理S3，我们有previous_round（𝐵）≥𝑛0。由于𝑛0= round（𝐵0）> 0，这意味着存在链𝐵3←𝐶3←𝐵，使得round（𝐵3）≥𝑛0。由于round（𝐵3）≥𝑛0和round（𝐵3）<round（𝐵），我们可以在𝐵3上应用归纳假设来推导出𝐵0←𝐵3。因此，𝐵0←𝐵3←*𝐵结束证明。

定理S5（安全性）： 在BFT假设下，与提交规则匹配的两个块不能冲突。

证明： 考虑与提交规则匹配的两个块𝐵0和$ 𝐵’_0 $的提交规则：$ 𝐵0 ←𝐶0 ← 𝐵1 ← 𝐶1 ← 𝐵2 ← 𝐶2 $ 和 $ 𝐵′_0 ← 𝐶′_0 ← 𝐵′_1 ← 𝐶′_1 ← 𝐵′_2 ← 𝐶′_2 $ (两种情况下都有连续轮次）。不失一般性的，我们可以假设$ round（𝐵’_0）≥round（𝐵0）$。通过命题S4，这意味着$ 𝐵0←*𝐵’_0 $。

推论S6: 在BFT假设下，自当前时期开始以来任何诚实节点看到的所有提交的集合形成一个线性链𝐵init←𝐵1←𝐶1←𝐵2…←𝐵𝑛。

证明： 使用定理S5，通过归纳提交数量。

7 LibraBFT的活性机制

LibraBFT遵循HotStuff [5]的例子，并将领导者选举委托给一个名为起搏器的特殊模块。我们现在详细描述LibraBFT的起搏器，以及转发数据和清理记录库的策略。这些机制对于活性都至关重要，我们将在第8节的证明中看到。

7.1 超时证书

我们将超时证书（TC）定义为在同一轮次n的一组超时对象，超时提议的总的投票数超过f。超时证书的轮次是轮次值𝑛。

7.2 起搏器概述

给定最新提交的块𝐵𝑐←𝐶𝑐及其QC,我们为每个轮次n>round(𝐵𝑐)指定一个领导者和一个最长持续时间。一旦共识节点在轮次𝑛-1收到QC，或者在轮次n-1有足够的超时形成TC时（以先到者为准），它就进入一轮次n。然后轮次𝑛被认为是活动的，直到节点进入轮次𝑛+ 1.当一个节点有一个活动轮次𝑛时，它可能只投票给轮次n的leader提交的轮次𝑛的区块。

为了在恶意或无响应的领导者的情况下实现活跃，节点在进入一个轮次时启动计时器并验证经过的时间尚未超过轮次的当前最大持续时间。新的超时对象立即被闲聊（gossiped）。一旦转发了足够的超时，节点将观察TC并更改其活动轮次，除非节点首先学习QC，这依然也会更新活动轮次。如果最新提交的块在轮次活动期间更改，则将更新活动轮次的最大持续时间。

重要的是，当节点进入使其成为领导者的轮次时，在提议一个区块前，它必须等待法定数量的节点的确认，以便他们也进入该轮次。这很重要，这样所提议的块就可以证明满足由法定数量的诚实节点计算的第二个投票约束（第8.3节）。

最后，在异步期间，一些节点可能不知道最新的已提交块。为了在GST之后从这种情况中恢复，我们确保节点在每个周期时间 𝐼>0 时至少广播一次其状态。

7.3 起搏器状态和更新API

我们以与节点本身相同的方式（第5.6节）在较高层次描述起搏器模块的本地状态和更新API.

可见起搏器状态: 起搏器模块负责推动领导者选举。因此，它将两个重要的状态值暴露给LibraBFT节点的其他组件：

当前活动轮次，表示为active_round（α），（初始值：0）;
当前轮次的领导者，写入active_leader（α），（初始值：⊥）。

这两个值主要由记录存储的proposal _block函数访问，该函数在主处理程序update_node（第5.7节）中被较早使用。具体来说，这个函数确保我们可以投票的块满足round（𝐵）= active_round（α）和author（𝐵）= active_leader（α）。

其余的起搏器状态将在第7.9节中描述。

起搏器更新API 我们期望起搏器模块提供方法update_pacemaker，意味着由更高级别的方法update_node调用。此方法应在输入参数的函数中刷新起搏器的状态，并返回要处理的节点的主处理程序的操作项列表。

update_pacemaker返回的操作项类似于update_node返回的操作项，并使用两个内部操作项进行扩充：

起搏器可以指示节点为给定轮次创建超时对象。
起搏器可能要求节点充当领导者并提出新的块。

起搏器模块的Rust描述如下：

trait Pacemaker {
    /// Update our state from the given data and return some action items.
    fn update_pacemaker(
        &mut self,
        // Identity of this node
        local_author: Author,
        // Tree of records
        record_store: &RecordStore,
        // Local time of the latest broadcast by us
        latest_broadcast: NodeTime,
        // Known active rounds of recent senders
        latest_senders: Vec<(Author, Round)>,
        // Current local time
        clock: NodeTime,
    ) -> PacemakerUpdateActions;
    /// Current active round and current leader.
    fn active_round(&self) -> Round;
    fn active_leader(&self) -> Option<Author>;
}

传递给update_pacemaker的参数先前在主处理程序update_node（表2）中进行了描述。

update_pacemaker返回的起搏器操作项可以描述如下：

struct PacemakerUpdateActions {
    /// Time at which to call `update_pacemaker` again, at the latest.
    should_schedule_update: Option<NodeTime>,
    /// Whether we should create a timeout object for the given round.
    should_create_timeout: Option<Round>,
    /// Whether we need to send our records to the given next leader.
    should_notify_leader: Option<Author>,
    /// Whether we need to broadcast our records.
    23
    should_broadcast: bool,
    /// Whether to propose a block and on top of which QC hash.
    should_propose_block: Option<QuorumCertificateHash>,
}

这些操作项由update_node解释执行并转换为节点操作项，如下所示：

impl NodeState {
    fn process_pacemaker_actions(
        &mut self,
        pacemaker_actions: PacemakerUpdateActions,
        smr_context: &mut SMRContext,
    ) -> NodeUpdateActions {
        let mut actions = NodeUpdateActions::new();
        actions.should_schedule_update = pacemaker_actions.should_schedule_update;
        actions.should_broadcast = pacemaker_actions.should_broadcast;
        actions.should_notify_leader = pacemaker_actions.should_notify_leader;
        if let Some(round) = pacemaker_actions.should_create_timeout {
            self.record_store.create_timeout(self.local_author, round, smr_context);
        }
        if let Some(previous_qc_hash) = pacemaker_actions.should_propose_block {
            self.record_store.propose_block(
                self.local_author,
                previous_qc_hash,
                self.latest_broadcast,
                smr_context,
            );
        }
        actions
    }
}

7.4 法定认证的等效性

要严格定义领导者和最长持续时间，包括在一个时代的开始，我们必须采取一些预防措施，并介绍QC等效的概念。

两个QC哈希值ℎ和ℎ’被认为是等价的，即ℎ≈ℎ’，当且仅当满足以下两个条件中的一个时：

ℎ = ℎ′
存在两个法定人数证书𝐶、𝐶’和一个块𝐵，使得ℎ=hash（𝐶），ℎ’=hash（𝐶’），𝐵←𝐶，𝐵←𝐶’和state（𝐶）=state（𝐶’）。

第一个条件仅适用于初始哈希值。在第二种情况下，我们说法定认证𝐶和𝐶’是等价的，写成𝐶≈𝐶’。

这个定义背后的原因是可能已知一个块具有有效的QC，例如，𝐵0←𝐶0，但是共识节点可能暂时不同意𝐶0。实际上，虽然我们要求𝐶0由𝐵0的作者签名，但不诚实的提议者可以以不同的方式选择和汇总投票，并广播几种𝐶0的变体。我们已经看到，在BFT假设下，所有变体必须在上面定义的意义上是等价的（引理S2）。

注释：在下面，我们将ℎ𝑐表示最新提交块的QC的哈希值，如果有的话; 否则，该时代的初始哈希。我们将要求领导者和最长持续时间的公式取决于ℎ𝑐直到等效 - 他们可能取决于状态和已提交的区块，而不是投票者。

当我们使用ℎ𝑐作为函数的输入时，我们将依赖于每个节点本地可用的记录存储这一事实，并且可以将最新的提交哈希值解析为实际数据。

7.5 先决条件：将领导者分配给轮次

给定一个合适的记录存储，一个QC哈希ℎ𝑐和一个轮次𝑛，我们假设一个算法leader（ℎ𝑐，𝑛）以公平的方式返回作者，这意味着所有𝑘（𝑘> 0）作者的顺序时相同频次的。如上所述（第7.4节），我们还要求ℎ𝑐≈ℎ’𝑐表示领导者（ℎ𝑐，𝑛）=领导者（ℎ’𝑐，𝑛）。

假设投票权相等，最简单的方法是让leader（ℎ𝑐，𝑛）=author（hash（𝑛）mod𝑁），其中𝑁是节点数。但是，这可以让任何人提前很长时间预测领导者。这是有问题的，因为它有助于准备针对领导者的针对性攻击。

我们还注意到，由于磨削攻击，以天真的方式取决于ℎ𝑐是不可能的 - 轮次n的领导者可以尝试选择交易或投票，一旦𝑛= round（ℎ𝑐），leader（ℎ𝑐，𝑛’）（𝑛’>𝑛+ 2）便指向特定节点。

为了降低这两种风险，我们打算在将来使用可验证的随机函数（VRF）[39]。如果QC散列下的认证块ℎ𝑐包含一些种子𝑠= VRFauthor（ℎ𝑐）（epoch_id

round（ℎ𝑐）），那么我们可以定义leader（ℎ𝑐，𝑛）=author（PRF𝑠（𝑛）mod𝑁） PRF代表伪随机函数的实现。