基于嵌套Merkle Hash tree区块链的云数据动态审计模型

周坚　金瑜　何亨　李鹏

摘 要：云存储凭借高扩展性、高可靠性、低成本的数据管理优点得到用户青睐。然而，如何确保云数据完整性成为亟待解决的安全问题。当前最成熟、高效的云数据完整性审计方案是基于半可信第三方来提供公共审计服务，但基于半可信第三方审计方案存在单点失效、算力瓶颈和错误数据定位效率低等问题。为了解决上述问题，提出了基于区块链的云数据动态审计模型。首先，采用分布式网络、共识算法建立一个由众多审计实体组成的区块链审计网络，并以此来解决单点失效和算力瓶颈问题;然后，在保证区块链数据可信度的前提下，引入变色龙哈希算法和嵌套MHT结构，以实现云数据标签在区块链上的动态操作;最后，借助嵌套MHT结构以及辅助路径信息，提高了在审计发生错误时对错误数据的定位效率。实验结果表明，与基于半可信第三方云数据动态审计方案相比，所提模型显著提高了审计效率，降低了数据动态操作时间开销，并提升了错误数据定位效率。

关键词：区块链;云存储;动态操作;审计;变色龙哈希

中图分类号： TP393.08;TP399在其他方面的应用文献标志码：A

Dynamic cloud data audit model based on nest Merkle Hash tree block chain

ZHOU Jian1，2， JIN Yu1，2*， HE Heng2， LI Peng2

（1. College of Computer Science and Technology， Wuhan University of Science and Technology， Wuhan Hubei 430065， China;

2. Hubei Province Key Laboratory of Intelligent Information Processing and Real-time Industrial System， Wuhan Hubei 430065， China）

Abstract： Cloud storage is popular to users for its high scalability， high reliability， and low-cost data management. However， it is an important security problem to safeguard the cloud data integrity. Currently， providing public auditing services based on semi-trusted third party is the most popular and effective cloud data integrity audit scheme， but there are still some shortcomings such as single point of failure， computing power bottlenecks， and low efficient positioning of erroneous data. Aiming at these defects， a dynamic cloud data audit model based on block chain was proposed. Firstly， distributed network and consensus algorithm were used to establish a block chain audit network with multiple audit entities to solve the problems of single point of failure and computing power bottlenecks. Then， on the guarantee of the reliability of block chain， chameleon Hash algorithm and nest Merkle Hash Tree （MHT） structure were introduced to realize the dynamic operation of cloud data tags in block chain. Finally， by using nest MHT structure and auxiliary path information， the efficiency of erroneous data positioning was increased when error occurring in audit procedure. The experimental results show that compared with the semi-trusted third-party cloud data dynamic audit scheme， the proposed model significantly improves the audit efficiency， reduces the data dynamic operation time cost and increases the erroneous data positioning efficiency.

Key words： block chain; cloud storage; dynamic operation; audit; chameleon Hash

0 引言

云計算是近几年研究和应用的热点，云存储作为云计算的重要服务模式之一，其目的是利用云计算技术将大量低成本、低可靠性的设备协同起来，向用户提供高可靠、高弹性、高性能、低成本的数据存储服务[1]。用户在享受便捷的云存储服务时，云存储也曝露出以下安全问题：1）用户数据的所有权和控制权相互分离，云服务提供商（Cloud Service Porvider， CSP）可能出于经济目的故意删除用户不经常访问的数据或者冗余数据。2）CSP可能出现软件失效或硬件损坏，直接导致用户数据丢失或者损坏。3）云数据可能遭到其他用户的恶意损坏。因此，为了验证用户云数据的完整性，数据审计方案应运而生。其中，基于半可信第三方审计（Third Party Audit， TPA）[2-7]是最具有代表性的审计方案，但上述基于TPA方案存在以下问题：1）单点失效。所有用户的云数据都由唯一的TPA实体完成审计，因此一旦TPA实体功能失效，则整个审计系统瘫痪。2）性能瓶颈。随着云用户和云数据规模增大，TPA需要处理的数据规模也会增大导致审计时间会急剧加大，因此TPA的算力成为了整个审计系统的瓶颈。3）错误数据定位效果差。在云数据审计方案[2-5，7-15]中，均不支持用户错误数据定位，不能为后续数据修复工作提供参考;文献[6]方案中虽然支持错误数据的定位，但定位效率仍然不高。

在充分研究了用户与CSP的信任矛盾和TPA审计模型的缺陷后，本文提出了基于去区块链的动态云数据审计模型。该方案借助区块链去中心化、高扩展性、安全可信等特点，将独立TPA实体的审计任务和用户数据标签一同转移到区块链上，采用分布式TPA实体来完成审计业务，利用区块链的分布式账本模型来存储用户的数据标签。 此外，本文在深入了解区块链系统和审计方案对用户动态数据的审计需求后，在保证区块链分布式账本安全可信的基础上，结合已有的变色龙哈希算法和新提出的嵌套MHT（Merkle Hash Tree）结构实现对用户存储在区块链上数据标签的动态操作功能。

1 相关工作

