基于B+樹的動態數據持有性證明方案

李昊宇，張龍軍，李慶鵬

(武警工程大學 信息工程系，西安 710086) (*通信作者電子郵箱459941720@qq.com)

基于B+樹的動態數據持有性證明方案

李昊宇*，張龍軍，李慶鵬

(武警工程大學 信息工程系，西安 710086) (*通信作者電子郵箱459941720@qq.com)

針對云存儲環境下的數據持有性證明(PDP)方案效率較低、不能很好支持全動態更新的問題，設計了一種基于B+樹的動態數據持有性證明方案。該方案引入雙線性對技術和數據版本表，支持用戶進行數據塊級的細粒度動態操作并能保護用戶的數據隱私。通過優化系統模型并設計節點索引值，使第三方檢測機構能識別錯誤數據并進行精確定位。理論分析及實驗結果表明，與基于Merkel哈希樹(MHT)的方案相比，所提方案能夠顯著降低系統構造認證數據結構的時間開銷，并且簡化了動態更新過程，提高了第三方檢測機構的驗證效率。

數據持有性證明；雙線性對；B+樹；云存儲；數據版本表

0 引言

隨著數據量的爆炸式增長，傳統的存儲服務已無法滿足用戶的日常需求。為節約成本，越來越多的公司和用戶選擇將數據外包給云服務商(Cloud Service Provider, CSP)進行管理和存儲[1]。為使利益最大化，CSP可能不按照服務等級協議的約定存儲數據，使用戶數據面臨極大的風險[2]。為保證數據的高可用性，CSP通常將數據分成多個副本進行存儲，所以用戶需要強有力的證據表明CSP完整無誤地存儲著所有數據且所有副本都與用戶最近一次修改保持一致[3]。

Ateniese等[4]最早提出可證明數據持有(Provable Data Possession，PDP)方案，該方案引入“挑戰—應答”協議，支持公開審計但計算開銷較大。之后他們提出改進的可擴展數據持有性(Scalable Provable Data Possession， SPDP)證明方案[5]，增加了部分動態更新功能，但方案驗證次數有限。Erway等[6]基于跳表(Skip List)結構提出支持全動態更新的PDP方案。Juels等[7]首次提出可恢復性證明(Proofs Of Retrievability， POR)方案，該方案能恢復部分受損數據，但不支持公開驗證和數據動態更新。Schacham等[8]在隨后提出支持公開驗證的POR機制，驗證次數沒有限制但通信開銷較大且不支持動態更新。Wang等[9]提出一種基于Merkel哈希樹(Merkel Hash Tree, MHT)的驗證方案，該方案支持公開審計和數據動態更新，但計算開銷較大。李勇等[10]提出一種基于多分支路徑樹的完整性驗證方案，簡化了動態更新過程但產生輔助信息過多，導致通信開銷較大。Wang[11]引入第三方審計者(Third Party Auditor， TPA)協助用戶驗證數據完整性，該方案減少了用戶負擔，但CSP計算開銷較大。Chen[12]提出一種基于代數簽名的驗證方案，支持用戶無限次驗證，但不支持動態操作。

為解決現有方案計算開銷大、不能較好地支持全動態更新的問題，本文提出一種基于B+樹的數據持有性證明方案，通過引入數據版本表以支持數據塊級的全動態更新；通過優化系統模型并引入節點檢索值，能識別定位錯誤數據并提高TPA的驗證效率。

1 相關知識

1.1 系統模型

方案模型如圖1所示，由4類實體組成。

1)數據擁有者。指有存儲需求的用戶，與遠程CSP建立通信，并將加密數據上傳至云存儲服務器中。

2)授權用戶。經過數據擁有者授權的其他用戶，與數據擁有者共享數據解密密鑰，可以遠程訪問數據并進行更新操作。

3)CSP。包括一個主服務器Master和若干個存儲服務器Slaves。為提高驗證效率，本方案設計由Master負責分配證據生成任務，并收集結果返回給TPA；Slave根據指令為被挑戰的數據生成證據，并返回給Master。

