周 鵬，龍士工

(1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽 550025； 2.貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025)

0 引 言

隨著分布式計(jì)算機(jī)硬件處理能力和網(wǎng)絡(luò)傳輸能力的提升，遠(yuǎn)程數(shù)據(jù)處理中心能夠給用戶提供高質(zhì)量的數(shù)據(jù)和軟件服務(wù)。云計(jì)算就在這種情況下應(yīng)運(yùn)而生了，它是繼網(wǎng)格計(jì)算、對(duì)等計(jì)算、分布式計(jì)算之后的又一種新型計(jì)算模式，其核心理念是按需服務(wù)、按用收費(fèi)，為用戶提供隨處可用的資源連接池。通過云計(jì)算技術(shù)，不僅使得用戶和企業(yè)可以隨時(shí)隨地通過網(wǎng)絡(luò)訪問自己的資源，同時(shí)減少了在軟硬件管理上的投入。云計(jì)算強(qiáng)大的計(jì)算能力和存儲(chǔ)能力使得用戶更愿意將復(fù)雜的任務(wù)交付給云平臺(tái)處理，然而當(dāng)用戶將大量的數(shù)據(jù)部署到云平臺(tái)時(shí)，云計(jì)算系統(tǒng)就演變成一個(gè)云存儲(chǔ)系統(tǒng)，使得用戶用低廉的價(jià)格就能獲得海量的存儲(chǔ)能力，但是高度集中的計(jì)算機(jī)資源給云存儲(chǔ)帶來了嚴(yán)峻的安全挑戰(zhàn)。根據(jù)Gartner調(diào)查結(jié)果顯示，曾經(jīng)70%受訪企業(yè)的CEO擔(dān)心云數(shù)據(jù)隱私被侵犯而拒絕大量使用云計(jì)算模式。而在最近幾年，各大云服務(wù)提供商也相繼暴露出安全問題，如谷歌Gmail郵箱故障和盛大云機(jī)房物理服務(wù)器磁盤故障。

在現(xiàn)有的完整性驗(yàn)證方案中由于自身原因存在著較大的局限性，如早期Deswarte等人[1]提出基于MAC認(rèn)證碼驗(yàn)證機(jī)制，后來又在此基礎(chǔ)上做出改進(jìn)，利用同態(tài)特性(am)=arm=(ar)m，提出了基于RSA簽名完整性驗(yàn)證機(jī)制以及Dan等人[2]提出的基于BLS的短簽名機(jī)制。上述方案中都在通訊效率和計(jì)算代價(jià)上做了改進(jìn)，但是都僅針對(duì)靜態(tài)數(shù)據(jù)存儲(chǔ)，并不能支持動(dòng)態(tài)數(shù)據(jù)更新，無法適應(yīng)動(dòng)態(tài)環(huán)境。因此，Ateniese等人[3]最先開始考慮如何支持動(dòng)態(tài)操作，對(duì)現(xiàn)有方案做出改進(jìn)，提出了支持部分動(dòng)態(tài)更新的驗(yàn)證機(jī)制，但不能進(jìn)行數(shù)據(jù)插入操作?；谶@個(gè)問題，Erway等人[4]提出了基于跳表的驗(yàn)證機(jī)制來支持插入操作，但其認(rèn)證路徑過長(zhǎng)，每次需要大量的輔助信息支持，計(jì)算代價(jià)和通訊開銷較大。后來又提出了一種以Merkle-Tree數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)的方案[5-6]，該方案中存儲(chǔ)數(shù)據(jù)集為S,將S中的元素存儲(chǔ)在Hash樹的葉子結(jié)點(diǎn)中，并且每個(gè)結(jié)點(diǎn)都存儲(chǔ)一個(gè)標(biāo)簽值。如果該結(jié)點(diǎn)為葉子結(jié)點(diǎn)，其標(biāo)簽值與其存儲(chǔ)的數(shù)據(jù)相同；否則其孩子結(jié)點(diǎn)的標(biāo)簽值就需要通過抗碰撞哈希函數(shù)計(jì)算得出。而用戶保存數(shù)據(jù)集S的摘要值就是Merkle-Tree根結(jié)點(diǎn)的摘要值。相比跳表具有更簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，但是造成存儲(chǔ)空間的極大浪費(fèi)。文獻(xiàn)[18]中將樹形結(jié)構(gòu)與RSA技術(shù)相結(jié)合構(gòu)造出一種RSA樹，該方案引入?yún)?shù)ε使得樹的高度和樹的分支都為常量，因此，該方案中得到的證據(jù)大小、查找和驗(yàn)證的時(shí)間復(fù)雜度為O(l)。但是該方案采用了單向累加技術(shù)，需要使用復(fù)雜的冪運(yùn)算，所以實(shí)際的運(yùn)行時(shí)間并不樂觀，并且RSA樹在大量數(shù)據(jù)插入操作上并不靈活，還會(huì)導(dǎo)致復(fù)雜的結(jié)構(gòu)重構(gòu)問題。

