Enabling Efficient Batch Updating Verification for Multi-versioned Data in Cloud Storage

Existing dynamic data possession verification schemes not only suffer from low efficiency of rebalancing its Merkle Hash tree (MHT) when executing data updating, but also lack effective mechanism to verify multi-version files. Aiming at these problems, this paper propose a new data structure called Rank-based multi-version Merkle AVL tree (RBMV-MAT) to achieve efficient batch updating verification for multi-version data. RBMV-MAT uses a special lock and relaxed balance to decrease the frequency of rebalacing operations. The experimental results show that our efficient scheme has better efficiency than those of existing methods.