一種帶權(quán)單鏈表多分支樹云數(shù)據(jù)完整性驗證方案

朱 彧，陳 越，嚴(yán)新成，王曉晶

1(戰(zhàn)略支援部隊 信息工程大學(xué)，鄭州 450001)

2(陸軍參謀部附屬單位，北京 100042)

E-mail:619717409@qq.com

1 引 言

云計算作為時下熱門的信息技術(shù)，通過共享自己的強(qiáng)大集中的資源為用戶提供服務(wù)，根據(jù)用戶需求分配資源來完成用戶的計算或存儲任務(wù)，因此越來越多的用戶選擇使用云計算服務(wù).云存儲服務(wù)是云計算的核心服務(wù)之一，云服務(wù)提供商(CSP,Cloud Service Provider)搭建具有強(qiáng)大存儲能力的云系統(tǒng)并向用戶提供數(shù)據(jù)存儲服務(wù).云存儲服務(wù)具有低成本、高擴(kuò)展性、易于運(yùn)行維護(hù)和訪問不受時間地點(diǎn)約束等優(yōu)點(diǎn).但近年來發(fā)生的安全事故表明，其也存在著嚴(yán)重安全隱患.2017年1月31日，Gitlab由于遭受到DDoS攻擊，運(yùn)維人員在修復(fù)過程中，執(zhí)行了錯誤的命令，導(dǎo)致約300GB的用戶數(shù)據(jù)被刪除，近6個小時的用戶數(shù)據(jù)丟失.2018年8月，騰訊云的客戶清博數(shù)據(jù)科技有限公司所屬的“前沿數(shù)控”平臺的一塊操作系統(tǒng)云盤發(fā)生故障，致其文件系統(tǒng)數(shù)據(jù)損壞.