4)TPA。第三方審計者，擁有強大的計算能力，代替數據擁有者對CSP發起挑戰，并對返回的證據進行驗證，將最終結果通知數據擁有者。

圖1 系統模型

1.2 安全模型

用戶數據的完整性面臨以下威脅：

1)CSP為獲取最大利益并保持公司聲譽，可能隱瞞數據損壞、丟失的情況，還可能刪除用戶訪問頻率較低的數據以節省存儲空間。

2)CSP可能存儲比服務協議更少的副本數量，并欺騙用戶，讓用戶以為所有數據被正確完整地存儲。

3)為節省計算資源，CSP可能忽略用戶的更新請求，或只更新部分數據，從而導致多個備份副本數據不一致。

1.3 B+樹和雙線性對

B+樹是一種n叉平衡樹，其每個非葉子節點可以擁有大量葉子節點。一棵深度為h、存儲索引值為b的n階B+樹應滿足以下特性[13]。

1)一棵B+樹由三部分組成：根節點、內部節點和葉子節點。

2)所有葉子節點的深度相同，數據索引值存儲在葉子節點中。

3)一棵B+樹中能夠存儲的最小數據量為：bmin=2?n/2」h，能夠存儲的最大數據量為：bmax=nh-nh-1。

4)進行數據查找、插入和刪除數據的時間復雜度均為O(lognb)。

圖2為B+樹結構的一種實例，其中每個葉子節點存儲一個數據塊索引Ii，根節點R的索引鏈接可表示為Hash函數:H(R1‖R2‖…‖Rn)。葉子節點Ri的索引鏈接為:H(I1‖I2‖…‖In)。

雙線性對 假設G1和G2是階為素數P的循環群。g1，g2是G1和G2的生成元。定義雙線性映射e:G1×G2→GT，滿足以下性質[14]。

1)可計算性。存在有效算法能夠計算e。

2)雙線性性。對所有的u∈G1，v∈G2和a,b∈Zp，有e(ua,vb)=e(u,v)ab。

3)非退化性。e(g1,g2)≠1。

計算性Diffie-Hellman(CDH)問題 給定e(g1,g2)≠1，其中x,y∈Zp，計算gxy。

圖2 B+樹結構

2 B+樹動態數據持有性證明方案

2.1 數據版本表

本文方案支持對外包數據進行動態更新，由于CSP是不可信的，所以需要對已更新數據塊進行驗證，以確保所有數據與用戶最近一次修改相一致。此外，TPA應該知道數據塊的索引值，以保證能夠驗證CSP是否在用戶所請求的特定數據塊位置執行相應的操作。由此引入數據版本表(Data Version Table， DVT)，DVT是一種小型元數據信息，由3部分組成。

1)數據塊索引號(IN)。IN是數據塊的索引值，它存儲著數據塊的具體物理地址。

2)數據塊編號(BN)。BN是數據塊的邏輯編號，它存儲著數據塊的邏輯地址。

3)數據塊版本號(VN)。VN是當前數據塊的版本號，初始設定值為1，每更新一次，VN值增加1。

2.2 方案步驟

為方便描述，符號定義如表1所示。

表1 符號定義

本文方案包含8個多項式時間算法，如下所示。

1)KeyGen→(pk,sk)。假設e:G1×G2→GT是一個雙線性映射，g是G2的生成元。用戶運行該算法生成用戶私鑰sk∈Zp和公鑰pk=gx∈G2。

2)GenB+tree。該算法在用戶端構造B+樹，每個葉子節點對應一個數據塊檢索值，映射完成后對B+樹的根節點簽名得到SignB+tree(H(R))=H(R)x。簽名后和隨后生成的數據塊標簽一起發送給CSP，CSP端由Master節點構造與用戶相同的B+樹。

a)在DVT中更新版本號，VN=VN+1；