基于上述完整性認(rèn)證方案所存在的不足，從存儲(chǔ)空間和通信效率角度出發(fā)，并與現(xiàn)有方案相結(jié)合，本文引入了一種平衡二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)——結(jié)點(diǎn)大小平衡樹(Size Balance Tree， SBT)，二叉排序樹的結(jié)構(gòu)特點(diǎn)使得數(shù)據(jù)的查找非常高效，可以快速定位到目標(biāo)結(jié)點(diǎn)；同時(shí)平衡二叉樹的結(jié)構(gòu)特點(diǎn)又能夠很好地維持樹的高度以至不退化為鏈表，保證了數(shù)據(jù)查找和更新的效率。

1 云存儲(chǔ)環(huán)境下的數(shù)據(jù)完整性證明

1.1 數(shù)據(jù)存儲(chǔ)模型

云存儲(chǔ)環(huán)境下的體系架構(gòu)一般基于2種基礎(chǔ)模型，分別為兩方模型和三方模型。三方模型即引入了可信第三方審計(jì)(Third Party Auditor， TPA)，具有更多的審計(jì)經(jīng)驗(yàn)和能力，替代用戶對(duì)云存儲(chǔ)中的數(shù)據(jù)執(zhí)行審計(jì)任務(wù)，也減輕了在驗(yàn)證階段用戶所需要的計(jì)算負(fù)擔(dān)。其結(jié)構(gòu)關(guān)系如圖1所示。

在三方模型中，由于接入云中的設(shè)備受到計(jì)算資源的限制，用戶不可能將大量的時(shí)間和精力花費(fèi)在對(duì)云數(shù)據(jù)的完整性檢測(cè)上，往往將其交付給經(jīng)驗(yàn)豐富的第三方來完成。因此，驗(yàn)證方只需要擁有少量的公開信息即可完成完整性驗(yàn)證。而在兩方模型中，沒有第三方審計(jì)，只有云存儲(chǔ)用戶和云服務(wù)提供商，用戶本身就具有三方模型中的審計(jì)功能。由于在這2種存儲(chǔ)模型中，三方模型的自身優(yōu)勢(shì)更符合云存儲(chǔ)的特性，所以本文中對(duì)云存儲(chǔ)環(huán)境下的數(shù)據(jù)完整性研究，都是基于三方模型展開。

圖1 云環(huán)境下存儲(chǔ)模型

1.2 構(gòu)建框架

數(shù)據(jù)完整性證明機(jī)制由Setup和Challege這2個(gè)階段構(gòu)成，通過隨機(jī)數(shù)據(jù)抽樣的方式對(duì)云存儲(chǔ)中數(shù)據(jù)進(jìn)行完整性驗(yàn)證。具體實(shí)現(xiàn)由如下4個(gè)多項(xiàng)式時(shí)間算法組成：

1)keyGen(1k)→(pk,sk)。密鑰對(duì)生成算法，由用戶來執(zhí)行。算法以安全參數(shù)k作為輸入，輸出密鑰對(duì)(pk,sk)作為返回值。

2)TagBlock(sk,f)→η。數(shù)據(jù)塊標(biāo)簽生成算法，由用戶來執(zhí)行。算法以私鑰和文件f作為輸入，將每個(gè)文件生成的標(biāo)簽集合η輸出作為認(rèn)證的元數(shù)據(jù)。

