HoneyBadgerBFT 共识
Andrew Miller
伊利诺伊大学香槟分校
Yu Xia
清华大学
伊莱恩·施
康奈尔大学
Kyle Croman
康奈尔大学
Dawn Song
加州大学伯克利分校
摘要
加密货币的惊人成功使人们倾向为金融交易应用部署大规模、高度健壮的拜占庭容错
(BFT)共识。人们通常使用 PBFT 等同步共识,但此类共识严重依赖网络计时假设。且仅在
网络环境正常时有效。所以这些共识其实并不不适合金融交易应用。
我们提出了一种替代方案,即“HoneyBadger-BFT 共识”。它没有时序假设,基于一种新
的原子广播共识,有最佳的异步效率。下面有实现方案和实验结果,证明系统可实现每秒数万
个交易的吞吐量。甚至在 Tor 网络中也能用,且无需调整任何参数。与现在常用的 PBFT 方案
不同,HoneyBadger-BFT 共识不关心底层网络。
1.简介
分布式容错共识是一些面向任务的区块链应用的有效解决方案。它们的部署规模相对较小,
通常部署在单个管理域中。这种共识设计时考虑了攻击环境,可以容忍一定程度的恶意网络环
境。举个例子,Google 的容错锁服务 Chubby[14]仅由五个节点组成,并且最多可容忍两个崩溃
节点。
近年来,随着“加密货币”或“区块链”出现,我们对分布式系统的理解开启了新篇章。
加密货币系统颠覆了传统的容错共识。与 Google 的“5 个 Chubby 节点”系统不同,加密
货币涉及大量互不信任的节点,这是对共识的新需求。网络环境更不可预测,甚至具有对抗性。
健壮性是最重要的。加密货币环境中应该避免出现异常节点,即使是以牺牲性能为代价。
比如,比特币的性能很糟糕:每次交易平均需要 10 分钟才能提交,同时整个系统的吞吐量
只有每秒 10 笔交易。但是,加密货币可以在充满恶意节点的环境中正常运行。
因此,比特币的支持者称它为“金钱的蜂蜜徽章”[41]。
稳健性往往与去中心化有关,因为去中心化需要在一个广域网络中有大量参与者。
要吞吐量不要延迟。大多数容错共识[6,49],侧重于在由单个管理域控制的局域网环境中优
化可扩展性。由于局域网内带宽充足,这些优化更多是减少(加密)计算和最小化响应时间。
其实,很多区块链系统中响应时间并不是最重要的,例如用于支付和结算[1]的区块链系统。
甚至某些财务应用会有意在提交交易时引入延迟,以便回滚/退款操作。
尽管这些应用并不对网络延迟敏感,但金融机构已表示有兴趣采用高吞吐量的区块链技术
替代方案,以便能够处理网络中的大量请求。例如,Visa 的区块链系统平均每秒处理 2,000 个
交易,峰值为每秒 59,000 个交易[1]。
1.1 我们的贡献
基于时序同步假设的共识往往不够健壮。大多数拜占庭容错(BFT)共识,都基于弱时序
同步的假设。
粗略地说,弱时序同步就是指两个节点建立连接后才能传递消息。
我们认为,基于时序假设的共识不适合分布式加密货币,因为网络可能有延迟。更糟糕的
是这个网络延迟还可能由攻击者主动触发。一旦违反时序同步假设,这些共识可能完全失效。
为了证明这一点,我们构造了违背时序同步的网络环境,使基于弱时序同步的 BFT 共识停
滞。
另一方面,即使满足了弱同步假设,弱同步共识的吞吐量也会很小。
最好能有一个共识,即使网络环境恶劣,也能有较好的交易吞吐量。
弱同步共识需要弱同步参数来调整。
弱同步参数就是共识实现时的超时时长。
当超时时长设置得太长或过短时,吞吐量就会很小。
在第 3 节中我们会举个例子来说明,即使满足弱同步假设,BFT 共识从超时的共识状态中
恢复所需的时间也会很长。
综上,我们建议使用 HoneyBadgerBFT 共识机制,这是史上第一个通过异步通信来提升交
易吞吐量的 BFT 共识。
BitCoin 的作者 Cachin 等人[15]规定:在共识过程中,每个节点最多发送 O(N2)位大小的消
息,这大大限制了共识的工作效率。
工作效率的降低有两个根本原因。
第一个原因是各节点之间传输的信息存在冗余。然而,如果直接消除冗余会使破坏共识中
信息传输的机密性。
第二个原因是使用了异步公共子集(ACS)协议。
所以我们在 HoneyBadgerBFT 共识中做了一些改良,从而规避以上问题。
1、通过使用门限加密来防止,冗余消除后,消息直接广播所造成的隐私泄漏。
2、加入了纠错码来更有效的使用 ACS 协议。
3、打破了每个节点最多发送 O(N2)位大小消息的限制。
从而提高了网络带宽利用效率,增加了共识的交易吞吐量。
HoneyBadgerBFT 共识针对加密货币部署方案做了优化。
在加密货币部署实践中节点的计算能力相对充足,这就使得我们可以使用一些需要大量计
算的门限加密技术。
在 异 步 通 信 的 网 络 中 , 消 息 传 递 时 不 需 要 时 序 假 设 。 与 现 有 的 弱 同 步 共 识 不 同 ,
HoneyBadgerBFT 共识对延时参数并不敏感。无论网络如何波动,HoneyBadgerBFT 的吞吐量始
终对齐网络带宽。只要消息最终传递到目标,HoneybadgerBFT 共识就能取得进展。
我们通过大量实验证明了 HoneyBadgerBFT 共识不仅安全,它还能提供比经典 PBFT 共识
[20]更好的吞吐量。
下文中我们会展示在 Amazon AWS 分布在五大洲的 100 多个节点上部署 HoneyBadgerBFT
的实验结果。同时我们还在 Tor 匿名中继网络上部署了 HoneyBadgerBFT。
两个实验结果都证实了 HoneyBadgerBFT 共识高效又安全。
在不久的将来我们会把它开源。1
1.2 部署方案
在众多应用场景中,我们重点介绍银行、金融机构和主张完全去中心化的加密货币的部署
方案。
有很多金融机构试图部署基于 BFT 共识的数字货币[24,25,47],这将使银行业务变得高效。
例如 IBM 的开放区块链和 Hyperledger 项目[40]。
这些在广域网上部署的基于 BFT 共识的数字货币系统,可能涉及数百到数千个共识节点。
而且这些系统的节点注册过程应该是可控的。
1https://github.com/amiller/HoneyBadgerBFT
显然,HoneyBadgerBFT 是的可选方案。
注册可控的区块链成为“许可型”区块链。相对的也有无许可区块链,例如比特币。
在比特币这种无许可区块链中,节点可以动态且频繁地加入和离开。
为了在这种注册不可控的情况下保证区块链的安全,比特币引入了工作量证明来防御 Sybil
攻击。
但是这样做的代价就是共识的交易吞吐量大幅下降,而且还会遇到网络延迟。
目前,比特币每 10 分钟才能记录一次交易。即使充分利用每个区块,其吞吐量也只有
7tx/sec。
最近有人提出了一个想法,在比特币这种慢速低效的区块链系统的基础上,引入委员会的
概念。仅让一小部分人来进行讨论具体共识。
这个方法既保证了无许可区块链的安全性,又满足了去中心化的特点,甚至还加快了共识
速度,提高了共识效率。
2.背景和相关工作
我们的研究目标是构建一个 BFT 共识的状态机模型,每个客户端根据这个模型来接收和处
理信息。
最终所有客户端对某一个命题达成统一,并记录在客户端本地的数据库中。
这其实就是区块链的本质。
BFT 共识机制保证了数据记录服务的安全,即使在众多客户端中有几个发生了故障,也可
以正常达成共识,所有客户端依旧可以正常的记录数据。
2.1 ROBUST BFT 共识
Paxos[36]、Raft[45]和其他很多共识可以容忍小部分节点发生故障(不参与共识,不发送共
识消息),拜占庭容错共识(PBFT)甚至还可以容忍小部分恶意节点的攻击(参与共识,但是发
送错误的共识消息)。
但这些共识都依赖于良好的网络环境。如果遇到网络延迟严重,恶意节点过多的情况。共
识就会停滞不前,区块链服务就会停滞。
因此有些共识为了在恶劣的网络环境中运行,最大限度的减少了加密操作。例如 Clement
等人[22] 推出的 Robust BFT 共识[4,6,10,21,22,50]。
我们的 HoneyBadgerBFT 共识也采用了这种方法,使其在恶劣的网络环境中,可以正常运
行。
2.2 随机共识
大多数同步性共识,都有不稳定性。虽然很多同步性共识试图通过时序假设的方法来避开
这种不稳定性,但效果都不好。例如二进制共识(ABA)、可靠广播(RBC)等[13,15,16]都是
不稳定的同步性共识。
我 们 的 项 目 类 似 SINTRA[17] ,SINTRA 是 基 于 Cachin 等 人 提 出 的 异 步 原 子 广 播 共 识
(CKPS01)的系统[15]。
该共识包括原子广播(ABC)、异步通用子集共识(ACS)、多值验证共识(MVBA)三
部分。
我们的 HoneyBadgerBFT 共识,使用了其中的 ABC 和 ACS 来提高效率。
另外我们使用了可靠广播(RBC)代替了 SINTRA 中的 MVCA。
最后,我们使用门限加密技术,来保证信息的机密性。
表 1 总结了 HoneyBadgerBFT 与其他几种原子广播共识的性能。此处“通信组合”表示每
次提交交易的预期通信复杂性(即传输的总字节数)。
可见,由于 PBFT 依赖于弱同步假设,因此在异步网络中可能无法取得进展。
共识 KS02[34]和 RC05[46]是异步的。但是通信复杂度较高,我们可以使用 ACS 共识来做
改进,使其复杂度降低 O(N)。
表 1:原子广播共识近似通信复杂性
异步性
通信组合
乐观的网络环境
PBFT 否
KS02 是
RC05 是
CKPS01 是
HoneyBadgerBFT 是
3.异步和弱同步网络之间的差异
O(N)
O(N2)
O(N)
O(N2)
O(N)
糟糕的网络环
境
∞
O(N3)
O(N3)
O(N2)
O(N)
市面上几乎所有的 BFT 类共识都依赖时序假设,很少有纯异步的 BFT 共识。
因为大家都觉得 BFT 共识必然要依赖时序假设,没了时序假设,性能不然大幅下降。
但这是对 BFT 类共识的误解。本节会介绍纯异步的 BFT 共识和普通的基于时序假设的
BFT 共识的区别。并且会提出两个论点,来证明,即使脱离了时序假设,BFT 类共识也可以有
其他方式,来保障共识的正常运行。
3.1 时序假设
时序假设是指,在共识过程中。网络中所有参与共识的节点,必须按照一定时间顺序,在
所有节点到达某一状态后,再进行下一个时间段的共识。(就像斗地主,下家必须等上家出牌
之后,才能出牌。如果上家出现延迟,下家必须一直等待上家)
异步网络是指,节点可以以任何顺序在任何时间发送共识消息。(就像飞行棋,如果一个
玩家出现了网络延迟,其他人可以照常仍骰子,照常游戏。等延迟玩家连上之后,只需根据延
迟时间,多扔几次骰子就行。)
确定性共识必须基于一些较强的时序假设,比如同步网络中的每一条消息在延迟最多∆秒
后传递到目标节点。(类比与斗地主中的计时器,30 秒不出牌,计作 pass)
另一种形式的时序假设是弱同步假设,即延时参数随时间变化,变化速度增长小于时间的
多项式函数。
上述两个形式的时序假设可行性相同。
就性能而言,后者的延时参数会随着时间增长。这就导致网络从崩溃中恢复的速度很慢。
在实际代码中,常常用超时事件来表示时序假设。例如,20 秒内矿工节点没有出块,则另
外选择一个新的矿工节点。
纯异步计时器不依赖与时序,只要消息被目标节点接收了,共识就可以进行。
3.2 弱同步失败
现在我们来解释一下,为什么基于弱同步的共识,如果处在恶劣的网络环境中,可能会发
生共识停滞。
以 PBFT 共识举例,PBFT 共识是一个典型的基于领导者的 BFT 共识。所有共识节点选择
领导者,由领导者决定区块链上的记账结果。
如果领导者遇到了网络故障,在规定时间内没有把区块广播出来,则其他所有节点会选择
另外一个领导者。
PBFT 严格遵守这个时序假设,于是我们实现了一个违反这一假设的网络模拟程序。
模拟程序原理如下,所有节点先正常共识,然后令一个领导者节点崩溃。
如果有正常节点被选为新领导者时,就让这个节点的网络延迟一下,直到其他节点开始选
择下一个领导者。
如果有崩溃节点被选为新领导者时,就放任网络正常通信,反正这个节点时崩溃节点,共
识不会有效进行。
如此往复,PBFT 共识就一直在选领导者,而共识本身停滞不前。
另一方面,PBFT 本身是弱同步机制,停滞时间越长,延时参数就越大。当有一个领导者
崩溃时,网络中的节点等待领导者出块的时间为 2D∆。如果它没有正常发出区块,会选择下一
个领导者,而留给下一个领导者的出块时间为 2D+1∆。
最终所有节点会为了找到新领导者而等待很长很长时间(2D+n∆)。(而且下一个领导人依旧
不能当选)
最终导致分布式系统崩溃。
为了证明如上推论,我们进行了实验,当有节点选为领导者时,拦截它的所有流量,造成
网络延迟。最终实验结果和上述分析一致。实验环境中的 PBFT 共识卡在一个高度不变。分布
式系统崩溃。
我们上面观察到的此类行为并非特定于 PBFT,而是针对所有从依赖于超时来应对崩溃的
共识。
可见,在共识设计过程中,开发者必须权衡调整其超时策略。
如果延时参数太低,则系统可能没有任何进展。过高,则不能充分利用带宽。
然而,我们提出的异步共识就无需调整此类参数。
4.HONEYBADGER-BFT 共识
在本节中,我们会介绍 HoneyBadgerBFT,这是第一个异步原子广播共识,可实现较高的
交易效率。
4.1 原子广播
我们首先定义原子广播的网络模型。
网络中有 N 个节点,分别是Ƥ0 到ƤN-1
节点的输入是一条交易。这里为了简化问题,交易就是一个字符串。
最终网络中的所有节点要输出完全一致的交易集合。即对交易集合中的交易达成共识。
我们的网络模型中有如下术语:
(纯异步网络)我们假设每对节点都通过可靠的经过身份验证的点对点通道进行连接,
该信道不会丢弃消息。每个节点有接收消息用的缓冲区,接收到的消息不是按照消息
的到达顺序进行处理,而是按照消息的序号进行处理。
(拜占庭共识的容忍极限)攻击者可以完全控制多达 f 故障节点,其中 f 是共识参数。
就是 PBFT 共识中的恶意节点数量上限。即3f+1≤N。
定理 1. 原子广播共识必须满足以下属性:
(达成共识)如果任何正确的节点输出交易 tx,则每个正确的节点输出 tx。
( 节点 输出 ) 如果 一个 正确 的节 点输 出交 易序 列tx0,tx1,…txj , 另一 个 节点 输出
tx0',tx1',…txj'' , 则有txi=txi'为i≤minj,j' .
(效率)假设每个诚实的节点的输入缓冲区已满Ω(sumN,λ )。效率就是总通信复杂
(弹性)如果交易 tx 输入到多余 N-f 个的正确节点,则它最终由每个正确的节点输出。
这就是 BFT 的弹性共识规则,不用所有节点都争取,容忍一小部分人有错误。
(交易延迟)假设对手将交易 tx 作为输入传递给 N-f 正确节点。记 T 为“积压”,即
度成本除以已处理的交易数量。
以前输入的交易总数与已提交的交易数之间的差异。
我们的 HoneyBadgerBFT 使用批处理技术实现了较好的交易吞吐量,但是,如果一批交易
中的交易数量较小时,平均每个交易所消耗的带宽就增加了。
有时区块链会有网络成本最小化的需求,那么这种批处理技术就不合适了。
4.2 概述和原理
在 HoneyBadgerBFT 共识中,节点将收到的交易存入缓冲区。共识每到达一个高度,就在
缓冲区中选择一些交易作为当前高度共识的输入。
当这个高度的共识结束时,输出一些交易作为共识的结果。
具体操作类似于 SINTRA 的异步原子广播共识,它的基础是异步公共子集 ACS。
粗略地说,ACS 机制允许每个节点提出一个值,并保证每个节点输出一个包含至少 N-2f
正确节点的输入值的矢量。
以此构建的原子广播的规模是很小的。同时有两个重要的挑战。
挑战 1:实现审查能力。ACS 的成本直接取决于每个节点提出的交易集的大小。由于输出
矢量至少包含 N-f 此类集,因此,需要通过确保节点提出大部分不相交的交易集来提高总体效
率,从而以相同的成本在一个批处理中提交更不同的交易。
因此,我们建议每个节点都随机选择交易。
但是,这种优化不够安全,因为 ACS 基元允许领导者选择最终包含哪些节点的提议。如果
领导者是攻击者,那么可以对上链的交易进行操作。
我们使用阈值加密来避免此缺陷,该加密可防止攻击者了解哪些节点提出了哪些交易。
挑战 2:实际吞吐量。虽然异步 ACS 和原子广播的理论可行性已经为[9,15,17]所知,但实
际性能并不好。
在本文中,我们使用批处理技术,将 ACS 的通信成本从 O(N2)提升到 O(1)。
接下来我们来正式介绍一下 HoneyBadgerBFT 共识机制。
4.3 从异步公共子集构造 HONEYBADGERBFT
输入。
我们以 ACS 为基础来实现 HoneyBadgerBFT 共识。
准确的说,ACS 共识满足以下属性:
(有效性)如果正确的节点输出一组 v,则v ≥−即 v 包含至少 N-2f 正确节点的
(共识)如果正确的节点输出 v,则每个节点输出 v。
(总计)如果 N-f 正确节点接收输入,则所有正确的节点都会生成输出。
另一项技术是门限密码。粗糙的说,门限密码 TPKE 将揭秘密钥分成了 N 份,每个节点有
其中一份。当有 f 个节点将手里的残缺密钥组合在一起,即可恢复出完整的解密密钥。铭文就
可以恢复。
门限密码提供以下接口:
算法 HoneyBadger-BFT(对于节点Ƥi)
者,如果 C 包含无效共享,则标识无效共享)。
在我们的具体实例化中,我们使用 Baek 和 Zheng[7]的门限密码方案。
i, →合并了一组解密共享i, 从至少 f+1 方获取纯文本 m(或
令 PK 为从 TPKE 收到的公钥,让 SKi 成为Ƥi 的密钥。
令 buf:=[ ]成为输入交易的 FIFO 队列。
For 共识高度 r do:
TPKE.set1λ →PK,SKi 生成公钥 PK,以及各方 SKi 私钥
TPKE.EncPK, →加密消息 m
TPKE.DecShareSKi, →生成解密的第 ith 共享
TPKE.DecPK,,
令=Ωλ2log 是批处理大小参数。
For proposal from bf /:
接收vj
每个j∈S:
让ej:=TPKE.DecShareSKi,vj
广播 DECr,j,i,ej
wait to receive at least f+1 messages of the form DECr,j,k,ej,k
_yj:=TPKE.DecPK, k,ej,k
令 blockr :=sortUj∈S,yj ,以便 blockr 按规范顺序排序(例如,按字典方式排序)
j∈S,其中S⊂ 1.. ,从 ACS[r]
//第 1 步:随机选择和加密
Encrypt_x:=TPKE.Enc(PK)
//第 2 步:关于密文的共识
将 x 作为输入传递给 ACS[r]//参见图 4
//第 3 步:解密
Set buf:=blockr
图 1:Honey-BFT。
如前所述,该共识以 ACS 为核心。为了获得更好的交易吞吐量,我们使用了批处理技术。
令 B 为批处理大小,并在每个共识高度提交Ω(B)个交易。每个节点都从队列中拿出 B/N 个交易。
为了确保节点提出大多数不同的交易,我们从每个队列中随机选择这些交易。
正如我们将在第 4.4 节中看到的,我们的 ACS 实例化的总通信成本为2v+λ3log ,
其中v 为节点的输入大小。因此,有批处理大小=Ωλ2log ,以便每个节点(B/N)的分
担此冗余开销。
4.4 如何让 ACS 更高效
Cachin 等人提出了一个我们称之为 CKPS01 的共识,该共识是在 ACS 中添加了 MVBA 多
值验证拜占庭共识机制。
方法很简单:验证输出必须来自至少 N-f 方的签名输入。
RBC 算法(Ƥi,与ƤSender)
input(v)(if Ƥi=Ƥ发送方):
令Sj
j∈[N]为应用于 v 的−2, 擦除编码方案的块
令 h 成为在Sj 上计算的 Merkle 树根
发送VALh,bj,Sj 到每个节点Ƥj,其中bj是 jth Merkle 树分支
收到VALh,bj,Sj 从Ƥ发送方,广播ECHOh,bj,Sj
从甲方Ƥj 接收ECHOh,bj,Sj 后,检查 bj 是否为根 h 和叶 sj 的有效 Merkle 分支,否则丢弃
, 来自−不同方的消息,
收到有效的ECHOh,
– 插值Sj' 从任何−2叶接收
– 重新计算 Merkle 根h'h'≠h 则中止
收到+1 匹配 READY(h)消息,如果尚未发送 READY,则多播 READY(h)
收到2+1 匹配 READY(h)消息后,等待−2 ECHO 消息,然后解码 v
图 2:可靠的广播算法,带有擦除代码,还能提高效率[18]
– 如果没有广播 READY(h),则广播 READY(h)
ACS 共识分两个主要阶段进行。
在第一阶段,每个节点Ƥi 使用 RBC 算法将其提出的交易传播到其他节点,
第二阶段,通过 ABA(二进制拜占庭)判断哪些 RBC 成功完成。
以上,我们简要解释了 RBC 和 ABA 的原理。
异步可靠广播信道满足以下属性:
(总计)如果任何正确的节点输出 v,则所有正确的节点都输出 v
(有效期)如果发送方正确且输入 v,则所有正确的节点都输出 v
(共识)如果任意两个正确的节点输出 v 和v',则v=v'。
Bracha 的[13]经典可靠广播共识需要2v 个通信位,广播的实际消息大小v ,Cachin
和 Tessaro [18]发现校验码可以降低这个成本到v+λ2log 。当实际消息大小很大时(当
v ≫λlog),校验码带来的效率提升会更强(回顾第 4.3 节)。
此处使用校验码本身最多会导致一个常量开销,大小等于 −2<3
如果发送方正确,则总运行时间是三轮。在任何情况下,第一个正确节点输出和最后一个
输出之间,最多两轮。
图 3:(如图是 ACS 执行的示例。我们共识的每次执行都涉及运行可靠广播(RBC)的并发,
以及拜占庭共识(BA)的 N 个实例。(a)在一般情况下,节点 0 从索引 1 的可靠广播接收值
V1(节点 1 的 proposal)。因此,节点 0 向 BA1 提供输入“true”,后者输出“true”。(b)