无冗余可变难度值平行区块链协议

Non-Redundant Parallel Blockchain Protocol with Variable Difficulty

摘要

为解决传统区块链协议的可扩展性差问题，提出一种结构化且安全高效的区块链协议。将单一链扩展为多条平行链来提高区块链吞吐量，并设计交易验证模式解决交易冗余问题。提出可变难度值的出块机制，提高协议适用性并保证其平稳运行。通过设计适用于平行链的区块序列化机制，优化区块确认延迟。分析区块链关键性质和潜在安全威胁以保证安全性。实验评估结果表明，本文协议可有效改善区块链的吞吐量、确认延迟等性能，可以解决区块链可扩展性问题。

Abstract

In order to solve the problem of poor scalability of traditional blockchain protocols, this paper proposes a structured secure and efficient blockchain protocol. We scale the single chain to multiple parallel chains to increase blockchain throughput and design a transaction verification model to solve the problem of transaction redundancy. Then we propose a variable difficulty value block-generating mechanism to improve the applicability of our protocol and ensure robust execution. In order to optimize block confirmation delays, we design a block confirmation mechanism applicable to parallel chains. Finally, we analyse the key properties and potential security threats of blockchain to ensure the security of the protocol. Our experiment evaluation verifies that our scheme can effectively improve the performance of the blockchain in terms of throughput and confirmation delay. So our protocol can solve the problem of blockchain scalability.

Graphical abstract

0　 引 言

区块链技术源于2008年中本聪发明的比特币^[1]，可看作一个公开不可变的分布式账本。矿工（区块链参与者）收集交易后需解决计算难题才能生成区块，这就是所谓的工作量证明（Proof-of-Work,PoW）机制。比特币所用的中本聪协议是最早采用工作量证明机制的区块链协议，中本聪协议实现简单并被证明具有很高安全性^[2]，但由于其吞吐量低、延迟高（每秒处理7笔交易，区块需等待6个后续区块才能被确认，平均区块间隔为10 min），因此其可扩展性较差。

目前关于解决中本聪协议可扩展性问题的研究层出不穷，这些研究大致可分为优化中本聪协议和改进区块链结构两个方向。文献[3~7]对中本聪协议进行优化，主要包含改变区块大小和降低区块难度两类工作。文献[3]突破中本聪协议中对区块大小的限制，增大区块容量直接增大吞吐量，但文献[8]证明直接改变区块大小会导致区块延迟骤增使得分叉率变大，影响系统安全性。文献[4~7]通过降低区块难度来提高出块速率，但是他们采用单链结构，直接降低出块难度会使得攻击者可以针对低难度区块序列实施自私挖矿攻击^[9]。上述工作虽然在一定程度改善了中本村协议的吞吐量，但受限于单链结构，对可扩展性提升有限。文献[10~12]对区块链结构进行了改进，突破传统的单链结构，利用有向无环图（directed acyclic graph, DAG）组织区块，保留多个分支并发产生的区块。虽然DAG结构可以有效改善吞吐量，但是该结构的多个分支可能会不断发散，导致区块链结构不稳定，难以维护区块时序关系，造成系统安全性证明复杂并且难以实现。比如文献[10]给出了DAG结构的理论方案但未提供具体实现细节，文献[12]为了避免处理复杂的区块关系，在对区块进行确认时将DAG结构压缩为单链，这实际限制了其性能。

为实现与DAG结构类似的并发出块功能并防止链结构发散，近年一些研究提出平行结构^[13~17]，进一步改善可扩展性。平行结构的主要思想是m-for-1挖矿（1.2节详述），将单链扩展为多条平行且对等的链，可以稳定地提高区块链吞吐量。尽管已有的平行链确实可以改善区块链的可扩展性，但它们仍有一些未解决的问题：

首先，分布式环境中的同一笔交易可能被打包到不同区块，即所谓的交易冗余问题。平行结构的区块是并发产生的，出现交易冗余记录的概率更高。已有的工作要么未考虑该问题，要么简单地忽略重复交易。这种在区块发布后忽略重复交易的方法虽然可以避免交易冲突，但会造成矿工计算和区块空间的浪费。平行链结构中，在区块发布前处理交易冗余是一个待解决问题。

其次，采用工作量证明机制的区块链需适应挖矿能力的不断变化。比特币诞生至今挖矿能力增长近10¹⁴倍，如果仍采用最初的难度值解决哈希难题，出块间隔会从10 min下降到6 ps（1 ps=10^-12 s），造成过高的分叉率，容忍恶意节点的能力从二分之一下降为千亿分之一，严重破坏安全性。已有的平行链协议均采用固定难度，设计适用于平行链的可变难度值机制是一个待解决问题。

最后，获取全局区块序列是保障区块链账本最终一致性的关键。区块链的执行是一个不断追加新区块到确认区块序列的过程，平行链中不同链上的区块关系并不直观，获取全局区块序列需要考虑多条链区块的时序关系。文献[13]预定义区块确认顺序，但预定义的区块确认顺序和区块加入区块链的时间顺序可能不一致，存在交易冲突的安全威胁。文献[14]的确认方案依赖于多条链中的某条特殊链进行时钟同步，若该链不增长将会影响全局区块确认。安全高效地确认平行链中的区块并给出全局区块序列是一个待解决问题。

本文主要贡献如下：

1） 提出无交易冗余的平行链协议。基于m-for-1挖矿思想提出平行链方案稳定地并行出块，设计新的交易整合结构，稀疏默克尔树（sparse Merkle tree, S-MerkleTree），在区块发布前避免交易被重复记录，有效提高实际的吞吐量。