数据完整性审计是数据拥有者检测远程云服务器中数据完整性的最佳途径和方法，本文主要研究的方向是数据持有性证明。

Anteniese等 [12]首次提出了基于RSA签名的数据持有者证明（Provable of Data Possession， PDP）方案。文献[12]方案采用抽取数据样本的策略，利用RSA同态的特性，结合其首次提出的样本抽样策略，能够在相同可信度基础上，明显减少了验证数据的数量，有效减少了计算代价和通信开销;但文献[12]方案只支持静态云数据审计，在动态操作数据的情况下，插入或删除数据块需要用户重新生成修改后数据块后续的全部首部哈希值，极大消耗了用户的计算资源。Anteniese等[13]对文献[12]方案进行改进，又提出了动态云数据审计（Dynamic PDP， DPDP）方案;但文献[13]方案只支持云数据的更新、删除和追加操作，不支持云数据插入操作，不能称得上完全的动态数据完整性验证方案。

Erway等 [7] 采用基于排名的认证跳表动态数据结构和RSA签名机制来支持全动态数据操作（Scable dynamic PDP， SPDP）方案。文献[7]方案是第一种支持全动态数据操作的PDP方案，但它存在寻找节点时间开销随着文件分块数规模增大而快速增大的问题，导致动态操作效率低下;此外，动态数据操作需要修改跳表中认证路径上所有节点的哈希值，需要计算大量辅助消息，存在计算代价和网络开销都比较大等问题。

Wang等 [5]提出了采用MHT和BLS签名机制的支持公开审计的动态数据完整性验证（Public PDP， P-PDP）方案。文献[5]方案中采用MHT结构保证数据块在空间上的正确性，通过BLS签名的PDP机制来保证数据在内容上的完整性。该方案的优势在于：1）借助BLS签名算法，用户可以将繁琐的审计任务转交给TPA来完成，从而实现公开审计。2）相较于RSA签名机制，BLS签名机制具有更低的计算开销和通信开销。3）借助MHT结构，该方案认证路径长度更短。相较于文献[13]方案，文献[5]方案在节点查询、生成的认证路径速度更快。但该方案中，用户将云数据审计工作交给了TPA处理，随着用户数量、托管数据增加，最终会导致TPA承担繁重的计算开销，大幅影响TPA性能;此外，该方案仍不支持审计发生错误时对错误数据的定位。

Yang等 [6]提出基于索引表结构和BLS（Boneh-Lynn-Shacham）签名算法，支持完全动态数据操作的PDP（Efficient PDP， EPDP）机制。在该方案中，由于采用的索引表是通过连续的存储空间实现分块文件元数据存储，导致删除和插入操作会移动大量的数据。随着用户数据规模扩大、文件分块数增多，删除和插入操作的时间开销会急剧增大，直接导致动态操作后的验证时间开销增大，使得其审计效率低于文献[5]方案;此外，该方案同样采用基于TPA的审计模型，存在单点失效和算力瓶颈缺陷。

李勇等 [8]在文献[5]方案研究的基础上，针对构建MHT中认证路径过长问题，改进MHT结构为多路分支树（Large Branching Tree， LBT）结构，提出基于LBT结构的PDP（LBT PDP， LPDP）审计模型。LBT采用多分支路径结构，所需构造的LBT深度随着出度的增加而减少，进而减少数据完整性验证过程中的辅助信息，简化了数据动态更新过程，降低了系统中实体之间的计算开销。但文献[8]方案依然采用文献[5]方案中基于TPA的审计模型，依然存在单点失效、算力瓶颈等问题。

Garg等 [9]在文献[5]方案引入的MHT结构上附加了相关索引和时间戳，提出了RIST-MHT（Relative Indexed and Time Stamped MHT）结构，并提出基于RIST-MHT结构的PDP（RIST PDP， RPDP）审计模型。文献[9]方案提出的RIST-MHT结构相较于MHT结构：一方面缩短了MHT中认证长度，从而缩短了节点查询的时间开销;另一方面在标签中添加时间戳属性，赋予标签数据新鲜度。但该方案依然没有解决文獻[5]方案中存在的问题。

为了让用户对已有的数据持有性证明审计方案有客观的认识，本文从审计时间复杂度、动态操作支持、错误数据定位三个视角对现有方案进行对比分析，具体结果如表1所示。表1中：n是文件块数;t是审计过程中挑战的文件块数;s是文件块二级分块文件数;M（Modify）是更新操作;I（Insert）是插入操作;D（Delete）是删除操作;EL（Error data Locate）是错误数据定位;Server表示计算元数据的时间复杂度;Vertify表示验证数据完整性时间复杂度。

从数据持有性证明方案的发展来看，最近几年来的研究方向主要是基于文献[5]方案，对MHT认证路径缩短、隐私保护方向加以改善，就计算开销而言没有实际的改进。就审计计算量方面而言，文献[5]方案凭借其简洁的审计过程，不需要额外的辅助数据，其计算量相较文献[6-7，9]方案更小。就支持错误数据定位的动态云数据审计方案而言，只有文献[6]方案适合作对比实验。因此，在审计效率方面将本文方案与文献[5]方案作横向对比;在动态数据操作方面，由于只有文献[6]方案在支持动态数据操作的同时支持错误数据定位，故在错误数据定位方面，主要将本文方案与文献[6]方案进行比较。

