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

# 基于交换操作的远程不可信服务一致性验证 ## 1. 研究背景 随着云计算的出现，大多数计算都在远程数据中心进行，而不再在本地设备上运行。用户不得不信任服务提供商来保证计算的机密性和正确性。然而，远程计算可能会因为各种原因出现问题，导致服务提供商的响应不一致或不正确。 ### 1.1 问题描述 假设有一组相互信任的客户端，它们希望协作使用由远程部分可信服务器提供的资源，如包含共同项目数据的维基、存档文档存储库或云端运行的群件工具。但服务器可能会受到攻击或出现错误，导致对客户端的响应出现问题。客户端希望评估计算的完整性，验证响应的正确性，并确保他们都能得到一致的响应。 ### 1.2 攻击类型 在客户端之间没有通信的异步网络模型中，服务器可能会进行分叉攻击，即在对一个客户端的响应中忽略另一个客户端的操作效果。由于客户端不知道其他客户端执行了哪些操作，被分叉的客户端无法检测到这种违规行为。 ### 1.3 一致性保证 为了解决这个问题，引入了叉线性化（fork - linearizability）的概念。叉线性化确保当服务器在对客户端 C1 的响应中忽略了客户端 C2 执行的操作时，C1 之后永远不会再观察到 C2 的操作，反之亦然。这一特性在面对攻击时确保了明确的服务语义，并允许客户端轻松检测服务器的不当行为。 ## 2. 相关工作 近年来，在使用叉线性化和相关概念进行一致性检查和验证方面取得了一些进展。这些协议确保当服务器正确时，服务是线性化的，并且理想情况下算法是无等待的，即每个客户端的操作独立于其他客户端完成。 ### 2.1 现有协议的问题 然而，读写冲突会导致这些协议阻塞，这适用于叉线性化语义和其他分叉一致性概念。如果所有操作都要不阻塞地进行，就需要将一致性保证弱化，例如弱叉线性化。 ### 2.2 对比协议：Blind Stone Tablet (BST) 协议 BST 协议支持由不可信服务器托管的加密远程数据库，多个客户端可以访问该数据库。其一致性检查算法允许一些可交换的客户端操作并发进行，但程度有限。每个客户端必须维护完整的服务状态并执行所有操作，并且该协议仅保证数据库状态更新的叉线性化，而不能确保客户端输出的所有响应都满足叉线性化。 ## 3. 主要协议介绍 ### 3.1 交换操作验证协议（COP） - **功能**：COP 为任意功能施加叉线性化语义，利用可交换操作，允许客户端在操作不冲突的情况下并发操作而不阻塞。 - **优势**：当服务器正确时，确保线性化；在其他情况下，保留叉线性化。所有观察到彼此操作的客户端都是一致的，即它们自己的操作和看到的其他客户端的操作都是线性化的。 ### 3.2 认证 COP（Authenticated COP） - **功能**：通过认证数据结