Paper 2025/804

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

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.