這些事故使得用戶擔(dān)心自己存儲在云系統(tǒng)中數(shù)據(jù)的安全，因為一旦數(shù)據(jù)被存儲到云系統(tǒng)上，用戶就無法像管理本地數(shù)據(jù)那樣管理云端數(shù)據(jù)了.云系統(tǒng)可能因為軟硬件故障導(dǎo)致數(shù)據(jù)丟失或損壞，惡意的攻擊者可能會破壞或篡改用戶數(shù)據(jù)，云服務(wù)提供商也可能丟棄那些長時間未被訪問或很少被訪問的數(shù)據(jù)以達(dá)到節(jié)省存儲空間的目的.但云服務(wù)提供商出于維護(hù)自身聲譽(yù)或者避免賠償?shù)饶康碾[瞞這些事故，并向用戶聲稱數(shù)據(jù)仍然被完整地存儲在云系統(tǒng)中.如何高效靈活地驗證存儲在云端數(shù)據(jù)的完整性是亟待研究的問題[1]，而數(shù)據(jù)完整性驗證方案可以很好的解決這個問題.

2 相關(guān)工作

數(shù)據(jù)完整性驗證方案根據(jù)存儲數(shù)據(jù)是否可恢復(fù)分為數(shù)據(jù)持有性證明(Provable Data Possession,PDP)[2]和數(shù)據(jù)可恢復(fù)證明(Proofs of Retrievability,PoR)[3].PDP能夠快速判斷數(shù)據(jù)是否損毀，效率較高.而POR可以在一定程度上恢復(fù)損壞的數(shù)據(jù)，但效率較低.本文的研究主要關(guān)注PDP的效率等問題.Ateniese等提出了一種采用概率性策略完整性驗證方案[2]，利用RSA簽名機(jī)制的同態(tài)特性將證據(jù)聚集成一個小的值，降低了驗證過程中的通信開銷，但其不能支持動態(tài)更新操作.為了支持用戶對存儲在云系統(tǒng)上的數(shù)據(jù)進(jìn)行動態(tài)更新操作，研究者們引進(jìn)動態(tài)數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù).Erway等引入跳表來組織數(shù)據(jù)，實(shí)現(xiàn)了支持塊級全動態(tài)更新操作[4]；Wang等采用Merkle哈希樹來保證數(shù)據(jù)塊在位置上的正確性，使得方案支持?jǐn)?shù)據(jù)的動態(tài)更新[5].然而采用動態(tài)數(shù)據(jù)結(jié)構(gòu)會由于數(shù)據(jù)塊的增多消耗很多的時間和空間，在驗證過程中需要傳遞很多的輔助驗證信息，增加了通信帶寬的開銷.為了提高驗證效率和減少驗證開銷，王瑞錦等將跳表數(shù)據(jù)結(jié)構(gòu)進(jìn)行改進(jìn)，引入可達(dá)范圍記數(shù)，以便高效地支持?jǐn)?shù)據(jù)塊在任意位置的更新操作[6]；Merkle哈希樹每個節(jié)點(diǎn)對應(yīng)兩個子節(jié)點(diǎn)，而李勇等采用的多分支樹(large branching tree，LBT)中每個節(jié)點(diǎn)對應(yīng)多個子節(jié)點(diǎn)，有效降低了樹的高度，簡化了數(shù)據(jù)動態(tài)更新過程[7]；方欣等對多分支路徑樹進(jìn)行改進(jìn)，降低了樹的高度，優(yōu)化了存儲空間，但并沒有考慮到用戶多次更新后樹的不平衡問題，且采取線性組合計算證據(jù)導(dǎo)致用戶數(shù)據(jù)有被不可信第三方獲取的風(fēng)險[8].針對上述問題，本文提出了采用帶權(quán)單鏈表多分支樹的云數(shù)據(jù)完整性驗證方案(weighted single linked list large branching tree scheme，WSLBTS),以進(jìn)一步提高驗證效率并保護(hù)用戶數(shù)據(jù)隱私.其主要貢獻(xiàn)如下：1)相對于多分支樹，WSLBT將葉節(jié)點(diǎn)設(shè)置為鏈表，使得每一葉節(jié)點(diǎn)對應(yīng)多個數(shù)據(jù)塊，進(jìn)一步降低了樹的高度，縮短了構(gòu)造時間和生成證據(jù)的長度；2)提出一種再平衡機(jī)制，可維持葉節(jié)點(diǎn)鏈表長度的平衡，提高了節(jié)點(diǎn)更新效率；3)采用了隨機(jī)掩碼技術(shù)[9]，使得第三方審計(Third Patry Auditor)無法從證據(jù)中得到數(shù)據(jù)的有關(guān)信息.

3 相關(guān)預(yù)備知識

3.1 雙線性對

假設(shè)G1,G2,GT都是素數(shù)階為p的乘法循環(huán)群，g1和g2分別是G1和G2的生成元，則雙線性對定義如下：

e:G1×G2→GT，

1)雙線性：?x∈G1,y∈G2?e(xa,yb)=e(x,y)ab；

2)非退化性：e(g1,g2)≠1；

3)可計算性：e能夠被高效地計算.

3.2 數(shù)據(jù)完整性驗證模型

為了減輕用戶端的負(fù)擔(dān)，數(shù)據(jù)完整性驗證方案一般引入具有很強(qiáng)計算和存儲能力的第三方審計，采用公開驗證的方法[10].數(shù)據(jù)完整性驗證方案驗證模型構(gòu)成一般由三個實(shí)體構(gòu)成，分別是用戶端、云系統(tǒng)和第三方審計(TPA).

用戶端將自己的數(shù)據(jù)上傳到云系統(tǒng)中，并且會在需要的時候向云系統(tǒng)發(fā)出請求將自己的數(shù)據(jù)取回.用戶端可以委托第三方審計(TPA)代替自己向云系統(tǒng)發(fā)出挑戰(zhàn)來驗證自己數(shù)據(jù)的完整性，因而需要向第三方審計提供必要的信息.

云系統(tǒng)能夠以經(jīng)濟(jì)的價格為用戶提供持續(xù)的存儲服務(wù)，當(dāng)用戶訪問或取回數(shù)據(jù)時，及時響應(yīng)用戶的請求，并保證用戶數(shù)據(jù)的完整性和可用性；當(dāng)在第三方審計發(fā)起完整性挑戰(zhàn)時，其應(yīng)能夠誠實(shí)的計算證據(jù)并返回.