3)GenProof(pk,f,η,chal)→ρ。證據(jù)生成算法，該算法在服務(wù)器上運(yùn)行。將用戶公鑰pk、文件f、認(rèn)證的標(biāo)簽集合η以及用戶的挑戰(zhàn)請(qǐng)求chal作為輸入，生成這次請(qǐng)求的驗(yàn)證證據(jù)ρ返回。

4)CheckProof(pk,ρ,chal)→(″true″,″false″)。證據(jù)驗(yàn)證算法，由可信第三方TPA執(zhí)行。該算法將用戶的公鑰pk、服務(wù)器生成的證據(jù)ρ以及用戶挑戰(zhàn)請(qǐng)求chal作為輸入?yún)?shù)返回驗(yàn)證成功或者失敗。

上述算法在數(shù)據(jù)完整性證明機(jī)制具體實(shí)施過程中可以分為2個(gè)階段:Setup階段和Challege階段。

1)Setup階段：初始化階段。用戶首先運(yùn)行keyGen(·)算法生成密鑰對(duì)(pk,sk)；然后對(duì)文件f分塊，執(zhí)行TagBlock(·)算法為每個(gè)數(shù)據(jù)塊fi生成標(biāo)簽集合η={ηf1,ηf2,…,ηfn}；最后將數(shù)據(jù)文件f和標(biāo)簽集合η發(fā)送給云服務(wù)器，刪除本地{f,η}。

2)Challege階段：用戶挑戰(zhàn)請(qǐng)求階段?？尚诺谌阶鳛門PA向云服務(wù)器周期性地發(fā)起完整性驗(yàn)證。從文件f中隨機(jī)選取c個(gè)數(shù)據(jù)塊{f1,f2,…,fc}生成挑戰(zhàn)請(qǐng)求chal發(fā)送給云服務(wù)器。

服務(wù)器作為證明者，通過存儲(chǔ)在服務(wù)器上的{f,η}，執(zhí)行GenProof(·)生成驗(yàn)證證據(jù)ρ返回給驗(yàn)證者,TPA作為驗(yàn)證者收到證據(jù)后，執(zhí)行CheckProof(·)驗(yàn)證證據(jù)是否正確。

2 基于SBT全結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)完整性方法

2.1 結(jié)點(diǎn)大小平衡樹——SBT

2.1.1 SBT的結(jié)構(gòu)

SBT本身也是一棵二叉排序樹,其性質(zhì)如下：

1)若左子樹非空，則左子樹上的所有結(jié)點(diǎn)關(guān)鍵字值均小于根結(jié)點(diǎn)的關(guān)鍵字值。

2)若右子樹非空，則右子樹上的所有結(jié)點(diǎn)關(guān)鍵字值均大于根結(jié)點(diǎn)的關(guān)鍵字值。

3)左、右子樹本身也分別是一顆二叉排序樹。

其又具備了平衡二叉樹的特點(diǎn)。為了避免樹的高度增長(zhǎng)過快，降低二叉排序樹的性能，規(guī)定在插入和刪除操作時(shí)，保證任意結(jié)點(diǎn)的左、右子樹高度差絕對(duì)值不超過1。它的優(yōu)點(diǎn)是可以高效動(dòng)態(tài)地維護(hù)二叉排序樹的高度，如果樹中出現(xiàn)結(jié)點(diǎn)不平衡的情況，需要進(jìn)行左旋或右旋操作來保持平衡，并且旋轉(zhuǎn)操作不需要額外的存儲(chǔ)空間。

SBT中的平衡性是通過其定義的結(jié)點(diǎn)大小，即以該結(jié)點(diǎn)為根的結(jié)點(diǎn)的個(gè)數(shù)之間的關(guān)系來維持的。其結(jié)構(gòu)如圖2所示。

圖2 SBT結(jié)構(gòu)圖

SBT樹中的每一個(gè)結(jié)點(diǎn)應(yīng)滿足如下性質(zhì)：

1)s[left[A]]≥s[right[right[A]]],s[right[left[A]]]

2)s[right[A]]≥s[left[left[A]]],s[left[right[A]]]

