基于分片的可扩展区块链框架

具有可扩展性的去中心化分片服务网络框架

1 引言

区块链，最初在比特币中提出[1],是一种去中心化分布式服务网络框架，能够在拜占庭容错网络中确保服务节点之间的一致性。中心化系统与区块链之间的显著区别在于，区块链没有专制监管者，且已执行操作无法被否认。大量虚拟货币应用、认证平台以及物联网（IoT）平台正在部署区块链基础设施[35–39]，希望通过区块链降低维护中心化系统的成本。

1.1 区块链中的工作流程

区块链的工作流程可以描述如下：客户端向所有服务节点广播请求，然后服务节点验证这些请求。根据其本地数据库独立进行。之后，每个服务节点选择若干可执行请求，并尝试按照给定规则将其封装成一个区块。区块包含两个部分，分别称为头部和主体。头部主要记录前一个区块的哈希值、主体的摘要、时间戳以及一个称为随机数的特殊随机字符串。区块之间的顺序由哈希值决定，而非全局定时器。区块中的主体包含服务节点选定的多个请求。

如果一个服务器在生成区块期间收到了一个合法区块，它将停止打包，并将接收到的区块追加到其本地链上。之后，该服务器将从新接收的区块开始重新启动打包。然而，有时会出现一种称为分叉的困境：当某个服务器在极短时间内收到多个合法区块时，就会发生分叉。分叉会导致服务器之间的不一致，破坏系统的一致性。区块链中采用单向链表结构的共识机制规定，最长链（包含最多区块数量）是合法的，较短的链将被丢弃。传统上，服务器仅认可最先接收到的区块。当区块链网络中超过一半的服务器对所有区块达成共识时，系统才是正确的。

1.2 问题与挑战

目前，区块链领域最具吸引力的研究集中在安全性和可扩展性方面。区块链中的安全问题主要涉及密码学以及网络中的攻击，包括分布式拒绝服务攻击、女巫攻击和双重支付。[8,9]去中心化区块链中的系统状态由所有服务器投票决定。但网络中的传播延迟和恶意节点可能导致不一致。许多研究人员一直在不懈努力寻找解决方案。埃亚尔·伊泰和埃明·G¨ün Sirer在一篇论文中提出了一个重要发现，指出原始的比特币共识机制忽略了传播延迟。传播延迟可能导致一些诚实节点接受来自恶意节点的错误区块。埃亚尔·伊泰和埃明·G¨ün Sirer规定，服务器应随机选择一个合法区块，而不是采用接收到的第一个区块。此外，这一新规则表明，仅仅拥有大多数（超过一半）是不够的，区块链网络中恶意节点的比例必须不超过四分之一。

同时，区块链的可扩展性也引起了学者们的探索。有三个主要因素制约着吞吐量。首先，在去中心化环境中，区块大小和链的形式极大地限制了吞吐量。我们最直观的优化思路是扩大区块容量。更大的区块可以包含更多的请求。然而，比特币中的扩容协议[16,17]在社区中引发了激烈争议。反对者坚持认为，大数据块会占用更多的传输时间，并增加数据损坏的风险。因此，一些学者转而尝试改变链的结构。约纳坦·索姆波林斯基和阿维夫·佐哈尔相继提出了用树[6]和有向无环图[7]来替代传统的链。在每一轮中，以树或有向无环图形式存在的区块链可以生成多个区块。然而，由于传输延迟的不确定性，具有相同前驱的区块之间的顺序难以确定。该视图关于这些区块可能不一致，从而破坏了系统的一致性。另一个缺点是一些请求可能会被打包进多个区块中。因此，重构链的模式需要一个全局排序算法。

其次，区块链中没有中心化节点，这要求客户端向每个服务器发送请求。在高流量场景下，大规模的广播将引发广播风暴，导致系统无法响应。减少发送消息的规模可以缓解系统的压力。一种有效的减少发送消息的方法是分片，该方法将请求划分为多个集合，并将这些请求映射到相应的委员会。尽管不同集合中的请求互不重叠，但在执行时这些请求仍可能存在冲突。因此，需要统一请求顺序。

