Verifying the consistency of remote untrusted services with conflict-free operations

Abstract

A group of mutually trusting clients outsources a computation to a remote server, which they do not fully trust and that may be subject to attacks. The clients do not communicate with each other and would like to verify the correctness of the remote computation and the consistency of the server's responses. This paper presents the Conflict-free Operation verification Protocol (COP) that ensures linearizability when the server is correct and preserves fork-linearizability otherwise. Clients that observe each other's operations are consistent and their operations are linearizable. If the server forks two clients by hiding an operation, however, they never again see operations of each other. CO..