Using Throughput-Centric Byzantine Broadcast to Tolerate Malicious Majority in Blockchains

区块链的容错性通常以其在系统中可以容忍的“对抗力量”的分数f为特征。尽管近年来区块链设计进展迅速，但现有区块链系统仍然只能容忍低于0.5的f。实际可用的区块链能否容忍恶意多数，即f高于0.5？这项工作对这个问题给出了肯定的答案。我们首先注意到，众所周知，f高于0.5的拜占庭共识不可能继续存在于区块链中。为了容忍f高于0.5，我们使用拜占庭广播，而不是拜占庭共识，作为区块链的核心。然而，这样做的一个主要障碍是由此产生的区块链可能具有极低的吞吐量。为了克服这一核心技术挑战，我们提出了一种新的拜占庭广播协议覆盖OVERLAY BB，它可以容忍f大于0.5，同时实现良好的吞吐量。以OVERLAY BB为核心，我们介绍了一个名为BC UBE的新的区块链证明的设计、实现和评估。BC UBE可以容忍恶意多数，同时在我们对10000个节点的实验中，在f=0.7以下实现了实际可用的事务吞吐量和确认延迟。据我们所知，BC UBE是第一个能够实现这些特性的区块链。

I. I NTRODUCTION
容错性在区块链等现代分布式系统中是一个非常重要的特性。容错通常以系统能够容忍的“对抗能力”的分数f为特征。这里的“对抗性力量”可能对应于
i）许可区块链中的恶意节点，
ii）基于工作证明的无许可区块链中的对抗性控制计算能力，
或iii）基于无许可区块链证明中的对抗性控制赌注。比特币的共识协议是十多年前发明的，可以容忍f低于1/2。虽然随后的区块链系统（例如[1]、[3]、[7]、[11]、[15]、[18]、[20]、[32]、[34]）取得了比比特币更好的性能，但所有这些系统仍然只能容忍低于1/2的f，有时甚至更低。这与这些设计是不管是用许可系统还是使用非许可系统。
然而，人们越来越希望区块链容忍f≥ 2 1 . 例如，出现了对公共区块链的双重支出攻击，恶意行为者暂时控制了网络中一半以上的对抗力量[12]、[23]、[26]、[27]。同样，有人强调，在许多工作证明和股权证明区块链中，少数集中式矿工控制了超过一半的权力[19]。

如今区块链无法容忍f的一个原因≥ 2 1是他们通常建立在拜占庭共识的基础上[21]。拜占庭共识是一个一次性的游戏——除其他外，它要求如果诚实的节点都对下一个区块有相同的建议，那么他们都必须决定该区块，而不是某个敌对选择的区块。这样的要求1使得不可能容忍f≥ 1/2 . 另一方面，区块链是一个连续的过程，其中分布式账本中的每个区块通常由随机提议者提出。如果提议人碰巧是恶意的，则可接受以敌对方式选择区块。因此，拜占庭共识在f≥ 1/2不一定结转到区块链。

Byzantine broadcast.拜占庭式广播。在我们追求能够容忍f≥ 1.2，我们回顾了各种经典原语。我们最终将注意力集中在一个这样的原始广播上——拜占庭广播[6]、[8]、[9]、[14]、[24]、[30]、[31]。在拜占庭广播中，有一个公共广播公司向所有节点广播一个对象（例如区块链中的块）。某些节点（包括广播者）可能是恶意的。拜占庭广播协议保证：

