Paper 2018/684

PIEs: Public Incompressible Encodings for Decentralized Storage

Ethan Cecchetti, Ben Fisch, Ian Miers, and Ari Juels


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.

Available format(s)
Publication info
Published elsewhere. 2019 ACM SIGSAC Conference on Computer and Communications Security
decentralized storage
Contact author(s)
ethan @ cs cornell edu
2019-08-24: last of 5 revisions
2018-07-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ethan Cecchetti and Ben Fisch and Ian Miers and Ari Juels},
      title = {PIEs: Public Incompressible Encodings for Decentralized Storage},
      howpublished = {Cryptology ePrint Archive, Paper 2018/684},
      year = {2018},
      doi = {10.1145/3319535.3354231},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.