一种基于Merkle-Tree的云存储数据持有性检查方案∗

孟浩华 曹波 袁慧 董亮

（国网湖北省电力公司信息通信公司武汉430077）

一种基于Merkle-Tree的云存储数据持有性检查方案∗

孟浩华 曹波 袁慧 董亮

（国网湖北省电力公司信息通信公司武汉430077）

随着用户使用云存储备份个人数据的流行，数据的完整性成为一个研究热点。数据持久性证明是解决这一问题的方法之一。但是有关数据持有性证明的验证机制大都带来较大的计算开销和通信开销。分析数据持有性证明存在的问题，提出基于Merkle-Tree的数据持有性验证机制。仿真实验结果表明，论文协议实现数据持有性的同时保证了较低的计算和通信开销。

云存储；数据持有性；Merkle-Tree；Merkle Hash Tree

Class NumberTP333

1 引言

云存储是一种新的网络存储技术，是在云计算概念上发展出来新概念。有了云存储技术，使用者可以在任何时间、任何地方、透过任何可连网的装置连接到云上方便地存取数据、但用户享受海量的云存储空间的同时，也出现了的一些云存储数据的安全性和完整性问题［1］。数据的机密性通常通过数据加密机制、匿名机制等保证。当用户将私有数据上传到云端后，可能没有在本地保存数据副本，此时云端数据的完整性则变得尤为重要［2］。而以下三种行为会导致云端数据持久性的破坏：1）云端用户数据丢失，主要是云存储系统的硬件故障或者软件系统故障引起的；2）云端用户数据被损坏，比如恶意用户故意破坏；3）云端用户数据被删除，比如云服务提供商出于自身利益擅自删除云端用户数据。这些因素导致的云端用户数据的丢失或损坏都属于数据持久性破坏的行为。

针对云存储中的数据持有性问题，学术界开展了大量的研究工作。本文对目前的研究成果进行了分析，提出了一种基于Merkle-Tree的数据持有性证明方案，该方案对于静态云存储系统非常高效。

2 相关工作

针对云存储中数据的损坏和丢失问题，学术界展开了大量的研究，出现了很多研究成果，数据完整性证明机制被认为是一种有效的识别云存储中数据是否损坏的机制。目前存储系统主要有两种数据完整性检查方案：1）基于访问的数据完整性检查，该方式访问服务器频繁，给服务器带来了很大的负担；2）基于挑战和应答的数据完整性检查，该方式不需要频繁访问服务器，用户需要的时候主动发起完整性验证请求（挑战），服务器根据查询的内容返回数据完整性的证明（应答），用户对收到的数据完整性证明进行判断。可证明数据持有（Prov⁃able Data Possession，PDP）机制就是一种基于挑战和应答的验证机制。PDP机制最初用于网格计算和P2P网络，在这两种应用中，用户将数据备份到了远程结点中［2］。PDP机制能快速判断远程节点上数据是否损坏，更多的注重效率，但该模型没有考虑数据在传输过程中的安全性；Deswarte［3］等最先利用HMAC哈希函数验证远程数据的完整性，将从远程节点取回的数据MAC值与本地保存的MAC进行比对，根据比较结果来判断远程节点的数据是否完整。但是该验证机制需要计算整个数据的MAC值，因此有很大的计算开销和通信开销。Zhu［4］等提出了分层混合云模型，将用户数据存储在不同的云储存服务商中。该模型增加用户数据的可靠性，但是增加了额外的存储开销。近年来，Wang等［5～6］和Zhang等［7］针对云存储中用户共享文件的完整性展开了研究，提出了多个解决方案，这些方案用于非用户组共享环境下效率不高。

以上的研究成果虽然在一定程度上都提高了云端用户数据的可靠性，能够进行一定程度的数据完整性检查，但是都会带来很大的存储开销或通信开销。本文基于静态存储系统，考虑到云存储的网络环境特征，使用安全协议来保障用户数据的安全性，提出一种基于Merkle-Tree的数据持有性证明方案，该方案对于静态云存储系统非常高效。

