1.简介

Libra 是由FaceBook及其它合作伙伴发起的项目，其使命是建立一套简单的、无国界的货币和为数十亿人服务的金融基础设施。项目最重要的基础就是“Libra 区块链”，它具有如下特点：

设计和使用 Move 编程语言。
使用拜占庭容错 (BFT) 共识机制。
采用和迭代改善已广泛采用的区块链数据结构。

本文主要介绍Libra所使用的共识协议LibraBFT。

Libra 区块链采用了基于 LibraBFT 共识协议的 BFT 机制来实现所有验证者节点就将要执行的交易及其执行顺序达成一致。这种方法可以在网络中建立信任，因为即使某些验证者节点（最多三分之一的网络）被破坏或发生故障，BFT共识协议的设计也能够确保网络正常运行。与其他一些区块链中使用的“工作量证明”机制相比，这类共识协议还可实现高交易处理量、低延迟和更高能效的共识方法。

2.HotStuff

PBFT

系统根据机器编号顺序轮流选举出一个primary，primary初始化时发出View-new消息，同步所有节点的数据
Client发起请求转发给primary，primary验证通过后，广播这个请求，发起pre-prepare消息给所有的follower节点，并且自己也保存这个request
所有的follower收到pre-prepare消息后，第一步是进行校验，包括数据的顺序是否正确，操作的先后有序性，以及交易是否有效比如签名。（防止客户端造假或者primary节点篡改造假）
follower验证正确之后，写到自己的磁盘里，然后广播Prepare消息，并且自己也进入Prepare阶段
所有节点统计针对某个Request的Prepare消息，当统计结果超过2f节点时，表明大部分节点已经完成了持久化，则自己进入commit阶段
广播 commit 消息，并且统计收到的commit 消息的数量，当超过2f节点都发出commit的消息时
该节点完成commit阶段，写入数据（该操作已经完成2/3共识了），运用自己的状态机，更新 stable checkpoint，缓存该客户端最后一次的请求，并且反馈给客户端
当客户端统计反馈的节点超过f个时，表示交易已经被大部分节点确认了，交易成功。如果超时还不成功，则向所有的replica广播这个request

LibraBFT是基于HotStuff协议的，并在此基础上做了一些改进。为了理解LibraBFT的工作原理，这里首先将介绍HotStuff协议。

HotStuff 算法论文由康奈尔大学的Maofan Yin以及 VMWare 的研究团队发表，其安全性及可用性已经过完整的数学证明。

2.1 基础HotStuff验证过程

HotStuff的验证大致分为PREPARE、PRE-COMMIT、COMMIT、DECIDE四个阶段，如下图所示。

HotStuff流程图

Prepare阶段

新的主节点将从其它节点收集New-View消息开始。New-View消息由副本在转换viewNumber（包括第一个视图）时发送。
随后主节点将开始新视图并提出自己的状态迁移要求，发送 prepare 消息给其它节点。在从主节点接收到当前视图的prepare消息后，其它节点将会对消息进行投票。如果接受，则发送带有部分签名的prepare投票给主节点。

pre-commit 阶段：

在收到足够多(n - f 个)的prepare投票后，主节点将所有投票合并入一个prepareQC，向所有节点广播包含 prepareQC的pre-commit 消息，向其它节点表明足够多的节点确认了此次状态迁移的要求。其它节点在收到消息后将会对pre-commit 消息进行投票。

commit 阶段：

在收到足够多(n - f 个)的pre-commit 投票后，主节点将所有投票合并入一个precommitQC，向所有节点广播包含 precommitQC的commit 消息。其它节点将对 commit 消息进行投票。同时，收到 commit 消息的节点可以锁定当前状态迁移要求以便即使视图切换也可以顺利达成共识。

decide 阶段：

在收到足够多(n - f 个)的commit 投票后，主节点将所有投票合并入一个commitQC，向所有节点广播包含 commitQC 的decide消息。当某个节点收到 decide 消息后将执行状态迁移，增加viewNumber并开始新的视图。

2.2 门限签名

HotStuff中使用了门限签名（Threshold Signatures），这让PBFT中需要点对点传输消息的过程变为了由其它节点与主节点之间传输消息，把消息传送的时间复杂度由O(N^2)变为O(N)。
下面简单介绍门限签名。

对于一个 (k, n)-门限签名方案，有一个被所有签名者共有的公钥，而 n 个签名者每人都拥有自己的私钥（分片）。每个签名者都可以使用自己的私钥对消息做部分签名，只要其中至少 k 个签名者对消息进行部分签名，那么由这 k 个部分签名可以导出对消息的完整签名，并且这个完整签名可以由公钥来验签。在HotStuff中门限k=2f+1。
一般情况下，完整签名的大小和签名者的个数无关。HotStuff 用门限签名来减少共识协议中签名的个数。

HotStuff中每个阶段验证节点对于消息的投票过程就是使用自己的私钥对消息进行部分签名操作。当主节点接收到足够多的部分签名后，便可以导出一个完整的消息签名。所有的节点都可以使用共有公钥对完整签名进行验证，从而确定大多数验证节点同意此消息。

2.3 HotStuff的链式结构

2.3.1 数据结构

message

m.type ∈ {new-view, prepare, pre-commit, commit, decide}; message的类型

基础的HotStuff中一个主节点提交一个提案需要经过三个阶段。这三个阶段都只做了相同的工作，即主节点发送消息给其他节点，其他节点对消息投票，并将部分签名发送给主节点，主节点统计投票结果。这些过程由相似的数据结构和处理方法，因此可以采用流水化处理。如下图所示，是链式结构的流程图。

链式结构

HotStuff的链式结构会在每个PREPARE阶段进行改变视图操作，这样每个提案都拥有自己的视图。
图中视图v1,v2,v3分别处于cmd1提案的PREPARE阶段、PRE-COMMIT、COMMIT阶段，并会在v4的结束阶段提交。类似地，视图v2,v3,v4分别处于cmd2提案的PREPARE阶段、PRE-COMMIT、COMMIT阶段，并会在v5的结束阶段提交。利用这种链式结构，极大提高了系统的效率。

3.LibraBFT改进

Libra 为了更好地适应其生态，对HotStuff进行了相应的优化，主要有：

通过让验证节点共同对区块的状态而不是交易的顺序进行签名，这使得协议会更加鲁棒。同时还允许客户端使用QC验证从数据库里读出的数据。
设计了一个Pacemaker 来发出明确的超时信号，验证节点通过他发出的信号自动进入下一个视图，而不需要一个同步的时钟；
设计一个不可预测的主节点选举机制，新一轮的主节点将会由最新提交区块的提议者使用可验证随机函数VRF确定。该机制将有效限制对主节点进行拒绝服务攻击的可能性。
使用聚合签名的方式保留QC中验证节点的身份，以提高验签效率，同时为这些验证节点提供奖励。

LibraBFT简介