Certificate-based multi-copy cloud storage auditing supporting data dynamics

这篇文章针对当前多副本云存储审计的不足，提出了一种支持数据动态更新、基于证书的多副本云存储审计方案，旨在解决数据完整性验证中的多项挑战，如复杂的证书管理、密钥托管问题，以及抵御复制总和攻击。

研究背景与问题

随着云计算技术的发展，用户将数据存储在云端以应对本地存储的限制。然而，云存储环境下，数据的完整性和可用性成为了关键问题，因为存储在云中的数据可能由于硬件故障、恶意攻击等原因而丢失或损坏，甚至云服务提供商也可能因恶意行为删除用户不常访问的数据。这种情况下，用户难以发现数据的损坏，因此，保证数据的完整性和安全性变得至关重要。

为了保证数据的完整性，Provable Data Possession (PDP) 方案被提出，用户可以在无需下载完整数据的情况下验证云中存储的数据完整性。随后的研究进一步提出了基于 PDP 的云存储审计方案，涉及数据隐私保护、用户撤销、数据去重和数据传输等多个问题。然而，多数方案仅存储单一副本，一旦数据丢失便无法恢复，因此，多副本存储成为提高数据可用性和恢复能力的有效策略。

Leaves Merkle Hash Tree (LMHT)(由本论文提出)

LMHT 的结构特点

LMHT 的基本构成类似于传统的 Merkle 哈希树，但它在节点的设计和数据管理上有一些改进和扩展：

节点的组成：

在 LMHT 中，每个节点 (N) 包含以下三项内容：
哈希值 (h)：当前节点的哈希值。
左子树叶节点数量 (n_l)：左子树中包含的叶节点数量。
右子树叶节点数量 (n_r)：右子树中包含的叶节点数量。

叶节点的哈希值计算：

每个叶节点存储的是数据块副本的哈希值。具体来说，第 j 个叶节点的哈希值计算为： h_j=h(b_1j ∥ b_2j ∥ ⋯ ∥ b_Pj ∥ T_j) 其中：
b_ij 表示第 j 个数据块的第 i 个副本。
P 是数据块副本的数量。
T_j是该数据块的创建或修改时间戳。
叶节点的 n_l 和 n_r 都为 0。

非叶节点的哈希值计算：

非叶节点 NNN 的哈希值由其左右子节点的哈希值组合计算： *h=h(left_child_hash ∥ right_child_hash)
对于非叶节点，n_l 和 n_r 分别表示左子树和右子树中的叶节点数量，可以通过对子树的 n_l 和 n_r 求和得到。

LMHT 的优势

LMHT 的设计在数据动态更新（尤其是删除操作）方面具有显著的优势，特别是在以下几点：

高效的连续数据块删除：

LMHT 在连续删除多个数据块时，通过记录子树中叶节点的数量，可以快速判断是否可以直接删除整棵子树。
具体来说，当需要删除某个范围内的数据块时，LMHT 能够通过比较左右子树的叶节点数量，直接删除整个子树，而不需要逐个节点地进行更新。这样可以显著降低连续删除操作的复杂度，从而提高删除效率。
删除的时间复杂度为 O(log⁡₂n)，其中 n 是数据块总数。而传统的 Merkle 树需要 O(d*log⁡₂n) 的时间复杂度来删除 d 个连续的数据块，这意味着 LMHT 在连续删除多个数据块时更为高效。

支持数据的动态更新：

LMHT 支持对数据块的 插入、修改和删除 操作，并且在进行这些操作后，能够高效地更新哈希树结构，从而保持数据的完整性。
例如，插入操作 会通过深度优先搜索的方法定位到要插入的位置，并将新的叶节点作为兄弟节点添加到目标节点旁，同时更新所有父节点的哈希值和叶节点数量信息。

数据动态性的有效性：

在进行数据动态更新时，LMHT 能够同步更新所有副本的数据块和相应的哈希值，确保多副本数据块之间的一致性和完整性。

抵御复制总和攻击：

在 LMHT 中，时间戳 (T_j) 被嵌入到叶节点中，用于防止云服务商通过未修改的旧数据块或副本总和来通过数据完整性验证。这样可以有效防止复制总和攻击，确保云服务商必须存储所有完整的数据副本，而不能通过简单计算数据块之和来欺骗验证过程。