最后一个关键要素是拜占庭将军网络中的通信协议。自从兰波特等人提出拜占庭将军问题以来[10],许多研究人员一直致力于提升拜占庭共识协议的可扩展性[19–26]。拜占庭将军问题中的讨论可分为两种不同情况。理想情况是网络中的每个节点都是诚实但易崩溃的。通过选举一个特殊的子委员会来管理整个网络，最优算法可以达到 O(n) 通信复杂度[11]。另一种情况由于网络中存在恶意节点而显得非常不理想且具有挑战性。多年来，许多学者提出了一些具有指数级通信复杂度的协议[12]。斯里坎特等人取得了一项重要改进，其方法达到了多项式级通信复杂度[13],。此外，一些研究人员指出，状态机复制（SMR）是构建容错分布式系统的基本方法[27]。他们引入原子广播[28–33]作为一种重要的通信原语。尽管在拜占庭网络中已提出了大量原子广播算法，然而其中很少有能在无领导者条件下工作的[34]。将原子广播应用于去中心化服务网络具有巨大潜力。

简而言之，提升性能的方法主要集中在两个方向。

领导者选举。

领导者可以确定请求的全局顺序，从而减少开销。例如，比特币‐NG [14]。事实上，传统区块链中使用的常见共识机制，如工作量证明（PoW）[1]和权益证明（PoS）[4],，也是领导者选举的形式。该框架面临两个问题是：一是如何公平地选择领导者，二是当选出多个领导者时如何确保系统一致性。由于独裁者的存在，或多或少都会出现集中化问题。例如，工作量证明存在计算集中化问题。

分片。

分片将较重的通信任务分摊为两个步骤——委员会内部和委员会之间。分片后，不同组在系统可以独立地从客户端选择互不重叠的请求，并将其打包成区块。分片最大的优势是不同的组可以独立生成区块，从而提高系统的吞吐量。然而，分片也存在两个问题。首先，我们无法保证每个委员会都是可靠的，因为在某些组中恶意节点的比例可能超过1/2。另一个威胁是如何在服务器之间就区块的顺序达成共识。代表性架构包括ELASTICO [2],以太坊[15],等。

1.3 贡献

本文提出了一种基于分片和原子广播协议的可扩展分布式框架。我们创新性地引入并改进了环形Paxos[3]以生成区块，取代工作量证明。此外，我们通过让客户端仅需向委员会中的成员广播其请求，从而减小了输入的可扩展性开销。该框架在容忍不超过1/4的自适应拜占庭对手的情况下，能够实现接近线性可扩展性，且可扩展性随服务节点数量近乎线性增长。

为了验证我们的框架性能优于ELASTICO和比特币‐NG，我们构建了一个最多包含1000个节点的模拟实验。由于我们在生成区块时未使用工作量证明，因此我们的框架性能远优于ELASTICO。此外，当网络规模超过约400个节点时，我们的模型表现优于比特币‐NG。

2 系统框架

在正式介绍我们的模型之前，我们首先在第2.1和2.2节中解释术语和一些基本假设。然后我们将详细阐述我们的模型中的工作流程和细节（第2.3至第2.6节）。

2.1 术语解释

定义1（组）。

我们将服务器划分为若干个具有固定成员数量的组（委员会的大小为 C）。如果一个组中恶意节点的比例超过1/2，则将该组标记为无信任；反之，该组将被标记为可靠。

定义2（工作状态和划分状态）。

当某些委员会达到预设阈值且所有委员会已工作足够长时间后，系统将停止工作并短暂进入划分状态。同时，原始组将被分割为至多两个子组。重新分配后，每个组将返回到工作状态。

2.2 假设

客户端与请求。

假设所有客户端都有自己的全局唯一标识符（GUID）、公钥和私钥对。每个请求都将被加密，且无法被篡改。

Servers.

