Paper 2018/684

PIEs: Public Incompressible Encodings for Decentralized Storage

Ethan Cecchetti and Ian Miers and Ari Juels

Abstract

We present the first provably secure, practical 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 ser vers or corrupt data. The public nature of DSNs, however, makes this goal challenging: no secret keys or trusted entities are available. Files must therefore 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 a public incompressible encoding (PIE), a tool that allows for file-replication proofs in this public setting. A PIE enables public verification that a server is (nearly) entirely storing a replicated encoding $G$ of a target file $F$, and has not deduplicated or otherwise compressed $G$ to save storage. In a DSN with monetary rewards or penalties, a PIE helps ensure that an economically rational server is incentivized to store $G$ and thus replicate $F$ honestly. We present a specific PIE based on a novel graph construction, called a Dagwood Sandwich Graph (DSaG), that includes long paths even when an adversary selectively discards edges. This PIE ensures that a cheating server must perform a large (and completely tunable) number of costly sequential cryptographic operations to recover any blocks of $G$ it chooses to discard. By periodically challenging the server to return randomly selected blocks of $G$ and timing the responses, the DSN can thus verify that a server is storing $G$ intact. We prove the security of our PIE construction and present performance evaluations demonstrating that it is efficient in practice---empirically within a factor of 6.2 of optimal by one metric. Our proposed PIE offers a valuable basic tool for building DSNs, such as the proposed Filecoin system, as well as for other challenging file-storage needs in public settings. PIEs also meet the critical security requirements for such applications: they preclude demonstrated attacks involving parallelism and acceleration via ASICs and other custom hardware.