②數據塊插入。假設用戶需要在文件f的第i個數據塊后插入新的數據塊b′，構造新的文件f=(b1,b2,…,bi,b′,…,bm+1)。由于本文方案的數據塊索引號不包含在數據塊標簽中，故不必計算插入新塊后移位的數據塊的標簽值。用戶執行如下算法：

③數據塊刪除。分為兩種情況，刪除最后一塊和刪除其他位置的數據塊。這里主要討論第二種情況。假設用戶刪除第i塊，執行算法如下：

a)用戶刪除DVT中的第i個表項，第i項后的所有表項IN減1，其余值不變；

圖3對動態更新過程中DVT的變化進行了舉例。假設初始文件f的DVT如圖3(a)所示，INi=BNi，VNi=1，1≤i≤n；當修改第3塊時，VN3加1，其余值不變，如圖3(b)所示；如果在第3塊后插入新的數據塊，新塊的IN4=4，BN4=n+1,VN4=1，如圖3(c)所示；刪除第3塊，DVT變化如圖3(d)所示。

圖3 DVT在動態操作時的變化

5)ExecUpdate。CSP收到更新請求后，執行下列算法。

①數據塊修改。CSP收到數據塊修改請求后，執行下列操作：

②數據塊插入。CSP收到數據塊插入請求后，執行下列操作：

③數據塊刪除。CSP收到數據塊刪除請求，執行下列操作：

a)刪除第i個數據塊，生成新的文件副本f′；

b)刪除數據標簽δi，生成新的標簽集合δ′。

6)Chal→(ω,πkey(k1),ψkey(k2))。TPA隨機抽取若干個數據塊進行挑戰。需要生成ω，πkey(k1)，ψkey(k2)，ω代表需要挑戰的文件編號，πkey(k1)代表偽隨機置換，ψkey(k2)代表偽隨機函數。將其組合成挑戰信息Chal=(ω,πkey(k1),ψkey(k2))發送給CSP。

7)GenProof→(μ,δ)。CSP收到挑戰信息后，Master節點對任務進行分配，每個Slave節點進行下列計算：

(1)

(2)

(3)

TPA由DVT可得數據塊邏輯號和版本號并對證據進行計算，如果等式成立，則輸出1，代表驗證成功；否則為0。最終，TPA將檢測結果發送給用戶。

2.3 識別損壞副本

圖4 3階B+樹結構

不同存儲服務器返回的證據不同說明用戶數據遭到破壞。假設TPA在驗證時檢測出不同存儲服務器返回的同一數據塊的Hash值hI3不同，需要檢測i=3的葉子節點，判斷哪個存儲服務器出現問題，利用RV可快速識別定位錯誤數據，具體算法如下：

1)比較i和RVA的值。如果RVA

2)比較x和RVB的值，如果X≤RVB，則對此節點的子節點進行檢索。如果X>RVB，則令x=x-RVB，比較x和RVC的大小，如果X≤RVC，則從此節點向下檢索；否則繼續重復該步驟，直到確定繼續向下檢索的節點。本例中x=i=3，可確定繼續檢索第一個子樹。

3)加入當前節點到該數據塊的認證路徑中。

重復步驟2)～3)，直到x=1，檢索到對應的葉子節點。在B+樹結構中使用本算法能較快地檢索到出現問題的節點，減少TPA的驗證開銷。

3 安全性分析

定理如果本文提出的B+tree簽名不可偽造，且CDH問題在雙線性群中是難解的，那么TPA在檢測數據完整性時，沒有攻擊者能夠欺騙TPA，除非返回的證據是正確的。

證畢。

4 性能分析

將本文方案與現有兩類方案進行對比，結果如表2所示，其中n表示數據塊的數量。通過對比，可以看出本文方案的TPA驗證開銷和通信開銷較小，具有實用性。

表2 3種方案性能對比

