  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.
Towards reducing this dependency, this paper introduces a protocol for
verification of integrity and consistency for cloud object storage (VICOS),
which 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 in a generic way on any 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.
