Cryptology ePrint Archive: Report 2018/684

PIEs: Public Incompressible Encodings for Decentralized Storage

Ethan Cecchetti and Ben Fisch and Ian Miers and Ari Juels

Abstract: We present a new primitive supporting file replication in distributed storage networks (DSNs) called a Public Incompressible Encoding (PIE). PIEs operate in the challenging public DSN setting where files must be encoded and decoded with public randomness—i.e., without encryption—and retention of redundant data must be publicly verifiable. They prevent undetectable data compression, allowing DSNs to use monetary rewards or penalties in incentivizing economically rational servers to properly replicate data. Their definition also precludes critical, demonstrated attacks involving parallelism via ASICs and other custom hardware.

Our PIE construction is the first to achieve experimentally validated near-optimal performance—within a factor of 4 of optimal by one metric. It also allows decoding orders of magnitude faster than encoding, unlike other comparable constructions. We achieve this high security and performance using a graph construction called a Dagwood Sandwich Graph (DSaG), built from a novel interleaving of depth-robust graphs and superconcentrators.

PIEs' performance makes them appealing for DSNs, such as the proposed Filecoin system and Ethereum data sharding. Conversely, their near-optimality establishes concerning bounds on the practical financial and energy costs of DSNs allowing arbitrary data.

Category / Keywords: applications / decentralized storage

Original Publication (in the same form): 2019 ACM SIGSAC Conference on Computer and Communications Security

Date: received 16 Jul 2018, last revised 23 Aug 2019

Contact author: ethan at cs cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20190824:025348 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]