2） 设计适用于平行链的难度值调节机制。基于比特币的难度值调节算法，设计适用于平行链的难度值变化机制，使得本文平行链具备自适应性。

3） 构建全局序列化机制。克服已有工作的不足，提出分布式环境中区块并发时的确认方案，得到全局区块序列，改善区块确认延迟。

此外，进行安全性分析和实验评估，保证本文方案可有效解决区块链的可扩展性问题。

1　 背景知识

1.1　中本聪协议

区块链中区块的产生和发布需要依赖共识机制，比特币采用中本聪协议。矿工收集交易后，首先验证其合法性，然后利用工作量证明机制产生区块。矿工需找到一个随机数来计算出满足难度值的区块哈希，这个过程通常被称为挖矿。找到解决难题的随机数后，挖矿过程结束，得到新区块。区块主要包含以下几个字段：双亲哈希（前一个区块的哈希值）、时间戳、交易的默克尔根、交易列表以及随机数。产生一个新区块后，矿工将其广播到全网。其余矿工收到该区块时验证完整性并校验区块哈希是否满足难度值，验证通过后矿工更新本地数据库。超过半数的节点更新数据库后，全网的状态发生更新。区块之间通过引用双亲哈希彼此相连，构成单一链结构，利用区块高度对区块排序进而得到交易账本。

1.2　 m-for-1挖矿思想

中本聪协议执行的理想情况是全网保持较高的同步，当矿工收到新的区块B_n 后立即基于它挖掘下一轮区块B_n+1。但由于网络延迟，矿工可能未收到区块B_n 而产生了新区块B_n+1，此时两个区块处于同一个区块周期，引发区块链分叉。中本聪协议等待一段时间后依据最长链原则保留一个分支作为主链。

本文采用的m-for-1挖矿思想可以保留多个分支的区块。文献[2]提出了一种称为2-for-1PoW哈希分类方法，将一次工作量证明机制的计算用于两个不同的区块链协议，该分类方法是m-for-1挖矿思想的基础。在m-for-1挖矿中，矿工可以在m条链进行挖矿，但是每个被挖出的区块只能追加到其中一条链。矿工收集m条链的末尾区块的区块哈希作为PoW的输入。当找到一个有效的随机数时，PoW计算可输出一个合法的区块哈希，该区块哈希的后log m位可以决定该区块归属于哪一条链。由于哈希计算具有随机性，每条链有相同的机会收到有效的区块，因此可以保持每条链的平均出块速率相同。m-for-1挖矿思想设定区块难度为中本聪协议的m倍，用B.h表示区块哈希，D_n 表示中本聪协议区块难度，中本聪协议B.h<D_n，本文协议为B.h<mD_n。区块被分散到m条链，所以平行链的每条链的出块概率和中本村协议是一样的。

1.3　自适应调节技术

中本聪协议采用固定的区块难度，随着节点计算能力的增加，区块间隔迅速下降，造成安全威胁。文献[2]提出依据过去2 016个区块的平均出块间隔计算新区块的难度值，维持平均每10 min一个区块。此外，近年一些研究^[18，19]提出了对DAG结构的自适应调节方案。文献[18]提出针对DAG的并发区块的自适应调节方案。它包含主区块和子区块两种数据结构，子区块生成速度较快，多个子区块和上一个主区块构成DAG结构，整体可看作多个DAG结构相连。通过维持两个主区块之间子区块的数量与难度值系数的比值，调节子区块数量自适应调节吞吐量。文献[19]动态调节DAG规模适应于不断变化的交易池，监测区块内交易数量。如果区块内平均含有交易较少说明分支过多，增大出块难度收缩DAG分支，反之减小出块难度扩大DAG分支。已有平行链方案^[13~17]不具备自适应力，上述方案无法直接适用于本文的平行链，基于上述技术设计适用于平行链的可变难度值机制，提高本文区块链协议的适用性。

2　 系统模型和问题描述

2.1　系统模型

本文的系统模型和假设基于文献[20，21]，相关符号定义如表1。一个区块链协议Π可看作一个用于多个区块链参与者交互的算法。协议的执行环境由n个参与者构成，参与者可以诚实地执行协议，也可以任意地偏离协议，系统最大容忍恶意节点的比例。本文区块链协议周期性执行，在每个周期，参与者可以从执行环境获取信息（交易或区块），然后利用随机哈希函数H计算新区块哈希并检查其是否满足难度值。在每次计算中，参与者挖出新区块的概率是mp，其中m是平行链数量，p是中本聪协议的区块生成概率。

诚实的参与者之间可以彼此传播消息，攻击者无法修改来自诚实参与者的消息，但是可以选择延迟广播或者改变消息的顺序进行广播。假设消息的传播延迟上界为Δ，以区块间隔为单位，表示区块B生成后最多经过Δ个出块间隔后会被传播到所有节点。比如，当区块间隔设定为10 s时，区块必须在10 s内传播到其余节点。参与者利用Gossip协议广播信息，在连接良好的P2P网络中Δ几乎保持不变。

2.2　问题描述

本文的目的是设计一个无交易冗余且难度值可自适应调节的平行区块链协议。该协议利用平行结构并发产生区块，同时解决交易被重复记录问题。区块难度值和区块间隔成反比例，即出块间隔小时区块难度增大，反之区块难度减小，并且保证难度值平缓地改变以及全局区块难度一致。此外，需保证在一定时间后诚实节点的交易被记录到区块链，并且所有的诚实节点的确认区块序列相同。