第三方審計是經(jīng)過用戶認(rèn)可的，擁有較強(qiáng)計算能力和存儲能力.在獲得用戶數(shù)據(jù)足夠的信息后，能夠代替用戶向云系統(tǒng)發(fā)起數(shù)據(jù)完整性驗證，根據(jù)云系統(tǒng)返回的證據(jù)計算判斷用戶數(shù)據(jù)是否被完整的存儲，并向用戶反饋結(jié)果.

數(shù)據(jù)完整性驗證方案一般包括密鑰生成算法、數(shù)據(jù)塊簽名算法、證據(jù)產(chǎn)生算法和證據(jù)驗證算法四個算法，具體描述如下：

密鑰生成算法(KeyGen)由用戶端運(yùn)行，生成用于數(shù)據(jù)塊簽名的公鑰與私鑰.

數(shù)據(jù)塊簽名算法(TagGen)由用戶端運(yùn)行，用上一算法生成的私鑰對用戶數(shù)據(jù)進(jìn)行簽名并生成數(shù)據(jù)塊標(biāo)簽.

證據(jù)生成算法(GenPro)由云系統(tǒng)運(yùn)行，利用第三方審計發(fā)送過來的挑戰(zhàn)信息生成挑戰(zhàn)證據(jù)并返回.

證據(jù)驗證算法(VerPro)由第三方審計運(yùn)行，根據(jù)云系統(tǒng)返回的證據(jù)計算驗證等式是否成立，并輸出驗證結(jié)果

3.3 隨機(jī)掩碼技術(shù)

4 WSLBTS構(gòu)造

4.1 帶權(quán)單鏈表多分支樹(WSLBT)

Merkle哈希樹(Merkle Hash Tree，MHT)是滿二叉樹，僅在葉子節(jié)點(diǎn)存儲數(shù)據(jù)信息，每個中間層節(jié)點(diǎn)和根節(jié)點(diǎn)都有兩個子節(jié)點(diǎn).在一般的完整性驗證方案中，每個葉子結(jié)點(diǎn)對應(yīng)一個數(shù)據(jù)塊的哈希值，而每個父節(jié)點(diǎn)的值是由它的子節(jié)點(diǎn)的哈希值鏈接之后再次哈希得到，以此類推，得到根結(jié)點(diǎn)root的值.相比于Merkle哈希樹，多分支樹(large branching tree，LBT)中每個節(jié)點(diǎn)擁有多個子節(jié)點(diǎn)，子節(jié)點(diǎn)的個數(shù)被稱為多分支樹的出度，每個葉節(jié)點(diǎn)對應(yīng)一個數(shù)據(jù)塊的哈希值.帶權(quán)單鏈表多分支樹(weighted single linked list large branching tree，WSLBT)中，葉子結(jié)點(diǎn)對應(yīng)的不是單個數(shù)據(jù)塊的哈希值，而是鏈表，而每個結(jié)點(diǎn)上存儲的值為(rx,h(x)).其中rx表示從該節(jié)點(diǎn)開始能夠訪問到的數(shù)據(jù)塊數(shù)量，若x不是葉節(jié)點(diǎn)，則h(x)是x的子節(jié)點(diǎn)哈希值鏈接之后再次進(jìn)行哈希運(yùn)算得到的，若x是葉節(jié)點(diǎn)，則h(x)是x對應(yīng)鏈表內(nèi)所有數(shù)據(jù)塊的哈希值鏈接之后再次進(jìn)行哈希運(yùn)算得到.以此類推就可以計算得到根節(jié)點(diǎn)R的hroot值.

圖1 WSLBT數(shù)據(jù)結(jié)構(gòu)

圖1是一個簡單的高度為3出度為3的WSLBT，其中葉節(jié)點(diǎn)D,E,F和非葉節(jié)點(diǎn)A及根節(jié)點(diǎn)R的值依次可由以下公式可得，B,C節(jié)點(diǎn)計算方式與A節(jié)點(diǎn)相似.

