一種基于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）；山東省網絡環境智能計算技術重點實驗室開放基金資助。

孟浩華，男，碩士研究生，高級工程師，研究方向：信息通信系統管理與信息安全。曹波，男，碩士研究生，高級工程師，研究方向：信息通信系統管理與信息安全。袁慧，男，碩士研究生，高級工程師，研究方向：信息通信系統管理與信息安全。董亮，男，碩士研究生，高級工程師，研究方向：信息通信系統管理與信息安全。