区块链协议如果要维持一个公开的交易账本，系统需要考虑安全性、活性、容错性三个属性。安全性保证账本的最终一致性。当一笔交易写入账本一段时间后，认为其被篡改的概率极低，所有诚实节点都可以在自己的账本中定位到该交易。活性保证系统不断向前推进，在一定的时间限制内，节点会将合法交易添加到自己的账本。容错性主要指对恶意节点的容忍能力。当恶意节点占少数时，需要分析区块链协议的安全性和活性。获取全局确认区块序列是保证上述属性的关键。安全性和活性在区块链协议中对应于一致性和增长-质量两个性质，将在第4节证明本文协议满足上述属性。

3　 方案设计

本小节首先给出了无冗余平行区块链协议方案，描述挖矿过程并构建平行链结构，提出冗余交易的解决方法；其次，结合平行链结构给出难度值调节方案，维持区块间隔稳定；最后，给出获取平行链的全局确认区块序列的方法，保证交易账本的最终一致性。表2定义了后续用到的相关名词。

3.1　无冗余平行链协议

平行挖矿机制旨在将中本聪协议的一条链扩展为多条链。初始m个创世区块，作为m条链的初始时的末尾区块，代表区块链的当前状态。矿工在哈希计算前整合m个末尾区块，得到新区块后，按照区块哈希的后log m位将新区块分类归属到某一条链。和中本聪协议不同，本文协议中多个矿工的区块都可以被保留。考虑同时期的多个区块都被保留时，同一交易可能会被不同区块重复打包，本文在并发出块时将不同交易分散到不同链。建立交易ID和链归属的映射关系，进行交易分类。不同区块保留不同交易，m类交易会被m条链记录。

3.1.1　区块和平行链

本文的区块链由m条平行的链组成，如图1所示。每条链由一个链标识i识别（Chain _i，i∈{0,1,…,m-1}），每条链由一个创世区块G_i 初始化。矿工采取m-for-1思想同时在m条链上挖矿，每个被挖出的区块B都只追加到某一条链Chain_ch(B)。

区块包含时间戳、随机数、前置信息（前置默克尔根ParentMT.root、双亲区块哈希PreBlock）、确认信息（同步区块哈希SynBlock）、交易信息（交易默克尔根TransMT.root、交易列表）和相关证明。为了简化，每个挖出的区块用B_ij 表示，其中i=ch(B)，j是区块周期，i、j可以在平行链中确定一个区块的位置。区块B_ij 可以用一个元组(h_-1,μ,p,t,s,h)表示，其中h_-1表示双亲区块B^-1的区块哈希（B.h_-1=B^-1.h=PreBlock），μ表示随机数，p表示前置区块合集，t表示交易信息，s表示确认信息，h表示区块B_ij 的哈希。p、t、s包含默克尔树信息和相关证明。

定义1（区块）：如果一个区块B是合法区块，它满足下述条件：

• H(B.h_-1,B.μ,B.p,B.t,B.s)<mD_n，其中m∈[1,2^κ/D_n ]，D_n 表示比特币的区块难度。

3.1.2　平行挖矿机制

节点只有收到一个新周期的区块时，才开始下一个周期的挖矿。本文的平行挖矿过程如图1，伪代码逻辑如算法1和算法2。协议首先为m条平行链生成m个创世区块进行初始化，之后进入挖矿阶段，挖矿阶段包含元信息收集、区块生成、广播验证三个阶段。

1） 元信息收集。要收集的信息包含前置信息、交易和确认信息三种。对于前置信息，多个矿工可同时在多条平行链挖矿，每个链当前的末尾区块是多个前置区块，收集这些区块的哈希值作为前置信息。对于交易，考虑冗余记录问题。希望不同的并发区块包含不重复的交易，不同链的交易分类不同。多个矿工依据随机的区块哈希将区块分类追加到m条平行链，但矿工在工作量哈希之前无法预知区块未来的链归属，而且不同链归属要求不同区块内容。本文利用默克尔树的存在性证明实现上述目的。对于确认信息，主要收集同步区块哈希SynBlock（第3.3节介绍）。所以，在信息收集阶段，可看作矿工首先生成一个“全”区块B^*，它包含一个区块可归属到任意链的信息，这个信息包括所有前置区块的哈希、所有的交易和确认信息。

2） 区块生成。处理收集的信息并变化随机数，进行工作量哈希计算。“全”区块B^* 可看作区块B在得到区块哈希之前的状态。利用本文设计的稀疏默克尔树整合交易得到交易树（TansMT=B^*.t.SMTroot），利用默克尔树整合m个前置区块得到前置树（ParentMT=B^*.p.MTroot）。构建预备区块头，preHead=(B^*.p.MTroot,B^*.μ,B^*.t.SMTroot,B^*.s)。不断变换随机数μ，当H(preHead)<mD_n 时，满足工作量目标，得到合法区块。中本聪协议的区块哈希必须有log（1/D_n ）个前导零，本文区块哈希必须有log（1/mD_n ）个前导零。依据区块哈希B.h的后log m位确定链归属ch(B)。

得到区块哈希和链归属后，将“全”区块的信息保留一部分填充到区块体生成新区块B。不同链归属的区块将保留不同的交易列表和双亲区块哈希，填充对应的区块体信息并补充成员证明，以保证数据的完整性和合法性。

3） 广播验证。区块填充完成表示新区块生成。矿工利用P2P网络广播区块，其余矿工收到区块后验证区块合法性并更新本地数据库。平行链中每个矿工都执行m-for-1挖矿，可在m条链挖矿但每次只追加到一条链。当有多个矿工同时挖矿时，多个区块被哈希分类到不同的链，全局表现为同一周期并发出块。尽管同周期的区块产生时间相近，但收到区块的矿工还是会按照时间顺序逐个接收。