其中s[A]指的是以結(jié)點(diǎn)A為根的子結(jié)點(diǎn)的個(gè)數(shù)，left[A]指的是A的左孩子，right[A]指的是A的右孩子。在圖2中該性質(zhì)體現(xiàn)為：

s[L]≥s[D],s[E]& s[R]≥s[B],s[C]

如果在SBT上進(jìn)行刪除或者插入操作后，可能導(dǎo)致SBT上結(jié)點(diǎn)不滿足上述性質(zhì)，則需要執(zhí)行Maintain()函數(shù)以調(diào)整樹的高度來維持樹的平衡。

以圖2中SBT為例，假如出現(xiàn)s[B]>s[R]的情況，則需要通過以下步驟對(duì)其進(jìn)行修復(fù)：

1)首先對(duì)根結(jié)點(diǎn)A進(jìn)行右旋轉(zhuǎn)Right-Rotate(A)操作，使得SBT由圖2轉(zhuǎn)化為圖3。

2)右旋操作后可能還會(huì)出現(xiàn)s[D]>s[C]或者s[E]>s[C],同樣不滿足上述性質(zhì)，所以還需要對(duì)A執(zhí)行Maintain()操作；

3)圖3中L的右子樹可能由于步驟2中的不斷調(diào)整出現(xiàn)不滿足性質(zhì)的情況，因此最后還需要對(duì)L執(zhí)行Maintain()操作。

圖3 右旋A后結(jié)構(gòu)圖

2.2 數(shù)據(jù)結(jié)構(gòu)可認(rèn)證化

基于SBT結(jié)構(gòu)構(gòu)建起來的全結(jié)點(diǎn)存儲(chǔ)樹A中每個(gè)結(jié)點(diǎn)都存儲(chǔ)著如下3個(gè)字段：

1)該結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)Dv4。

2)該結(jié)點(diǎn)數(shù)據(jù)的摘要值Hv=h(Dv4)。

3)該結(jié)點(diǎn)上的聯(lián)合摘要值Hsum(v)：如果該結(jié)點(diǎn)為底層葉結(jié)點(diǎn)，則Hsum=Hv；若該結(jié)點(diǎn)中只存在右孩子結(jié)點(diǎn)，則Hsum=h(Hv,Hsum(v.getLeft))；如果該結(jié)點(diǎn)只存在左孩子結(jié)點(diǎn)，則Hsum=h(Hv,Hsum(v.getRight))；如果該結(jié)點(diǎn)左孩子和右孩子結(jié)點(diǎn)都存在，則Hsum=h(Hv,Hsum(v.getLeft),Hsum(v.getRight))。

圖4 可認(rèn)證的SBT結(jié)構(gòu)示意圖

云存儲(chǔ)環(huán)境中某個(gè)數(shù)據(jù)集的哈希摘要值為Digest(A)，即在驗(yàn)證過程中用來進(jìn)行對(duì)比的摘要值，就是該結(jié)點(diǎn)大小平衡樹的聯(lián)合摘要值。一個(gè)可認(rèn)證的結(jié)點(diǎn)大小平衡樹結(jié)構(gòu)示意圖見圖4

2.3 驗(yàn)證過程

當(dāng)用戶發(fā)送一個(gè)檢測(cè)數(shù)據(jù)請(qǐng)求到云服務(wù)器時(shí)，假如服務(wù)器在全結(jié)點(diǎn)存儲(chǔ)樹中找到存儲(chǔ)著目標(biāo)數(shù)據(jù)對(duì)應(yīng)的目標(biāo)結(jié)點(diǎn)target時(shí)，并且服務(wù)器會(huì)記錄root到target的查找路徑path={v0(target)→v1→…→vl-1→vl(root)}。此時(shí)，服務(wù)器還會(huì)給審計(jì)第三方TPA返回Yes并返回相應(yīng)的證據(jù)ρ={η,λ1,λ2，…,λl}。其中η的定義如下：

1)如果v0是葉子結(jié)點(diǎn)，則η={Dv0}。

2)如果v0不是葉子結(jié)點(diǎn)，則η={Dv0,Hsum(v0.getLeft),Hsum(v0.getRight)}。

λ的定義如下：