拜占庭广播与拜占庭共识密切相关，但与之截然不同——特别是，对于所有f<1的情况，拜占庭广播在同步系统中是可解的。从现在开始，本文将只关注能够容忍f的拜占庭广播协议≥ 2 1 .
虽然在文献中很少提及，但拜占庭广播可用于构建区块链[25]。特别是，如果我们使用拜占庭式的广播协议，可以容忍f≥ 1.2，则生成的区块链将立即能够容忍f≥ 2.1也是。但与此同时，由此产生的区块链吞吐量也将继承拜占庭广播协议的吞吐量。这是主要障碍，因为现有的拜占庭广播协议[6]、[8]、[9]、[14]、[24]、[30]、[31]严重无法提供可接受的吞吐量，如下所示。
throughput：
现有拜占庭广播协议的吞吐量。让我们明确定义吞吐量。假设每个节点都有B个可用带宽，这是部署环境提供的。在这种约束条件下，设x为拜占庭广播协议在时间段y内可以广播的总比特数。我们将协议的吞吐量定义为T=x/y，将标准化吞吐量定义为R=T/B。我们也将R称为吞吐量带宽比或TTB比。此比率基本上用于将协议的固有优点与部署环境的优点隔离开来，因为当在提供更高B的更好环境中部署时，协议可实现的吞吐量自然会增加。显然，R始终在0和1之间，越大越好。
II. S YSTEM M ODEL AND ATTACK M ODEL
我们将散列函数建模为随机预言。我们假设一些初始的可信设置提供了一个genesis块，其中包含一个无偏随机信标，用于第一个纪元。这是股权证明区块链中的典型假设（例如，[7]、[11]）。
Nodes and stakes/coins.我们考虑无许可设置（即，类似于Algand（11）），没有PKI或初始可信设置来绑定节点到身份。系统中的每个节点都持有本地生成的公钥-私钥对，公钥被视为节点的id。每个节点可以是诚实的，也可以是恶意的。恶意节点完全是拜占庭式的，可以任意偏离协议。他们也可能任意串通，我们认为他们都受到对手的控制。我们允许对手具有适度的适应性[7]、[15]、[34]——例如，对手需要多个时期才能自适应地破坏节点。
在我们的无许可环境中，我们依靠利害关系证明（PoS）[7]、[11]、[15]为Sybil辩护：我们假设系统中的一些（或硬币），其中硬币的总数可能随时间而变化。在任何时候，每枚硬币都有一个拥有者，即持有该硬币的节点。同样，所有者可能会随着时间的推移而改变。关于哪些节点持有哪些硬币的信息存储在区块链中，并且是公开的。我们假设在任何时间点，系统中最多有f部分硬币属于恶意节点，其中f是某个不大于0.99的常数。（我们的实验主要考虑F＝0.7）。有时，作为一个垫脚石，我们还考虑了一个简单的N个节点允许的设置，在这里我们用f表示恶意节点的分数。
为了简化周期性信标生成，BC UBE进一步依赖于弱工作证明（PoW）假设：我们假设对手的计算能力最多是诚实节点总计算能力的100倍。该假设独立于早期的f阈值。（如果需要，此“100”值可以在不影响安全性的情况下进一步增加，但会降低性能。）请注意，我们的假设与基于POW的区块链不同，后者的安全性取决于对手的计算能力低于诚实节点。
**Communication **
我们假设所有诚实的节点形成一个连接的覆盖网络——这是大规模区块链系统中的典型假设（例如，[11]）。考虑覆盖层中任意两个相邻的诚实节点A和B。将A和B之间的无向边视为两个方向上的两条有向边是很方便的。关于某个δ1值，我们认为，如果A发送的消息能够在δ1时间内到达（通过适当的重试）B，则从A到B的定向边是好的，只要消息相对较小（例如，≤ 10KB）。否则边缘就不好了。一般来说，在相当大的δ1（例如δ1=10秒）下，人们会期望，尽管某些边有时可能是坏的，但诚实节点中的大多数边将是好的。因此，我们假设诚实子图（即，包含所有诚实节点和所有好边的子图）是连通的。我们用d来表示这个诚实子图直径的上界。
我们假设节点具有松散同步的时钟，因此任意两个节点上的时钟读数相差不超过δ2（例如δ2=2秒）。我们将拜占庭式广播执行描述为一系列轮，每个节点使用其本地时钟来跟踪此执行的开始以及当前轮数。由于δ2时钟误差，我们允许不同节点上每一轮的开始时间稍微不对齐。每轮都有一个固定的持续时间δ=δ1+δ2（例如δ=12秒）。与δ相比，我们假设CPU处理延迟可以忽略不计。在每一轮开始时，节点接收消息，对其进行处理，然后发送新消息。由于δ=δ1+δ2，因此只要消息相对较小（例如，≤ 10KB）。
问题定义。我们的目标是设计一个区块链系统，其中每个节点维护一个仅附加的区块序列。（BCUBE没有分叉，该序列中的所有块都被视为“已确认”。）例如，每个块可以包含事务列表。尽管所有恶意节点的行为都是拜占庭式的，但区块链应该实现标准的安全性和活性保证。粗略地说，安全性意味着所有诚实节点上的序列彼此一致，而活跃性意味着每个诚实节点上的序列随时间不断增长。我们将准确定义推迟到第七节。
III. BACKGROUND ON B YZANTINE B ROADCAST
我们回顾了两个现有的拜占庭广播协议[6]，[8]，它们是BB的基础。为了帮助理解，我们在一个具有n个节点的简单许可设置中描述它们，其中fn是恶意的。我们将首先假设n个节点之间存在一个团拓扑，然后将其推广到任意多跳拓扑。
A. Dolev-Strong Protocol [8]