[發(fā)明專利]一種基于哈希樹的數(shù)據(jù)動(dòng)態(tài)操作可驗(yàn)證性方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201310132565.0
• 申請(qǐng)日: 2013-04-09
• 公開（公告）號(hào): CN103218574A
• 公開（公告）日: 2013-07-24
• 發(fā)明（設(shè)計(jì)）人: 邢建川;韓帥
• 申請(qǐng)（專利權(quán)）人: 電子科技大學(xué)
• 主分類號(hào): G06F21/64
• 分類號(hào): G06F21/64
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種基于哈希樹的數(shù)據(jù)動(dòng)態(tài)操作可驗(yàn)證性方法，其特征在于，包括以下步驟：

A文件預(yù)處理

文件進(jìn)行預(yù)處理之前，USER會(huì)向CDC提出數(shù)據(jù)文件的存儲(chǔ)請(qǐng)求，CDC按照其預(yù)先設(shè)定的訪問控制規(guī)則對(duì)USER進(jìn)行身份驗(yàn)證，通過CDC身份驗(yàn)證的合法用戶便會(huì)獲得進(jìn)行文件存儲(chǔ)的權(quán)限；

USER通過CDC的身份驗(yàn)證之后，CDC便開始接收USER需要存儲(chǔ)的數(shù)據(jù)文件，并對(duì)其進(jìn)行預(yù)處理：

(1)首先，數(shù)據(jù)文件將被分成大小相同的若干個(gè)數(shù)據(jù)塊，F(xiàn)→(f1，f2，f3，f4，f5，f6，...fn)，

(2)然后，CDC對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行哈希操作并求出所有數(shù)據(jù)塊的哈希值H(fi)(1≤i≤n)，

(3)哈希操作之后，數(shù)據(jù)文件可以記為：F’→(f1+H(f1)，f2+H(f2)，f3+H(f3)，...，fn+H(fn))，CDC將暫時(shí)保存所有數(shù)據(jù)塊的哈希值，為接下來(lái)構(gòu)造文件的驗(yàn)證數(shù)據(jù)結(jié)構(gòu)Merkle?Hash?Tree做準(zhǔn)備，

(4)為了對(duì)數(shù)據(jù)塊進(jìn)行唯一的地理位置標(biāo)記，方案為每個(gè)數(shù)據(jù)塊添加了一個(gè)5字節(jié)大小的位置標(biāo)簽(LTag)，標(biāo)簽由2字節(jié)的次序標(biāo)記信息、1字節(jié)的機(jī)架標(biāo)記信息和2字節(jié)的節(jié)點(diǎn)標(biāo)記信息組成，次序標(biāo)記信息記錄的是數(shù)據(jù)塊在所有數(shù)據(jù)塊中的次序編號(hào)，機(jī)架標(biāo)記信息記錄的是該數(shù)據(jù)塊存儲(chǔ)在數(shù)據(jù)中心的具體機(jī)架編號(hào)，節(jié)點(diǎn)標(biāo)記信息則標(biāo)明數(shù)據(jù)塊存儲(chǔ)的節(jié)點(diǎn)服務(wù)器的具體編號(hào)，CDC會(huì)為每個(gè)數(shù)據(jù)文件維護(hù)一個(gè)LTag標(biāo)簽列表，記錄該文件所有數(shù)據(jù)塊的LTag標(biāo)簽信息；

(5)標(biāo)簽添加完畢之后，所有數(shù)據(jù)塊將會(huì)被CDC存入數(shù)據(jù)中心，數(shù)據(jù)塊所存儲(chǔ)的地理位置信息也會(huì)被記錄在數(shù)據(jù)塊自己的LTag標(biāo)簽之中，待所有數(shù)據(jù)塊的LTag標(biāo)簽記錄完畢，CDC將會(huì)為數(shù)據(jù)文件創(chuàng)建一個(gè)包含全部數(shù)據(jù)塊地理位置信息的LTag標(biāo)簽信息列表，

(6)隨后，進(jìn)行關(guān)鍵數(shù)據(jù)結(jié)構(gòu)Merkle?Hash?Tree的構(gòu)造，

