Integrita: a BFT distributed storage system

Abstract

Collaborative data sharing underlies applications in systems such as online social networks and cloud storage. A central provider hosts shared data, e.g., a Facebook group page, and provides sharing users with read/write access according to user-defined settings. Historical incidents prove that data storage centralization enables a corrupted provider to censor or diverge users’ views of the shared data. Such misbehavior is hardly detectable as users update the shared data unbeknown to each other. Existing solutions suggest server-side data replication, which is storage inefficient, or users’ out-of-band communication, which is communication intensive. Addressing these inefficiencies, we propose Integrita, a data-sharing mechanism that protects users’ view-consistency needless to out-of-band communication. We present a novel distributed history tree algorithm to partition the shared data among N storage providers, N−1 of which are Byzantine faulty and colluding. Our data partitioning solution reduces storage overhead by a multiplicative factor of N and allows provable detection of server-side equivocation and identification of corrupted servers. We introduce and achieve a new consistency level, named q-detectable consistency, where users’ views inconsistency cannot remain undetected for more than q updates, q being the system parameters’ function. Without loss of generality, we use online social networks as a case study to deploy Integrita and supply performance/numerical analysis accordingly.