假设所有服务节点都具有全局唯一标识符和密钥对。每个节点要么是诚实节点，要么是恶意节点。此外，所有诚实节点不会永久离线，一旦诚实节点离线，它将尽快重新上线。本系统中恶意节点的比例从不超过1/4。

网络和通信。

假设网络是异步的，这意味着消息在传输过程中可能会乱序、重传和丢失。但消息的内容不会被篡改。每个节点都可以直接与其他节点和客户端通信。

委员会。

每个委员会要么是可靠的，要么是无信任的。可靠委员会中的恶意节点比例小于1/2。我们系统中的第一个组称为 group0，它是可靠的。每个委员会初始化时包含 C个成员。普通组中的成员数量范围从 C+1 2 到 2C。成员数不超过 C的委员会需要至少 C+1 2 张投票才能通过提案，而更大的组则需要超过一半的投票。

2.3 系统概述

将服务器划分为多个委员会是我们的核心概念。正如我们之前提到的，具有分片特性的去中心化框架需要一种全局排序算法来排列区块。因此，我们引入了一种树结构来决定组的顺序。该树中的每个节点分别对应一个链段以及负责维护该链段的组。通过这棵树，我们可以利用树遍历算法对委员会进行排序。

工作状态下的工作流程主要包含三个步骤。首先，每个组根据原子广播协议独立生成区块。其次，各组的领导者之间相互交换区块，并在各自组内同步区块。最后，所有服务节点独立校验区块，并将可执行的区块写入其本地数据库。区块链的形式可以如图1。

当某些组达到预设阈值时，它们将约定分裂的时间点，并将该时间点通知其他组。在我们的系统中，过大的组（大小为 2C）将最多被分裂为两个大小为 C 的部分。在同步区块后，其他组将获知该变更并更新其视图。分割完成后，原始组终止，其所维护的链段将被封存。

2.4 生成区块

与传统的生成区块方法不同，我们利用原子广播在组内构建区块。原子广播可以消除分歧并保证集群内一致性，因此我们引入原子广播作为组内生成区块的通信协议。本文中，我们采用了一种环形Paxos的变体算法。算法1展示了变体环形Paxos。

算法1. 变体环形Paxos

1: 任务1 (Leader)
2: //收到足够多的请求 R
3: b=生成区块 (R)
4: 广播 (b, others)
5: 令环为委员会内的覆盖环
6：任务2 (AllNodes)
7: //收到 b后
8: 如果 first (ring) 那么
9: 启动 (poll)
10: 追加 (poll)
11: 发送 (successor, poll)
12: 结束 if
13: 任务3 (AllNodes)
14: //收到发送 (successor, poll)
15: 如果 不是最后一个 (ring) 那么
16: 追加 (poll)
17: 发送 (successor, poll)
18: 否则
19: 广播 (poll, others)
20: 结束 如果

在算法1中，我们引入了两个额外的变量。环是决定组内成员顺序的一个序列。投票包含每个节点关于是否执行请求的意见。注意，投票是仅可追加且由所有成员加密的。此外，领导者不仅是环中的第一个节点，也是最后一个节点。

首先，领导者将一些请求打包成一个区块并广播给其他节点。之后，领导者会发起一个投票并将其随同环发送出去。当节点收到投票时，会附上自己的视图并进行加密。当领导者收到投票后，会将其广播给其他成员。随后，每个节点将检查投票并对获得半数以上投票的请求执行请求。

进一步观察可以发现，变体环形Paxos在每一轮都需要一个领导者和一个环。我们必须提供一种公平的方式来选举领导者并构建一个环。当委员会诞生时，会发现一个特殊的区块，称为同步信号。这个特殊区块是不可预测的。因此，我们可以使用种子来生成新组中的第一个领导者。构建环实际上要容易得多。我们可以通过以不同的头部旋转环来获得多个不同的环（例如，图2）。然而，领导者可能在工作期间崩溃。在生成区块过程中会出现若干异常。

2.5 委员会内同步

