周堅　金瑜　何亨　李鵬

摘 要：云存儲憑借高擴展性、高可靠性、低成本的數(shù)據管理優(yōu)點得到用戶青睞。然而，如何確保云數(shù)據完整性成為亟待解決的安全問題。當前最成熟、高效的云數(shù)據完整性審計方案是基于半可信第三方來提供公共審計服務，但基于半可信第三方審計方案存在單點失效、算力瓶頸和錯誤數(shù)據定位效率低等問題。為了解決上述問題，提出了基于區(qū)塊鏈的云數(shù)據動態(tài)審計模型。首先，采用分布式網絡、共識算法建立一個由眾多審計實體組成的區(qū)塊鏈審計網絡，并以此來解決單點失效和算力瓶頸問題;然后，在保證區(qū)塊鏈數(shù)據可信度的前提下，引入變色龍哈希算法和嵌套MHT結構，以實現(xiàn)云數(shù)據標簽在區(qū)塊鏈上的動態(tài)操作;最后，借助嵌套MHT結構以及輔助路徑信息，提高了在審計發(fā)生錯誤時對錯誤數(shù)據的定位效率。實驗結果表明，與基于半可信第三方云數(shù)據動態(tài)審計方案相比，所提模型顯著提高了審計效率，降低了數(shù)據動態(tài)操作時間開銷，并提升了錯誤數(shù)據定位效率。

關鍵詞：區(qū)塊鏈;云存儲;動態(tài)操作;審計;變色龍哈希

中圖分類號： 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 引言

云計算是近幾年研究和應用的熱點，云存儲作為云計算的重要服務模式之一，其目的是利用云計算技術將大量低成本、低可靠性的設備協(xié)同起來，向用戶提供高可靠、高彈性、高性能、低成本的數(shù)據存儲服務[1]。用戶在享受便捷的云存儲服務時，云存儲也曝露出以下安全問題：1）用戶數(shù)據的所有權和控制權相互分離，云服務提供商（Cloud Service Porvider， CSP）可能出于經濟目的故意刪除用戶不經常訪問的數(shù)據或者冗余數(shù)據。2）CSP可能出現(xiàn)軟件失效或硬件損壞，直接導致用戶數(shù)據丟失或者損壞。3）云數(shù)據可能遭到其他用戶的惡意損壞。因此，為了驗證用戶云數(shù)據的完整性，數(shù)據審計方案應運而生。其中，基于半可信第三方審計（Third Party Audit， TPA）[2-7]是最具有代表性的審計方案，但上述基于TPA方案存在以下問題：1）單點失效。所有用戶的云數(shù)據都由唯一的TPA實體完成審計，因此一旦TPA實體功能失效，則整個審計系統(tǒng)癱瘓。2）性能瓶頸。隨著云用戶和云數(shù)據規(guī)模增大，TPA需要處理的數(shù)據規(guī)模也會增大導致審計時間會急劇加大，因此TPA的算力成為了整個審計系統(tǒng)的瓶頸。3）錯誤數(shù)據定位效果差。在云數(shù)據審計方案[2-5，7-15]中，均不支持用戶錯誤數(shù)據定位，不能為后續(xù)數(shù)據修復工作提供參考;文獻[6]方案中雖然支持錯誤數(shù)據的定位，但定位效率仍然不高。

在充分研究了用戶與CSP的信任矛盾和TPA審計模型的缺陷后，本文提出了基于去區(qū)塊鏈的動態(tài)云數(shù)據審計模型。該方案借助區(qū)塊鏈去中心化、高擴展性、安全可信等特點，將獨立TPA實體的審計任務和用戶數(shù)據標簽一同轉移到區(qū)塊鏈上，采用分布式TPA實體來完成審計業(yè)務，利用區(qū)塊鏈的分布式賬本模型來存儲用戶的數(shù)據標簽。 此外，本文在深入了解區(qū)塊鏈系統(tǒng)和審計方案對用戶動態(tài)數(shù)據的審計需求后，在保證區(qū)塊鏈分布式賬本安全可信的基礎上，結合已有的變色龍哈希算法和新提出的嵌套MHT（Merkle Hash Tree）結構實現(xiàn)對用戶存儲在區(qū)塊鏈上數(shù)據標簽的動態(tài)操作功能。

1 相關工作

數(shù)據完整性審計是數(shù)據擁有者檢測遠程云服務器中數(shù)據完整性的最佳途徑和方法，本文主要研究的方向是數(shù)據持有性證明。