1)首先，CDC從Ltag標(biāo)簽列表中取出文件所有數(shù)據(jù)塊的機(jī)架值Rack(LTag(fi))，對(duì)存儲(chǔ)在不同機(jī)架中的數(shù)據(jù)塊進(jìn)行劃分，存入相應(yīng)機(jī)架的ListRack[]列表，

2)然后，CDC依次從不同機(jī)架的ListRack[]列表中取出所有數(shù)據(jù)塊Ltag標(biāo)簽中的節(jié)點(diǎn)信息，對(duì)存儲(chǔ)在相同機(jī)架不同節(jié)點(diǎn)的數(shù)據(jù)塊再次進(jìn)行劃分，

3)接著，對(duì)存儲(chǔ)在相同機(jī)架相同節(jié)點(diǎn)的數(shù)據(jù)塊，CDC將取出它們Ltag標(biāo)簽中的次序信息，進(jìn)行按序排列，用數(shù)據(jù)塊的哈希值作為葉子節(jié)點(diǎn)構(gòu)造節(jié)點(diǎn)Merkle?Hash?Tree，并計(jì)算其根節(jié)點(diǎn)值，如果節(jié)點(diǎn)僅存有一個(gè)數(shù)據(jù)塊，則該數(shù)據(jù)塊的哈希值便為該節(jié)點(diǎn)Merkle?Hash?Tree的根節(jié)點(diǎn)值，，記為NRoot[i，j]，其中i代表所在機(jī)架編號(hào)，j代表所在節(jié)點(diǎn)編號(hào)，

4)完成文件存儲(chǔ)的所有節(jié)點(diǎn)Merkle?Hash?Tree的構(gòu)造和根節(jié)點(diǎn)值的計(jì)算工作之后，CDC將存儲(chǔ)在相同機(jī)架的所有節(jié)點(diǎn)Merkle?Hash?Tree根節(jié)點(diǎn)值按節(jié)點(diǎn)順序進(jìn)行排序，將其作為葉子節(jié)點(diǎn)構(gòu)造各個(gè)機(jī)架的Merkle?Hash?Tree，并計(jì)算其根節(jié)點(diǎn)值，如果機(jī)架僅有一個(gè)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)文件，則該節(jié)點(diǎn)的Merkle?Hash?Tree根節(jié)點(diǎn)值便為機(jī)架Merkle?Hash?Tree的根節(jié)點(diǎn)值，記為RRoot[i]，其中i代表機(jī)架序號(hào)，

5)最后，對(duì)所有機(jī)架Merkle?HashTree的根節(jié)點(diǎn)值進(jìn)行按序排列，將它們的根節(jié)點(diǎn)值作為葉子節(jié)點(diǎn)構(gòu)造文件的Merkle?Hash?Tree，并計(jì)算其根節(jié)點(diǎn)值(如果僅有一個(gè)機(jī)架存儲(chǔ)數(shù)據(jù)文件，則該機(jī)架的Merkle?Hash?Tree根節(jié)點(diǎn)值便為文件Merkle?Hash?Tree的根節(jié)點(diǎn)值)，記為FRoot；

B數(shù)據(jù)文件的驗(yàn)證

(1)首先，CDC完成USER的數(shù)據(jù)文件存儲(chǔ)工作，并向TPA提交USER所存儲(chǔ)數(shù)據(jù)文件的相關(guān)驗(yàn)證信息，數(shù)據(jù)文件在被USER刪除之前，只要發(fā)生了改動(dòng)，CDC都將負(fù)責(zé)為數(shù)據(jù)文件生成最新的驗(yàn)證信息，并與TPA進(jìn)行實(shí)時(shí)更新，

(2)然后，CDC通知USER數(shù)據(jù)文件的存儲(chǔ)及驗(yàn)證信息的生成工作已經(jīng)完成，并告知USER可以開始委托TPA對(duì)數(shù)據(jù)文件進(jìn)行完整性和一致性的驗(yàn)證，

(3)USER可以選擇馬上或者另選其他時(shí)間與TPA進(jìn)行通信，來(lái)委托TPA對(duì)數(shù)據(jù)文件進(jìn)行完整性和一致性驗(yàn)證，

