详解LibraBFT共识机制

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算法流程

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)。

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中验证者的身份,以提高验签效率,同时为这些验证者提供奖励。

Libra白皮书技术解读

简介
Libra 目前是一个联盟链的组织形式,他的去中心化体现在,由多个 validator 来共同处理交易以及区块链中的状态,但是随着时间的推移,Libra 也计划朝着公有链的方向发展。
对于 Libra,我们可以将其看做是一个通过 Libra 协议管理的带加密认证的数据库,通过 LibraBFT 共识算法,可以保证每个诚实节点中数据库的数据是一致的。与以太坊相似,Libra 也有智能合约和账户的概念,但是不同的是,Libra 将合约和资源是分开存储的,这个会在后续详细展开。
下面这个图是 Libra 协议中两种角色:客户端 client,验证器 validator。validators 就像是元老会,会轮流着产生提议者,用来将当前的交易定序、打包形成区块,并且共同维护着数据库的一致性。client 就是负责发起提交交易,查询信息等,比如钱包就是一个典型的 client。
这里简单介绍上图的流程,当用户通过钱包(client)发起了一笔转账交易后,钱包就会将这笔经过用户签名的交易通过 grpc 发送给 validator(过程 1)。节点在收到 client 提交的交易后,首先会对交易进行预检验,只有有效的交易才会被 validator 节点转发给当前轮次下的 leader,leader 是 validator 集合中在某个轮次下有提议权利的节点,leader 从本地的交易池中获取若干条有效的交易,对其定序打包后,转发给其他 validator(过程 2)。validator(包括 leader)可以理解为是一个状态机,每个 validator 在收到 leader 广播的 block 后,会执行其中的所有交易(过程 3)。由于 validator 存在作恶的可能性,因此每个 validator 在执行完交易后不能直接将结果写入 storage 中,Libra 的共识要求他们对执行完的结果进行投票,只有达成共识的结果才能写入到 storage 中(过程 4)。在交易被提交成功后,validator 不仅会将交易,以及结果写入到 storage,还会生成一个当前交易版本下整个数据状态的签名(其实就是 Merkle Accumulator),client 在进行一些只读的查询时可以从这个数据结构里进行查询(过程 5)。

数据的逻辑结构

相比于以太坊(ethereum),Libra 弱化了区块(block)的概念,只是把它当做是交易(transaction)的载体,实际的最小执行单位是交易。对于 Libra,我们可以看做是一个带版本号的数据库,这里的版本其实就是交易
Ti
的序号
KaTeX parse error: Can't use function '\(' in math mode at position 2: i\)̲\( ,这个序号是严格递增的。在…
i
时,数据库会保存元组
(T_i, O_i, S_i)
数据,这里的
T_i
表示序号为
i
的交易,
O_i
表示执行完交易
T_i
后的输出结果,
S_i
表示账本状态。当我们执行某个程序,过程的大致可以表述为,在某个状态下,程序代码按照给定的参数执行。例如validator收到了一笔序号为
i
的交易
T_i
,当validator执行时交易时,他的状态是基于上一个版本
S_(i-1)
,输入参数则是接收到的交易
T_i
,而需要执行的代码,其实在
T_i\)$ 中指定了需要执行的合约。所以,按照数学归纳法的推导,如果 validator 的最初状态都是一致,并且是诚实的节点(即诚实的执行),那么只要他们的输入是一致的,这些 validator 的账本状态也将是一致的。
通过这种带版本号的数据库,可以方便的查询在各个版本下的账本数据。例如,我们需要查询在版本号为 10 下某个账户的余额信息。
但是随之而来的问题是,我们如何判断上述的交易、状态数据等是有效和没有被篡改的?Libra 针对上述情况,设计了 Ledger History 数据结构。

账本状态

Libra 和以太坊一样,采用了账户模型,这里之所以没有采用 UTXO,主要是因为 UTXO 模型不适合用于复杂的合约。
以太坊的账户地址是由公钥衍生出来的,Libra 也是一样,不过 Libra 在创建用户的时候会生成两对公私钥:验证、签名(vk,sk)公私钥对。其中 Libra 的账户地址是由 vk 的公钥经过哈希后生成的。之所以要区分 vk 和 sk 是为了安全起见,Libra 用户可以在不更换地址的情况下,更换新的签名公私钥对。
关于账户状态,Libra 和以太坊的区别比较大。在以太坊中,账户下面会存放余额、合约、nonce 等信息。Libra 的账户状态主要包含了两部分:module、resource。module 类似于以太坊中的合约,resource 则是 module 中定义好的资源。module 和 resource 的归属权是分开来的,如下图所示。方框表示的是 module,椭圆表示的是 resource。例如对于账户0x56来说,他发布了一个 Currency 的 module(合约),那么这个 module 是存储在其0x56的目录下的,如果另外一个账户0x12也拥有了 Currency.T 这个资源,那么该资源是存储在0x12的目录下的,相当于是将代码段和数据段分开来了。
而以太坊的合约并不是这样的,例如我们发布了一个ERC20的合约,我们会定义一个 map 结构 mapping (address => uint256) public balanceOf; 该结构会存储某个账户在这个合约中包含有多少 ERC20 的 token。也就是说,以太坊中的合约是将数据段和代码段混合在一起的。
Libra 之所以这样做,主要是为了保证资源的所属权,从而保证其安全性。