3.1.3　无交易冗余设计

依据m-for-1挖矿思想，矿工不知道自己正在挖的区块将会追加到哪一条链，因此他们在收集信息时需准备所有的交易，但保留所有的交易会造成区块空间负担和交易冗余。本文结合平行链结构，不同矿工在并行出块时保留各自“全”区块中不同的交易列表，将交易按照“类型”分散到不同的链。

为实现这一目的，本文优化默克尔树结构为稀疏默克尔树S-MerkleTree来整合交易，如图2所示。首先，交易按照交易ID的后log m位被映射为m种类型，对应m条链。矿工为每条类交易构建传统默克尔树，得到m个树根ω_i。然后，使用(hash _i,ω_i )再次作为默克尔树的叶子计算树根ω，整体构成S-MerkleTree。最后，树根ω就是所需的交易根，参与工作量证明的哈希计算，用于之后验证交易的完整性。工作量哈希计算完成后，根据区块的链归属ch(B)填充区块B的区块体，保留S-MerkleTree中第ch(B)个分支下的交易列表到区块B，并提供(hash_ch(B),ω_ch(B))分支的默克尔证明。其余矿工收到区块B后可根据链归属ch(B)验证交易列表的一致性，根据默克尔证明验证交易列表的完整性。

本文的无冗余设计与一些分片方案^[22]有类似的目的，但本质上不属于同一类技术。分片技术对区块链节点进行网络分区，将交易分散到不同的片区。本文方案不对节点进行划分，只对交易进行分类打包。分片中交易分散后需处理不同片区间的跨片交易。本文的矿工共享全网交易，在打包交易时避免重复记录而设计上述无冗余方案。

3.2　可变难度值机制

3.2.1　相关知识

比特币难度值调节算法有三个关键思想：1） 依据过去的区块间隔来改变区块难度；2） 使用最重链原则（区块难度值求和）代替最长链原则决定账本；3） 每个挖矿周期只允许对区块难度值进行微调。

将工作量证明机制挖矿中解决哈希难题的阈值称为区块目标值。每个区块的区块难度值表示当前区块相较于创世区块的难度倍数。一条区块链的链难度值是组成该链的所有区块难度值的总和。链难度值最大的链被称为最重链。区块的链难度值指的是以该区块结尾时当前区块链的链难度值。

3.2.2　平行链难度值调整方法

已有的平行链方案^[13，14]都采取固定难度值，未实现可变难度值，本文在平行链中实现可变难度值很有意义。目前，结合比特币难度值调节算法，实现平行链的难度值调节有两种方式。一是将比特币的难度值调节算法独立地应用于每条链，但是这无法和m-for-1挖矿思想兼容。区块依据区块哈希被随机分散到多条链构成平行结构，某个区块在工作量证明时需要整合其他链的末尾区块信息，在哈希计算之前不可预测区块的链归属，因此无法在哈希计算时确定该区块所需达到的难度值，所以上述单链难度值调节算法无法直接应用于平行链。二是利用所有链的平均区块间隔计算挖矿所需的区块难度，所有链使用公共的难度值。但是这个公共难度值的选取需要各个链高度同步，这在区块链的分布式环境难以实现。

本文提出一个通用的方法来实现平行链的可变难度值挖矿。主要包含三个关键原则：

原则一：选取轴心链。使用平行链中的一条链作为轴心链进行难度值调整，其他链在生成区块时需参考轴心链的一个区块，由此推断出挖矿所需的目标值；原则二：单调性。在非轴心链，区块只能引用轴心链上具有非递减的链难度值的区块；原则三：最重链原则。若某条链产生分歧，优先选择链难度值较大的分支作为主链。

原则一保证可变难度机制兼容使用m-for-1思想，原则二保证非轴心链的区块不会引用轴心链的陈旧区块使得获取的目标值和当前周期的预估值相差较大，原则三主要结合第3.3节的区块确认机制。依据上述原则，本文的难度值调节算法主要包含如下步骤：

步骤1，每个链采用最重链原则而非最长链原则进行主链选取。

步骤2，链Chain₀的区块难度值变化与比特币规则^[23]相同。

步骤3，依据原则1，链Chain₁,…,Chain _m-1的区块B需要一个字段参考区块哈希PivotParent指向在链Chain₀上的参考区块B'，该字段在挖矿哈希计算之前设定。B的区块难度等于产生B'的下一个区块的难度。

步骤4，依据原则二，为防止攻击者采用链Chain₀上旧的区块难度值，本文要求非轴心链引用链Chain₀的参考区块B'应具备非递减的链难度值。如图3所示，链Chain₁和链Chain₂引用链Chain₀的参考区块（虚线）决定区块的区块难度。

步骤5，原则三的作用在于当两个区块在同一个周期内被分类到同一条链时，矿工根据最重链原则以及确认机制进行主链选取。

3.3　区块序列化机制

对区块进行序列化是保证区块链协议交易账本最终完整性的关键。比特币的一个区块被广播并被验证合法后，等待T个后续区块即可认为其不可被篡改，之后可根据区块高度值排序得到区块序列。但在平行链协议中，每个链相对独立并随机增长，全局无法完全同步增长，多条链的全局区块序列化需要考虑不同链的区块加入系统的时序关系。本文利用有向图和逻辑时钟实现平行链区块序列化，既不用像文献[13]一样对区块进行预定义排序，也不用像文献[14]一样依赖某一条链进行时钟同步。

每个区块链节点保存有向图D，代表当前区块链状态视图，其中点代表区块，边代表对之前区块（双亲区块PreBlock或同步区块SynBlock）的引用。收到新区块时，若矿工本地视图D中存在该区块引用的双亲区块或同步区块，则计算该区块的时钟并添加到本地链；否则，该区块一直在缓存里直到其双亲区块或同步区块被接收。

