文献总结

完整性验证

完整性验证的本质用户首先对数据进行预处理，保存一些私有验证元数据，然后将文件发送给服务器存储。在验证完整性时用户向服务器发送挑战，服务器根据挑战返回给用户证明，用户验证证明的正确性。
验证证明时通常是判断某两个值是否相等，其中一个值是根据服务器返回的证明构造的，另一个值是用户根据私有的验证元信息构造的，这里通常使用的技术有双线性映射、同态验证标签等。

基于密钥哈希的方案

不推荐该方案

在存储文件 F 之前，验证者计算并存储哈希值 r = hκ(F) 以及秘密随机密钥 κ。为了检查证明者是否拥有 F，验证者向证明者出示 κ 并要求证明者计算并返回 r。这个简单的协议就提供了证明者知道 F 的有力证明。通过在不同的密钥上存储多个哈希值，验证者可以发起多个独立的检查。

注意：这里使用基于密钥的哈希而不能使用单独的哈希，因为证明者可能只保存文件的哈希而不保存原始文件，使用密钥哈希这样证明者返回的证明值需要根据用户提供的密钥计算，每次都不同，所以必须保存原始文件

缺点：资源成本高，要求验证者存储与其要执行的检查数量成线性关系的多个哈希值。并且每次调用都要求证明者处理整个文件F，对于大的 F ，即使是像散列这样的轻量级计算操作也可能非常繁重。

PDP方案（同态可验证标签）

ATENIESE G, BURNS R, CURTMOLA R, 等. Provable data possession at untrusted stores[C/OL]

基于同态可验证标签

同态特性可以将多个标签组合成单个标签，可以实现常量大小且比实际文件小得多的证明

本方案对文件进行分块处理，在验证时会抽样验证文件块的子集，减少通信开销，实验证明验证的成功率也比较高。

PDP方案包括四个算法

• KeyGen(1^k^)→(pk,sk)：客户端执行，生成密钥对
• TagBlock(pk,sk,m)→Tm：客户端执行，生成验证元数据。m是文件
• GenProof(pk,F,chal,Σ)→V：服务器运行，生成所有权证明。F是文件块集合、chal是挑战 、Σ是F中对应块的验证元数据集合。
• CheckProof(pk,sk,chal,v)→{“success”,“failure”}：客户端执行，验证所有权证明

具体算法:

个人理解，这里同态特性体现在将多个标签T相乘后得到的黄色部分，随后在计算ρ的时候也得到了对应的部分，这样在验证的时候可以相互抵消。即一次可以验证任意个标签，证明的大小始终是相乘后的结果为一个常量。

这里aj的作用是：由于aj​ 是随机生成的，服务器无法预测哪些 aj​ 将被用于下一个证明。因此，服务器不能只存储数据块的总和或任何其他简化形式的数据表示，因为这样做将无法满足 aj​ 系数的特定组合。

另一种方案是去掉aj：去掉aj可以减少计算量，但是只能保证服务器具有m的总和，而不一定拥有每个文件块

POR方案（随机哨兵）

JUELS A, KALISKI B S. Pors: proofs of retrievability for large files[C/OL]

简而言之，我们的 POR 协议对 F 进行加密并随机嵌入一组称为哨兵的随机值校验块。这里使用加密使得哨兵与其他文件块无法区分。验证者通过指定哨兵集合的位置并要求证明者返回相关的哨兵值来挑战证明者。如果证明者修改或删除了 F 的很大一部分，那么它也很有可能删除了一些哨兵。因此它不太可能正确响应验证者。为了防止 F 的一小部分的证明者损坏，我们还使用了纠错码。F ̃表示证明者存储的完整文件

本方案的两种情况：

• 假设证明者在接收到编码文件F ̃后，破坏了三个随机选择的位：β1、β2、β3。这些位不太可能驻留在哨兵中，哨兵只构成F ̃的一小部分。因此，验证器可能不会通过 POR 执行检测到损坏。然而，由于 F 中存在错误纠正，验证者可以完整地恢复原始文件 F。
• 相反，假设证明者损坏了 F 中的许多块，例如文件的 20%。在这种情况下（没有非常严重的错误编码），验证者不太可能恢复原始文件 F 。另一方面，验证者在 POR 中请求的每个哨兵将以大约 1/5 的概率检测到损坏。通过请求数百个哨兵，验证者可以以压倒性的概率检测到损坏。

前面提到的PDP方案依赖于文件的模幂运算，属于计算密集型的运算

过程细节：

用户只在本地存储哨兵的值作为验证元数据

1. 密钥生成
2. 文件编码：将文件分成多个块并使用纠错码以恢复原始数据；加密文件，生成随机的哨兵值，并将其嵌入到加密文件的随机位置中。并使用伪随机排列对加密文件的数据块进行重新排列，以隐藏哨兵的位置。
3. 挑战生成：根据预先排列的策略，验证者选择一组哨兵，将该组哨兵的位置作为挑战发送给证明者
4. 证明生成：证明者将该位置上的内容返回给验证者
5. 验证：验证证明者返回的值是否与本地存储的哨兵值相匹配

基于Merkle树的方案

YUE D, LI R, ZHANG Y, 等. Blockchain-based verification framework for data integrity in edge-cloud storage[J/OL]

准备阶段

1. 客户端将数据分成多个分片，并使用这些分片构建哈希 Merkle 树。
2. 客户端将该哈希树的根存储在区块链上，表示为root1。
3. 客户端将其数据和公共 Merkle 树上传到 ECS

验证阶段

1. 客户端向ECS节点发送挑战数si，ECS节点选择分片i进行验证。
2. ECS根据si和分片i，使用哈希函数计算哈希摘要i‘。（si+i -> i’）
3. ECS将摘要i’和相应的辅助信息发送给BC。  
4. 区块链上的智能合约计算一个新的哈希根，记为root2，并将root1与root2进行比较。如果相等，则保证数据完整性；否则，数据完整性将被破坏。
5. BC将验证结果返回给客户端。

Merkle树的结构：

Merkle树分为公共和私有两部分，私有部分的底层由分片和挑战数组成。私有部分的第二层包含摘要，Digesti=H(si+shardi)。公共部分的Leafmn是第m层的第n个节点，树的根记为R。

Merkle树的公共部分需要上传到ECS节点，以协助验证每个数据分片。私有部分的数据分片shardi也会上传到ECS节点。至于随机挑战数si，只有当客户端需要验证相应的数据分片时才可以发送给ECS节点。因此，si是由客户端保存在本地的。

辅助信息：
假设原始数据分为12个分片，分支数为4，创建如下merkle 树，假设验证shard0，我们需要D1,D2,D3,D13,D14，这些就是验证shard0需要的辅助信息。

TODO:如何保证区块链收到的摘要和辅助信息就是对应的客户端发送的挑战的文件块呢？这里感觉客户端在发送挑战的时候应该将文件块摘要发给区块链，然后由区块链根据辅助信息验证（也不行那样的话ECS可以只保存摘要而不保存原始数据，ECS仍需发送摘要，ECS发送摘要可以证明它保存了原始数据，因为s是客户端私有的，只有ECS收到了s后才能结合本地保存的原始数据计算摘要，但是这只能使用一次，因为下一次ECS就可以只保存摘要而不保存原始数据，这在该场景下不可行，但是在我们跨链的场景下应该是可行的，因为我们只需要在接收数据时验证一次正确性即可。）（区块链需要能够验证数据摘要确实是用户发起挑战对应的数据，用户同步将挑战发给区块链，区块链进行比对！但是用户没有原始数据！用户只有随机数s）