交易

交易中有个 program 字段,包含了需要执行的脚本以及参数,或者需要部署的 module 字节码。由于 Libra 采用 LibraBFT 的共识,当 validator 接收到 block,并不意味着这轮的共识结束了,所以 validator 在执行完接收到的交易后,并不会马上将执行后的状态写入到分布式账本状态(Ledger state)中,只有当大部分的节点关于该交易执行的结果投票达成共识后才会更改 Ledger state。
交易
Ti
执行完后,除了会生成新的状态
Si
外,还会额外产生一个交易输出
Oi
。交易输出可以类比于以太坊的交易收据,包括了 gas 使用、执行状态、event 等。这里的执行状态是指虚拟机的执行状态,并不是具体合约的业务执行状态。例如,执行状态是成功,表示虚拟机在执行过程中没有出现 gas 不足或者导致执行异常的触发条件。
为了能够清晰的了解合约执行的执行过程,Libra 参考了以太坊,加入了 event 事件。event 就像是我们在开发中采用 print 方法打印某些日志数据以此判断代码的执行逻辑。事实上,在以太坊的 ERC20 中,开发者为了判断 token 转账是否成功,会在 transfer 函数执行成功后,加上一个 Transfer event,一旦交易执行完成后,抛出了 Transfer 类型的 event,那么开发者就可以认为此次合约转账是成功的(除去分叉的概率外)。

账本历史

账本历史(Ledger History)存储了已经执行并提交(达成共识)的交易,以及 event 信息等。这些信息对于 validator 执行交易来说是不需要的,之所以存储了上述信息,主要的目的是为了保证 validator 的可信度。client 通过查询 validator 的数据,以此监督 validator 在正确的执行交易。

交易执行

再来看一下 Libra 区块链的交易执行,Move 语言会在后续通过实际编写和部署合约的时候仔细介绍。
在 Libra 中,能够触发状态变化的只能是通过执行交易,目前 Libra 的测试网络还不允许普通用户发布合约,并且能够调用的脚本也是有限的,下面是 Libra 中 config 的配置信息,Locked 表示不允许普通用户发布和调用非白名单里外的脚本。
不过最新的 Libra 代码,在 testnet 分支中已经将该限制打开了,普通用户可以在本地进行合约的部署。

交易执行的条件

对于区块链中每个诚实 validator 节点,我们可以把它当做一个状态机,他会在当前的状态下,按照既定的逻辑诚实的执行输入。
那么在最初的时刻,这个初始状态是如何确定的呢?我们用以太坊来进行对比。下面是以太坊的 genesis.json,这个文件确定了以太坊网络最初的状态,比如在 alloc 中设定了两个地址的初始 eth 数量,以及最初的难度值等信息。
Libra 对 genesis 的处理与以太坊的不同,正如 Libra 在白皮书中说的,能够改变状态的唯一方式是交易的执行,而 genesis 作为初始状态的输入,其实也是一个交易,只不过这个交易的序号是 0(
T0
)。这个交易相比于其他交易的特殊点在于,这个交易是一个 writeset 类型的,我们暂时可以将其理解为是一个写入类型的交易,不需要执行。另外,writeset 类型的交易只能在 genesis 阶段运行发布。
既然 genesis 作为
T0
交易,那么必然需要满足他的发送者有足够的费用支付交易费用,同时由于 Libra 是联盟链,因此
T0
会指明当前的 validator 集合以及他们的验证信息等,另外由于 Libra 的 token 是通过合约发布的,因此在
T0
中还会部署上 Libra 的 account 和 coin 两个合约,如果大家有兴趣可以查看下 genesis.blob 来验证下,不过 genesis.blob 有部分是乱码,但是基本上足够支撑上述的论点了。这里之所以这么关注 genesis,是因为通过了解这个方便我们可以自己搭建 Libra 的测试网络。
另外,白皮书提到了确定性,这个比较好理解,如果无法保证确定性,那么意味着不同 validator 对同一个交易的执行结果是不同的,那么就无法达成一致,分叉就开始了。Libra 的 gas 机制与以太坊的比较相似,例如:
1. 影响 gas 的是 gas price 和实际消耗的 gas cost;
2. 一旦交易执行中的 gas 使用超过了 gas limit,那么就会立马 halt,并且将数据回滚到上一个版本,虽然该交易没有执行成功,但是还是会出现在 block 中。
Libra 和以太坊关于 gas 的最大区别是,Libra 设定 gas 的主要目的是为了防止 DDoS,而以太坊的 gas 除了这个目的外,还将 gas 作为激励的一部分给 miner。之所以有这个区别,是因为以太坊是公有链,简单说,你要吸引 miner 来挖矿执行交易,必然需要激励。但是 Libra 是强联盟链, 不太需要这种激励模式。