区块链系统的节点应当是可开放自由参与，身份平等，如此形成自治的系统[16]。为了更好适应区块链系统，大多数系统采用对等分布式网络来进行数据传播。为了使众多的节点能够在保证安全性的前提下完成网络中数据打包，则需要全网节点达成共识，共同完成任务[17-19]。

区块链的共识算法主要分为证明类算法和选举类算法，其中普遍应用的PoW（Proof of Work）方案[20] 和PoS（Proof of Stake）方案[21]是证明类共识算法，DPoS（Delegated Proof of Stake）方案[22]是选举类算法。其具体性能如表2所示，主要针对PoW、PoS、DPoS就性能效率、去中心化、确定性和资源消耗几个方面作对比。为了最大限度提升云数据的审计效率，本文采用DPoS共识算法。

为了从根本上解决基于TPA的云数据审计方案的单点失效、算力瓶颈等问题，本文引入区块链技术弱化TPA在审计系统的地位，借助分布式网络提升审计系统的算力;此外，本文通过一个创新的嵌入式MHT结构，在实现云数据动态操作的前提下，提高了审计错误时对错误数据定位的效率。

2 背景知识

2.1 BLS签名

BLS签名方案使用双线性映射的性质进行验证和签名。记e：GG→G′是一个非退化双线性映射，G和G′是素数r阶的乘法群，生成元是g。根据双线性映射的性质e（gx，gy）=e（g，g）xy，要求在G上，CDH（Computational-Diffie-Hellman）求解是困难的。

BLS签名分成三个函数：

1）KeyGen：选取一个随机整数x作为私钥sk，gx作为公钥pk。

2）Sign：计算消息h 的签名sig=hx。

3）Verification：验证者知道G、pk、h、sig′，为了验证sig′=hx，即签名是拥有私钥x的人产生的，验证者计算e（gx，h）=e（g，sig′），若成立则消息的完整性得到证明。

2.2 变色龙哈希

哈希函数简单来讲就是能将任意长度的输入转换成一个固定长度的输出，这个固定长度的输出称为原数据的散列值或哈希值。通过原始输入消息能够很容易计算哈希值，通过输出（哈希值）则很难还原出原始输入。理想的哈希函数针对不同的输入产生不同的输出。如果两个不同的消息产生了相同的哈希值，则称为发生了碰撞[23]。

与一般哈希函数不同，变色龙哈希函数（Chamelelon Hash）可以人为设下陷门密钥，掌握了陷门密钥就能轻松计算出不同数据指向相同的哈希碰撞[24]。对没有陷门密钥的用户而言，变色龙哈希函数依然满足抗碰撞性 。

定义1 一个变色龙函数由四个算法组成Cham_hash=（Setup，KeyGen，CHash，CForge）组成。

1）Setup（）：输出公共参数pp。

2）KeyGen（pp）：输入公共参数pp，输出公私钥对（HK，CK），HK为公钥，CK为私钥又称陷门。

3）CHash（HK，m，r）：输入公钥HK、消息m和随机数r，输出变色龙哈希值CH。

4）CForge（CK，m，r，m′）：输入私钥CK、消息m、随机数r、消息m′，输出另一个随机值r′，满足CH=CHash（HK，m，r）=CForge（CK，m，r，m′）。

变色龙哈希函数的安全性要求为：

1）抗碰撞性（collision resistance）：不存在一个有效算法，在输入公钥HK，可以得到（m1，r1）和（m2，r2），其中m1≠m2，满足CHash（HK，m1，r1）=CHash（HK，m2，r2） 。

2）陷门碰撞（trapdoor collisions）：存在有效算法，在输入陷门CK后，对于任意的m1、r1，给定m2，可计算出r2满足CHash（HK，m1，r1）=CHash（HK，m2，r2）。

3）语义安全（semantic security）：对于任意消息m1、m2，CHash（HK，m1，r1） 与CHash（HK，m2，r2）的概率分布是不可区分的;特别地，当r为随机选择时，从Chash（HK，m，r）无法得到关于m的任何消息。

3 本文方案

3.1 系统框架和流程

基于嵌套MHT区块链的云数据动态审计模型框架如图1所示。

整个模型中涉及到的实体以及功能如下：

普通用户（Common Owner， CO）：该角色主要是持有大量的数据，同时将数据托管给云存储服务提供商，该角色可以是私人用户或者公司等需要保存数据的角色。

授權用户（Delegate Owner， DO）：该角色是通过DPoS共识，由分布式网络所有的CO投票产生，该角色持有大量数据托管给云存储服务提供商，同时监测全网CO发送的元数据证据消息，为全网用户的数据提供数据完整性验证服务。

云存储服务提供商（CSP）：该角色提供云存储服务，拥有海量的存储空间、可靠的计算资源，同时提供稳定服务。

该方案的大致过程如下：

