基于中国剩余定理的区块链存储扩展模型

卿欣艺，陈玉玲*，周正强，涂园超，李 涛

（1.贵州大学计算机科学与技术学院，贵州 550025；2.省部共建公共大数据国家重点实验室（筹）（贵州大学），贵州 550025）

0 引言

自《比特币：一种点对点电子现金系统》［1］发表以来，比特币的底层技术区块链被认为是下一代的颠覆性技术。区块链是一种去中心化、由多方共同维护的分布式账本技术，它基于P2P（Peer-to-Peer）网络［2］，要求每个节点都需持有该账本的数据副本并同步更新。区块链中，数据的写入由节点之间的分布式共识算法来完成，如工作量证明（Proof-of-Work，POW）［3］等，数据以块的方式进行存储，并按照时间顺序构成链式结构。此外，还采用密码学技术来保证分布式账本防篡改、可溯源。

区块链由于其去中心化、防篡改和可以溯源等特点，引起了金融机构、投资机构、监管部门以及政府部门的广泛关注。但目前区块链仍存在较多技术难点，存储问题就是其中之一。区块链网络中，节点以哈希链的形式存储完整的数据副本，而由于其链式结构的特殊性只能对区块进行增加和查询。对节点而言，即使没有参与交易，也必须存储该笔交易数据，这极大增加了节点存储成本。以比特币为例：比特币每秒平均交易不到3.5 笔［4］，即使按照这个速度，节点平均每天也需要消耗近160 MB 的存储空间，大约60 GB/a。截至2020 年7 月15日，比特币一共产生了639 487 个区块，平均区块大小为1.28 MB，整个区块链大小约为287.9 GB，有效地址总数约3 000 万［5］。为了达到最高的安全性和信任度，节点需要浪费将近300 GB 的存储空间来记录大量无关的交易数据，而整个区块链系统需要使用近9 000 PB 的空间来存储300 GB 的有效数据，而且随着区块和节点数量不断增加，存储消耗将持续增加，因此解决区块链的存储问题日渐紧迫。

针对这一问题，许多学者进行了大量研究。文献［1］提出SPV（Simplified Payment Verification）协议，轻量级节点（运行SPV 的节点）只存储区块头，本身无法验证交易。故轻量级节点执行支付验证全部依赖于全节点（存储全部区块数据），导致区块链的去中心化减弱、安全性和稳定性降低。Franca等［6］针对比特币网络提出迷你区块链，节点只存储区块头和最新的区块，并使用账户树来保障用户余额，这极大地降低了节点的存储压力，但会导致交易数据的丢失。Xu 等［7］针对传感器以及智能手机等移动设备的存储能力缺乏问题提出了EPBC（Efficient Public Blockchain Client），节点存储区块链摘要来验证数据的正确性，但不能解决数据中心化的问题。Jia等［8］提出存储容量可扩展性模型，根据每个区块安全性高低来决定其存储副本的数量，节点按照功能划分，不再要求每个节点存储完整的区块链信息；但该模型使用了两条辅助链，增加了系统的复杂性。文献［9-10］在文献［6］研究的基础上引入余数系统（Residual Number System，RNS）与冗余余数系统（Redundant Residual Number System，RRNS）将账户树分片来减小节点的存储压力并保障数据的完整性，但仍然无法解决交易数据丢失的问题。文献［11-14］中分别使用哈希一致性算法、纠删码、改进的Shamir秘密共享技术［15］和建立路由表来减小节点的存储压力。

本文在现有研究的基础上提出了一种基于中国剩余定理（Chinese Remainder Theorem，CRT）的区块链存储扩展模型。在该模型中，根据基于CRT 的分割算法将高安全性区块的区块体进行分片，每个节点存储一份数据碎片来减少存储消耗，多个节点（共识单元［16］）共同保存一份高安全性区块的数据副本，而全网节点都需要存储一份低安全性区块数据副本；此外，还加入了RRNS 错误检测与纠正来提高数据的稳定性和完整性。

本文主要的工作如下：

