【Libra 技术解读】共识原理详解

发布时间:2019-06-25           作者:超哥


 

Libra技术系列解读

本期详解“LibraBFT共识机制”

 

Libra白皮书中关于共识机制的描述

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

 

1. libra共识简介

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在所有验证节点都重启的情况下,也能够保证网络的一致性。

Libra白皮书指出,其将以许可型区块链的方式起步。未来为了确保Libra的真正开放,始终以符合用户最佳利益的方式运作,Facebook的最终目标是让Libra网络成为"非许可型网络",但是其目前的挑战在于,他们目前还没有成熟的解决方案可以通过非许可型网络,提供支持全球数十亿人和交易所需的规模、稳定性和安全性。从“许可型”网络过渡到“非许可型”网络,共识层面还需要做非常大的改进。

 

2. HotStuff算法

2.1 HotStuff算法特点

HotStuff 是一个三阶段的BFT算法,允许一个新的leader简单地选择一个最新的的QC(Quorum certification)。它引入了一个第二阶段,允许副本在投票后在不需要请求leader请求的基础上改变他的决策。这一改进大大降低了复杂度,同时也降低了leader替换的复杂度。最后,由于长期委任所有的状态,这样HotStuff非常容易通过事件机制的方式实现,适合leader经常切换的场景。HotStuff主要有以下几个特性:

• 线性的视图切换:在GST后,对于一个诚实的leader,一旦被指定,会发给n个验证者来收集签名,以推动共识的决定;

• 乐观的响应:在GST后,对于一个诚实的leader,一旦被指定,只需要等最早的 n-f 个验证者返回消息就可以发起有效的提案,包括leader替换;

• 支持频繁切主:HotStuff还有一个特点是新leader的推动协议达成共识的成本不高于当前领导者的成本,所以其适用于leader切换的协议;

• 决策简单:HotStuff中副本只有两种消息类型和一个简单的规则来决定是否要接受一个提案,其通过投票和提交规则来达成一致性,通过Pacemaker来保证可用性,并且各阶段的算法复杂度低;

• 阈值签名:HotStuff使用阈值签名的方式来收集签名,使得签名的验证会更为简单;

 

2.2 HotStuff算法流程

2.2.1 Basic HotStuff

Basic HotStuff 协议是HotStuff的基本过程,他在一系列的视图中切换,视图以单调递增编号方式切换。在每个视图内,有一个唯一的达成共识的leader。每个副本在起本地数据结构中会记录所有请求的tree,tree的每个叶子节点是一个已经提出的提案。一个给定节点的分支是该节点到达树根的所有路径。按照HotStuff协议,随着视图的增长,分支会被提交。Leader需要像(n-f)个验证者采用阈值签名的方式收集签名,收集签名的过程主要包括3个阶段,PREPARE、PRE-COMMIT和COMMIT阶段,整个算法包括5个阶段,PREPARE、PRE-COMMIT、COMMIT、DECIDE和FINALLY阶段,如下图所示:

1. PREPARE阶段:该阶段,leader发起一个high的提案(highQC),组成消息,消息内容 m = MSG(PREPARE, curProposal,highQC),并广播给所有的验证节点;验证节点在收到时上述提案消息后会进行投票,如果m的node超过本地已经判决过的node是则会投票,并返回消息给leader,m' = voteMSG(PREPARE,n.node,⊥)。

2. PRE-COMMIT阶段:该阶段,当Leader收到(n-f)个验证节点的PREPARE阶段的投票信息后,会发起一个 PREPARE的提案(prepareQC),组成消息,消息内容为 m = MSG(COMMIT, ⊥,prepareQC),并广播给所有的验证节点;验证节点在收到上述提案消息后会进行投票,并返回消息给leader,m' = voteMSG(PRE-COMMIT,m.justify.node,⊥)。

3. COMMIT阶段:该阶段,当Leader收到(n-f)个验证节点的PRE-COMMIT阶段的投票信息后,会发起一个 PRE-COMMIT的提案(precommitQC),组成消息,消息内容为 m = MSG(COMMIT, ⊥,precommitQC),并广播给所有的验证节点;验证节点在收到上述提案消息后会进行投票,并返回消息给leader,m' = voteMSG(COMMIT,m.justify.node,⊥)。

4. DECIDE阶段:该阶段,当Leader收到(n-f)个验证节点 COMMIT 的投票后,会生成一个COMMIT的提案(commitQC),组成消息,消息内容为 m = MSG(DECIDE,⊥,commitQC),并广播给所有的验证者;验证者在收到该消息后,会执行命令,并返回给客户端。

5. FINALLY阶段:如果系统进入下一个View,各个副本会发送一个消息给下一个View的leader,消息内容为 m = MSG(NEW-VIEW,⊥,prepareQC)。

2.2.2 Chained HotStuff

上图中可以看出来Basic HotStuff的各个phase中的流程都非常相似,作者又提出了一种Chained HotStuff来优化和简化Basic HotStuff。改进的点主要是改变每个PREPARE节点的View。这将大大降低通信消息的数量,并且可以对决策进行管道处理。Chained HotStuff的流程如下所示:

上述Figure1可以看出一个节点可以同时处于不同的View,通过链式的结构,一个提案在经过3个块后能够达成共识。其内部有一个状态转换器,通过genericQC实现提案的自动切换。其主要算法流程如下所示:

 

3. LibraBft改进 

Libra 为了更好地适应其生态,对HotStuff进行了相应的优化,主要有5点:

1.首要的是Libra定义了安全的条件,提供了安全性、活性和乐观响应的扩展证明;

2.第二点:Libra 通过让验证器集体对区块的状态而不是事务的顺序进行签名,使得协议会更加鲁棒。同时还允许客户端使用QC验证从数据库里读出的数据。

3.第三点:Libra 设计了一个Pacemaker 来发出显示的超时信号,验证者通过他发出的提案自动进入下一个视图,而不需要一个同步的时钟;

4.第四点:Libra 希望让矿工变得不可预测,它最新提交的区块信息为种子生成一个可验证的随机数VRF,成为下一个矿工;

5.第五点:Libra 使用聚合签名的方式保留QC中验证者的身份,以提高验签效率,同时为这些验证者提供奖励。