执行算法1后，领导者将向其他领导者发送其区块和投票。当领导者接收到带有其投票的区块时，他会向自己的组成员广播。正如我们之前提到的，我们引入了树结构来映射组与树中的节点。因此，我们可以使用树遍历算法在各组之间对序列达成共识。

同步区块后，一项重要任务是在下一个时期选举领导者。显然，仅使用其组内生成的区块的哈希值是不公平的，因为当前领导者可以精心选择请求并找到一种特殊组合以实现连任。但来自其他委员会的区块并非全部可预测。因此，我们按照组的顺序重新组织区块，并构建一棵默克尔哈希树。根节点中的哈希值，称为seed，将决定下一个领导者是谁。

此外，领导者在此步骤中可能离线。我们必须制定一项策略来处理此类事故。

显然，恶意领导者可以故意在委员会之间制造分歧。因此，我们需要进行两轮广播来消除不一致。在第一轮中，领导者将相互发送和接收区块及投票。经过足够的间隔后，每位领导者将广播其缺失情况，并尝试填补空缺。在理想环境中，我们的模型在此同步过程中仅需两次广播。

2.6 拆分委员会

拆分委员会也需要公平性。因此，我们重用第2.5节中提到的种子来分裂组。拆分委员会的任务包括检查节点质量、分割过大的组以及在新组中构建环。

与生成区块不同，拆分委员会是本框架中最耗费资源的操作，因为我们需要所有服务器执行工作量证明以验证其真实性。这是因为恶意势力可能通过伪造数千个虚拟服务节点发起女巫攻击。当某个节点找到符合要求的答案时，会向原始组中的其他节点广播该答案。当服务器收到其他节点的工作量证明结果后，将独立对其进行排序。

达到峰值的委员会将被拆分为最多两个大小为 C 的部分。因此，本轮的领导者将最多生成两个同步信号。未能成功建立组的节点将被丢弃并重新加入网络。该机制还确保了服务网络中服务器的质量。算法2描述了拆分委员会的过程。然而，无需急于将此变更通知客户端。假设客户端不知道该变更，并将请求发送到已过期的组。原团队的成员已分散到两个新组中，会向客户端回复该修改信息。因为新生组继承其父级规则并对其进行扩展，映射到旧组的请求必然落入由其父组派生的某个组中。

算法2。 拆分委员会

任务1 (AllNodes)
2: 答案=工作量证明 (seed)
广播 (answer, others)
4: 任务2 (AllNodes)
收到来自 othersnodes的答案后//
6: 排序 (results)
任务3 (Leader)
8: groupNumber= 0
收到标记为 A的答案 C//
10: 当 groupNumber< 2 时执行
b= generateBlock (A)
12: 变体环形Paxos (b)
++ groupNumber
14: 结束 while
任务4 (AllNodes)
16: //收到同步信号 A 时
ring=sort (A)
18: 更新组()

接收到同步信号后，下一步是在每个新生的委员会中建立一个环。由于每个节点的答案都是不可预测的，因此答案的排序序列将被视为它们新环中节点的顺序。

3 系统分析

在本节中，我们对框架如何防范潜在威胁并安全运行进行分析。同时，我们将解释本文中一些关键参数的意义。

不失一般性，我们假设网络包含 N个具有等效资源分配的服务器。系统中恶意节点的比例为 f（0 ≤ f< 1/2），恶意节点的数量为 Nm（Nm= N·f）。组的正常容量为 C，组的数量为 K。为了简化起见，我们假设 N= C · K。其他假设已在第2.2节中介绍。

3.1 安全分析

系统安全定义为系统中无信任组的比例，当系统中恶意节点的比例小于 f时，系统安全永远不会达到 2f。

证明概要。

我们使用 N1 m和 N2 m分别描述无信任委员会和可靠委员会中的恶意节点数量。显然，Nm= N1 m + N2 m （0 ≤ N1 m , N2 m ≤ Nm）。恶意力量将试图最大化节点间的分歧。污染诚实节点的唯一方法是占据委员会中超过一半的集合，并误导少数诚实成员跟随恶意行为。恶意目标可以在公式(1)中表示。