3 基于Merkle-Tree的安全云存储数据持有性检查方案

3.1 Merkle-Tree

Merkle Tree［8～9］也被称为Merkle Hash Tree，是一种数据结构中的树，该树中的所有节点的数据都是Hash值，如图1所示。Merkle Tree具有以下三个特点：

1）它是一种树，从而具有树结构的所有特点；

2）该树中叶子节点上的值可以自行指定，比如指定为数据的Hash值；

3）树中非叶子节点的值是由某个算法根据其下面所有的叶子节点值计算出来的。如图1中节点7的值是通过节点15和16的值计算得到的。

图1Merkle Hash Tree

下面来说明数据验证过程，如图1中，15，16，…，30分别是不同数据块的hash值，当这些数据从一个端点A传输到另一个端点B后，只要验证A和B两端的Merkle Tree的根节点的值是否一致即可判断数据在传输过程中是否被篡改过，并且通过比对树中所有节点的值能够定位哪些数据被修改过。

目前，Merkle Tree已在处理对比或者验证的计算机应用场景得到了广泛应用，在处理这些对比或验证时，可以降低计算的复杂性并减少数据的通信消耗。

3.2 云存储系统模型

本文提出的基于Merkle-Tree的数据持有性证明采用的云存储模型如图2所示，该模型由云存储服务器（Cloud Storage Server，CSS）、可信第三方审计（Trusted Party Auditor，TPA）和用户Users三方组

成［10］。

云存储服务器CSS由云服务提供商（Cloud ServerProvider，CSP）管理，拥有很强计算能力和海量的存储空间，可以为用户提供计算或者存储服务。第三方审计TPA拥有用户所不具备的审计能力，可以代替用户向CSS发出数据完整性验证请求，减轻用户端的负担。用户Users则是需要海量存储或超强计算的实体，可以根据需求定制云存储服务。

图2云存储模型

3.3 基于Merkle-Tree的数据持有性验证协议

该算法为用户端提供一种有效的验证算法，在云存储服务器不可信且本地没有存储备份的前提下，该验证周期性地去检查用户的数据是否完整，有没有被篡改或者丢失。

基于Merkle-Tree的数据持有性验证方案由准备阶段和验证阶段组成，因此基于Merkle-Tree的数据持有性验证协议分为准备阶段协议和验证阶段协议，下面分别介绍这两个协议。

假设文件F被分割为相互独立的n块m1，m1，m2，…，mn，记为F=(m1，m2，…，mn)。其中mi∈Zp且p为大质数，令双线性映射e:G×G→GT，其哈希函数为H:{0，1}*→G，g为G的生成子。

协议1准备阶段协议

准备阶段工作由用户端完成，主要是生成Merkle Hash Tree，发送给CSS，具体流程如下：

1）用户端Users通过RSA非对称加密算法生成一对签名的密钥（spk，ssk）后，选择一个随机数Zp→α，计算出ga→v。令其私钥为sk=(α，ssk)，公钥为pk=(v，spk)。

2）给定一个文件F=(m1，m2，…，mn)，用户端Users选择一个随机元素G→u，令t= name||n||u||SSigssk（name||n||u），其中SSigssk（.）表示用私钥ssk签名。

3）用户端Users为每一个文件块mi(i=1，2，…，mn)生成签名σi，其中σi←(H(mi)·umi)α为了方便，将签名的集合表示为Φ={σi}，1≤i≤n。

4）用户端Users生成一个Merkle Hash Tree，其叶子节点为文件块的哈希值H(mi)(i=1，2，…，n)，根记为R。

5）用户端Users使用私钥sk对Merkle Hash Tree的根R进行签名：sigsk(H(R))←(H(R))α。

6）用户端Users将{F，t，Φ，sigsk(H(R))}发送给CSS，删除本地的{F，t，Φ，sigsk(H(R))}。

协议2验证阶段协议