1）提出基于CRT 的区块链存储扩展模型，模型中节点采用不同的策略存储安全性不同的区块，节点存储一部分区块链数据来降低存储消耗。该模型解决了节点因存储能力不足而变为轻量级节点，导致全节点网络带宽压力增大以及区块链系统去中心化减弱的问题。

2）在确保区块数据安全性和可用性的前提下，提出了一种基于CRT 的分割算法来对区块数据进行分片，并将分片后的区块碎片以分布式的方式进行存储。此外，利用RRNS 的错误检测和校正［17］来恢复区块数据，使部分节点相互通信就可以恢复区块数据，提高了数据稳定性和模型的容错性。

3）对模型进行安全性分析以及仿真实验，结果表明本文提出的基于CRT 的区块链存储扩展模型在降低节点存储压力的同时，具有良好的容错性和安全性。

1 相关知识

1.1 中国剩余定理

m1，m2，…，mk是两两互素的正整数，组成模数集合β={m1，m2，…，mk}，M=当X＜M，则X能被唯一的φ={a1，a2，…，ak}表示，其中X≡ai(modmi)(i=1，2，…，k)。当β和φ可知时，就能够恢复X，X可表示为：

1.2 冗余余数系统

使用CRT 进行数据恢复时，若有恶意节点提供错误信息，将无法还原正确数据。因此，引入RRNS 的错误检测与纠正来提升数据稳定性和保障数据完整性。

假设余数集合φ={a1，a2，…，ak，ak+1，…，ak+s}由原始数据X对新模数集合β={m1，m2，…，mk，mk+1，…，mk+s}中的模数取余得到，并且φ={a1，a2，…，ak，ak+1，…，ak+s}中存在被恶意篡改的余数项。

图1 RRNS的错误检测与纠正流程Fig.1 Flowchart of RRNS error detection and correction

1.3 共识单元

共识单元由多个节点组成，多个节点共同存储一份区块链数据副本。共识单元可以看作一个存储能力较强的节点，通过整合多个节点的存储能力来存储全部区块数据，共识单元基本框架如图2 所示。由图2 可知，共识单元中的节点为N1～N6，每个节点的存储空间各不相同。假设在一个区块链的应用场景中，区块链的总数据量为100 GB，N1～N6 都不能独自存储全部区块链数据，但可以分别存储区块链的部分数据来共同存储一份完整的区块链数据副本。节点可以向共识单元中的其他节点发送请求来获得完整的区块链数据，以达到全节点的效果。

图2 共识单元基本框架Fig.2 Basic framework of consensus unit

2 基于CRT的区块链存储扩展模型

本文利用分布式存储方法［19-20］和分片思想来提出一个基于CRT 的区块链存储扩展模型，其核心思想是在保证区块数据的安全性与可靠性的前提下，将区块数据分片，分布式存储分片后的区块数据，模型框架如图3 所示。该模型中包含多个共识单元，共识单元由多个节点组成。模型通过对区块的安全性进行判定，将区块链分为高安全性和低安全性区块，区块链网络中的节点直接存储低安全性区块，而对于高安全性的区块，区块链网络中的节点利用基于CRT 的分割算法进行分片，节点只需要存储区块碎片。此外，节点可以向同一共识单元的节点发送请求获取区块碎片以还原区块数据。

图3 基于CRT的区块链存储扩展模型Fig.3 Blockchain storage expansion model based on CRT

在现有的区块链模型中，想要篡改区块数据，需要控制区块链网络中半数以上的节点。在本模型中，共识单元存储一份完整的区块链数据，将会导致区块链副本数量减少，而攻击者掌握少于区块链网络中半数的节点，就有可能篡改区块数据。同时，为提高区块数据的稳定性和模型的安全性，本文模型添加了RRNS 的错误检测与纠正，使共识单元中的少量节点相互通信就能正确恢复区块数据，节点的数量与信息模数基相关。模型为不同的共识单元设置不同的模数集合β={m1，m2，…，mk，mk+1，…mk+s}，节点可根据自身存储能力和网络带宽来选择共识单元，加入共识单元并随机选择一个模数，其中{m1，m2，…，mk}为信息模数基，{mk+1，…，mk+s}为冗余检错基。若所有的节点同属一个共识单元，很难设定信息模数基的长度k，k值若太大，会增加某些节点的带宽压力；而太小的话，会增加某些节点的存储压力。因此，本模型设置多个共识单元，来提升系统的负载均衡。