$$

\\max\\left{\\left\\lfloor \\frac{N^1_m}{\\left\\lceil \\frac{C+1}{2} \\right\\rceil} \\right\\rfloor \\cdot C + N^2_m\\right} \\tag{1}

$$

我们可以发现，当N2 m= 0时，公式(1)达到峰值，最大值为 $\\left\\lfloor \\frac{f·C}{\\left\\lceil \\frac{C+1}{2} \\right\\rceil} \\right\\rfloor · C$。公式 (2)中最大值的第一项限制表明，当系统中恶意节点的比例小于 f时，我们系统中无信任组的比例永远不会达到 2f。因此，只要无信任组不超过一半，即可保证系统安全，这要求 f< 1/4。

$$

\\lim_{C \\to \\infty} \\frac{f \\cdot C}{\\left\\lceil \\frac{C+1}{2} \\right\\rceil} = 2f \\tag{2}

$$

3.2 性能分析

在本节中，我们将分析去中心化服务网络框架中的三个核心指标，包括吞吐量、延迟和消息数量。同时，我们将其与比特币、比特币‐NG和ELASTICO进行比较。在分析中，我们考虑系统稳定运行时一个工作量证明间隔内的期望时间，并在此间隔内权衡这些指标。此外，我们统一了不同框架中区块的格式以及委员会的大小。并且假设系统中无崩溃且无恶意行为。

延迟。

直观上，本文中的延迟指的是从打包区块到在系统中达成共识的时间。给定一个时间 t和一个比例 x（0< x ≤ 1），x点表示最小的时间差 y，使得在时间 t至少有 x · N的节点报告相同的状态前缀，直到 t − y。形式上，系统的（ε, δ）共识延迟是 ε‐百分位 δ‐点共识延迟。我们要求在至少90%的时间内，至少75%的节点对系统状态达成一致。比特币中的延迟可以视为工作量证明耗时与传播延迟的上四分位数之和。然而，比特币‐NG中的延迟仅表现为传播延迟的上四分位数，因为在领导者的任期内会生成多个区块。ELASTICO的情况更为复杂。在每个周期中，ELASTICO要求所有节点自行完成工作量证明，然后广播其证明以建立委员会。之后，ELASTICO利用PBFT[18]在每个组内生成区块，并将该区块发送至第一个组，即最终委员会。随后，最终委员会运行相同的PBFT协议以对最终结果达成共识，并向整个网络广播。相比之下，我们的情形要简单得多。在委员会内部，变体环形Paxos需要两次广播和 C次单播。然后领导者将相互发送消息，并在两轮中检查缺失区块。之后，领导者将向其组内的所有成员广播回复，这需要另一次广播。我们使用 PoW来表示期望时间工作量证明，B表示在整个网络中广播的期望时间的上四分位数，S表示单播的期望时间。为了简化比较，我们假设集群内广播的期望时间的上四分位数恰好为 $ \\frac{1}{k} \\cdot B $ 当集群包含 $ \\frac{1}{k} $ 个成员时。表1显示了这四种框架中的延迟。如果我们认为在任意规模的网络中，单播和广播所花费的时间相同，均为 T，则ELASTICO中的共识延迟为 PoW+ 7T，而我们的共识延迟为（C+ 3/k+ 2/C）· T。假设工作量证明为600秒，且传播一个1MB大小的区块大约需要1秒，则当我们的共识延迟短于ELASTICO时，C的取值可被限制在 0< C< 600以内。然而，ELASTICO中委员会的推荐大小约为600，而ELASTICO的实验则将组的容量固定为100，这是PBFT性能的上限。

在委员会内同步中，领导者需要进行两次广播以交换他们的区块。这正是我们系统中的瓶颈所在。随着系统规模的扩大，同步过程中的时间延迟会随着委员会组数量的增加而上升。