Anteniese等 [12]首次提出了基于RSA簽名的數(shù)據持有者證明（Provable of Data Possession， PDP）方案。文獻[12]方案采用抽取數(shù)據樣本的策略，利用RSA同態(tài)的特性，結合其首次提出的樣本抽樣策略，能夠在相同可信度基礎上，明顯減少了驗證數(shù)據的數(shù)量，有效減少了計算代價和通信開銷;但文獻[12]方案只支持靜態(tài)云數(shù)據審計，在動態(tài)操作數(shù)據的情況下，插入或刪除數(shù)據塊需要用戶重新生成修改后數(shù)據塊后續(xù)的全部首部哈希值，極大消耗了用戶的計算資源。Anteniese等[13]對文獻[12]方案進行改進，又提出了動態(tài)云數(shù)據審計（Dynamic PDP， DPDP）方案;但文獻[13]方案只支持云數(shù)據的更新、刪除和追加操作，不支持云數(shù)據插入操作，不能稱得上完全的動態(tài)數(shù)據完整性驗證方案。

Erway等 [7] 采用基于排名的認證跳表動態(tài)數(shù)據結構和RSA簽名機制來支持全動態(tài)數(shù)據操作（Scable dynamic PDP， SPDP）方案。文獻[7]方案是第一種支持全動態(tài)數(shù)據操作的PDP方案，但它存在尋找節(jié)點時間開銷隨著文件分塊數(shù)規(guī)模增大而快速增大的問題，導致動態(tài)操作效率低下;此外，動態(tài)數(shù)據操作需要修改跳表中認證路徑上所有節(jié)點的哈希值，需要計算大量輔助消息，存在計算代價和網絡開銷都比較大等問題。

Wang等 [5]提出了采用MHT和BLS簽名機制的支持公開審計的動態(tài)數(shù)據完整性驗證（Public PDP， P-PDP）方案。文獻[5]方案中采用MHT結構保證數(shù)據塊在空間上的正確性，通過BLS簽名的PDP機制來保證數(shù)據在內容上的完整性。該方案的優(yōu)勢在于：1）借助BLS簽名算法，用戶可以將繁瑣的審計任務轉交給TPA來完成，從而實現(xiàn)公開審計。2）相較于RSA簽名機制，BLS簽名機制具有更低的計算開銷和通信開銷。3）借助MHT結構，該方案認證路徑長度更短。相較于文獻[13]方案，文獻[5]方案在節(jié)點查詢、生成的認證路徑速度更快。但該方案中，用戶將云數(shù)據審計工作交給了TPA處理，隨著用戶數(shù)量、托管數(shù)據增加，最終會導致TPA承擔繁重的計算開銷，大幅影響TPA性能;此外，該方案仍不支持審計發(fā)生錯誤時對錯誤數(shù)據的定位。

Yang等 [6]提出基于索引表結構和BLS（Boneh-Lynn-Shacham）簽名算法，支持完全動態(tài)數(shù)據操作的PDP（Efficient PDP， EPDP）機制。在該方案中，由于采用的索引表是通過連續(xù)的存儲空間實現(xiàn)分塊文件元數(shù)據存儲，導致刪除和插入操作會移動大量的數(shù)據。隨著用戶數(shù)據規(guī)模擴大、文件分塊數(shù)增多，刪除和插入操作的時間開銷會急劇增大，直接導致動態(tài)操作后的驗證時間開銷增大，使得其審計效率低于文獻[5]方案;此外，該方案同樣采用基于TPA的審計模型，存在單點失效和算力瓶頸缺陷。