2.1 区块安全性判定

共识机制中最早出现的是POW。在POW 中，率先计算出满足规则的随机数的节点获得记账权，计算出满足规则的随机数的概率与节点算力成正比，若攻击者获得全网一半以上的算力，就能控制整个区块链系统。51%攻击通过区块链分叉来实现区块数据的篡改，攻击者产生一条攻击链来代替区块链，要使区块数据篡改成功，攻击者需要比诚实者更快地产生下一个区块。文献［1］中已给出关于51%攻击的证明，攻击者潜在进展符合泊松分布，分布期望为：

其中：p为诚实者率先计算出满足规则的随机数概率；q为攻击者率先计算出满足规则的随机数概率(p+q=1)；z为诚实节点领先的区块数。攻击者成功篡改区块的概率Pz如下：

由式（1）可知，攻击者成功篡改区块的概率与p、q和z有关。当p＞q时，随着z增加，攻击者成功篡改区块数据的概率呈指数趋势下降，如图4所示。

图4 攻击成功的概率Fig.4 Probability of successful attack

从图4 可以看出，随着诚实者领先的区块数量增加，攻击者成功篡改区块的概率不断减小，并趋向于0。因此，可以得出越原始的区块数据被篡改的可能性就越低，其安全性越高。Borel 定律［21］定义了任何事件低于10-50的概率都是不可能的事件。由式（1）可知，当诚实者领先的区块数量z增加到某一定数量时，Pz就会低于10-50。因此，在一条高度为n的区块链中，高度为n-z+1之前的区块可以被视为无法篡改的，故称为高安全性区块，高度为n-z+1 之后的区块则被称为低安全性区块，如图5所示。

图5 区块的安全性判定Fig.5 Security judgment of block

2.2 数据存储

模型进行数据存储时，需对区块的安全性进行判定，对不同安全性的区块采取不同的存储策略。根据式（1）计算出Pz＜10-50时z的大小，来判断区块安全性的高低。区块链的高度会随着区块地不断加入逐渐增大，当区块链的高度n≤z，区块全部是低安全性区块，节点直接存储全部区块；当区块链的高度n＞z，将会有低安全性区块转变为高安全性区块，因此节点需要根据基于CRT 的分割算法将高安全性区块分片，然后存储区块碎片数据。基于CRT的分割算法如下：

算法1 基于CRT的分割算法。

输入 区块bki，节点选择的模数mi；

输出 区块bki的碎片数据。

在算法1中，第1）行来判断区块是否为高安全性区块，第3）～7）行来进行区块数据分片。节点将高安全性区块的区块体bli转为16进制数，再转为10进制数来得到Ti。然后节点使用Ti与节点加入共识单元时选取的模数mi做取余运算，得到区块体碎片，并将区块体碎片以及区块头存储到本地磁盘。为保证数据恢复时的正确性，共识单元在设定模数集合时，需要保证Ti＜Mk。

随着时间的推移和区块数量的增加，区块会从刚加入区块链时的低安全性区块转变为高安全性块。节点通过算法1将高安全性区块的区块体数据分片来获得区块体碎片数据。节点存储区块体碎片与区块头数据不但降低了存储消耗，而且由于区块头的存储，也有效增加了攻击者生成攻击链来代替区块链的难度，增强了模型的安全性。

2.3 数据读取

节点读取属于低安全性区块的区块数据，直接访问本地磁盘获取区块信息，而读取属于高安全性块的区块数据，则需要向其他节点发送请求获取区块碎片，并利用RRNS 的错误检测与纠正来正确恢复区块数据。其中，节点读取高安全性区块数据分为两个阶段：数据碎片获取阶段和数据恢复阶段。

在数据碎片获取阶段，数据读取节点向同一共识单元中的节点发送请求，其他节点收到请求返回所选取模数以及碎片数据，如图6所示，具体过程如下：