1）DPoS共识：分布式网络中所有的CO执行该过程，产生DO用户，约定区块生成的顺序和审计任务。

2）上传UBlock：分布式网络中所有的用户将要保存在CSP的文件经过处理后生成一个UBlock文件上传到CSP保存。

3）上传Ublock* ：分布式网络中所有的用户在上传UBlock的时候，会生成一个不包含原始数据但包含元数据的Ublock*发送给指定的DO（激活）保存。

4）区块签署：当DO（激活）生成一个区块文件之后，向CSP发起一个区块签署挑战请求CSP返回一个签署证据响应。DO（激活）通过检查CSP返回的证据响应就可以确定CSO是否如约保存了分布式网络全体用户在该DO（激活）工作时间内托管的文件。

5）区块审计：DO为了验证其存储的所有区块代表的用户数据的完整性，依照DPoS规定的时间表，周期性地向CSP发起区块审计挑战，验证CSP返回的证据的正确性。

6）动态操作：当分布式网络中的用户需要修改、删除、增加其已经托管在CSP的数据时，执行该操作。

3.2 嵌套MHT数据结构

传统的区块链应用模型中，用户每一次交易的证据都保存在区块链上，交易数据较小且每次交易之间的数据没有关联性。但是，在审计过程中，用户文件比较大，为了减轻元数据的计算压力，文件一般会进行分块处理。如果直接引用传统区块链上的概念来存储数据，则会破坏分块数据之间的关联性。此外，传统的区块链应用模型中，是不允许对交易数据进行修改的。但是现今的审计往往要求针对动态数据的完整性验证，为了将区块链技术和动态云数据审计结合起来，必须要对区块链的底层数据结构作出相应修改。故本文专门引入变色龙哈希技术和嵌套MHT结构来适应区块链上验证动态数据的完整性。该结构中，顶层的MHT用来保证多个文件的完整性和空间位置的正确性，底层的MHT保证单个文件的分块数据在空间位置的正确性和数据的完整性，其具体结构如图2所示。

为了支持数据动态操作和数据安全，用户只能操作底层MHT结构。通过变色龙哈希算法，假设底层MHT结构发生了改变也能保证上层MHT结构不变，从而解决了区块链不可变和云存储动态操作的矛盾。由图2可知，顶层MHT的叶子节点保存都是某个用户存储在CSP的文件，其内部非叶子节点存储的都是经过变色龙哈希函数计算得到的哈希值。底层MHT的叶子节点保存都是某个用户托管于CSP文件的分块数据，其内部非叶子节点存储的都是经过变色龙哈希函数计算得到的哈希值。

3.3 模型关键流程

本文的方案主要由密钥初始化阶段、元数据和变色龙哈希生成阶段、数据分发和区块生成阶段、签署阶段、区块审计和错误数据定位阶段等六部分组成。

3.3.1 密钥初始化阶段

选取公共参数e和安全参数λ，构造满足安全参数λ的大素数p、q。其中p、q满足p=k·q+1，选取乘法循环群Zp*阶为q的元素gc，输出公共参数pp=（p，q，gc）;G×G→GT是双线性映射，gb是G的生成元;Hb：{0，1}*→G是将数据映射到G群的哈希函数;Hc： {0，1}*→Zp*是数据映射到Zp*群的哈希函数;H： {0，1}*→Zr是数据映射到Zr群的哈希函数 。输入公共参数pp， 在乘法循环群Zp*中随机选择指数x，计算h=gxc，最后得到私钥CK=x，公钥HK=h;随机选取私钥SK=a←Zp，计算其相对应的公钥PK=gab。

3.3.2 元数据和变色龙哈希生成阶段

选取文件的唯一标识v←{0，1}R，随机辅助变量v←G，对文件F进行分块：F={b1，b2，…，bn};将所有分块文件分别映射到Zr群，得到mi=H（bi）生成认证元数据集合={σi}1≤i≤n，这里σi=Hb（mi）·umi。对每一个分块文件mi，生成一个随机数ri←Zq*，输出变色龙哈希CHmi=gmic·hri mod p。

3.3.3 数据分发和区块生成阶段

用户将文件F的每个分块文件bi、mi、σi和CHmi组合成Unodei，后执行底层MHT构造算法（详情见算法2）生成UBF发往CSP存储，同理生成相应的证据UBF*发往DO（激活）存储。用户可以删除本地文件，只保留UBF*数据以便以后修改数据用。当CSP接收到m个用户发送的UBF之后，执行顶层MHT构造算法（详情见算法2）生成一个区块文件。同理DO（激活）在收集到m个用户发送的UBF*之后，也生成一个未签署、未审计的区块文件。

3.3.4 签署区块阶段

当DO生成一个区块文件之后，直接读取头部文件中的ID值，要求CSP就符合ID一致的区块返回其头部的U_ROOT值。若DO本地区块的U_ROOT值和CSP返回的U_ROOT值一致，则CSP可以证明其已经保存了该时间段内区块链网络中所有用户托管在CSP的数据，DO发送签署消息到CSP完成区块签署。

3.3.5 区块审计和错误数据定位阶段