為更好地評估方案性能，將本文方案與基于MHT的方案[9]進行對比。實驗在Hadoop 2.7.3框架下的Spark平臺上使用Python語言編程實現，雙線性對運算和哈希運算分別在OpenSSL庫和PBC庫中實現。設群階的大小為160 bit，獲得80 bit的安全參數。隨機生成數據文件2 000個，分塊大小為64 KB，數據文件的大小為2 GB，DVT為1 MB，實驗取10次結果的平均值。

首先，通過計算用戶和CSP構建B+樹、MHT樹的時間，比較本文方案與文獻[9]方案的性能。MHT樹是二叉樹結構，假設數據被分為n塊，則至少需要建立深度為1+lbn的二叉樹，樹的深度隨數據塊n呈線性增加。相較于B+樹結構，構造MHT的計算開銷較大。生成不同認證樹結構的時間如圖5所示，可以看到構建B+樹的時間與構建MHT樹的時間在樹的出度為2時相同，隨著出度的增加，構建MHT樹的時間逐漸增加，而構建B+樹的時間大大減少，說明本文方案能夠有效地降低構建數據結構的計算開銷。

圖5 不同出度樹的構建時間對比

為進一步分析方案性能，對CSP計算證據的時間開銷進行分析。運行程序后輸入不同的數據塊數量，得到計算證據的時間如圖6所示。可以看出隨著數據塊大小的增加，CSP計算證據的時間都會逐漸增加；每次驗證的數據塊數量越多，CSP計算證據所花費的時間也越多，CSP的計算開銷越大。

最后對TPA的驗證時間開銷進行分析。以數據塊大小作為輸入，程序最終輸出TPA相應的驗證時間。選取數據塊大小分別為64 KB和128 KB兩種情況，實驗結果如圖7所示。通過實驗對比，可以發現在數據塊大小均為64 KB時，兩種方案的TPA驗證時間在數據塊數量較少時較為相近；但隨著抽取數據塊的數量不斷增加，本文方案的驗證時間開銷明顯低于文獻[9]方案的時間開銷。當設定本文方案數據塊大小為128 KB時，TPA驗證時間與數據塊大小為64 KB的文獻[9]方案的時間相近。

圖6 CSP計算證據的時間開銷

圖7 TPA驗證時間

通過上述實驗可知，相比文獻[9]方案，本文方案使用B+樹認證結構能夠有效降低用戶和CSP構建數據結構的計算開銷，減少TPA的驗證時間，提高數據完整性驗證效率。

5 結語

為解決傳統數據持有性證明方案計算開銷大、驗證時間較長等問題，提出基于B+樹的數據持有性證明方案。在B+樹認證結構中引入數據版本表和節點檢索值，有效支持數據動態更新和錯誤數據識別。實驗證明：本文方案能有效降低模型中各實體的計算開銷，提高TPA的驗證效率。由于本文方案假設TPA是完全可信的，審計過程中用戶數據可能遭到TPA和CSP的共謀攻擊而泄露，下一步將對如何保護用戶數據隱私展開研究。

References)

[1] 俞能海,郝卓,徐甲甲,等.云安全研究進展綜述[J].電子學報,2013,41(2):371-381.(YU N H, HE Z, XU J J, et al. Review of cloud computing security [J]. Acta Electronica Sinica, 2013, 41(2): 371-381.)

[2] 李暉,孫文海,李鳳華,等.公共云存儲服務數據安全及隱私保護技術綜述[J].計算機研究與發展,2014,51(7): 1397-1409.(LI H, SUN W H, LI F H, et al. Secure and privacy-preserving data storage service in public cloud [J]. Journal of Computer Research and Development, 2014, 51(7): 1397-1409.)

[3] BARSOUM A F, HASAN M A. Provable multicopy dynamic data possession in cloud computing systems [J]. IEEE Transactions on Information Forensics & Security, 2015, 10(3): 485-497.

[4] ATENIESE G, BURNS R, CURTMOLA R, et al. Provable data possession at untrusted stores [C]// Proceedings of the 2007 ACM Conference on Computer and Communications Security. New York: ACM, 2007: 598-609.

[5] 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 Networks. New York: ACM, 2008: Article No. 9.