图6 数据读取过程Fig.6 Process of data reading

1）数据读取节点随机向共识单元中k+s个节点发送请求；

2）节点收到请求，返回所选取的模数mi和存储的碎片数据Si；

3）数据读取返回数据并删除重复的(mi，Si)，重复1）、2），当(mi，Si)个数为k+s时，结束。

在数据恢复阶段，节点通过RRNS 错误检测与纠正进行数据恢复，具体过程如下：

1）节点使用CRT 恢复来区块数据X。若X≤Mk-1，执行步骤3）；若X＞Mk-1，执行步骤2）。

2）节点通过RRNS错误检测与纠正，获得X。

3）将X转化为16 进制数，最后将16 进制转为数据信息输出。

在区块链系统中，可能存在恶意节点，数据读取节点可能接收到被恶意篡改的数据，使用CRT 可能无法恢复正确的区块数据，因此模型使用RRNS 的错误检测和纠正来恢复区块数据。RRNS 的错误检测和纠正能够有效地保证区块数据被正确恢复，并提高模型的容错性和数据的完整性。

新节点加入区块链网络，需要进行数据同步。新加入的节点随机选取一个共识单元模数集合β={m1，m2，…，mk，mk+1，…，mk+s}中的模数mi，向共识单元中的其他节点发送请求，获取低安全性区块和区块头，以及同一模数节点存储的数据碎片数据。当获取多个同一模数节点的数据碎片存在不同时，新节点选取多数节点保存的数据碎片进行存储。

2.4 安全性分析

若在区块链网络中节点数量为N，恶意节点数量为Nd，恶意节点的概率为：pd=其中，共识单元中节点数量为Nc（Nc≥k+s）。对于低安全性区块，所有节点都需存储，因此将低安全性区块视为无法被篡改的。高安全性区块被分片由节点分布式存储。因此，只需要对高安全性区块进行分析。分析最简单的情况，Nc=k+s，共识单元中至少需要k个诚实节点才可以恢复正确的区块数据，共识单元中的节点能够恢复区块数据的概率为：

由式（2）可知，随着恶意节点的概率不断增加，数据恢复的概率由开始的基本没影响，然后呈指数化下降，最后趋向于0。模型选取不同的k、s进行分析，具体情况如图7所示。

图7 数据恢复的概率变化Fig.7 Probability change of data recovery

对比k=30，s=30 和k=50，s=50 图像发现，k、s相等时，取值越大，数据恢复的概率会相对较慢地呈指数化下降，但总体来说k、s相等时的取值对数据恢复影响较小。而对比k=50，s=50；k=50，s=70 和k=50，s=100 图像，发现k设定为定值时，s的值越大，数据恢复的概率就越慢呈指数化下降，模型会具有更好的容错性，能够更好地保障数据的完整性和稳定性；并且随着节点源源不断地加入区块链系统，多个节点获取同一模数并存储相同的数据碎片，模型的容错性将持续提高。

在模型中，所有节点保存低安全性区块来防止攻击者通过区块链分叉来篡改数据，并通过存储高安性区块的区块头来保障区块数据的真实性和增加攻击者生成攻击链替代区块链的难度。此外，节点存储的高安全性区块的区块体碎片是一串没有意义的数值，能够有效地提高数据的隐私性，确保模型的安全性。

模型将高安全性区块分片后分布式存储，有效地降低了节点的存储压力，但会增加节点的计算消耗和通信消耗。针对节点计算和通信消耗问题，模型可以根据不同的应用场景来设置不同的信息模数基的和冗余检错基来进行调节，并且随着计算和通信技术的发展，所遇问题可能迎刃而解。

3 实验结果与分析

