Cryptology ePrint Archive: Report 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.

Category / Keywords: applications / decentralized storage

Date: received 16 Jul 2018, last revised 12 Aug 2018

Contact author: ethan at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20180813:002317 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]