DO（激活）选择一个未审计的区块，这个区块内包含m个UBF*文件。针对每个UBF*文件随机抽取C个UN*的索引为UnodeIDi，并对每个索引选取一个相对应的随机数vi←Zp/2。由此可以组成一个UBF*挑战块τF={Unodei，vi}（1≤i≤c），m个UBF*挑战块组成了这个区块文件的挑战chal={τFi，BlockIDi}（1≤i≤m）发送到CSP。

CSP接收到chal挑战后，依據BlockID找到被挑战的区块UBlock。依据τFi找到被挑战的UN分块文件，通过UnodeIDi得到每个被挑战分块文件的辅助消息αi=（UnodeIDi，LMi，dataHashi），将c个辅助消息组合成一个集合β={αi}1≤i≤c。对每一个τFi，首先计算σFi=∏cj=1σvjj，后计算μFi=∑cj=1mj·vj，最后组成φFi=（σFi，μFi，βFi）。同理可得，对于其他的τF，CSP计算与其对应的φF。CSP计算完所有的φF，将其整合成一个Res={φFi}1≤i≤m返回给发出挑战的DO。

DO接收到CSP返回的Res={φFi}1≤i≤m消息之后，对其中的每一个φFi依据式（1）判断存储在CSP的用户数据的完整性。若式（1）输出true，则说明该UB文件块数据内容完整;若式（1）判断发生错误，则说明DO挑战的该UB中的分块文件发生错误，此时执行错误数据定位，具体流程详见算法4。此时，DO读取发生错误的UB的βFi，通过直接读取辅助消息UnodeID，确定DO发出的挑战分块文件在DO本地存储的LM消息和dataHash消息，通过比较LM=LMi和dataHash=dataHashi来定位错误数据的具体位置。

3）MHT[0]=new Unode[n]

4）While i less than n

5） set MHT[0][i]←UNodei

6） Construction inner node

7）If n equal 1

8） set URoot←MHT[0][0].getHash（）

9）Else

10） set flow←0

11） While n not equal to 1

12）If n is EVEN

13） flow++;n←n/2;

14） MHT[flow]←GenFlow（MHT[flow-1]）

15）Else

16） flow++;n←n/2+1;

17） MHT[flow]←GenFlow（MHT[flow-1]）

18） MHT[flow][n-1]←pGen（MHT[flow-1]

[2（n-1）]）

19）End If

20） End While

21）End If

22）set URoot←MHT[flow][0].getHash（）程序后

该算法中，首先通过第2）～5）行将所有的UNode存储在最顶层的叶子节点中;如果叶子节点数唯一，则叶子节点就是根节点，MHT构造结束;若叶子节点不是1，则通过层次构建思想，在第11）～20）行中，通过高一层的节点，从上往下构造下层内部节点，同时依据上层节点数目的奇偶来执行不同的构造过程。若上层是偶数节点，则下层节点数目一定是奇数，通过上层节点两两配对的方式，计算下层节点的变色龙哈希数据;若上层是奇数节点，则除开最后一个奇数节点直接复制到下层节点。其余偶数个节点和偶数层节点处理方式一样，通过层层递进的方式，最终将所有的叶子节点映射成最下层的根节点。

3.5.3 动态操作插入算法

算法3 动态操作插入（CSP_INSERT）。

输入 N-MHT，Insert_to_CSP（insertNode，LM）;

输出 {false/true}。程序前

1） Find insert UBlock

2）ublock←N-MHT.getUblock（UblockID）

3） Find insert position Node

4）insert_pNode←ublock.getNode（LM）

5） Judege Insert Operation legal

6）If ublock.check（insetNode，insert_pNode）

7） return false

8）Else

9） set mhtHeigh←ublock.level-1

10） If node.isLeafNode（）

11）If LM.x

12）Insert（LM.x，LM.y，insertNode）

13） Else If LM.x equal mhtHeih

14） curN←mht[mhtHeigh].getSize（）

15） mhtHeigh++

16） ublock.getMHT（）.createArea（mhtHeiht，

2*curN）

17） Insert（LM.x+1，2*LM.y，insertNode）

18）End If

19） Else

20）Insert（LM.x，LM.y，insertNode）

21）End If

22） End If

23） Update Insert Position Parent Node message

24）updateParentMess（LM，insertNode.getLM（））

25） return true

26）End If程序后

该算法中，首先通过第1）～3）行确定用户插入的节点位置，在通过第5）行，验证用户动态操作的合法性，判断通过才能执行插入操作;在第9）～11）行中，用户插入的位置是叶子节点，且其插入位置的深度小于此时MHT的深度，即内部节点已经构造完毕，因此只需要将节点插入即可;第12～16）行中，用户插入节点的位置是叶子节点且插入位置的深度和MHT的深度一致，即插入的位置是MHT最底层的节点，因此必须要构造新的下一层空间来存储插入的节点;在第19）行中，插入节点的位置不是叶子节点，即插入的位置是原先存放叶子节点但经过删除操作的节点，因为删除操作不会删除存储空间，因此不需要构造额外空间，直接进行存储;在第22）行中，执行了存储操作之后，需要修改插入操作所涉及的节点的关系信息和MHT的深度和叶子节点个数等信息。