1)如果vi-1為左孩子結(jié)點(diǎn)，則λi={Hvi,Hsum(vi-1),Hsum(vi.getRight)}。

2)如果vi-1為右孩子結(jié)點(diǎn)，則λi={Hvi,Hsum(vi.getLeft),Hsum(vi-1)}。

以圖4所示的可認(rèn)證的SBT為例，如果需要驗(yàn)證的數(shù)據(jù)塊為Dv4,則證據(jù)ρ生成信息示例如圖5所示。

圖5 證據(jù)ρ生成示意圖

當(dāng)可信第三方TPA收到云服務(wù)器返回的證據(jù)ρ時(shí)，將進(jìn)行如下驗(yàn)證過程：

1)計(jì)算目標(biāo)結(jié)點(diǎn)v0的摘要值，即a=h(Dv0)，如果v0是葉子結(jié)點(diǎn)，則驗(yàn)證a=Hsum(Dv0)是否成立；否則，驗(yàn)證h(a,Hsum(v0.getLeft),Hsum(v0.getRight))=Hsum(v0)是否成立。

2)對(duì)于路徑中的某個(gè)結(jié)點(diǎn)vi，即λi(i

3)對(duì)于根結(jié)點(diǎn)vl，即λl，同理如果vi-1為根的左孩子結(jié)點(diǎn)則計(jì)算h(Hvl,Hsum(vl-1),Hsum(vl.getRight))；否則計(jì)算h(Hvl,Hsum(vl-1),Hsum(vl.getLeft))；并與用戶之前發(fā)送給TPA的數(shù)據(jù)摘要值Digest(A)作比較。

圖6 完整性驗(yàn)證過程示意圖

如果上述驗(yàn)證過程全部成立，則證明云服務(wù)器返回的證據(jù)ρ是正確的，即所查詢的數(shù)據(jù)是完整的；否則，用戶就會(huì)認(rèn)為該數(shù)據(jù)已被修改或者偽造，此時(shí)就需要采取數(shù)據(jù)恢復(fù)技術(shù)對(duì)云存儲(chǔ)中的數(shù)據(jù)進(jìn)行恢復(fù)操作。

以圖5結(jié)構(gòu)為例，其數(shù)據(jù)完整性驗(yàn)證過程如圖6所示。

3 結(jié)果分析

通過上述分析，可得到如下結(jié)論：

1)對(duì)于查詢驗(yàn)證操作，SBT認(rèn)證及Merkle-Tree認(rèn)證算法的時(shí)間復(fù)雜度在同一數(shù)量級(jí)，均為O(logn)。而與RSA樹認(rèn)證相對(duì)比，這2種認(rèn)證方案都使用了哈希函數(shù)替代復(fù)雜的模冪運(yùn)算，因此計(jì)算上更加簡(jiǎn)單。

2)在支持動(dòng)態(tài)數(shù)據(jù)集方面，Merkle-Tree認(rèn)證采用2-3樹支持動(dòng)態(tài)數(shù)據(jù)集，而RSA樹認(rèn)證是將成員哈希分組為固定大小的Bucket來支持動(dòng)態(tài)數(shù)據(jù)集。因此這2種方式都不可避免地導(dǎo)致了認(rèn)證結(jié)構(gòu)的周期性重構(gòu)。

3)SBT結(jié)構(gòu)具有良好的自平衡性，能夠有效地控制樹高，使其趨近于完全二叉樹。二叉樹上的查詢和更新操作時(shí)間復(fù)雜度都和樹高有關(guān)，相對(duì)于非平衡樹而言，SBT結(jié)構(gòu)在數(shù)據(jù)操作效率上大大提高，將時(shí)間復(fù)雜度維持在O(logn)。此外，SBT認(rèn)證也可以完全避免認(rèn)證結(jié)構(gòu)周期性重構(gòu)。針對(duì)上述方案在插入操作中的重構(gòu)分析，分別對(duì)SBT、Merkle-Tree、RSA樹插入100萬、200萬、500萬、1000萬以及2000萬個(gè)隨機(jī)值，重構(gòu)時(shí)間統(tǒng)計(jì)如圖7所示。