每条链维持一个逻辑时钟，是一个计数器，随着区块追加而增大。逻辑时钟根据节点本地的有向图D计算，无需作为区块的内嵌字段。为了在不同链之间同步时钟，区块生成时在预备区块头中添加一个同步区块字段SynBlock（m条链中有最大逻辑时钟的区块）。当一个区块要加入节点的本地视图时，节点计算区块的逻辑时钟。创世区块的时钟为0，其余区块B的逻辑时钟是双亲区块和同步区块的时钟最大值加1，B.clock = max(B.preBlock.clock, B.SynBlock.clock)+1。

利用全局时间戳(clock,ch(B))，每个节点可以输出一个全局区块的顺序序列，其中clock是区块的逻辑时钟，表示区块的生成周期，ch(B)是区块B的链归属。依据clock和ch(B)递增且clock优先的规则输出一个全局区块序列。区块在序列化之前要先在单链被确认，本文称之为局部确认，每条链除后T个区块外，其余区块是局部确认区块。设B_i 是每条链的局部确认区块，定义可确认标志confirm_bar = min(B_i.clock),其中i∈{0,…,m-1}。如果区块B_i 的逻辑时钟小于等于可确认标志confirm_bar时，B_i 可被完全确认，进而可以序列化所有的局部确认区块。比如在图4中，当T=2时，除去末尾两个点，其余点代表局部确认区块，B03、B13、B22是最新的局部确认区块，他们的逻辑时钟依次是4、5、5，确认标志confirm_bar=min(4,5,5)=4，则逻辑时钟小于等于4的局部确认区块可按照(clock,ch(B))排序，所以全局的区块确认序列为B00、B10、B20、B01、B21、B11、B02、B12、B03。

4　 分析与评估

4.1　安全分析

本文的分析基于文献[2，21，23]，相关假设和符号定义与第2节和第3节一致。文献[2]分析中本聪协议并提出证明比特币协议的一致性和活性需要证明两个属性：公共前缀和链质量。文献[21]将活性扩充为链质量和链增长。本文区块不是由单一链决定，而是由多条链的前置区块决定，已有的结论不能直接适用，需证明本文协议满足上述属性。

4.1.1　性质分析

前缀：给定区块链C由num _c 个区块组成以及非负整数T，则C{}^{⌊T⌋}表示C去掉末尾T个区块的前缀。如果T >num _c，则C{}^{⌊T⌋}=\mathrm{\varnothing }，如果C_A 是C_B 的前缀，则表示为C_A ≼C_B。

定理1 （文献[21]推论3）假设ρ<1/2，给定任意自然数n和Δ，存在正常数c以及p<1/(cΔn)，在(ρ,Δ,n,p)设定下Π_nak满足如下属性（此结论成立概率关于T呈指数下降）：

• （一致性）在任意不同区块周期，诚实节点N₁、N₂的区块序列表示为S₁、S₂，则S₁≼S₂或S₂≼S₁。

• （链增长）在任意执行周期，诚实节点的链长度最新2T/(pn)个周期至少增长T个区块。

• （链质量）对于任意诚实节点的任意T个连续区块，诚实节点产生的区块所占比例至少为(1-ρ/(1-ρ))。

推论1 任意给定i满足0≤i≤m-1，Π_par协议的链C_i 在(m,ρ,Δ,n,mp)环境下和Π_nak在(ρ,Δ,n,p)环境下拥有相同的属性。

证 协议Π_par的链C₀除了区块生成，和Π_nak以同样的方式运行。在Π_par中，每个参与产生一个带有log（1/mp）个前导零的新区块的概率为mp。每次哈希计算后置log m位值为零的概率为1/m。因为这两个事件是独立的，在每次随机计算中，矿工在链C₀挖出一个新区块且该区块带有log（1/mp）个前导零和log m个后置零的概率为p。因此，Π_par的链C₀产生一个新区块的概率与Π_nak相等。在Π_par中，双亲区块的哈希值包括在前置信息默克尔树ParentMT中并给出成员证明，树根包括在区块头中。与Π_nak相同，区块一旦产生，就不能被篡改，这意味着系统只知道一个双亲区块。因此，链C₀中的区块就像Π_nak一样被连接起来。证毕。

定理2 假设ρ<1/2，给定任意自然数n和Δ，存在正常数c、m以及p<1/(cΔn)，在(m,ρ,Δ,n,mp)设定下Π_par满足如下属性（此结论成立概率关于Tkg呈指数下降）：

• （一致性）假设时间t₁≤t_2，任意诚实节点N₁、N₂得到的区块序列为S₁、S₂，Π_par保证S₁≼S₂。

• （序列增长）存在任意整数γ≥1，任意诚实节点的全局区块确认序列S每(γ+2)2T/pn个周期至少增长m·γ·T个区块。

• （序列质量）对于任意诚实节点的全局区块序列S中的任意m·γ·T个连续区块，诚实节点产生的区块所占比例至少为(1-ρ/(1-ρ))。

定理2表明全局区块确认列表满足一致性、链质量和链增长属性。序列增长和序列质量说明全局区块确认列表按照一定的速率包含诚实矿工的区块。换言之，一致性对应到平行链协议的安全性，序列质量和序列增长对应平行链协议的活性。

推论2 任意给定i满足0≤i≤m-1，若Π_par协议的链C_i 在(m,ρ,Δ,n,mp)设定下满足定理1，则Π_par协议满足定理2。