李勇等 [8]在文獻[5]方案研究的基礎上，針對構建MHT中認證路徑過長問題，改進MHT結構為多路分支樹（Large Branching Tree， LBT）結構，提出基于LBT結構的PDP（LBT PDP， LPDP）審計模型。LBT采用多分支路徑結構，所需構造的LBT深度隨著出度的增加而減少，進而減少數(shù)據完整性驗證過程中的輔助信息，簡化了數(shù)據動態(tài)更新過程，降低了系統(tǒng)中實體之間的計算開銷。但文獻[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中認證長度，從而縮短了節(jié)點查詢的時間開銷;另一方面在標簽中添加時間戳屬性，賦予標簽數(shù)據新鮮度。但該方案依然沒有解決文獻[5]方案中存在的問題。

為了讓用戶對已有的數(shù)據持有性證明審計方案有客觀的認識，本文從審計時間復雜度、動態(tài)操作支持、錯誤數(shù)據定位三個視角對現(xiàn)有方案進行對比分析，具體結果如表1所示。表1中：n是文件塊數(shù);t是審計過程中挑戰(zhàn)的文件塊數(shù);s是文件塊二級分塊文件數(shù);M（Modify）是更新操作;I（Insert）是插入操作;D（Delete）是刪除操作;EL（Error data Locate）是錯誤數(shù)據定位;Server表示計算元數(shù)據的時間復雜度;Vertify表示驗證數(shù)據完整性時間復雜度。

從數(shù)據持有性證明方案的發(fā)展來看，最近幾年來的研究方向主要是基于文獻[5]方案，對MHT認證路徑縮短、隱私保護方向加以改善，就計算開銷而言沒有實際的改進。就審計計算量方面而言，文獻[5]方案憑借其簡潔的審計過程，不需要額外的輔助數(shù)據，其計算量相較文獻[6-7，9]方案更小。就支持錯誤數(shù)據定位的動態(tài)云數(shù)據審計方案而言，只有文獻[6]方案適合作對比實驗。因此，在審計效率方面將本文方案與文獻[5]方案作橫向對比;在動態(tài)數(shù)據操作方面，由于只有文獻[6]方案在支持動態(tài)數(shù)據操作的同時支持錯誤數(shù)據定位，故在錯誤數(shù)據定位方面，主要將本文方案與文獻[6]方案進行比較。

區(qū)塊鏈系統(tǒng)的節(jié)點應當是可開放自由參與，身份平等，如此形成自治的系統(tǒng)[16]。為了更好適應區(qū)塊鏈系統(tǒng)，大多數(shù)系統(tǒng)采用對等分布式網絡來進行數(shù)據傳播。為了使眾多的節(jié)點能夠在保證安全性的前提下完成網絡中數(shù)據打包，則需要全網節(jié)點達成共識，共同完成任務[17-19]。

區(qū)塊鏈的共識算法主要分為證明類算法和選舉類算法，其中普遍應用的PoW（Proof of Work）方案[20] 和PoS（Proof of Stake）方案[21]是證明類共識算法，DPoS（Delegated Proof of Stake）方案[22]是選舉類算法。其具體性能如表2所示，主要針對PoW、PoS、DPoS就性能效率、去中心化、確定性和資源消耗幾個方面作對比。為了最大限度提升云數(shù)據的審計效率，本文采用DPoS共識算法。

為了從根本上解決基于TPA的云數(shù)據審計方案的單點失效、算力瓶頸等問題，本文引入區(qū)塊鏈技術弱化TPA在審計系統(tǒng)的地位，借助分布式網絡提升審計系統(tǒng)的算力;此外，本文通過一個創(chuàng)新的嵌入式MHT結構，在實現(xiàn)云數(shù)據動態(tài)操作的前提下，提高了審計錯誤時對錯誤數(shù)據定位的效率。

2 背景知識

2.1 BLS簽名

BLS簽名方案使用雙線性映射的性質進行驗證和簽名。記e：GG→G′是一個非退化雙線性映射，G和G′是素數(shù)r階的乘法群，生成元是g。根據雙線性映射的性質e（gx，gy）=e（g，g）xy，要求在G上，CDH（Computational-Diffie-Hellman）求解是困難的。

BLS簽名分成三個函數(shù)：

1）KeyGen：選取一個隨機整數(shù)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 變色龍哈希

哈希函數(shù)簡單來講就是能將任意長度的輸入轉換成一個固定長度的輸出，這個固定長度的輸出稱為原數(shù)據的散列值或哈希值。通過原始輸入消息能夠很容易計算哈希值，通過輸出（哈希值）則很難還原出原始輸入。理想的哈希函數(shù)針對不同的輸入產生不同的輸出。如果兩個不同的消息產生了相同的哈希值，則稱為發(fā)生了碰撞[23]。

與一般哈希函數(shù)不同，變色龍哈希函數(shù)（Chamelelon Hash）可以人為設下陷門密鑰，掌握了陷門密鑰就能輕松計算出不同數(shù)據指向相同的哈希碰撞[24]。對沒有陷門密鑰的用戶而言，變色龍哈希函數(shù)依然滿足抗碰撞性 。

定義1 一個變色龍函數(shù)由四個算法組成Cham_hash=（Setup，KeyGen，CHash，CForge）組成。

1）Setup（）：輸出公共參數(shù)pp。

2）KeyGen（pp）：輸入公共參數(shù)pp，輸出公私鑰對（HK，CK），HK為公鑰，CK為私鑰又稱陷門。

3）CHash（HK，m，r）：輸入公鑰HK、消息m和隨機數(shù)r，輸出變色龍哈希值CH。

4）CForge（CK，m，r，m′）：輸入私鑰CK、消息m、隨機數(shù)r、消息m′，輸出另一個隨機值r′，滿足CH=CHash（HK，m，r）=CForge（CK，m，r，m′）。

變色龍哈希函數(shù)的安全性要求為：

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）的概率分布是不可區(qū)分的;特別地，當r為隨機選擇時，從Chash（HK，m，r）無法得到關于m的任何消息。

3 本文方案

3.1 系統(tǒng)框架和流程

基于嵌套MHT區(qū)塊鏈的云數(shù)據動態(tài)審計模型框架如圖1所示。

整個模型中涉及到的實體以及功能如下：

普通用戶（Common Owner， CO）：該角色主要是持有大量的數(shù)據，同時將數(shù)據托管給云存儲服務提供商，該角色可以是私人用戶或者公司等需要保存數(shù)據的角色。

授權用戶（Delegate Owner， DO）：該角色是通過DPoS共識，由分布式網絡所有的CO投票產生，該角色持有大量數(shù)據托管給云存儲服務提供商，同時監(jiān)測全網CO發(fā)送的元數(shù)據證據消息，為全網用戶的數(shù)據提供數(shù)據完整性驗證服務。

云存儲服務提供商（CSP）：該角色提供云存儲服務，擁有海量的存儲空間、可靠的計算資源，同時提供穩(wěn)定服務。

該方案的大致過程如下：

1）DPoS共識：分布式網絡中所有的CO執(zhí)行該過程，產生DO用戶，約定區(qū)塊生成的順序和審計任務。

2）上傳UBlock：分布式網絡中所有的用戶將要保存在CSP的文件經過處理后生成一個UBlock文件上傳到CSP保存。

3）上傳Ublock* ：分布式網絡中所有的用戶在上傳UBlock的時候，會生成一個不包含原始數(shù)據但包含元數(shù)據的Ublock*發(fā)送給指定的DO（激活）保存。

4）區(qū)塊簽署：當DO（激活）生成一個區(qū)塊文件之后，向CSP發(fā)起一個區(qū)塊簽署挑戰(zhàn)請求CSP返回一個簽署證據響應。DO（激活）通過檢查CSP返回的證據響應就可以確定CSO是否如約保存了分布式網絡全體用戶在該DO（激活）工作時間內托管的文件。

5）區(qū)塊審計：DO為了驗證其存儲的所有區(qū)塊代表的用戶數(shù)據的完整性，依照DPoS規(guī)定的時間表，周期性地向CSP發(fā)起區(qū)塊審計挑戰(zhàn)，驗證CSP返回的證據的正確性。

6）動態(tài)操作：當分布式網絡中的用戶需要修改、刪除、增加其已經托管在CSP的數(shù)據時，執(zhí)行該操作。

3.2 嵌套MHT數(shù)據結構

傳統(tǒng)的區(qū)塊鏈應用模型中，用戶每一次交易的證據都保存在區(qū)塊鏈上，交易數(shù)據較小且每次交易之間的數(shù)據沒有關聯(lián)性。但是，在審計過程中，用戶文件比較大，為了減輕元數(shù)據的計算壓力，文件一般會進行分塊處理。如果直接引用傳統(tǒng)區(qū)塊鏈上的概念來存儲數(shù)據，則會破壞分塊數(shù)據之間的關聯(lián)性。此外，傳統(tǒng)的區(qū)塊鏈應用模型中，是不允許對交易數(shù)據進行修改的。但是現(xiàn)今的審計往往要求針對動態(tài)數(shù)據的完整性驗證，為了將區(qū)塊鏈技術和動態(tài)云數(shù)據審計結合起來，必須要對區(qū)塊鏈的底層數(shù)據結構作出相應修改。故本文專門引入變色龍哈希技術和嵌套MHT結構來適應區(qū)塊鏈上驗證動態(tài)數(shù)據的完整性。該結構中，頂層的MHT用來保證多個文件的完整性和空間位置的正確性，底層的MHT保證單個文件的分塊數(shù)據在空間位置的正確性和數(shù)據的完整性，其具體結構如圖2所示。

為了支持數(shù)據動態(tài)操作和數(shù)據安全，用戶只能操作底層MHT結構。通過變色龍哈希算法，假設底層MHT結構發(fā)生了改變也能保證上層MHT結構不變，從而解決了區(qū)塊鏈不可變和云存儲動態(tài)操作的矛盾。由圖2可知，頂層MHT的葉子節(jié)點保存都是某個用戶存儲在CSP的文件，其內部非葉子節(jié)點存儲的都是經過變色龍哈希函數(shù)計算得到的哈希值。底層MHT的葉子節(jié)點保存都是某個用戶托管于CSP文件的分塊數(shù)據，其內部非葉子節(jié)點存儲的都是經過變色龍哈希函數(shù)計算得到的哈希值。

3.3 模型關鍵流程

本文的方案主要由密鑰初始化階段、元數(shù)據和變色龍哈希生成階段、數(shù)據分發(fā)和區(qū)塊生成階段、簽署階段、區(qū)塊審計和錯誤數(shù)據定位階段等六部分組成。

3.3.1 密鑰初始化階段

選取公共參數(shù)e和安全參數(shù)λ，構造滿足安全參數(shù)λ的大素數(shù)p、q。其中p、q滿足p=k·q+1，選取乘法循環(huán)群Zp*階為q的元素gc，輸出公共參數(shù)pp=（p，q，gc）;G×G→GT是雙線性映射，gb是G的生成元;Hb：{0，1}*→G是將數(shù)據映射到G群的哈希函數(shù);Hc： {0，1}*→Zp*是數(shù)據映射到Zp*群的哈希函數(shù);H： {0，1}*→Zr是數(shù)據映射到Zr群的哈希函數(shù) 。輸入公共參數(shù)pp， 在乘法循環(huán)群Zp*中隨機選擇指數(shù)x，計算h=gxc，最后得到私鑰CK=x，公鑰HK=h;隨機選取私鑰SK=a←Zp，計算其相對應的公鑰PK=gab。

3.3.2 元數(shù)據和變色龍哈希生成階段

選取文件的唯一標識v←{0，1}R，隨機輔助變量v←G，對文件F進行分塊：F={b1，b2，…，bn};將所有分塊文件分別映射到Zr群，得到mi=H（bi）生成認證元數(shù)據集合={σi}1≤i≤n，這里σi=Hb（mi）·umi。對每一個分塊文件mi，生成一個隨機數(shù)ri←Zq*，輸出變色龍哈希CHmi=gmic·hri mod p。

3.3.3 數(shù)據分發(fā)和區(qū)塊生成階段

用戶將文件F的每個分塊文件bi、mi、σi和CHmi組合成Unodei，后執(zhí)行底層MHT構造算法（詳情見算法2）生成UBF發(fā)往CSP存儲，同理生成相應的證據UBF*發(fā)往DO（激活）存儲。用戶可以刪除本地文件，只保留UBF*數(shù)據以便以后修改數(shù)據用。當CSP接收到m個用戶發(fā)送的UBF之后，執(zhí)行頂層MHT構造算法（詳情見算法2）生成一個區(qū)塊文件。同理DO（激活）在收集到m個用戶發(fā)送的UBF*之后，也生成一個未簽署、未審計的區(qū)塊文件。

3.3.4 簽署區(qū)塊階段

當DO生成一個區(qū)塊文件之后，直接讀取頭部文件中的ID值，要求CSP就符合ID一致的區(qū)塊返回其頭部的U_ROOT值。若DO本地區(qū)塊的U_ROOT值和CSP返回的U_ROOT值一致，則CSP可以證明其已經保存了該時間段內區(qū)塊鏈網絡中所有用戶托管在CSP的數(shù)據，DO發(fā)送簽署消息到CSP完成區(qū)塊簽署。

3.3.5 區(qū)塊審計和錯誤數(shù)據定位階段

DO（激活）選擇一個未審計的區(qū)塊，這個區(qū)塊內包含m個UBF*文件。針對每個UBF*文件隨機抽取C個UN*的索引為UnodeIDi，并對每個索引選取一個相對應的隨機數(shù)vi←Zp/2。由此可以組成一個UBF*挑戰(zhàn)塊τF={Unodei，vi}（1≤i≤c），m個UBF*挑戰(zhàn)塊組成了這個區(qū)塊文件的挑戰(zhàn)chal={τFi，BlockIDi}（1≤i≤m）發(fā)送到CSP。

CSP接收到chal挑戰(zhàn)后，依據BlockID找到被挑戰(zhàn)的區(qū)塊UBlock。依據τFi找到被挑戰(zhàn)的UN分塊文件，通過UnodeIDi得到每個被挑戰(zhàn)分塊文件的輔助消息α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返回給發(fā)出挑戰(zhàn)的DO。

DO接收到CSP返回的Res={φFi}1≤i≤m消息之后，對其中的每一個φFi依據式（1）判斷存儲在CSP的用戶數(shù)據的完整性。若式（1）輸出true，則說明該UB文件塊數(shù)據內容完整;若式（1）判斷發(fā)生錯誤，則說明DO挑戰(zhàn)的該UB中的分塊文件發(fā)生錯誤，此時執(zhí)行錯誤數(shù)據定位，具體流程詳見算法4。此時，DO讀取發(fā)生錯誤的UB的βFi，通過直接讀取輔助消息UnodeID，確定DO發(fā)出的挑戰(zhàn)分塊文件在DO本地存儲的LM消息和dataHash消息，通過比較LM=LMi和dataHash=dataHashi來定位錯誤數(shù)據的具體位置。

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存儲在最頂層的葉子節(jié)點中;如果葉子節(jié)點數(shù)唯一，則葉子節(jié)點就是根節(jié)點，MHT構造結束;若葉子節(jié)點不是1，則通過層次構建思想，在第11）～20）行中，通過高一層的節(jié)點，從上往下構造下層內部節(jié)點，同時依據上層節(jié)點數(shù)目的奇偶來執(zhí)行不同的構造過程。若上層是偶數(shù)節(jié)點，則下層節(jié)點數(shù)目一定是奇數(shù)，通過上層節(jié)點兩兩配對的方式，計算下層節(jié)點的變色龍哈希數(shù)據;若上層是奇數(shù)節(jié)點，則除開最后一個奇數(shù)節(jié)點直接復制到下層節(jié)點。其余偶數(shù)個節(jié)點和偶數(shù)層節(jié)點處理方式一樣，通過層層遞進的方式，最終將所有的葉子節(jié)點映射成最下層的根節(jié)點。

3.5.3 動態(tài)操作插入算法

算法3 動態(tài)操作插入（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）行確定用戶插入的節(jié)點位置，在通過第5）行，驗證用戶動態(tài)操作的合法性，判斷通過才能執(zhí)行插入操作;在第9）～11）行中，用戶插入的位置是葉子節(jié)點，且其插入位置的深度小于此時MHT的深度，即內部節(jié)點已經構造完畢，因此只需要將節(jié)點插入即可;第12～16）行中，用戶插入節(jié)點的位置是葉子節(jié)點且插入位置的深度和MHT的深度一致，即插入的位置是MHT最底層的節(jié)點，因此必須要構造新的下一層空間來存儲插入的節(jié)點;在第19）行中，插入節(jié)點的位置不是葉子節(jié)點，即插入的位置是原先存放葉子節(jié)點但經過刪除操作的節(jié)點，因為刪除操作不會刪除存儲空間，因此不需要構造額外空間，直接進行存儲;在第22）行中，執(zhí)行了存儲操作之后，需要修改插入操作所涉及的節(jié)點的關系信息和MHT的深度和葉子節(jié)點個數(shù)等信息。

3.5.4 錯誤數(shù)據定位算法

算法4 錯誤數(shù)據定位（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）行直接遍歷所有挑戰(zhàn)節(jié)點的位置信息，找到存放在UBlock*中的節(jié)點;通過第5）行比較UBlock*中節(jié)點的Data_hash和CSP返回的認證消息中對應的Data_hash得出節(jié)點數(shù)據是否發(fā)生改變;第6）行得到發(fā)生錯誤數(shù)據的LM消息，從而定位錯誤數(shù)據具體位置。

4 實驗與結果分析

4.1 安全性分析

為了保證云存儲數(shù)據的完整性和區(qū)塊鏈簽署速度，本文方案主要引入了變色龍哈希算法、非對稱加密算法（主要應用BLS簽名算法）和N-MHT結構。用戶的數(shù)據都保存在N-MHT的底層MHT中，通過變色龍哈希算法將每個文件的變色龍哈希值最終映射成頂層MHT的根節(jié)點值，通過根節(jié)點值來保證區(qū)塊快速簽署和查找;通過底層MHT結構和非對稱加密算法來保證數(shù)據完整性檢測。當用戶需要執(zhí)行數(shù)據動態(tài)操作，需要通過變色龍哈希算法計算出需要修改數(shù)據的變色龍哈希陷門，通過CSP和DO的認證就可以執(zhí)行。變色龍哈希滿足一般安全哈希算法的強抗碰撞性、高靈敏度等要求，除非持有變色龍哈希算法私鑰才能計算出陷門，得出哈希碰撞，惡意用戶不能通過收集到的動態(tài)操作數(shù)據計算出用戶持有的變色龍私鑰，無法非法執(zhí)行動態(tài)操作，污染用戶數(shù)據。

4.2 實驗分析

4.2.1 實驗環(huán)境

實驗硬件環(huán)境為：1）4臺PC機器組成分布網絡，CPU 2.0GHz，RAM為2GB;2）1臺PC機器作為CSP服務器，CPU 3.2GHz，RAM為24GB。

實驗軟件環(huán)境為：1）操作系統(tǒng)為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云存儲服務器，用于存儲區(qū)塊鏈網絡中用戶托管的數(shù)據和維護數(shù)據動態(tài)操作;4臺機器搭建Jxta分布式網絡組成區(qū)塊鏈網絡，每臺機器上可以同時運行若干區(qū)塊鏈節(jié)點實體，各個節(jié)點實體之間沒有主次之分，每個節(jié)點都可能成為普通用戶和授權用戶。

4.2.2 審計時間分析

實驗一 設置1個DO用戶，3個CO用戶，CSP/DO接收到4個Ublock/Ublock*時生成一個區(qū)塊文件。規(guī)定每個用戶發(fā)送的文件大小為50MB，每個用戶和DO均發(fā)送5個文件，總計有1GB的數(shù)據存儲在CSP上，預計生成5個區(qū)塊文件;規(guī)定在可信度為99%的條件下，在文件分塊數(shù)分別為10、50、100、250時比較審計完所有用戶數(shù)據所需要的平均時間開銷，具體結果如圖6所示。由圖6可以看出，文獻[5]方案驗證1GB用戶數(shù)據的時間隨著分塊文件規(guī)模增大而減少，但是整體時間開銷仍然大于本文方案。根據BLS簽名的特性，在文件容量不變的前提下，文件分塊數(shù)越多，計算其元數(shù)據的時間開銷會減少，審計需要計算的元數(shù)據開銷也會減少，本文方案和文獻[5]方案均是基于BLS簽名的PDP方案，因此隨著文件分塊數(shù)增加，審計時間開銷會減少。在文獻[5]方案中，每次均是對1個用戶的1個文件發(fā)出挑戰(zhàn)。為了驗證全網4位用戶總計20個文件的完整性，文獻[5]方案需要對CSP發(fā)出20次挑戰(zhàn)才能驗證所有文件的完整性;而本文方案采用區(qū)塊挑戰(zhàn)，每個區(qū)塊中存放4個用戶文件，只需要挑戰(zhàn)5次就達到和文獻[5]方案一樣的效果，減少了審計挑戰(zhàn)次數(shù)，降低整體時間開銷。

實驗二 規(guī)定用戶每次發(fā)送的文件大小為50MB，文件分塊數(shù)為50，即每個分塊文件大小為1MB，每個用戶發(fā)送的文件數(shù)目為5，共計1GB的數(shù)據存儲在CSP;CSP/DO接收到4個Ublock/Ublock*時生成1個區(qū)塊文件，預計生成5個區(qū)塊文件，修改了DO用戶的數(shù)量從1到3，在可信度為99%的條件下，比較審計完所有用戶數(shù)據所需要的平均時間開銷，具體結果如圖7所示。從圖7可以看出，本文方案和文獻[5]方案均對CSP中存放的1GB數(shù)據進行完整性驗證，隨著DO用戶數(shù)量增加，完成1GB數(shù)據完整性驗證的時間逐漸減少。在文獻[5]方案中，只有1個TPA實體提供審計服務，而在本文方案中，同樣提供審計服務的DO實體是可以隨著DPoS共識動態(tài)設定的，因此本文方案可以避免單TPA失效導致審計服務崩潰，同時多DO環(huán)境下可以有效加速用戶數(shù)據審計速度。

4.2.3 動態(tài)操作時間分析

實驗三 規(guī)定用戶文件大小為50MB，文件分塊數(shù)為100，用戶發(fā)送文件數(shù)量分別為20、50、100;規(guī)定區(qū)塊鏈網絡設置DO用戶為1，CO用戶數(shù)量設置為3;CSP/DO收集到5個Ublock/Ublock*則生成一個區(qū)塊文件，預計生成16、40、100個區(qū)塊文件。動態(tài)操作涉及Update、Insert、Delete，均是在隨機位置執(zhí)行，每種操作均執(zhí)行50次，統(tǒng)計每種操作的平均時間開銷，具體結果如圖8所示。從圖8可以看出，動態(tài)操作得時間開銷均隨著用戶文件規(guī)模增大而增大，本文方案的動態(tài)操作時間開銷均小于文獻[6]方案，其原因在于：在文獻[6]方案中，刪除和插入操作需要移動動態(tài)操作節(jié)點后續(xù)的所有節(jié)點，導致時間開銷增大。對于更新操作，本文方案將用戶的文件處理成為1個區(qū)塊文件，動態(tài)操作文件定位時間開銷較小，而文獻[6]方案中必須按照順序去查找用戶的文件從而增加了文件查詢的時間。

4.2.4 錯誤數(shù)據定位時間分析

實驗四 規(guī)定用戶文件大小為50MB，文件分塊數(shù)為50，全網用戶總計發(fā)送文件數(shù)目分別為為100、200、300、400;區(qū)塊鏈網絡設置DO用戶為1，CO用戶數(shù)量設置為3;CSP/DO收集到5個Ublock/Ublock*則生成1個區(qū)塊文件，預計生成區(qū)塊文件數(shù)目分別為20、40、60、80。當DO對CSP發(fā)送回的挑戰(zhàn)證據進行驗證發(fā)現(xiàn)錯誤時，查找具體分塊數(shù)據錯誤位置信息的平均時間，結果如圖9所示。從圖9可以得出，在相同文件總量的條件下，本文方案的定位錯誤數(shù)據的時間開銷要小于文獻[6]方案，其原因在于：本文方案中用戶的文件經過一定的聚合，實際遍歷所有用戶文件數(shù)目要少于文獻[6]方案中依靠順序遍歷的方式。

5 結語

為了克服基于TPA方案單點失效、算力瓶頸等缺陷，本文提出了一種基于變色龍哈希算法的可編輯區(qū)塊鏈的云數(shù)據完整性驗證方案。該方案借助區(qū)塊鏈技術中的分布式網絡，將云用戶的數(shù)據標簽存儲在區(qū)塊鏈上，通過共識算法選出的授權用戶代替全體用戶，借助區(qū)塊鏈上的數(shù)據標簽向云存儲服務提供商發(fā)出數(shù)據完整性挑戰(zhàn)并驗證。此外，為了滿足云數(shù)據動態(tài)操作的需求，特別地引入了變色龍哈希算法和獨創(chuàng)的N-MHT結構，保證了修改區(qū)塊鏈上部分區(qū)塊文件不會導致整個鏈上數(shù)據均發(fā)生改變，滿足了用戶數(shù)據動態(tài)操作的可能和審計錯誤時針對錯誤數(shù)據的定位。實驗結果表明，本文提出的方案相較TPA方案能顯著縮短平均審計、動態(tài)操作、錯誤數(shù)據定位的時間開銷。雖然本文方案挖掘了區(qū)塊鏈和審計之間的聯(lián)系，但由于時間和水平有限，本文研究還有以下問題，可以作為我們進一步研究的方向：

1）在刪除操作過程中，N-MHT結構并沒有回收節(jié)點的存儲空間，只是將該節(jié)點的數(shù)據部分置空，該節(jié)點的殘余信息依然殘留在區(qū)塊鏈中，浪費了存儲空間。

2）在插入操作過程中，如果插入的位置是底層MHT的最底層葉子節(jié)點，將會在原先底層MHT的基礎上，額外開辟新的一層空間去存儲插入節(jié)點，對同一位置進行連續(xù)插入操作會造成極大的空間浪費。

3）由于該區(qū)塊鏈系統(tǒng)主要是來考慮私有鏈，假定認為所有的節(jié)點都是可信的，因此沒有考慮動態(tài)操作過程中可能存在惡意用戶發(fā)動的重復攻擊和偽造攻擊。針對重復攻擊和偽造攻擊，可以借助時間戳解決該缺陷。

參考文獻 （References）

[1]譚霜，賈焰，韓偉紅.云存儲中的數(shù)據完整性證明研究及進展[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]李勇，姚戈，雷麗楠，等.基于多分支路徑樹的云存儲數(shù)據完整性驗證機制[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]袁勇，王飛躍.區(qū)塊鏈技術發(fā)展現(xiàn)狀與展望[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]謝輝，王健.區(qū)塊鏈技術及其應用研究[J].信息網絡安全，2016（9）：192-195.（XIE H， WANG J. Study on blockchain technology and its applications [J]. Netinfo Security， 2016（9）： 192-195）

[18]何蒲，于戈，張巖峰，等.區(qū)塊鏈技術與應用前瞻綜述[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]楊宇光，張樹新.區(qū)塊鏈共識機制綜述[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]李佩麗，徐海霞，馬添軍，等.可更改區(qū)塊鏈技術研究[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—），男，湖北武漢人，副教授，博士，主要研究方向：車聯(lián)網。

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