圖7 重構(gòu)時(shí)間統(tǒng)計(jì)圖

因此，對(duì)于大規(guī)模并且需頻繁更新的數(shù)據(jù)集，該方案具有明顯的優(yōu)勢(shì)。為了驗(yàn)證該樹形結(jié)構(gòu)更適合構(gòu)建數(shù)據(jù)認(rèn)證，下面通過實(shí)驗(yàn)將SBT與AVL樹、Treap進(jìn)行比較，評(píng)估基于SBT全結(jié)點(diǎn)存儲(chǔ)云數(shù)據(jù)完整性驗(yàn)證方案中查詢和更新的時(shí)間復(fù)雜度。

3.1 數(shù)據(jù)更新操作分析

圖8 插入操作時(shí)間統(tǒng)計(jì)圖

針對(duì)基于SBT上插入操作分析，在SBT、AVL和Treap結(jié)構(gòu)中分別插入100萬、500萬、1000萬、2000萬以及5000萬個(gè)隨機(jī)值，時(shí)間統(tǒng)計(jì)見圖8。

圖9 刪除操作時(shí)間統(tǒng)計(jì)圖

針對(duì)基于SBT上刪除操作分析，在具有100萬、500萬、1000萬、2000萬以及5000萬個(gè)隨機(jī)值的SBT、AVL和Treap結(jié)構(gòu)中，分別刪除100萬個(gè)值所用時(shí)間，刪除操作時(shí)間統(tǒng)計(jì)如圖9所示。

3.2 驗(yàn)證過程分析

針對(duì)基于結(jié)點(diǎn)大小二叉樹上的查詢驗(yàn)證操作的時(shí)間分析，在具有100萬、500萬、1000萬、2000萬以及5000萬個(gè)隨機(jī)值的SBT、AVL和Treap結(jié)構(gòu)中分別查詢100萬個(gè)目標(biāo)值運(yùn)行結(jié)果時(shí)間統(tǒng)計(jì)如圖10所示。

圖10 查詢驗(yàn)證操作平均時(shí)間統(tǒng)計(jì)圖

對(duì)于用戶向云服務(wù)器發(fā)送驗(yàn)證請(qǐng)求時(shí)，服務(wù)器在生成證據(jù)信息過程中，沒必要進(jìn)行數(shù)據(jù)摘要值的重新計(jì)算，只需要在認(rèn)證化的SBT中找到相應(yīng)的數(shù)據(jù)結(jié)點(diǎn)，并把根結(jié)點(diǎn)到該目標(biāo)結(jié)點(diǎn)路徑上的結(jié)點(diǎn)摘要值及其子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)作為返回值，返回的摘要值的個(gè)數(shù)與SBT的高度之間呈線性關(guān)系。可信第三方TPA在對(duì)返回的證據(jù)進(jìn)行驗(yàn)證時(shí)，僅需進(jìn)行O(logn)次哈希計(jì)算即可。

3.3 安全性分析

基于SBT認(rèn)證的安全性與基于Merkle-Tree的認(rèn)證相同，其安全性保證都是以其哈希函數(shù)的抗碰撞性為基礎(chǔ)實(shí)現(xiàn)。

4 結(jié)束語

目前，云計(jì)算的優(yōu)勢(shì)使得越來越多的企業(yè)和個(gè)人更愿意將數(shù)據(jù)交付到平臺(tái)處理，這給云存儲(chǔ)的普及帶來了非常可觀的發(fā)展前景，然而數(shù)據(jù)本身的不確定性以及云服務(wù)器的不完全可信又使得云存儲(chǔ)下的數(shù)據(jù)安全難以得到保障。針對(duì)數(shù)據(jù)完整性驗(yàn)證問題，本文提出了一種基于SBT全結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)完整性驗(yàn)證方案，并詳細(xì)地介紹了云存儲(chǔ)下完整性驗(yàn)證框架和基于結(jié)點(diǎn)大小平衡樹全結(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)驗(yàn)證過程。全結(jié)點(diǎn)存儲(chǔ)相比葉結(jié)點(diǎn)存儲(chǔ)無疑減少了服務(wù)器上的存儲(chǔ)開銷，也降低了樹的高度，再者SBT本身具有二叉排序樹和二叉平衡樹的結(jié)構(gòu)特性，不僅使得數(shù)據(jù)查找時(shí)非常高效，同時(shí)又很好地維持了樹的高度，也保證了數(shù)據(jù)更新操作時(shí)的效率。