3.5.4 错误数据定位算法

算法4 错误数据定位（Location_error_data）。

输入 βFi=（α1，α2，…，αc），UB*Fi;

輸出 LM。程序前

1） Find challenged Node

2） While αi in βFi

3）chalNode←UB*Fi.getNode（αi.LM）

4）Judge node is wrong

5） If judgeNode（αi，chalNode） is wrong

6）return chalNode.getLM（）

7） End If

8） End While程序后

该算法中，第2）～3）行直接遍历所有挑战节点的位置信息，找到存放在UBlock*中的节点;通过第5）行比较UBlock*中节点的Data_hash和CSP返回的认证消息中对应的Data_hash得出节点数据是否发生改变;第6）行得到发生错误数据的LM消息，从而定位错误数据具体位置。

4 实验与结果分析

4.1 安全性分析

为了保证云存储数据的完整性和区块链签署速度，本文方案主要引入了变色龙哈希算法、非对称加密算法（主要应用BLS签名算法）和N-MHT结构。用户的数据都保存在N-MHT的底层MHT中，通过变色龙哈希算法将每个文件的变色龙哈希值最终映射成顶层MHT的根节点值，通过根节点值来保证区块快速签署和查找;通过底层MHT结构和非对称加密算法来保证数据完整性检测。当用户需要执行数据动态操作，需要通过变色龙哈希算法计算出需要修改数据的变色龙哈希陷门，通过CSP和DO的认证就可以执行。变色龙哈希满足一般安全哈希算法的强抗碰撞性、高灵敏度等要求，除非持有变色龙哈希算法私钥才能计算出陷门，得出哈希碰撞，恶意用户不能通过收集到的动态操作数据计算出用户持有的变色龙私钥，无法非法执行动态操作，污染用户数据。

4.2 实验分析

4.2.1 实验环境

实验硬件环境为：1）4台PC机器组成分布网络，CPU 2.0GHz，RAM为2GB;2）1台PC机器作为CSP服务器，CPU 3.2GHz，RAM为24GB。

实验软件环境为：1）操作系统为64位Windows 10;2）编程语言为Java;3）编程工具为Eclipse ide、jdk1.8.0、Jxta 2.4、Jxta CMS 2.4.1、JPBC 2.0.0。

本实验使用1台高性能计算机搭建CSP云存储服务器，用于存储区块链网络中用户托管的数据和维护数据动态操作;4台机器搭建Jxta分布式网络组成区块链网络，每台机器上可以同时运行若干区块链节点实体，各个节点实体之间没有主次之分，每个节点都可能成为普通用户和授权用户。

4.2.2 审计时间分析

实验一 设置1个DO用户，3个CO用户，CSP/DO接收到4个Ublock/Ublock*时生成一个区块文件。规定每个用户发送的文件大小为50MB，每个用户和DO均发送5个文件，总计有1GB的数据存储在CSP上，预计生成5个区块文件;规定在可信度为99%的条件下，在文件分块数分别为10、50、100、250时比较审计完所有用户数据所需要的平均时间开销，具体结果如图6所示。由图6可以看出，文献[5]方案验证1GB用户数据的时间随着分块文件规模增大而减少，但是整体时间开销仍然大于本文方案。根据BLS签名的特性，在文件容量不变的前提下，文件分块数越多，计算其元数据的时间开销会减少，审计需要计算的元数据开销也会减少，本文方案和文献[5]方案均是基于BLS签名的PDP方案，因此随着文件分块数增加，审计时间开销会减少。在文献[5]方案中，每次均是对1个用户的1个文件发出挑战。为了验证全网4位用户总计20个文件的完整性，文献[5]方案需要对CSP发出20次挑战才能验证所有文件的完整性;而本文方案采用区块挑战，每个区块中存放4个用户文件，只需要挑战5次就达到和文献[5]方案一样的效果，减少了审计挑战次数，降低整体时间开销。

实验二 规定用户每次发送的文件大小为50MB，文件分块数为50，即每个分块文件大小为1MB，每个用户发送的文件数目为5，共计1GB的数据存储在CSP;CSP/DO接收到4个Ublock/Ublock*时生成1个区块文件，预计生成5个区块文件，修改了DO用户的数量从1到3，在可信度为99%的条件下，比较审计完所有用户数据所需要的平均时间开销，具体结果如图7所示。从图7可以看出，本文方案和文献[5]方案均对CSP中存放的1GB数据进行完整性验证，随着DO用户数量增加，完成1GB数据完整性验证的时间逐渐减少。在文献[5]方案中，只有1个TPA实体提供审计服务，而在本文方案中，同样提供审计服务的DO实体是可以随着DPoS共识动态设定的，因此本文方案可以避免单TPA失效导致审计服务崩溃，同时多DO环境下可以有效加速用户数据审计速度。

4.2.3 动态操作时间分析