验证阶段即是数据完整性检查阶段，发起数据完整性验证请求称为“挑战”。该阶段中Users和TPA都可以向CSS发起验证数据完整性的请求。下面以TPA向CSS发起挑战为例，介绍验证流程：

1）在发起挑战之前，TPA首先用Users的公钥spk验证存储在t中的Users的签名，如果签名验证不能通过，则直接返回验证失败，如果验证通过，则将u恢复出来，继续执行下一步。

2）TPA生成一个含有c个元素的[1，n]的子集I={s1，s2，…，sc}，其中s1≤…≤sc，对于每一个i∈I，TPA选择一个随机的元素vi←B⊆Zp。在此定义chal{(i，vi)}s1≤i≤sc为“挑战信息”，挑战信息的i代表了文件F中文件块的位置。

3）TPA将挑战信息chal{(i，vi)}s1≤i≤sc发送给CSS，发起验证数据完整性的请求。

4）CSS收到挑战信息chal{(i，vi)}s1≤i≤sc之后会计算两个值，分别是

其中m值是将被选中的若干文件块都聚合成一个文件块μ，σ值是将和文件块对应的签名块都聚合成一个签名块。

5）CSS用生成的m和s两个值加上一些辅助信息{Ωi}s≤i≤s生成证据P={μ，σ，{H(mi)，Ωi}s1≤i≤sc，'1c'sigsk(H(R))}，回应TPA挑战。

TPA可以根据辅助信息{Ωi}s≤i≤s和叶子节点

1c'{h(H(mi))}s≤i≤s计算出Merkle Hash Tree的根R。

1c

6）TPA接收到CSS返回的证据P之后，验证CSS返回的证据P，看其是否能够证明用户存储在CSS的文件F是完整的。

TPA根据接收到的辅助信息{H(mi)，Ωi}s1≤i≤sc'计算出MerkleHash Tree的根R，然后验证以下等式是否成立：

如果等式不成立，则表示验证失败，否则，再验证如下等式是否成立：

如果等式不成立，表示验证失败；否则，表示完整性验证成功。

综上所述，基于Merkle-Tree的数据持有性验证方案首先是由用户端根据文件块构造Merkle Hash Tree，并将其发送给CSS，当用户需要检查CSS中存储的数据是否完整时，则可以由TPA向CSS发起数据完整性验证请求，TPA根据CSS返回的应答证据进行验证，检查Merkle Hash Tree中根节点的哈希值是否与原始的Merkle Hash Tree一致，根据验证结果为用户返回数据是否完整信息。

4 协议性能分析

本文在Inter（R）Core（TM）i5-4590 3.30 GHz CPU，4G内存的Windows 7系统进行仿真实验，仿真程序在VS2010开发环境中设计，Hash函数使用SHA1，文件块大小为64KB。

4.1 时间开销

对不同大小的文件通过仿真程序进行测试，随机抽取其中20%的数据库进行验证完整性，得到如图3所示的验证时间开销，从中可知，基于Merk⁃le-Tree的数据持有性协议进行数据完整性验证所花费的时间比PDP更小。

图3时间开销对比

4.2 通信开销

使用Merkle Hash Tree进行数据持有性验证，TPA发起的挑战信息和CSS返回的应答信息都不需要传输所有文件块的哈希值，有效的节约了通信开销。实验对不同大小的文件分别进行测试，然后统计验证过程中发生的通信数据总和，得到如图4所示的通信开销，从中可知基于基于Merkle-Tree的数据持有性协议降低了数据完整性检查中的通信开销。

图4通信开销对比

5 结语

对于云存储中数据完整性验证问题，大多PDP验证机制会带来额外的通信开销和计算开销。本文提出基于Merkle-Tree的持有性检查方案采用第三方审计模式，为用户验证云存储中的文件是否完整提供了有效的机制。同时仿真实验结果表明，该机制的计算开销和通信开销都比较小，非常适应于静态云存储。但是该方案对于动态数据存储方面不够高效，因此，对于动态云存储环境下，数据的完整性验证问题仍是一个有待研究的问题。