(4)TPA在收到USER的審計(jì)委托請(qǐng)求之后，會(huì)根據(jù)USER的需求對(duì)數(shù)據(jù)文件進(jìn)行定期或不定期的審計(jì)驗(yàn)證，并對(duì)所有審計(jì)操作保留驗(yàn)證日志以供USER日后查驗(yàn)，驗(yàn)證過程中，如果出現(xiàn)數(shù)據(jù)文件驗(yàn)證失敗的情況，則TPA將通過郵件或短信等通信方式告知USER，同時(shí)要求CDC進(jìn)行數(shù)據(jù)文件的副本恢復(fù)等補(bǔ)救措施，

方案中數(shù)據(jù)文件的驗(yàn)證過程是指USER委托TPA所進(jìn)行的定期不定期的數(shù)據(jù)文件完整性和一致性審查，TPA通過向CDC提出數(shù)據(jù)文件的完整性和一致性驗(yàn)證請(qǐng)求，并對(duì)CDC回復(fù)的驗(yàn)證信息進(jìn)行審核，來(lái)完成USER所委托的驗(yàn)證工作，具體描述如下：

1)驗(yàn)證的起始階段，TPA生成驗(yàn)證信息checkM(UInfo，F(xiàn)Info，RInfo(FRoot，RRoot[i]，NRoot[i，j]))，checkM驗(yàn)證消息由三部分組成：一是用戶的個(gè)人信息UInfo，UInfo可以幫助CDC迅速準(zhǔn)確定位需要進(jìn)行查驗(yàn)的數(shù)據(jù)文件的擁有者；二是需要查驗(yàn)的數(shù)據(jù)文件信息FInfo，F(xiàn)Info明確的指出需要進(jìn)行查驗(yàn)的數(shù)據(jù)文件；三是具體的Merkle?Hash?Tree根節(jié)點(diǎn)信息RInfo，RInfo由數(shù)據(jù)文件Merkle?Hash?Tree根節(jié)點(diǎn)值FRoot、指定機(jī)架Merkle?Hash?Tree根節(jié)點(diǎn)值RRoot[i]和指定節(jié)點(diǎn)Merkle?Hash?Tree根節(jié)點(diǎn)值NRoot[i，j]三部分組成，

2)驗(yàn)證消息checkM生成之后，TPA會(huì)通過通信網(wǎng)絡(luò)將checkM傳送給CDC，

3)CDC接收到驗(yàn)證信息后，首先會(huì)對(duì)checkM進(jìn)行分解，確定TPA所要審查的相關(guān)內(nèi)容，

4)然后，CDC使用上述A節(jié)介紹的相關(guān)Merkle?Hash?Tree生成算法重新生成并計(jì)算相應(yīng)Merkle?Hash?Tree及其根節(jié)點(diǎn)值，

5)完成所有驗(yàn)證信息的生成工作之后，CDC將生成驗(yàn)證回復(fù)信息respondM(UInfo，F(xiàn)Info，RInfo’(FRoot’，RRoot’[i]，NRoot’[i，j]))，其中，UInfo和FInfo的內(nèi)容與checkM驗(yàn)證信息的前兩部分保持一致，RInfo’則返回TPA需要審查的相關(guān)Merkle?Hash?Tree根節(jié)點(diǎn)值，包括指定的數(shù)據(jù)文件Merkle?Hash?Tree根節(jié)點(diǎn)值FRoot’、指定的機(jī)架Merkle?Hash?Tree根節(jié)點(diǎn)值RRoot’[i]和指定的節(jié)點(diǎn)Merkle?Hash?Tree根節(jié)點(diǎn)值NRoot’[i，j]三部分，

6)最后，TPA在收到respondM驗(yàn)證回復(fù)信息之后，將與自身保存的相關(guān)Merkle?Hash?Tree根節(jié)點(diǎn)值進(jìn)行比對(duì)，如果結(jié)果一致，則審查失敗，數(shù)據(jù)完整且與先前版本一致，反之，則說(shuō)明數(shù)據(jù)與先前版本不一致，TPA將要求CDC進(jìn)行數(shù)據(jù)文件的副本恢復(fù)等異常處理操作，并將審查結(jié)果告知USER；