证 设常数c在定理1和定理2中相等，对于任意给定的i满足0≤i≤m-1，定理1和推论1表明在(m,ρ,Δ,n,mp)设定下，链C_i 具有定理1的三个属性，成立概率关于T呈指数下降。因此，Π_par协议全部的m条链具备定理1的三个属性，成立概率关于T呈m倍的指数下降。定理2的序列增长和序列质量属性直接满足。对于一致性，区块确认序列是根据二元组(链归属,区块周期)排序得到的，若t₁<t₂且r₁<r₂，则可确认周期r₁-T<r₂-T，全局区块序列S₁是S₂的前缀。若t₁<t₂且r₁=r₂，则确认周期r₁-T=r₂-T，全局区块序列S₁=S₂，亦满足一致性。证毕。

定理1定义了中本聪协议需要满足的基本性质，推论1证明本文的平行链协议中的任意一条链具备和中本聪协议的单链同样的性质。定理2定义了本文协议需满足的基本性质，推论2补充证明本文协议满足安全性和活性的各个属性。

4.1.2　可变难度值原则分析

1） 只有原则一没有原则二：缺乏安全性

为了兼容m-for-1挖矿和难度值可变，一个直接的方法是将平行链的一条链（如链Chain₀）作为轴心链（原则一）：链Chain₀的区块的难度值按照文献[23]中比特币的规则进行调节，其余链的区块难度值依据参考区块跟随轴心链。然而，如果允许矿工参考任意轴心链区块来获取区块难度值（无原则二），那么其余链可能存在安全缺陷。假设存在如下一种安全缺陷：令诚实参与者当前用于挖矿的区块难度为d0，攻击者不断地在轴心链计算私有区块，直到该区块难度达到d0*T，其中T是区块安全确认周期数。由于最重链原则，攻击者虽然不能在轴心链保证其自私区块具有最大链难度值。但是，在当前的非轴心链中，攻击者可以将这个高难度值的自私区块作为参考区块PivotParent进行区块挖掘，攻击者有机会产生高难度的非轴心链区块。如果攻击者足够幸运，在非轴心链挖掘到一个区块难度值为d0*T的区块，那么攻击者可以篡改非轴心链区块，并且成功挖到该非轴心链区块的概率相对于T是常数级而不是指数级。为解决这一问题，本文要求每个非轴心链区块的引用的轴心链参考区块具备非递减链难度值（原则二），因此攻击者无法采用一个旧的轴心链难度值。有了原则二，即使攻击者不参考轴心链的末尾区块，非轴心链的安全性也可以得到保障。

2） 没有原则三：缺乏活性

在平行链协议中采取可变难度值机制时，如果不采用原则三，攻击者有概率通过降低轴心链区块难度，产生一条较长且低难度的分支，那么诚实的轴心链分支将无法得到确认。因此，一个通用的方法是在分歧发生的时候采用最重链进行主链选取（原则三）。结合本文的确认机制，可以在安全确认周期内完成分歧选择，保持平行链协议的活性。

4.1.3　安全问题讨论

考虑合法性。平行链协议中新区块在产生时将所有m条链的末尾区块整合，作为全局的前置状态进行哈希计算，但是新区块只会被追加到其中一条链。换言之，一次PoW的计算绑定到一个区块，然后被添加到某一条链。用默克尔树收集所有链的末尾区块（前置区块），新区块追加到某个末尾区块（双亲区块）后，提供双亲区块到树根的默克尔证明，保证双亲区块在工作量哈希计算之前就存在于矿工收集的信息中。简言之，如果矿工要想合法地追加区块到某条链，那么他必须证明他的本地数据库存在该链的末尾区块。

考虑双花问题。区块链中的双花问题^[9]指的是当矿工之间的交易账本不一致时，可能会导致同一笔交易被两次花费。实现区块链账本一致性可防止双花问题，如果两笔交易花费相同的资金，所有的节点只接收全局账本的第一笔交易。本文获取全局区块序列的主要目的就是保障账本一致性。此外，交易冗余设计可以解决相同交易被不同区块打包的情况，避免对全局区块列表造成影响。

考虑分叉问题。在比特币中，由于区块传播存在网络延迟，两个区块可能处于同一高度（同周期），依据最长链原则只保留一个区块。平行结构旨在安全地利用分支的区块以提高吞吐量。由于m-for-1中PoW哈希的随机性，攻击者无法像中本聪协议一样针对某一条链进行人为分叉。考虑一种罕见情况，同一周期有多个区块被分类到平行链中的同一条链。由于区块的链归属是由区块哈希决定的，而哈希计算具有随机性，攻击者无法控制计算结果，所以此类情况看作哈希碰撞。本文方案采用可变难度值机制，用最重链原则选择单链中主链。事实上，可变难度值的出发点就是根据区块链状态调整出块难度以保证出块间隔稳定，稳定的出块间隔有助于防止分叉。

4.1.4　攻击情况讨论

1） 自私挖矿

考虑如下场景，本文协议中矿工在构建前置信息树ParentMT时收集多条链的末尾区块，但如果攻击者不诚实执行协议，在某一条链收集所有信息，比如m=4，攻击者选择链Chain₂的末尾4个区块（假设为B20、B21、B22、B23）作为前置信息。当攻击者产生一个带有log（1/mp）位前导零的区块B时，若B的后log m位不等于2，则所有诚实节点不会接受B；否则，B将会被接受，因为诚实节点会验证第3个叶子节点的成员证明，只有攻击者使用Chain₂的最新区块作为树的第3个叶子才会通过验证。此假设是合理的，比特币也允许从任何区块开始挖矿。本文的验证还包括验证同步区块SynBlock的存在性和一致性，即使通过了前置验证，也会因为无法和多数人的确认信息一致而被后续区块否认。