实验三 规定用户文件大小为50MB，文件分块数为100，用户发送文件数量分别为20、50、100;规定区块链网络设置DO用户为1，CO用户数量设置为3;CSP/DO收集到5个Ublock/Ublock*则生成一个区块文件，预计生成16、40、100个区块文件。动态操作涉及Update、Insert、Delete，均是在随机位置执行，每种操作均执行50次，统计每种操作的平均时间开销，具体结果如图8所示。从图8可以看出，动态操作得时间开销均随着用户文件规模增大而增大，本文方案的动态操作时间开销均小于文献[6]方案，其原因在于：在文献[6]方案中，删除和插入操作需要移动动态操作节点后续的所有节点，导致时间开销增大。对于更新操作，本文方案将用户的文件处理成为1个区块文件，动态操作文件定位时间开销较小，而文献[6]方案中必须按照顺序去查找用户的文件从而增加了文件查询的时间。

4.2.4 错误数据定位时间分析

实验四 规定用户文件大小为50MB，文件分块数为50，全网用户总计发送文件数目分别为为100、200、300、400;区块链网络设置DO用户为1，CO用户数量设置为3;CSP/DO收集到5个Ublock/Ublock*则生成1个区块文件，预计生成区块文件数目分别为20、40、60、80。当DO对CSP发送回的挑战证据进行验证发现错误时，查找具体分块数据錯误位置信息的平均时间，结果如图9所示。从图9可以得出，在相同文件总量的条件下，本文方案的定位错误数据的时间开销要小于文献[6]方案，其原因在于：本文方案中用户的文件经过一定的聚合，实际遍历所有用户文件数目要少于文献[6]方案中依靠顺序遍历的方式。

5 结语

为了克服基于TPA方案单点失效、算力瓶颈等缺陷，本文提出了一种基于变色龙哈希算法的可编辑区块链的云数据完整性验证方案。该方案借助区块链技术中的分布式网络，将云用户的数据标签存储在区块链上，通过共识算法选出的授权用户代替全体用户，借助区块链上的数据标签向云存储服务提供商发出数据完整性挑战并验证。此外，为了满足云数据动态操作的需求，特别地引入了变色龙哈希算法和独创的N-MHT结构，保证了修改区块链上部分区块文件不会导致整个链上数据均发生改变，满足了用户数据动态操作的可能和审计错误时针对错误数据的定位。实验结果表明，本文提出的方案相较TPA方案能显著缩短平均审计、动态操作、错误数据定位的时间开销。虽然本文方案挖掘了区块链和审计之间的联系，但由于时间和水平有限，本文研究还有以下问题，可以作为我们进一步研究的方向：

1）在删除操作过程中，N-MHT结构并没有回收节点的存储空间，只是将该节点的数据部分置空，该节点的残余信息依然残留在区块链中，浪费了存储空间。

2）在插入操作过程中，如果插入的位置是底层MHT的最底层叶子节点，将会在原先底层MHT的基础上，额外开辟新的一层空间去存储插入节点，对同一位置进行连续插入操作会造成极大的空间浪费。

3）由于该区块链系统主要是来考虑私有链，假定认为所有的节点都是可信的，因此没有考虑动态操作过程中可能存在恶意用户发动的重复攻击和伪造攻击。针对重复攻击和伪造攻击，可以借助时间戳解决该缺陷。

参考文献 （References）

[1]谭霜，贾焰，韩伟红.云存储中的数据完整性证明研究及进展[J].计算机自动化学报，2015，38（1）：164-177.（TAN S， JIA Y， HAN W H. Research and development of provable data integrity in cloud storage [J]. Chinese Journal of Computers， 2015， 38（1）： 164-177.）

[2]WANG Q， WANG C， LI J， et al. Enabling public verifiability and data dynamics for storage security in cloud computing [C]// Proceedings of the 2009 European Conference on Research in Computer Security， LNCS 5789. Berlin： Springer， 2009： 355-370.

[3]WANG C， WANG Q， REN K， et al. Privacy-preserving public auditing for data storage security in cloud computing [C]// Proceedings of the 29th Conference on Information communications. Piscataway： IEEE， 2010： 525-533 .

[4]ZHENG Q， XU S. Fair and dynamic proofs of retrievability [C]// Proceedings of the 1st ACM Conference on Data and Application Security and Privacy. New York： ACM， 2011： 290-295.

[5]WANG Q， WANG C， REN K， et al. Enabling public auditability and data dynamics for storage security in cloud computing [J]. IEEE Transactions on Parallel and Distributed Systems， 2011， 22（5）： 847-859.

[6]YANG K， JIA X. An efficient and secure dynamic auditing protocol for data storage in cloud computing [J]. IEEE Transactions on Parallel and Distributed Systems， 2013， 24（9）： 1717-1726.

[7]ERWAY C C， KP A， PAPAMANTHOU C， et al. Dynamic provable data possession [J]. ACM Transactions on Information and System Security. New York： ACM， 2015： Article No.15.

[8]李勇，姚戈，雷麗楠，等.基于多分支路径树的云存储数据完整性验证机制[J].清华大学学报（自然科学版），2016，56（5）：504-510.（LI Y， YAO G， LEI L N， et al. LBT-based cloud data integrity verification scheme [J]. Journal of Tsinghua University （Science and Technology）， 2016， 56（5）： 504-510）.