交易结构

Libra 的交易结构与以太坊的比较相似,对于一个已经签名的交易,他的结构如下:
sender address:很好理解,就是这笔交易发起者地址。
sender public key:表示交易发起者的公钥,这里之所以还要额外再增加这个,是因为 Libra 的账户有两对公私钥(vk,sk),sk 用来签名,因此为了验证交易是否被篡改,需要表明 sk 的公钥。
program:这个就和以太坊的 data 字段一样,用来存放需要执行的 script 或者需要部署的 module。
gas price:和以太坊的一样。
maximum gas amout:就是以太坊的 gas limit。
sequence number:就是以太坊的 nonce,防止双花的。
交易执行
交易执行表示在 VM 中执行阶段,他的行为不会对外部有影响,只有达成共识后,该交易执行的结果才会反应到账本状态。在虚拟机中执行交易一共分 6 个步骤。
1. 验证签名。根据交易的签名数据以及交易的字段中的sender public key来验证内容是否被篡改。
2. 前置校验。一些执行前的前置条件的检验,主要有:
* 身份认证:签名验证确保了数据没有被篡改,这块验证发送者的身份。具体的做法是读取账户的 authentication key,判断和交易中的 sender public key 相同。这个信息在 LibraAccount module 中被定义了。
3.
* 检验 gas 是否足够:因为交易执行过程需要 gas,确保账户有足够的余额来执行交易。通过判断 gas_price * max_gas_amount <= sender_account_balance 来检查。
* seq 检查:检查当前用户的 seq 与交易的 seq 是否一致,防止双花。这个 seq 也是在 LibraAccount module 中定义好的。
4. 验证script和module。这个步骤是 Libra 特有的,以太坊在做完上述检查后就直接进入到了执行步骤。由于 Libra 主打 move,他的特性就是资源的所有权,因此为了保证能够安全的操作这些资源,Libra 相当于做了一个在线的编译器(bytecode verifier),在执行前先做静态分析,确保 module 或 script 对资源的操作是安全。对于这个,有些人认为做成线下的 bytecode verifier 在性能上会更加友好,但是一旦线下的话,Libra 主打的安全其实也就失效了。不过,既然都是 validator 执行交易,那么能否设计成,validator 放出官方的 bytecode verifier,用户的 script、module 需要线下经过官方 bytecode verifier 验证并签名后,才可以发布,此时对于 Libra 来说只需要验证这些 script、module 是否经过官方签名即可,这样也避免影响了 Libra 网络的性能。不过这种方式听起来不是很去中心化,似乎不太符合大家对区块链的理解。我倒是觉得,能够避免一家独大,各家能够充分博弈,这才是比较符合现状。去中心化并不银弹。
5. 发布合约。就是将 module 部署到这个账户下面,注意同一个账户下是不允许发布同名的 module 的。
6. 执行脚本。这块展开的内容比较多,后续会作为重点来讲。这里就认为 VM 根据 program 的 script 执行对应的逻辑。
7. 扫尾工作。在执行完后,就会对账户 seq 自增,以及扣减实际消耗的 gas 等操作。

Move 语言

Move 是 Libra 面向其合约开发者的编程语言,通过 move 可以实现:
1. 我们可以创建 script 从而让交易能执行更多地逻辑;
2. 允许用户按照实际的业务逻辑来自定义数据类型和代码,并发布到链上。
3. 允许配置和扩展 Libra 的协议(包括 Libra 的 token 铸币,validator 管理等)。
Move 最大的一个特性就是,将 resource(资源)当做了一等公民,并且可以自定义 resource。例如上面贴出的 LibraAccount 中的 resource T,就定义了账户的一些基本属性。
Libra 一共有三种编写 Move 程序的方式:source code,intermediate representation(IR),byte code。对应起来就是,高级语言(C 语言),汇编语言,字节码。现在 Libra 还没提供高级语言。
和以太坊一样,Libra 的虚拟机也是基于栈的,基于栈的虚拟机的好处是指令比较精简,不像基于基于寄存器的,指令集满天飞。基于栈的虚拟机是没有堆区的,所有的局部变量和入参以及返回值等都是加载到栈中,每次函数调用完成后,栈的高度应该是和调用前相同的,Libra 基于这个特性做了一个 stack depth 检测,从而增加了交易执行的安全性。