基于嵌套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