Paper 2018/684

PIEs: Public Incompressible Encodings for Decentralized Storage

Ethan Cecchetti and Ben Fisch and Ian Miers and Ari Juels

Abstract

We present a provably secure approach to proving file replication (or other erasure coding) in distributed storage networks (DSNs). Storing multiple copies of a file $F$ is essential in DSNs to ensure against file loss in the event of faulty servers or corrupt data. The public nature of DSNs, however, makes this goal challenging. Files must be encoded and decoded using public coins—i.e., without encryption or other secret-key operations—and retention of files by servers in the network must be publicly verifiable. We introduce and formalize the notion of a public incompressible encoding (PIE), a primitive that supports file-replication proofs in the public setting. A PIE enables public verification that a server is storing a replicated encoding $G$ of a target file $F$, and has not compressed $G$ to save storage. In a DSN with monetary rewards or penalties, PIEs can help ensure that economically rational servers store $G$ and thus replicate $F$ honestly. Our PIE constructions are the first to achieve experimentally validated near-optimal performance—only a factor of 4 from optimal by one metric. They also support fast decoding which no other comparable construction does—as much as a factor of 800 in one experiment. PIEs additionally meet the critical security requirements for DSNs and related applications: they preclude demonstrated attacks involving parallelism via ASICs and other custom hardware. They achieve all of these properties using a graph construction we call a Dagwood Sandwich Graph (DSaG) that involves a novel interleaving of depth-robust graphs and superconcentrators. PIEs' performance makes them appealing for DSNs, such as the proposed Filecoin system, and other challenging file-storage needs in public settings. Conversely, their near optimality provides realistic measures of the (considerable) practical costs and limitations of DSNs and other applications.