節(jié)點(diǎn)D=h(h(f1)||h(f2)…||(h(f10))

節(jié)點(diǎn)E=h(h(f11)||h(f12)…||(h(f20))

節(jié)點(diǎn)F=h(h(f21)||h(f22)…||(h(f30))

節(jié)點(diǎn)A=h(h(D)||h(E)||h(F))

節(jié)點(diǎn)R=h(h(A)||h(B)||h(C))

4.2 基本方案構(gòu)造

構(gòu)造的方案由以下幾個步驟構(gòu)成.

4.2.1 初始化

4.2.2 發(fā)起挑戰(zhàn)

4.2.3 返回證據(jù)

運(yùn)行算法GenPro.云系統(tǒng)收到挑戰(zhàn)信息后，根據(jù)索引值找到數(shù)據(jù)塊所在節(jié)點(diǎn)，并對WSLBT進(jìn)行回溯，找到該節(jié)點(diǎn)到根節(jié)點(diǎn)之間路徑上所有兄弟節(jié)點(diǎn)，將兄弟節(jié)點(diǎn)值匯聚成一個集合作為輔助信息{Ωi}s1≤i≤sc.計算證據(jù)如公式(1)所示：

(1)

將證據(jù)Pro={h(Fi),S,P,{Ωi}s1≤i≤sc,Sigsk(hroot)}發(fā)送給挑戰(zhàn)方.

4.2.4 證據(jù)檢驗

用戶或第三方收到證據(jù)后，運(yùn)行算法VerPro，進(jìn)行以下驗證.

1)根據(jù)(h(Fi))和{Ωi}s1≤i≤se，用戶或第三方審計重新計算根結(jié)點(diǎn)值hroot′.

4.3 數(shù)據(jù)的動態(tài)更新

在實(shí)際應(yīng)用中，用戶需要更新存儲在云系統(tǒng)中的數(shù)據(jù)，例如修改、插入、刪除等操作.當(dāng)用戶更新數(shù)據(jù)時，需要向云系統(tǒng)提供更新數(shù)據(jù)塊的信息，如數(shù)據(jù)塊的位置和新標(biāo)簽值等.云系統(tǒng)在收到信息后，對WSLBT進(jìn)行更新，更新數(shù)據(jù)塊所在葉節(jié)點(diǎn)的值，并重新計算該葉節(jié)點(diǎn)到樹根節(jié)點(diǎn)上所有兄弟節(jié)點(diǎn)的值.和Merkle哈希樹及LBT相比，WSLBT的數(shù)據(jù)塊查詢效率要更高效，在同樣高度的情況下，可以存儲更多的數(shù)據(jù)塊.

4.3.1 修改

若用戶需要將數(shù)據(jù)塊F12更新為F12′，則發(fā)送更新消息{modify,12,F12′,T12′}到云系統(tǒng).云系統(tǒng)收到更新消息，解析到這是個修改請求，將第12個數(shù)據(jù)塊改為F12′，并將相應(yīng)的數(shù)據(jù)塊標(biāo)簽改為T12′.此時需要將WSLBT一并更新，將該數(shù)據(jù)塊所在葉節(jié)點(diǎn)的值重新計算，并重新計算該葉節(jié)點(diǎn)到樹根節(jié)點(diǎn)上所有節(jié)點(diǎn)的值.

4.3.2 刪除

若用戶需要刪除數(shù)據(jù)塊F12，則向云系統(tǒng)發(fā)送更新消息{delete,12}.云系統(tǒng)解析到這是一個刪除消息，將數(shù)據(jù)塊F12及其標(biāo)簽T12一并刪除，重新計算相應(yīng)節(jié)點(diǎn)并更新WSLBT,結(jié)果如圖2所示.

圖2 刪除數(shù)據(jù)塊F12

4.3.3 插入

若用戶需要在數(shù)據(jù)塊F19和F20之間插入Fi，則發(fā)送更新消息{insert,19,Fi,Ti}到云系統(tǒng).云系統(tǒng)解析到這是一個插入消息，將數(shù)據(jù)塊Fi插入到鏈表中F19和F20之間，重新計算鏈表對應(yīng)的葉節(jié)點(diǎn)的值，并更新該葉節(jié)點(diǎn)到樹根節(jié)點(diǎn)上所有節(jié)點(diǎn)的值，需要重新計算的節(jié)點(diǎn)與刪除操作所更新節(jié)點(diǎn)相似.

4.4 樹的再平衡

在多次更新之后，WSLBT中葉節(jié)點(diǎn)對應(yīng)鏈表的長度可能差距比較大，有些鏈表由于插入操作比較多導(dǎo)致鏈表長度很長，有些鏈表則由于刪除操作比較多長度會很短，這就造成了WSLBT的不平衡.當(dāng)樹的不平衡十分嚴(yán)重的時候，查詢效率就會受到很大的影響，若要操作的數(shù)據(jù)塊在較長的鏈表中，那么就會需要很長的查詢時間.同時鏈表過長也導(dǎo)致葉節(jié)點(diǎn)值的計算開銷增大，因此需要一種機(jī)制來維持樹的平衡.

在用戶對數(shù)據(jù)進(jìn)行多次更新后，WSLBT的葉節(jié)點(diǎn)所對應(yīng)的鏈表長度可能不等.在WSLBT中，每個節(jié)點(diǎn)上存儲的信息(rx,h(x))不僅有節(jié)點(diǎn)哈希值h(x)，而且有該節(jié)點(diǎn)下數(shù)據(jù)塊的數(shù)目rx.如圖3所示，節(jié)點(diǎn)x,y,z的值分別為rx,ry,rz，假設(shè)rx>ry>rz，當(dāng)最大的rx與最小的rz值相差大于閾值δ時，則稱節(jié)點(diǎn)x,y,z不平衡.此時需對該節(jié)點(diǎn)進(jìn)行再平衡，計算所有節(jié)點(diǎn)r值的平均值r=[(rx+ry+rz)/3]，d=(rx+ry+rz)mod3.將前d個節(jié)點(diǎn)的數(shù)據(jù)塊值調(diào)整為r+1,其余節(jié)點(diǎn)的數(shù)據(jù)塊值調(diào)整為r，至此節(jié)點(diǎn)x,y,z之間實(shí)現(xiàn)了平衡.從根節(jié)點(diǎn)向下，對每一對兄弟節(jié)點(diǎn)進(jìn)行再平衡，使得其節(jié)點(diǎn)之間r值最大最小之差小于閾值δ，從而實(shí)現(xiàn)WSLBT的平衡，平衡后的WSLBT如圖4所示.閾值δ選擇比較關(guān)鍵，如果過大，那么節(jié)點(diǎn)之間即便數(shù)據(jù)塊差距比較大也不會進(jìn)行再平衡，如果閾值δ過小，那么WSLBT就會頻繁更新，造成系統(tǒng)資源的浪費(fèi).

圖3 不平衡狀態(tài)下的WSLBT

圖4 WSLBT的再平衡

5 正確性與安全性分析

5.1 正確性分析

(2)

5.2 安全性分析

在將數(shù)據(jù)存儲到云系統(tǒng)之后，用戶主要面臨的數(shù)據(jù)完整性驗證威脅有重放攻擊、丟失攻擊和篡改攻擊.

重放攻擊是云系統(tǒng)由于數(shù)據(jù)損壞、丟失或篡改之后無法提供有效證據(jù)時，將以前提供過的證據(jù)重復(fù)提供給用戶以期掩蓋數(shù)據(jù)不可用事實(shí)的行為.假設(shè)某些數(shù)據(jù)塊由于云系統(tǒng)的責(zé)任而不可用，那么在用戶發(fā)起完整性挑戰(zhàn)的時候，云系統(tǒng)可能將以前通過完整性驗證的證據(jù)再次返回以期通過驗證.但是由于隨機(jī)數(shù)vi參與證據(jù)的生成，同一批數(shù)據(jù)生成的證據(jù)S和P也是不同的.故云系統(tǒng)無法通過重放證據(jù)來通過驗證，隱瞞自己的失職行為.

丟失攻擊是云系統(tǒng)有意或無意將用戶數(shù)據(jù)丟失后，計算偽造證據(jù)并希望通過完整性驗證的行為.假設(shè)云系統(tǒng)丟失了數(shù)據(jù)塊Fi，那么就要偽造一個數(shù)據(jù)塊的標(biāo)簽Ti=(H(Fi)uFi)x才能通過完整性挑戰(zhàn).但是由于云系統(tǒng)并不知道私鑰x，不能偽造出正確的數(shù)據(jù)標(biāo)簽通過完整性驗證，從而無法欺騙用戶.

篡改攻擊是云系統(tǒng)在用戶數(shù)據(jù)被篡改后，無法通過正常計算得出證據(jù)時，提供偽造證據(jù)的行為.假設(shè)數(shù)據(jù)塊Fi被非法篡改為Fi′，那么云系統(tǒng)同樣需要偽造出數(shù)據(jù)塊標(biāo)簽才能通過驗證.但是由于哈希函數(shù)的抗碰撞性，不存在H(Fi)=H(Fi′)的情況.所以在數(shù)據(jù)塊被非法篡改的情況下，云系統(tǒng)是無法偽造出數(shù)據(jù)塊標(biāo)簽的，也就不能通過完整性驗證的.

6 性能分析

6.1 根節(jié)點(diǎn)計算復(fù)雜度和通信效率分析

本方案與Wang[5]的基于Merkle哈希樹的方案和李勇[7]的基于多分支樹的方案相比，比較結(jié)果如表1所示，可以看出本方案在計算和通信開銷方面有所降低.

表1 方案性能比較

Table 1 Comparison for performance

方案支持公開驗證全動態(tài)操作根節(jié)點(diǎn)計算復(fù)雜度通信復(fù)雜度Wang否否O(log2N)O(log2N)李勇是是O(lognN)O(lognN)本文方案是是 O(logn(N/m))O(logn(N/m))

用戶要存儲的文件經(jīng)初始化可以分為N個數(shù)據(jù)塊，用出度為n的多分支樹LBT來組織這些數(shù)據(jù)，那么葉節(jié)點(diǎn)的個數(shù)就為N，樹的高度為lognN.用WSLBT來組織數(shù)據(jù)，假設(shè)鏈表初始長度為m，出度為n，那么葉節(jié)點(diǎn)個數(shù)為N/m，樹的高度變?yōu)閘ogn(N/m).可以看出，在數(shù)據(jù)塊總數(shù)和樹的出度相同的情況下，WSLBT有著更低的高度，根節(jié)點(diǎn)計算所需時間也就更短.為了進(jìn)行效率分析，在Windows系統(tǒng)中用Java語言實(shí)現(xiàn)了方案基本功能.實(shí)驗環(huán)境為：CPU是Pentium(R)Dual-Core,內(nèi)存為4GB.實(shí)驗將100M的文件劃分為10000個大小為10kb的數(shù)據(jù)塊，分別為其構(gòu)造LBT和鏈表長度為50的WSLBT(當(dāng)出度為2時，LBT樹可視為Merkle哈希樹)，結(jié)果如圖5所示.從圖中可以看出，在出度相同的情況下，WSLBT根節(jié)點(diǎn)計算時間總是要小于LBT的.

在完整性驗證的過程中，用戶需要和云系統(tǒng)進(jìn)行信息的交互.云系統(tǒng)向用戶返回證據(jù)是帶寬開銷最大的過程.在這一過程中，云系統(tǒng)需要向用戶返回證據(jù)Pro={h(Fi),S,P,{Ωi}s1≤i≤sc,Sigsk(hroot)}，其中輔助信息{Ωi}s1≤i≤sc的長度是影響帶寬開銷最大的因素.實(shí)驗對比文獻(xiàn)[7]和本文方案在驗證單個數(shù)據(jù)塊時所生成證據(jù)中輔助信息Ω的大小(本文方案中鏈表長度設(shè)置為30)，得出結(jié)果見圖6.從圖中可以看出，在樹出度相同的情況下，本文方案產(chǎn)生證據(jù)中的輔助信息Ω要比文獻(xiàn)[7]小，證據(jù)更短，驗證時通信效率更高.

圖5 LBT與WSLBT構(gòu)造時間對比

圖6 LBT與WSLBT生成證據(jù)中輔助信息大小對比

6.2 隱私保護(hù)與證據(jù)生成效率

本方案與文獻(xiàn)[8]相比，引入了隨機(jī)掩碼技術(shù)對數(shù)據(jù)塊進(jìn)行簽名保護(hù)了用戶隱私，并且提出了再平衡機(jī)制來維持樹結(jié)構(gòu)的平衡.

文獻(xiàn)[8]采用BLS簽名，對分塊后的數(shù)據(jù)Fi用公式Ti=(H(Fi)uFi)x來計算標(biāo)簽.在驗證過程中，若第三方重復(fù)地對{s1,…,sc}位置上的數(shù)據(jù)進(jìn)行檢測，每次挑戰(zhàn)請求為 chalj={si,vi(j)}，其中1≤i≤c,1≤j≤c，vi(j)表示第j次挑戰(zhàn)中第i數(shù)據(jù)塊對應(yīng)的隨機(jī)數(shù)，經(jīng)過c次挑戰(zhàn)后，就可以得到方程組(3):

(3)

文獻(xiàn)[8]采用的數(shù)據(jù)結(jié)構(gòu)是單鏈表多分支樹(Single Linked List Large Branching Tree,SLBT)，將葉節(jié)點(diǎn)設(shè)置為單向鏈表，降低了樹的高度.該方案支持?jǐn)?shù)據(jù)全動態(tài)更新，但在插入和刪除數(shù)據(jù)塊時鏈表長度會發(fā)生變化，WSLBT會出現(xiàn)不平衡狀態(tài).葉節(jié)點(diǎn)對應(yīng)鏈表長度過長時，重新計算該葉節(jié)點(diǎn)的值就會需要較長的時間.本方案所提出的再平衡機(jī)制可以保證WSLBT的平衡，避免出現(xiàn)葉節(jié)點(diǎn)對應(yīng)鏈表過長的情況，提高了葉節(jié)點(diǎn)總體更新效率.實(shí)驗對比圖3和圖4狀態(tài)下(即平衡狀態(tài)和不平衡狀態(tài))WSLBT葉節(jié)點(diǎn)更新所用時間，得出結(jié)果見圖7.從圖中可以看出，平衡狀態(tài)下的WSLBT在葉節(jié)點(diǎn)更新時所用的時間更少，更新效率更高.

圖7 WSLBT平衡與不平衡狀態(tài)下葉節(jié)點(diǎn)更新時長對比

7 結(jié)束語

隨著越來越多的用戶選擇將數(shù)據(jù)移植到云中，云存儲服務(wù)的安全成為保證用戶資源對服務(wù)忠誠度重要指標(biāo)[11].數(shù)據(jù)完整性是云存儲服務(wù)安全中的重要組成部分，因而確保用戶數(shù)據(jù)完整性是最近研究的一個熱點(diǎn).本文提出了基于帶權(quán)單鏈表多分支樹的數(shù)據(jù)完整性驗證方案，能高效地支持?jǐn)?shù)據(jù)全動態(tài)操作，并保證多次動態(tài)操作后節(jié)點(diǎn)更新效率，適用于用戶數(shù)據(jù)頻繁更新的場景；引入隨機(jī)掩碼技術(shù)，保證了在第三方審計不可信時用戶數(shù)據(jù)的隱私安全.在下一步的工作中，如果能夠利用WSLBT的中間節(jié)點(diǎn)來存儲數(shù)據(jù)，方案效率會得到更進(jìn)一步的提高.