C數(shù)據(jù)的動(dòng)態(tài)操作

C1數(shù)據(jù)的插入操作

插入操作是數(shù)據(jù)文件最基本的動(dòng)態(tài)操作內(nèi)容，相對(duì)于修改和刪除操作也是方案中最為復(fù)雜的動(dòng)態(tài)操作，在數(shù)據(jù)文件的第i個(gè)數(shù)據(jù)塊fi之后插入數(shù)據(jù)塊fi’，方案的操作步驟可以描述如下：

(1)CDC計(jì)算出新的數(shù)據(jù)塊fi’的哈希值H(fi’)，并為需要進(jìn)行插入操作的數(shù)據(jù)塊fi’創(chuàng)建標(biāo)簽信息LTag(fi’)，

(2)生成并運(yùn)行插入操作函數(shù)Insert(fi’，H(fi’)，LTag(fi))，通過LTag(fi)定位數(shù)據(jù)塊插入的具體位置，進(jìn)行數(shù)據(jù)塊的插入操作，

(3)調(diào)用Merkle?Hash?Tree插入操作函數(shù)MerkleInsert(h(fi)，h(fi’)，LTag(fi))，該函數(shù)對(duì)h(fi)和h(fi’)進(jìn)行連接操作，并對(duì)連結(jié)后的數(shù)值再次進(jìn)行哈希操作，然后CDC使用哈希操作產(chǎn)生的新結(jié)果替代原來(lái)節(jié)點(diǎn)Merkle?Hash?Tree中LTag(fi)位置節(jié)點(diǎn)的哈希值，，連結(jié)后數(shù)值進(jìn)行哈希得到的結(jié)果已不再是Merkle?Hash?Tree的葉子節(jié)點(diǎn)，而是作為由h(fi)和h(fi’)兩個(gè)葉子節(jié)點(diǎn)生成的中間節(jié)點(diǎn)，

(4)調(diào)用fi’所在節(jié)點(diǎn)的Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的節(jié)點(diǎn)MerkleHash?Tree，并計(jì)算其根節(jié)點(diǎn)值NRoot[i，j]，其中i代表數(shù)據(jù)塊所在的節(jié)點(diǎn)，j代表數(shù)據(jù)塊所在機(jī)架，

(5)調(diào)用fi’所在機(jī)架的Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的機(jī)架MerkleHash?Tree，并計(jì)算其根節(jié)點(diǎn)值RRoot[i]，其中i代表數(shù)據(jù)塊所在的機(jī)架，

(6)重新調(diào)用文件Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的文件Merkle?HashTree，并計(jì)算其根節(jié)點(diǎn)值FRoot，

(7)CDC將更新信息向TPA進(jìn)行匯報(bào)，發(fā)送更新請(qǐng)求信息UpdateRequest(UInfo，F(xiàn)Info，RInfo(FRoot，RRoot[i]，NRoot[i，j])，其中UInfo、FInfo和RInfo與B節(jié)定義相同，，

(8)TPA按照更新請(qǐng)求信息的具體內(nèi)容對(duì)數(shù)據(jù)文件的驗(yàn)證信息進(jìn)行更新，以備以后查驗(yàn)之用，

C2數(shù)據(jù)的修改操作

修改操作是云計(jì)應(yīng)用中最頻繁的數(shù)據(jù)動(dòng)態(tài)操作，對(duì)數(shù)據(jù)文件的第i塊數(shù)據(jù)塊fi進(jìn)行修改，修改之后第i塊數(shù)據(jù)塊將變?yōu)閒i’，方案的具體操作步驟描述如下：

(1)CDC計(jì)算出新的數(shù)據(jù)塊fi’的哈希值H(fi’)，并使用fi的標(biāo)簽信息LTag(fi)作為fi’的標(biāo)簽信息LTag(fi’)，

(2)生成并運(yùn)行更新操作函數(shù)Update(fi’，H(fi’)，LTag(fi))，通過LTag(fi)定位需要進(jìn)行修改的數(shù)據(jù)塊的具體位置，進(jìn)行數(shù)據(jù)塊的修改操作，

