Paper 2018/684

PIEs: Public Incompressible Encodings for Decentralized Storage

Ethan Cecchetti, Ben Fisch, 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Published elsewhere. 2019 ACM SIGSAC Conference on Computer and Communications Security
DOI
10.1145/3319535.3354231
Keywords
decentralized storage
Contact author(s)
ethan @ cs cornell edu
History
2019-08-24: last of 5 revisions
2018-07-17: received
See all versions
Short URL
https://ia.cr/2018/684
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/684,
      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{https://eprint.iacr.org/2018/684}},
      url = {https://eprint.iacr.org/2018/684}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.