2） 审查攻击

攻击者的目标是通过生成空的区块来减缓区块的确认。有两个效果：1） 延迟包含交易的区块的创建；2） 延迟对之前区块的确认。本文方案在对区块进行合法性验证的时候会验证交易类型和链归属的映射关系，所以空区块显然是非法的。但上述情景确实会对确认延迟造成影响，在实验评估时进行了相关测试，与非恶意设置相比，审查攻击使得本文协议的确认延迟增加。

还有一些常见的攻击如平衡攻击。传统区块链的平衡攻击指的是攻击者对单链进行分叉并维持多个分叉竞争，影响区块确认延迟。本文的平行链协议实现了m-for-1思想，区块动态地并发产生并被追加到多条链，哈希计算的随机性以及完整性和合法性验证使得攻击者难以实现针对某条链的平衡攻击。

4.2　实验评估

4.2.1　实验环境

本文通过实现一个原型系统检测协议的性能，主体模块大约由3 200行Golang代码实现。整个系统由12台计算机搭建组成（Intel Core i7-8700，16 GB内存，Ubuntu 20.04.3 LTS），每台计算机都是宿主机，宿主机上通过Docker运行实际的区块链节点。本文进行两组实验，一组实验每个宿主机5个节点进行参数确定，另一组每个宿主机15个节点进行性能测试。区块链节点构建的P2P网络每个节点关联8个其余节点，采用Gossip进行信息传播，每个节点网络带宽上限为20 Mb/s。

4.2.2　性能分析

1） 参数确定

为确定适合实验环境的参数，首先测试区块传播延迟，是一个区块传播到整个系统所经历的时间。区块传播延迟结合网络带宽可以确定合适的区块大小以及平行链数量。配置每个节点带宽为8~20 Mb/s测试区块传播延迟，从10~40 KB变化区块。图5（a）展示不同带宽的情况下区块大小的变化对于区块传播延迟的影响。从图5（a）可以看出，区块大小为20~25 KB时，区块传播延迟可以在2 s左右，本文选取的区块大小为25 KB。根据文献[9]的分析，当区块间隔为5倍的区块传播延迟时，可以容忍恶意节点的比例为43%，这个结论用于确定实际的挖矿可能性p（实验中表现为设置目标哈希的前导零数量）。理论上区块的并发数越多性能越好，但是大量的区块并发对于区块传播会造成影响，本文测试区块并发数对于区块传播的影响，利用每秒并发的区块数进行测试。当区块大小固定时（25 KB），并发区块数和区块传播延迟的关系如图5（b），当区块并发数不断增加使得带宽利用率超过50%时（实点），并发区块数将会显著影响区块的传播延迟，这一结论可用于确定平行链的数量。

2） 性能测试

关注区块链可扩展性指标：交易吞吐量和区块确认延迟。交易吞吐量衡量区块链系统信息处理能力，用每秒处理交易的数量表示（transaction per second,TPS）；区块确认延迟指区块从生成到被全网确认花费的时间，与协议设定的确认周期T有关。交易吞吐量越大确认延迟越低，区块链的可扩展性越好。

选定区块大小为25 KB，区块间隔维持在10 s左右，根据关系m×区块大小/区块间隔=0.5×可用带宽，计算出在不同的网络带宽下平行链的条数（分别为m=200,300,400,500）。本文在实验时，如果m的数量不为2的指数，采用对区块哈希取模的方式散列。比如m=200，无法用区块哈希的后几位分类，2⁸=256，对后8位进行针对200的取模，余数为区块的链归属。如图6（a）所示，按照比特币的平均交易大小，本文的吞吐量在20 Mb/s的设定下可达到2 800 TPS，不采用交易冗余的S-Merkle树时吞吐量最高为2 500 TPS。从0到20变换确认周期参数T测试确认延迟的变化情况如图6（b），区块确认机制确实可以大幅改善区块确认速率（比特币为10 min）。为了进一步测试系统的实际性能，本文设定部分节点（ρ=1/3）不诚实执行协议，图6（b）显示的分别是无攻击和审查攻击（生成空的区块）对于系统确认延迟的影响，审查攻击会让本文的确认延迟增加13~18 s。

对于可变难度值机制，验证相较于固定难度值的有效性和难度值变化的及时性，结果如图7。为检测可变难度值的有效性，本文测试在平行链结构中采取固定难度和可变难度对算力利用率的影响。算力利用率=被确认的区块数目/所有生成的区块数目。测试结果表明可变难度机制可依据出块间隔自适应调节难度维持算力利用率稳定。此外，为检测难度值变化是否及时，本文测试非轴心链的区块难度在轴心链难度变化之后的更新延迟，更新延迟超过1 min的比例为千分之一级别。

5　 结 语

本文提出一种基于工作量证明机制的平行区块链协议，利用m-for-1挖矿大幅改善吞吐量，通过设计新的存储结构解决区块并发中更严重的交易冗余问题，考虑区块难度值变化问题提高区块链协议适用性，给出切实有效的区块序列化机制，优化区块确认延迟。分析和实验表明本文协议确实可以在提高可扩展性的同时权衡安全性问题。下一步将优化难度值调控思想使其更加充分地贴近挖矿场景，改进确认机制以进一步减缓确认延迟。

参考文献

[1] NAKAMOTO S. Bitcoin：A Peer-to-Peer Electronic Cash System［EB/OL］. ［2021-11-29］. DOI: 10.2139/ssrn.3977007 .