(3)調(diào)用Merkle?Hash?Tree修改操作函數(shù)MerkleUpdate(fi’，H(fi’)，LTag(fi’))，通過LTag(fi’)定位需要進(jìn)行修改的數(shù)據(jù)塊的具體位置，用H(fi’)替代H(fi)，

(4)調(diào)用fi’所在節(jié)點(diǎn)的Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的節(jié)點(diǎn)Merkle?HashTree，并計(jì)算其根節(jié)點(diǎn)值NRoot[i，j]，其中i代表數(shù)據(jù)塊所在的節(jié)點(diǎn)，j代表數(shù)據(jù)塊所在機(jī)架，

(5)調(diào)用fi’所在機(jī)架的Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的機(jī)架Merkle?Hash?Tree，并計(jì)算其相應(yīng)的根節(jié)點(diǎn)值RRoot[i]，其中i代表數(shù)據(jù)塊所在的機(jī)架，

(6)調(diào)用文件Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的文件Merkle?Hash?Tree，并計(jì)算其根節(jié)點(diǎn)值FRoot，

(7)CDC將更新信息向TPA進(jìn)行匯報(bào)，發(fā)送更新請(qǐng)求信息UpdateRequest(UInfo，F(xiàn)Info，RInfo(FRoot，RRoot[i]，NRoot[i，j])，其中UInfo、FInfo和RInfo與B節(jié)定義相同，

(8)TPA按照更新請(qǐng)求信息的具體內(nèi)容對(duì)數(shù)據(jù)文件的驗(yàn)證信息進(jìn)行更新，以備以后查驗(yàn)之用；

C3數(shù)據(jù)的刪除操作

例如將數(shù)據(jù)文件的第i個(gè)數(shù)據(jù)塊fi之后的數(shù)據(jù)塊fi+1刪除，方案的具體操作步驟描述如下：

(1)生成并運(yùn)行刪除操作函數(shù)Delete(fi+1，H(fi+1)，LTag(fi+1))，通過LTag(fi+1)定位需要進(jìn)行刪除的數(shù)據(jù)塊的具體位置，進(jìn)行數(shù)據(jù)塊的刪除操作，

(2)調(diào)用Merkle?Hash?Tree刪除操作函數(shù)MerkleDelete(LTag(fi+1)，LTag(fi))函數(shù)，將LTag(fi+1)位置上的h(fi+1)刪除，使用h(fi)值替代h(fi)和h(fi+1)哈希生成的Merkle?Hash?Tree中間節(jié)點(diǎn)h(h(fi)+h(fi+1)，刪除操作雖然使Merkle?Hash?Tree減少了兩個(gè)葉子節(jié)點(diǎn)，但是Merkle?Hash?Tree基本的邏輯結(jié)構(gòu)并沒有改變，

(3)調(diào)用fi所在節(jié)點(diǎn)的Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的節(jié)點(diǎn)Merkle?Hash?Tree，并計(jì)算其根節(jié)點(diǎn)值NRoot[i，j]，其中i代表數(shù)據(jù)塊所在的節(jié)點(diǎn)，j代表數(shù)據(jù)塊所在的機(jī)架，

(4)調(diào)用fi所在機(jī)架的Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的機(jī)架Merkle?Hash?Tree，并計(jì)算其相應(yīng)的根節(jié)點(diǎn)值RRoot[i]，其中i代表數(shù)據(jù)塊所在的機(jī)架，

(5)調(diào)用文件Merkle?Hash?Tree生成函數(shù)CreateMerkle()，生成新的文件Merkle?Hash?Tree，并計(jì)算其根節(jié)點(diǎn)值FRoot，

(6)CDC將更新信息向TPA進(jìn)行匯報(bào)，發(fā)送更新請(qǐng)求信息UpdateRequest(UInfo，F(xiàn)Info，RInfo(FRoot，RRoot[i]，NRoot[i，j])，其中UInfo、FInfo和RInfo與B節(jié)定義相同，

(7)TPA按照更新請(qǐng)求信息的具體內(nèi)容對(duì)USER的數(shù)據(jù)文件進(jìn)行更新，以備以后查驗(yàn)之用。