表1. 四种去中心化框架中的延迟

延迟

吞吐量。

吞吐量表示打包和响应客户端请求的能力。我们分析一个周期内的吞吐量，并以比特币的吞吐量作为基准。在每个周期内，比特币平均期望生成一个区块，耗时10分钟。比特币‐NG的输出可根据共识延迟预先设定。因此，该框架中的吞吐量可由公式（3）描述，表2展示了理想条件下平均的吞吐量。

$$

\\text{Throughput} = \\frac{\\text{Number of Blocks}}{\\text{Expectancy Delay}} \\tag{3}

$$

表2. 期望吞吐量

吞吐量

消息数量。

该指标反映了去中心化系统中的可扩展性以及带宽消耗。比特币和比特币‐NG 的成本均达到 O(n)。在 ELASTICO 的委员会形成过程中，所有节点需要识别自身并找到下一个时期的新组，从而产生 O(nc) 条消息。委员会内生成区块以及在中心化组内重新组织区块均由于 PBFT 需要 O(c²)。因此，ELASTICO 的可扩展性可达 O(nc²)。我们的框架引入了变体环形Paxos作为生成算法，将消息数量减少到 O(n²)，但代价是高延迟。委员会内生成区块需要 3C条消息，而委员会之间的同步需要 n²/C条消息。之后，领导者将在其集群内广播区块，消耗 N条消息。因此，本框架中的消息复杂度为 O(n²)。

4 实验

我们在内部模拟了一个包含 1000 个虚拟节点的去中心化分布式平台。为了节省时间，我们引入了事件驱动机制而非定时器。我们平台中的每个节点具有相同的资源分配，并且可以直接与其他所有节点通信，这意味着带宽消耗可能非常巨大。等效分配的好处在于，我们可以使用随机数生成器来决定每轮的领导者，而不会造成较大的能耗。区块大小为 1MB，网卡带宽为 100 Mbps，在实验中我们强制节点尽可能充分利用其带宽。为了减少偶然因素的干扰，我们在实验中连续记录了 10 轮。

我们在实验中预设工作量证明耗时为 600 秒。实验中委员会的大小固定为 100 个节点。仿真实验结果明显表明，ELASTICO 在传播延迟方面的性能最差。ELASTICO 存在两个致命缺点：其一是 ELASTICO 要求每轮通过工作量证明计算身份，耗时约 10 分钟；另一个是 PBFT 的局限性。PBFT 主要通过三个步骤在集群内达成共识：第一步是领导者在委员会内广播区块；第二步要求每个成员向集群中的其他成员广播其视图；这一大规模广播在第三步中会再次发生。整个过程的消息成本为 2C² + C。此外，组的数量增长将加重中心化委员会的负担，因为来自所有子委员会的区块都会发送到中心化集群的每个成员，大量的消息将迅速消耗其中心节点的带宽（图3）。

ELASTICO中的相同威胁也存在于我们的分片框架中。然而，我们通过使用变体环形Paxos替代PBFT，在增加延迟的代价下减少了消息数量，并且利用两次广播在领导者之间达成共识，而不是依赖中心化机构。

当网络规模超过400个节点时，比特币‐NG的表现不如我们的模型。尽管比特币‐NG在每次同步中仅需要 N条消息，但在大规模系统中，领导者的带宽将成为瓶颈。

5 未来工作

根据上述分析和实验，我们的模型似乎非常高效。然而，我们的系统确实存在一些缺点。首先，我们模型中的服务节点需要存储所有客户端和其他服务器的 UID及公钥，这需要大量的内存。该内存可能成为我们服务器中的新瓶颈。其次，我们的框架具有两种不同状态。当系统进入分裂状态时，由于所有服务器都需要通过工作量证明来证明它们不是虚拟节点，因此系统无法处理请求。这意味着我们的框架可能会间歇性地保持静默。

在未来研究中，我们将进一步努力完善框架中的细节并对其进行优化。同时，我们也关注原子广播的发展及其应用。