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

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

1 引言

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

1.1 区块链中的工作流程

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

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

1.2 问题与挑战

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

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

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

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

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

领导者选举。

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

分片。

分片将较重的通信任务分摊为两个步骤——委员会内部和委员会之间。分片后，不同组在系统可以独立选择来自客户端的不相交请求，并将它们打包成区块。分片的最大优势在于不同的组可以独立生成区块，从而提高系统的吞吐量。然而，分片也存在两个问题。首先，我们无法保证每个委员会都是可靠的，因为在某些组中恶意节点的比例可能超过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）和公私钥对。每个请求都将被加密，且无法被篡改。

服务器.

假设所有服务节点也都具有全局唯一标识符和密钥对。每个节点要么是诚实的，要么是恶意的。此外，所有诚实节点不会永久离线，当诚实节点离线时，会尽快重新上线。本系统中恶意节点的比例永远不会超过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后，领导者将把他的区块和投票发送给其他领导者。当领导者收到带有其投票的区块时，他会向他的组成员广播。正如我们之前提到的，我们引入了一种树形结构来将映射组与树中的节点关联起来。因此，我们可以使用树遍历算法在各组之间就顺序达成共识。

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

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

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

2.6 拆分委员会

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

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

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

算法 2。 拆分委员会

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

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

3 系统分析

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

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

3.1 安全分析

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

证明概要。

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

$$

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

$$

我们可以发现，当 N₂ₘ = 0 时，公式(1)达到峰值，最大值为 $\\left\\lceil \\frac{f \\cdot C}{\\left\\lceil \\frac{C+1}{2} \\right\\rceil} \\right\\rceil \\cdot 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%的节点对系统的状态达成一致。比特币中的延迟可以视为 PoW耗时与传播延迟的上四分位数之和。然而，比特币‐NG中的延迟仅表现为传播延迟的上四分位数，因为在领导任期期间会生成多个区块。ELASTICO的情况更为复杂。在每个周期中，ELASTICO要求所有节点先自行完成工作量证明，并广播其证明以建立委员会。随后，ELASTICO利用PBFT[18]在每个组内生成区块，并将该区块发送至第一个组（称为最终委员会）。然后，最终委员会运行相同的PBFT协议以对最终结果达成共识，并向整个网络广播。相比之下，我们的系统场景要简单得多。在委员会内部，变体环Paxos需要两次广播和 C次单播。之后，领导者将相互发送消息，并通过两轮检查缺失的区块。此后，领导者将向其组内的所有成员广播回复，这需要另一次广播。我们使用 PoW来表示期望时间工作量证明，B表示在整个网络中广播的期望时间的上四分位数，S表示单播的期望时间。为了简化比较，我们假设在集群内广播的期望时间的上四分位数恰好为 (1/k) · B当集群包含 (1/k)个成员时。表1显示了这四种框架中的延迟情况。

如果我们认为在任何规模的网络中，单播和广播所花费的时间相同，均为 T，那么ELASTICO中的共识延迟为 PoW + 7T，而我们的系统中的延迟为（C + 3k + 2/C）· T。假设工作量证明为600秒，且一个大小为1 MB的区块大约需要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轮。

我们预设PoW耗时为600秒。在实验中，委员会的大小固定为100个节点。

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

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

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

5 未来工作

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

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