［1］曹夕，许力，陈兰香.云存储系统中数据完整性验证协议［J］.计算机应用，2012，32（1）：8-12. CAO Xi，XU Li，CHEN Lanxiang.Data integrity verifica⁃tion protocol in cloud storage system［J］.Journal of Com⁃puter Applications，2012，32（1）：8-12.

［2］谭霜，贾焰，韩伟红.云存储中的数据完整性证明研究及进展［J］.计算机学报，2015，38（1）：164-177. TAN Shuang，JIA Yan，HAN Weihong.Research and De⁃velopment of Provable Data Integrity in Cloud Storage［J］. Chinese Journal of Computers，2015，38（1）：164-177.

［3］Deswarte Y，Quisquater J J，Saidane A.Remote integrity checking［C］//Proceedings of the IFIP TC11/WG11.5 6thWorking Conference on Integrity and Internal Control in Information Systems（IICIS）.Lausanne，Switzerland，2004：1-11.

［4］ZHU Y，WANG H，HU Z，et al.Efficient provable data possessionfor hybrid clouds［C］//CCS'10：Proceedings of the 17th ACM Conference on Computer and Communica⁃tions Security.New York：ACM Press，2010：756-758.

［5］B.Wang，B.Li，H.Li.Oruta：Privacy-Preserving Public Auditing for Shared Data in the Cloud［C］//Proceedings of IEEE Cloud 2012，2012：295-302.

［6］B.Wang，B.Li，H.Li.Knox：Privacy-Preserving Public Auditing for Shared Data with Large Groups in the Cloud［C］//in the Proceedings of ACNS 2012，2012：507-525.

［7］Jianhong Zhang，Xubing Zhao.Privacy-Preserving Public AuditingSchemeforSharedDatawithSupporting Multi-function［J］.Journal of Communication，2015，10（7）：535-542.

［8］Merkle R C.A certified digital signature［M］.New York：Springer，1990：218-238.

［9］邱登峰.基于Hadoop可公共审计云存储的设计与实现［D］.大连：大连理工大学，2015. QIU Dengfeng.Design and Implementation of Public Au⁃ditable Cloud Storage Based on Hadoop［D］.Dalian：Da⁃lian University of Technology，2015.

［10］Wang Qian，Wang Cong，Li Jin，et al.Enabling public verifiability and data dynamics for storage security in cloud computing［C］//Proceedings of the 14thEuropean Symposiumon Research in Computer Security.Saint Ma⁃lo，France，2009：355-370.

A Merkle-Tree Based Cloud Storage Data Hold Check Scheme

MENG HaohuaCAO BoYUAN HuiDONG Liang
（Information Communication Company State Grid Hubei Electric Power Company，Wuhan430077）

With the popularity of cloud storage users to back up personal data，data integrity becomes a hotspot.Data persis⁃tence is proved to be one way to solve this problem.However，the most of authentication mechanisms of data persistence bring great⁃er computational overhead and communication costs.In this paper，it analyses the problem of data persistence，and presents as⁃cheme based on Merkle-Tree.Simulation results show that the present protocol ensures data persistence of lower computation and communication overhead.

cloud storage，data persistence，Merkle-tree，Merkle Hash Tree

TP333

10.3969/j.issn.1672-9722.2017.07.033

2017年1月7日，

2017年2月18日

山东省自然科学基金（编号：ZR2014FL012）；山东省网络环境智能计算技术重点实验室开放基金资助。

孟浩华，男，硕士研究生，高级工程师，研究方向：信息通信系统管理与信息安全。曹波，男，硕士研究生，高级工程师，研究方向：信息通信系统管理与信息安全。袁慧，男，硕士研究生，高级工程师，研究方向：信息通信系统管理与信息安全。董亮，男，硕士研究生，高级工程师，研究方向：信息通信系统管理与信息安全。