參考文獻(xiàn)：

[1] Deswarte Y, Quisquater J J, Sa?dane A. Remote integrity checking[M]// IFIP International Federation for Information Processing. Springer, 2004,140.

[2] Dan B, Lynn B, Shacham H. Shortsignatures from the weil pairing[M]// Advances in Cryptology—ASIACRYPT 2001. Springer Berlin Heidelberg, 2001:514-532.

[3] Ateniese G, Pietro R D, Mancini L V, et al. Scalable and efficient provable data possession[C]// Proceedings of the 4th International Conference on Security and Privacy in Communication Netowrks. ACM, 2008:1-10.

[4] Erway C, Papamanthou C, Tamassia R. Dynamic provable data possession[C]// ACM Conference on Computer and Communications Security. 2009:213-222.

[5] Merkle R C. A certified digital signature[J]. Lecture Notes in Computer Science, 1990,435:218-238.

[6] Merkle R C. Protocols for public key cryptosystems[C]// Proceedings of IEEE Symposium on Security and Privacy. 1980,3:122.

[7] 任化強(qiáng). 云環(huán)境下操作外包的動(dòng)態(tài)審計(jì)方案設(shè)計(jì)與實(shí)現(xiàn)[D]. 成都:電子科技大學(xué), 2016.

[8] 鄧曉鵬,馬自堂,高敏霞,等. 一種基于雙線性對(duì)的云數(shù)據(jù)完整性驗(yàn)證算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2013,30(7):2124-2127.

[9] 李瑩,張永勝,馬潔. 一種基于H-MHT的動(dòng)態(tài)數(shù)據(jù)完整性檢查方案[J]. 計(jì)算機(jī)應(yīng)用研究, 2015,32(12):3710-3713.

[10] 張亮. 云存儲(chǔ)數(shù)據(jù)完整性檢測(cè)技術(shù)研究[D]. 大連:大連理工大學(xué), 2014.

[11] 譚霜,賈焰,韓偉紅. 云存儲(chǔ)中的數(shù)據(jù)完整性證明研究及進(jìn)展[J]. 計(jì)算機(jī)學(xué)報(bào), 2015,38(1):164-177.

[12] 秦志光,王士雨,趙洋,等. 云存儲(chǔ)服務(wù)的動(dòng)態(tài)數(shù)據(jù)完整性審計(jì)方案[J]. 計(jì)算機(jī)研究與發(fā)展, 2015,52(10):2192-2199.

[13] 姚戈. 云存儲(chǔ)數(shù)據(jù)完整性驗(yàn)證機(jī)制研究[D]. 北京:北京交通大學(xué), 2016.

[14] 趙宇龍. 云存儲(chǔ)中第三方審計(jì)機(jī)構(gòu)在數(shù)據(jù)完整性驗(yàn)證中的應(yīng)用[D]. 成都:電子科技大學(xué), 2015.

[15] 杜朝暉,王建璽. 云存儲(chǔ)中利用TPA的數(shù)據(jù)隱私保護(hù)公共審計(jì)方案[J]. 電子技術(shù)應(yīng)用, 2015,41(5):123-125.

[16] 邢建川,韓帥. 一種基于哈希樹的數(shù)據(jù)動(dòng)態(tài)操作可驗(yàn)證性方法: 中國(guó), CN103218574A[P]. 2013-07-24.

[17] Motghare S, Khandait S P, Mohod P S. Framework of data integrity for cross cloud environment using CPDP scheme[J]. International Journal of Advanced Research in Computer Science, 2013,4(2):55.

[18] Papamanthou C, Tamassia R, Triandopoulos N. Authenticated hash tables based on cryptographic accumulators[J]. Algorithmica, 2016,74(2):664-712.

[19] Rao S, Gujrathi S, Sanghvi M, et al. Analysis on data integrity in cloud environment[J]. IOSR Journal of Computer Engineering, 2014,16:71-76.