Cloud services have turned remote computation into a commodity and enable convenient online collaboration. However, they require that clients fully trust the service provider in terms of confidentiality, integrity, and availability. Toward reducing this dependency, this article introduces VICOS, a protocol for verification of integrity and consistency for cloud object storage that enables a group of mutually trusting clients to detect data integrity and consistency violations for a cloud object storage service. It aims at services where multiple clients cooperate on data stored remotely on a potentially misbehaving service. VICOS enforces the consistency notion of fork-linearizability, supports wait-free client semantics for most operations, and reduces the computation and communication overhead compared to previous protocols. VICOS is based on a generic authenticated data structure. Moreover, its operations cover the hierarchical name space of a cloud object store, supporting a real-world interface and not only a simplistic abstraction. A prototype of VICOS that works with the key-value store interface of commodity cloud storage services has been implemented, and an evaluation demonstrates its advantage compared to existing systems. Marcus Brandenburger, Christian Cachin, and Nikola Knežević. 2017. Don't trust the cloud, verify: Integrity and consistency for cloud object stores. 8:2 M. Brandenburger et al. repositories, global project teams produce technical deliverables, and friends share their photo albums. Nevertheless, the clients need to trust the cloud provider, as they rely on it for the confidentiality and correctness of their data. Encryption may preserve the confidentiality of data but cannot prevent inadvertent or malicious data modifications. This work shows how to protect the integrity and consistency of data on an untrusted cloud storage service accessed by multiple clients. With a single client only, the client may locally keep a short cryptographic hash value of the outsourced data. Later, this can be used to verify the integrity of the data returned by the cloud storage service. However, with multiple disconnected clients, no common synchronization, and no communication among the clients, neither hashing nor digital signatures are sufficient by themselves. The reason is that a malicious or Byzantine server may violate the consistency of the data, for example, by reordering or omitting properly authenticated operations so that the views of the storage state at different clients diverge. A malicious cloud server may pretend to one set of clients that some operations by others simply did not occur. In other words, freshness can be violated and the clients cannot detect such replay attacks until they communicate directly. The problem is particularly relevant in cryptographic online voting and for Web certificate transparency (Laurie 2014). The strongest achievable notion of consistency in this multiclient model is captured by forklinearizability, introduced by Mazières and Shasha (2002). A consistency and integrity verification protocol may guarantee this notion by adding condensed data about the causal evolution of the client's views into their interaction with the server. This ensures that if the server creates only a single discrepancy between the views of two clients, these clients may never observe operations of each other afterward. In other words, if the server ever lies to some clients and these clients communicate later, they will immediately discover the violation. Hence, with only one check they can verify a large number of past operations. The SUNDR system (Li et al. 2004 ) pioneered fork-linearizable consistency and demonstrated a network file system protected by a hash tree of every user's files. SUNDR uses an expensive protocol, requiring messages of size Ω(n 2 ) for n clients (Cachin et al. 2007) . Like other systems providing fork-linearizability, it suffers from the inherent limitation that sometimes, even with a correct server, clients have to block and cannot proceed with their next operation because other clients are concurrently executing operations (Cachin et al. 2007 ). To prevent blocking, FAUST (Cachin et al. 2011b), SPORC (Feldman et al. 2010), and Venus (Shraer et al. 2010) relax their guarantees to weak fork-linearizability, which establishes consistency only eventually, after further operations occur; this is not desirable because a client may only know later that a protocol output was not correct. SPORC and the related blind stone tablet (BST) (Williams et al. 2009 ) protocol shift the maintenance of state to the clients such that the server is merely responsible for coordination; every client holds a complete copy of the system's state. This contradicts the goal of outsourcing data to the cloud. Another way to avoid blocking is explored by BST and the commutative-operation verification protocol (COP) (Cachin and Ohrimenko 2014): they let any commuting operations proceed immediately. In this article, we present VICOS, a protocol for verification of integrity and consistency for cloud object storage, which overcomes these limitations and demonstrates a complete practical system. VICOS supports the optimal consistency notion of fork-linearizability, provides wait-free semantics for all compatible client operations, and has smaller overhead than previous protocols. The notion of compatible operations, as introduced here, generalizes the progress condition over commuting operations, which are considered in past work. Informally, an operation o is compatible with ω if executing o before ω does not influence the behavior of ω (i.e., the observed behavior of ω and all future operations remains after ω the same as if o were absent). Conceptually, VICOS is based on abstract authenticated data structures (ADSs) in a modular way. Moreover, it unifies
VICOS REF protects the integrity and consistency verification of a generic cloud-object storage ser-vice.
Don’t Trust the Cloud, Verify: Integrity and Consistency for Cloud Object Stores
TOPS
Computer Science