Paper 2025/804

Putting Sybils on a Diet: Securing Distributed Hash Tables using Proofs of Space

Christoph U. Günther, Institute of Science and Technology Austria
Krzysztof Pietrzak, Institute of Science and Technology Austria
Abstract

Distributed Hash Tables (DHTs) are peer-to-peer protocols that serve as building blocks for more advanced applications. Recent examples, motivated by blockchains, include decentralized storage networks (e.g., IPFS), data availability sampling, or Ethereum's peer discovery protocol. In the blockchain context, DHTs are vulnerable to Sybil attacks, where an adversary compromises the network by joining with many malicious nodes. Mitigating such attacks requires restricting the adversary's ability to create a lot of Sybil nodes. Surprisingly, the above applications take no such measures. Seemingly, existing techniques are unsuitable for the proposed applications. For example, a simple technique proposed in the literature uses proof of work (PoW), where nodes periodically challenge their peers to solve computational challenges. This, however, does not work well in practice. Since the above applications do not require honest nodes to have a lot of computational power, challenges cannot be too difficult. Thus, even moderately powerful hardware can sustain many Sybil nodes. In this work, we investigate using Proof of Space (PoSp) to limit the number of Sybils DHTs. While PoW proves that a node wastes computation, PoSp proves that a node wastes disk space. This aligns better with the resource requirements of the above applications. Many of them are related to storage and ask honest nodes to contribute a substantial amount of disk space to ensure the application's functionality. With this synergy in mind, we propose a mechanism to limit Sybils where honest nodes dedicate a fraction of their disk space to PoSp. This guarantees that the adversary cannot control a constant fraction of all DHT nodes unless it provides a constant fraction of whole the disk space contributed to the application in total. Since this is typically a significant amount, attacks become economically expensive.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
proofs of spacedistributed hash tablessybil resistance
Contact author(s)
cguenthe @ ista ac at
pietrzak @ ista ac at
History
2025-05-05: approved
2025-05-05: received
See all versions
Short URL
https://ia.cr/2025/804
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/804,
      author = {Christoph U. Günther and Krzysztof Pietrzak},
      title = {Putting Sybils on a Diet: Securing Distributed Hash Tables using Proofs of Space},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/804},
      year = {2025},
      url = {https://eprint.iacr.org/2025/804}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.