[2] GARAY J A， KIAYIAS A， LEONARDOS N. The bitcoin backbone protocol： Analysis and applications［C］// Annual International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT）. Berlin：Springer， 2015： 281-310. DOI: 10.1007/978-3-662-46803-6_10 .

[3] KIM S， KWON Y， CHO S. A survey of scalability solutions on blockchain［C］// 2018 International Conference on Information and Communication Technology Convergence （ICTC）. Piscataway：IEEE， 2018： 1204-1207. DOI: 10.1109/ictc.2018.8539529 .

[4] EYAL I， GENCER A E， SIRER E G， et al. Bitcoin-NG： A scalable blockchain protocol ［C］// 13th International Conference on Emerging Networking Experiments and Technologies（NSDI）. Berkeley：USENIX， 2016： 45-59.

[5] DAS D. Toward next generation of blockchain using improvized bitcoin-NG［J］. IEEE Transactions on Computational Social Systems， 2021， 8（2）： 512-521. DOI： 10.1109/TCSS.2021. 3049477 .

[6] PASS R， SHI E. FruitChains： A fair blockchain ［C］// ACM Symposium on Principles of Distributed Computing. New York：ACM， 2017： 315-324. DOI：10.1145/3087801.3087809 .

[7] RIZUN P R. Subchains： A technique to scale bitcoin and improve the user experience ［J］. Ledger， 2016， 1（1）：38-52. DOI： 10.5195/ledger.2016.40

[8] ZHANG R， PRENEEL B. On the necessity of a prescribed block validity consensus： Analyzing bitcoin unlimited mining protocol ［C］// Proceedings of the 13th International Conference on Emerging Networking Experiments and Technologies. New York：ACM， 2017： 108-119. DOI：10.1145/3143361.3143389 .

[9] APOSTOLAKI M， ZOHAR A， VANBEVER L. Hijacking bitcoin： Routing attacks on cryptocurrencies［C］// 2017 IEEE Symposium on Security and Privacy （SP）. Piscataway：IEEE， 2017： 375-392. DOI：10.1109/SP.2017.29 .

[10] SOMPOLINSKY Y， LEWENBERG Y， ZOHAR A. Spectre： A Fast and Scalable Cryptocurrency Protocol［EB/OL］. ［2016-12-18］.

[11] SOMPOLINSK Y， WYBORSKI S， ZOHAR A. PHANTOM GHOSTDAG： A scalable generalization of Nakamoto consensus ［C］// Proceedings of the 3rd ACM Conference on Advances in Financial Technologies. New York：ACM. 2021： 57-70. DOI：10.1145/3479722.3480990 .

[12] LI C， LI P， ZHOU D， et al. A decentralized blockchain with high throughput and fast confirmation［C］// 2020 USENIX Annual Technical Conference. Berkeley：USENIX， 2020： 515-528.

[13] YU H F， NIKOLIĆ I， HOU R M，et al. OHIE： Blockchain scaling made simple［C］// 2020 IEEE Symposium on Security and Privacy （SP）. Piscataway：IEEE， 2020： 90-105. DOI：10.1109/SP40000.2020.00008 .

[14] BAGARIA V， KANNAN S， TSE D， et al. Prism： deconstructing the blockchain to approach physical limits［C］// 2019 ACM SIGSAC Conference on Computer and Communications Security （CSS）. New York：ACM， 2019： 585-602. DOI：10.1145/3319535.3363213 .

[15] LI S Z， TSE D. TaiJi： Longest Chain Availability with BFT Fast Confirmation［EB/OL］. ［2020-11-22］.

[16] FITZI M， GAẐI P， KIAYIAS A， et al. Parallel chains： Improving throughput and latency of blockchain protocols via parallel composition ［EB/OL］. ［2018-11-17］.

[17] MARTINO W， QUAINTANCE M， POPEJOY S. Chainweb： A Proof-of-work Parallel-chain Architecture for Massive Throughput ［EB/OL］. ［2021-11-29］.

[18] XIONG T， XIE T， XIE J， et al. ORIC： A self-adjusting blockchain protocol with high throughput ［C］// 2021 IEEE Intl Conferencw on Parallel & Distributed Processing with Applications. New York： IEEE Press， 2021： 1422-1434. DOI：10.1109/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00193 .

[19] XU J， CHENG Y Y， WANG C， et al. Occam： A secure and adaptive scaling scheme for permissionless blockchain［C］// 2021 IEEE 41st International Conference on Distributed Computing Systems （ICDCS）. New York： IEEE Press， 2021： 618-628. DOI：10.1109/ICDCS51616.2021.00065 .

[20] KIFFER L， RAJARAMAN R， SHELAT A. A better method to analyze blockchain consistency［C］// 2018 ACM SIGSAC Conference on Computer and Communications Security （CCS）. New York：ACM， 2018： 729-744. DOI：10.1145/3243734.3243814 .

[21] PASS R， SEEMAN L， SHELAT A. Analysis of the blockchain protocol in asynchronous networks［C］// Annual International Conference on the Theory and Applications of Cryptographic Techniques （EUROCRYPT ）. Berlin：Springer， 2017： 643-673. DOI：10.1007/978-3-319-56614-6_22 .

[22] WANG J， WANG H. Monoxide： Scale out blockchains with asynchronous consensus zones［C］// 16th USENIX Symposium on Networked Systems Design and Implementation （NSDI 19）. Berkeley：USENIX， 2019： 95-112.

[23] GARAY J， KIAYIAS A， LEONARDOS N. The bitcoin backbone protocol with chains of variable difficulty［C］// Annual International Cryptology Conference （CRYPTO）. Berlin：Springer， 2017： 291-323. DOI：10.1007/978-3-319-63688-7_10 .