[6] ERWAY C C, PAPAMANTHOU C, TAMASSIA R. Dynamic provable data possession [J]. ACM Transactions on Information & System Security, 2009, 17(4): 213-222.

[7] JUELS A, KALISKI B S. PORs: proofs of retrievability for large files [C]// Proceedings of the 2007 ACM Conference on Computer and Communications Security. New York: ACM, 2007: 584-597.

[8] SHACHAM H, WATERS B. Compact proofs of retrievability [C]// ASIACRYPT ’08: Proceedings of the 14th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology. Berlin: Springer, 2008: 90-107.

[9] 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 & Distributed Systems, 2011, 22(5): 847-859.

[10] 李勇,姚戈,雷麗楠,等.基于多分支路徑樹的云存儲數據完整性驗證機制[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.)

[11] WANG H. Identity-based distributed provable data possession in multicloud Storage [J]. IEEE Transactions on Services Computing, 2015, 8(2): 328-340.

[12] CHEN L. Using algebraic signatures to check data possession in cloud storage [J]. Future Generation Computer Systems, 2013, 29(7): 1709-1715.

[13] JENSEN C S, LIN D, OOI B C. Query and update efficient B+-tree based indexing of moving objects [C]// Proceedings of the Thirtieth International Conference on Very Large Data Bases. Amsterdam: Elsevier, 2004: 768-779.

[14] VAPNIK V N. The Nature of Statistical Learning Theory [M]. Berlin: Springer, 2000: 988-999.

[15] WANG H, ZHANG Y. On the knowledge soundness of a cooperative provable data possession scheme in multicloud storage [J]. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(1): 264-267.

[16] BARSOUM A F, HASAN M A. Provable multicopy dynamic data possession in cloud computing systems [J]. IEEE Transactions on Information Forensics & Security, 2015, 10(3): 485-497.

This work is partially supported by the National Natural Science Foundation of China (61402529), the Natural Science Foundation of Shaanxi Province (2015JQ6266).

LIHaoyu, born in 1993, M. S. candidate. His research interests include cloud computing security, cryptology.

ZHANGLongjun, born in 1964, Ph. D., professor. His research interests include information and network security, cryptology.

LIQingpeng, born in 1992, M. S. candidate. His research interests include data mining, privacy protection.

DynamicprovabledatapossessionschemebasedonB+tree

LI Haoyu*, ZHANG Longjun, LI Qingpeng

(DepartmentofInformationEngineering,EngineeringUniversityofChinesePeople’sArmedPoliceForce,Xi’anShaanxi710086,China)

Concerning the problem that the existing schemes of provable data possession are inefficient and can not support full dynamic update, a novel dynamic provable data possession scheme based on B+tree was proposed. Bilinear pairing techniques and data version table were introduced to support fine-grained dynamic operations at the block level and to protect user’s data privacy in the proposed scheme. The third party auditor could identify the wrong data and locate it accurately by optimizing the system model and designing the retrieved value of data node. In comparison with the scheme based on the Merkel Hash Tree (MHT), theoretical analysis and experimental results show that the proposed scheme can significantly reduce the cost of constructing the authentication data structure, simplify the dynamic update process, and improve the verification efficiency of the third party auditor.

Provable Data Possession (PDP); bilinear pairing; B+tree; cloud storage; data version table

TP309.2

:A

2016- 12- 22;

:2017- 02- 15。

國家自然科學基金資助項目(61402529)；陜西省自然科學基金資助項目(2015JQ6266)。

李昊宇(1993—)，男，陜西富平人，碩士研究生，CCF會員，主要研究方向：云計算安全、密碼學； 張龍軍(1964—)，男，陜西扶風人，教授，博士生導師，博士，主要研究方向：信息與網絡安全、密碼學； 李慶鵬(1992—)，男，山東莒縣人，碩士研究生，主要研究方向：數據挖掘、隱私保護。

1001- 9081(2017)07- 1931- 05

10.11772/j.issn.1001- 9081.2017.07.1931