可交换操作的远程不可信服务一致性验证

### 可交换操作的远程不可信服务一致性验证 #### 研究背景与问题提出 随着云计算的发展，大多数计算任务在远程数据中心运行，用户不得不依赖服务提供商来保证计算的机密性和正确性。然而，远程计算可能会因错误或恶意攻击而出现微妙变化，导致客户端收到错误响应。因此，验证外包数据和计算的完整性以及服务提供商响应的一致性变得至关重要。 在一个客户端之间不进行通信的异步网络模型中，服务器可能会进行分叉攻击，在对某些客户端的响应中忽略其他客户端操作的影响。在这种情况下，最佳的一致性保证是分叉线性化（fork - linearizability），它能确保服务语义清晰，并让客户端轻松检测服务器的不当行为。 #### 相关工作 以下是一些相关协议的总结： | 协议 | 无阻塞操作 | 功能 | 一致性 | 执行方 | | ---- | ---- | ---- | ---- | ---- | | SUNDR [23, 18] | — | 存储 | 分叉线性化 | 服务器 | | FAUST & Venus [6, 27] | ✓ | 存储 | 弱分叉线性化 | 服务器 | | BST [29] | (✓) | 单个可交换操作 | (分叉线性化) | 客户端 | | SPORC [13] | ✓ | 通用操作转换操作 | (弱分叉线性化) | 客户端 | | COP (Sec. 3) | ✓ | 通用可交换操作 | 分叉线性化 | 客户端 | | ACOP (Sec. 4) | ✓ | 通用可交换操作 | 分叉线性化 | 服务器 | ##### Blind Stone Tablet (BST) BST协议用于协调远程服务器上的数据库事务。客户端先在本地模拟事务，然后与服务器协调事务顺序。根据服务器响应判断事务是否与其他客户端的待处理事务冲突，冲突则撤销事务，否则提交并通过服务器转发给其他客户端。 BST存在以下局限性： 1. 客户端的事务更新依赖于其他客户端，可能导致操作阻塞，无法实现无阻塞操作。 2. 其“跟踪一致性”的概念只考虑应用到本地状态的事务，而不是满足分叉线性化所需的响应，因此客户端操作可能不满足分叉线性化。 3. 每个客户端都要维护数据库副本并在本地重放所有操作。 ##### 非阻塞协议 - **SPORC**：是一个群组协作系统，通过操作转换允许操作以不同顺序执行并收敛到相同状态。它声称提供了近似于弱分叉线性化的分叉 - *线性化，但无正式分析，且只关注客户端状态更新，不考虑本地输出。 - **FAUST**：从不阻塞客户端，具有最终一致性，但仅保证弱分叉线性化。 #### 解决方案：COP和ACOP协议 为了解决上述问题，提出了Commutative - Operation验证协议（COP）及其扩展A