为了分析模型的相关性能，在Python 环境下搭建仿真平台，开启不同的服务器端口来创建本地共识节点，硬件参数：8 GB内存，i5-6 500 CPU和GeForce GT 730显卡。实验将本文提出的基于CRT 的区块链存储扩展模型和传统区块链模型所需要的时间和存储空间进行对比。实验主要针对存储和时间消耗，因此简化了工作量证明，将两模型POW 的难度值设为2（当取的随机数满足整个区块的哈希值前2 位为0 时获得记账权）。实验一共建立了12 个节点，每产生10 笔交易数据进行一次挖矿（每笔交易数据相同）。本文模型中每个节点选取不同的模数mi（模数集合为{m1，m2，…，m12}，其中信息模数基的长度为k=5，冗余检错基的长度为s=7）形成共识单元，并且选取q=0.1，p=0.9，故z增加到100，Pz＜10-50，即区块链当前高度的前100个区块都是低安全性区块。

实验生成300 个区块，将两模型区块生成和存储的时间消耗进行对比。其中，本文模型只对生成300 个区块中的前200 个区块进行分片，两模型后100 区块时间消耗相同，因此只需对比前200 个区块生成和存储时间消耗。为了更好地测试时间消耗，实验中直接对前200 区块进行分片，并计算出平均时间消耗，结果如图8 所示。由图8 可知，本文模型与传统区块模型的时间消耗相差不大。传统区块链模型中，区块生成后直接存储，主要的时间消耗包括挖矿时间和存储时间；而本文模型需要判断已经生成的区块的安全性，低安全性区块直接存储，高安全性区块分片后存储。两种模型中区块生成时间相同，主要差异为是否进行区块分片。对前200 个区块，本文模型平均时间消耗约为0.042 2 s，传统区块链模型平均时间消耗约为0.040 5 s。本文模型时间消耗略高于传统区块链模型的原因是模型需要将高安全性区块的区块体数字化，节点根据所选取的模数来分片。

图8 传统区块链模型与本文模型在区块生成与存储的时间对比Fig.8 Comparison of time consumption of traditional blockchain model and the proposed model in block generation and storage time

实验中分别生成不同的区块数，包括0、100、200、300，对比模型中的节点将区块数据存入数据库，以此对比存储消耗，如图9、10所示。由图9可知，随着区块数量的增加，与传统区块链模型相比，本文模型具有更低的存储消耗。图10 为图9在0 个区块数据时，两个模型的节点所消耗的存储空间。本文模型因需要存储一个额外的模数，所以存储消耗略大于传统区块链模型。当区块链中的区块数量小于或等于100 时，本文模型节点的存储消耗略大于传统区块链模型中的节点。这是由于所有区块都属于低安全性区块，两模型中的节点都是直接存储，而相比传统区块链模型中的节点，基于CRT 的区块链存储扩展模型中的节点需要额外存储选取的模数。当区块链中的区块数量大于100 时，随着区块数量的增加，本文模型节点的存储消耗逐渐小于传统区块链模型中的节点。这是由于将会有区块从低安全性区块变为高安全性区块，本文模型中的节点将高安全性区块分片，存储区块碎片，减少了存储消耗。因此，本文模型能有效减轻节点的存储压力，增加区块链系统的存储扩展性。

图9 两模型节点存储消耗对比Fig.9 Comparison of two models for node storage consumption

图10 在0个区块时节点存储消耗对比Fig.10 Comparison of node storage consumption with 0 block

4 结语

本文主要对区块链的存储问题进行研究，提出了一种基于CRT 的区块链存储扩展模型来降低节点的存储消耗。通过对区块数据被篡改的可能性进行分析，将区块链划分为高安全性区块和低安全性区块。区块链网络中的节点根据区块的安全性使用不同的存储策略来存储区块：低安全性区块直接存储，高安全性区块被基于CRT 的分割算法分片后被存储，有效地减少了节点的存储消耗。为保障区块数据的完整性和提升区块链系统的容错性，引入RRNS 的错误检测和纠正来防止区块数据被篡改以及恶意节点作恶。实验结果表明，该模型在保障区块链系统安全的前提下，有效地降低了节点的存储压力，增加了区块链系统的存储可扩展性。未来可以进一步研究由节点的存储能力和网络带宽来确定其所属共识单元，提升系统的负载均衡。同时，将继续研究怎么更加完善地解决区块系统的存储问题。