LibraBFT 共识算法介绍

1 概述

Libra 的共识机制采用的是 LibraBFT 共识，是一个为 Libra 设计的健壮、高效的状态复制系统。它基于一种新型的 BFT 共识算法，HotStuff(BFT Consensus in Lens of Blockchain)，在扩展性和一致性上达到了较高的水平。LibraBFT 在 HotStuff 的基础上引入显示活跃度的机制并提供了具体的延时分析。

LibraBFT 在 3f+1 个验证节点之间收集投票，这些验证者可能是诚实的节点也可能是拜占庭节点。在网络中有 2f+1 个诚实节点的前提下， Libra 能够抵御 f 个验证节点的双花攻击和分叉攻击。

LibraBFT 在一个有全局统一时间（GST），并且网络最大延时（ΔT）可控的 Partial Synchrony 的网络中是有效的。并且， LibraBFT 在所有验证节点都重启的情况下，也能够保证网络的一致性。

为了能够更好地理解 LibraBFT，我们回顾一下 PBFT 和 HotStuff 共识协议。

2 PBFT

原始的拜占庭容错系统由于需要展示其理论上的可行性而缺乏实用性，另外需要额外的时钟同步机制支持，算法的复杂度也是随节点增加而指数级增加。Castro and Liskov 在 1999 年提出实用拜占庭容错系统（Practical Byzantine Fault Tolerance，PBFT），降低了拜占庭协议的运行复杂度，从指数级别降低到多项式级别（Polynomial），使拜占庭协议在分布式系统中应用成为可能。

PBFT 是一类状态机拜占庭系统，要求整个系统共同维护一个状态，所有节点采取的行动一致。为此，需要运行三类基本协议，包括一致性协议、检查点协议和视图更换协议。视图转换协议保证共识协议的活性（liveness）。当主节点出故障时能保证共识能继续进行。PBFT 的视图转换协议是非常复杂的，涉及到很多消息的重传。HotStuff 的最重要的改进，主要是针对视图更换的协议。

3 HotStuff

HotStuff 的基本假设是系统有固定的节点数 n = 3f+1，其中 f 是系统能容忍的最大拜占庭节点数。系统通信是点对点的认证和可靠通信。网络通信的假设是半同步，也就是说，网络有一个知道的延迟 D，以及一个不知道的全网稳定时间（Global Stabilization Time，简称 GST），当 GST 过后，任意两个节点之间的通信都将在 D 时间内完成。HotStuff 能总保证正确性（safety），在 GST 后的消息时延在一定限度（D）内能保证活性 （liveness）。

HotStuff 采用门限签名机制，门限设置是（k, n）。n 个节点中所有的节点共用一个公钥，但每一个节点有自己的私钥。每个节点用自己的私钥签名消息 m，叫部分签名消息，多个节点的部分签名消息可以用来生成一个联合签名消息，当至少有 k = 2f+1 个节点提供部 分签名消息时，其它任何一个节点能用公钥验证该联合签名消息。其中 f 是系统能容忍的拜 占庭节点总数，n = 3f+1。

HotStuff 论文中提出一个“认证复杂度”的概念。认证复杂度简单来说，统计协议交 互时通信的认证消息数，也就是部分签名或联合签名消息的个数。

HotStuff 两个重要的优点

一个是 linearity，指的是通信的复杂程度和节点数成线性关系；

另一个是 responsiveness，指的是当网络通信成为同步的时候，HotStuff 能产生 正确的 Leader 来推动协议在网络延迟的实际值内而非最大值达到共识。

HotStuff 在原先诸多的 BFT 共识协议中提升了效率，降低了复杂度。基于这些特性， HotStuff 适合于构建大规模的状态复制服务。因此，不难看出，Libra 从众多的区块链共识算法中挑选 HotStuff，看中的是 HotStuff 的效率、线性的扩展性，以及拜占庭容错的安全性。

这也体现了 Libra 的平衡术 – 在去中心、安全、扩展性这个棘手的区块链三难问题上， 巧妙的选择一个平衡点。

4 LibraBFT

严格说来，LibraBFT 是基于 HotStuff 的一个变种，叫链式HotStuff（Chained HotStuff）。链式 HotStuff 是在基本 HotStuff（Basic HotStuff）上引入流水线概念，进一步提升效率的一个改进共识协议。LibraBFT 最初会选择一些在不同地理上分布的创始成员做共识节点，以后逐渐的，共识节点会对外开放，并基于 libra 稳定币的多少来选择共识节点，也就是转变成 PoS 机制。

LibraBFT 的共识流程是分为不同轮次（rounds），每一轮中一个 Leader 主节点被选出。主节点会提议一个区块，里面包括多个交易。该区块将广播给其它共识节点。其它共识节点会验证区块里的交易，并对其投票。主节点收到大多数（超过 2f+1，f 是系统中能容忍的拜占庭节点数）节点的投票后，主节点把确认消息发给所有共识节点确认。如果主节点没收到大多数投票，或者主节点出现故障，副本共识节点的定时将超时，副本节点会发起新的一轮提议。

LibraBFT 在 HotStuff 基础上的改进主要在于提供一个详细的参与同步轮次的 Pacemaker 设计和实现。并提供对实际交易确认的活性分析。LibraBFT 提供对共识节点投票权力的重配置机制。同时它给出了对提议节点和投票节点激励的机制。白皮书给出了如何检测投票节点破坏正确性的行为，为今后在协议中加入惩罚机制打下基础。同时白皮书也详 细讨论如何做同步，使得投票节点能同步它们的状态。libraBFT 白皮书采用 Rust 语言来描 述协议。

在 LibraBFT 中，为了更好地支持 Libra 生态系统的目标，LibraBFT 以多种方式扩展和调整了核心 HotStuff 协议和实现。重要的是，LibraBFT 重新定义了安全条件，并提供了安全、存活度和更高响应度的扩展证明。LibraBFT 还实现了一些附加功能。

首先，通过让验证器对块的结果状态(而不仅仅是交易序列)进行集体签名，LibraBFT 使协议更能抵抗非确定性错误。还允许客户端使用法定人数证书来验证读取的数据库。

其次，LibraBFT 设计了一个发出明确超时的起搏器，验证器依靠法定人数来进入下一轮 - 不需要同步时钟。

第三， LibraBFT 打算设计一个不可预测的领导者选举机制，其中一轮的领导者由最新提交的块的 提议者使用可验证的随机函数 VRF 确定。这种机制限制了攻击者可以针对领导者发起有效拒绝服务攻击的时间窗口。

第四，LibraBFT 使用聚合签名来保留签署仲裁证书的验证者的身份。这使我们能够为有助于仲裁证书的验证人提供激励，聚合签名也不需要复杂的密钥阈值设置。