[9]GARG N， BAWA S. RITS-MHT： relative indexed and time stamped merkle Hash tree based data auditing protocol for cloud computing [J]. Journal of Network and Computer Applications， 2017， 84： 1-13.

[10]FILHO D L G， BARRETO P S L M. Demonstrating data possession and uncheatable data transfer [EB/OL]. [2019-01-20]. https：//eprint.iacr.org/2006/150.pdf.

[11]DESWARTE Y， QUISQUATER J J， SA？DANE A. Remote integrity checking [C]// Proceedings of the 2003 Working Conference on Integrity and Internal Control in Information Systems， IFIPAICT 140. Boston： Springer， 2004： 1-11.

[12]ATENIESE G， BURNS R， CURTMOLA R， et al. Provable data possession at untrusted stores [C]// Proceedings of the 14th ACM Conference on Computer and Communications Security. New York： ACM， 2007： 598-609.

[13]ATENIESE G， DI PIETRO R， MANCINI L V， et al. Scalable and efficient provable data possession [C]// Proceedings of the 4th International Conference on Security and Privacy in Communication Networks. New York，： ACM， 2008： Article No. 9.

[14]CURTMOLA R， KHAN O， BURNS R C， et al. Robust remote data checking [C]// Proceedings of the 4th ACM International Workshop on Storage Security and Survivability. New York： ACM， 2008： 63-68.

[15]ATENIESE G， BURNS R， CURTMOLA R， et al. Remote data checking using provable data possession [J]. ACM Transactions on Information and System Security， 2011， 14（1）：  Article No.12.

[16]袁勇，王飞跃.区块链技术发展现状与展望[J].自动化学报，2016，42（4）：481-494.（YUAN Y， WANG F Y. Blockchain： the state of the art and future treads [J]. Acta Automatica Sinica， 2016， 42（4）： 481-494.）

[17]谢辉，王健.区块链技术及其应用研究[J].信息网络安全，2016（9）：192-195.（XIE H， WANG J. Study on blockchain technology and its applications [J]. Netinfo Security， 2016（9）： 192-195）

[18]何蒲，于戈，張岩峰，等.区块链技术与应用前瞻综述[J].计算机科学，2017，44（4）：1-7，15.（HE P， YU G， ZHANG Y F， et al. Survey on blockchain technology and its application prospect [J]. Computer Science， 2017， 44（4）： 1-7， 15.）

[19]杨宇光，张树新.区块链共识机制综述[J].信息安全研究，2018，4（4）：369-379.（YANG Y G， ZHANG S X. Review and research for consensus mechanism of block chain [J]. Journal of Information Security Research， 2018， 4（4）： 369-379）

[20]NAKAMOTO S. Bitcoin： a peer-to-peer electronic cash system [EB/OL]. [2019-01-20]. https：/bitcoin.org/bitcoin.pdf.

[21]LARIMER D. Transactions as proof-of-stake [EB/OL]. [2019-01-20]. http：//7fvhfe.com1.z0.glb.clouddn.com/wp-content/uploads/2014/01/TransactionsAsProofOfStake10.pdf.

[22]LARIMER D. Delegated proof-of-stake white paper [EB/OL]. [2019-01-20]. http：//www.bts.hk/dpos-baipishu.html.

[23]杜欣军，王莹，葛建华，等.基于双线性对的Chameleon签名方案[J].软件学报，2007，18（10）：2662-2668.（DU X J， WANG Y， GE J H， et al. Chameleon signature from bilinear pairing [J]. Journal of Software， 2007， 18（10）： 2662-2668.）

[24]李佩丽，徐海霞，马添军，等.可更改区块链技术研究[J].密码学报，2018， 5（5）：501-509.（LI P L， XU H X， MA T J， et al. Research on fault-correcting blockchain technology [J]. Journal of Cryptologic Research， 2018， 5（5）： 501-509.）

ZHOU Jian， born in 1994， M. S. candidate. His research interests include cloud computing security.

JIN Yu， born in 1973， Ph. D.， associate professor. Her research interests include cloud computing， software defined network， network security.

HE Heng， born in 1981， Ph. D.， associate professor. His research interests include cloud computing， software defined network， network security.

LI Peng， born in 1981， Ph. D.， associate professor. His research interests include Internet of vehicles.

收稿日期：2019-05-06;修回日期：2019-08-06;錄用日期：2019-08-12。

作者简介：周坚（1994—），男，湖北咸宁人，硕士研究生，主要研究方向：云计算安全; 金瑜 （1973—），女，湖北武汉人，副教授，博士，主要研究方向：云计算、软件定义网络、网络安全; 何亨（1981—），男，湖北武汉人，副教授，博士，主要研究方向：云计算、软件定义网络、网络安全;李鹏（1981—），男，湖北武汉人，副教授，博士，主要研究方向：车联网。

文章编号：1001-9081（2019）12-3575-09DOI：10.11772/j.issn.1001-9081.2019040764