Computer Science ETDs

Publication Date

Fall 12-14-2020

Abstract

In 1993, Dwork and Naor proposed using computational puzzles, a resource burning mechanism, to combat spam email. In the ensuing three decades, resource burning has broadened to include communication capacity, computer memory, and human effort. It has become a well-established tool in distributed security. Due to the cost attached to utilizing resource burning mechanism, these have not been popularized in domains apart from cryptocurrency.

In this dissertation, we design efficient resource burning based Sybil defense techniques for permissionless systems. As a first step, we identify existing resource burning mechanisms in literature in Chapter 2. Additionally, we enumerate numerous open problems in a wide variety of distributed systems, where resource burning might come in handy.

Next, we develop scalable distributed protocols to reduce the fraction of Sybil participants in large scale permissionless systems. To this end, we design a family of provably secure resource burning protocols that have a resource cost which is commensurate with that of the attacker and the number of honest participants that join the system in Chapter 3.

In practice, we observed that the behavior of the join and departure of non-malicious IDs does not vary rapidly over a short duration of time. Using this insight, we design an algorithm that estimates the join rate of non-malicious IDs in the system in Chapter 4. Later, we use this algorithm to determine if the system is under attack.

Our third contribution in this dissertation is a Sybil defense protocol that guarantees an algorithmic spend rate that is a slow-growing function of the resource cost to the adversary in Chapter 5. Additionally, we ensure that in the absence of an attack, the algorithmic spending is commensurate with the join rate of non-malicious IDs.

To test the theory in practice, we simulate the various Sybil defense protocols proposed throughout this dissertation on several real-world networks. We compare the performance of our protocols against the state-of-the-art and discuss several heuristics that further improve the algorithmic spend rate in Chapter 6.

Finally, we present preliminary results for a technique that makes use of our Sybil defense protocols in designing resource-efficient distributed hash tables with efficient reconfiguration costs. We conjecture that the number of reconfigurations of non-malicious IDs grows as a function of the number of joins by the bad IDs.

Language

English

Keywords

Sybil Defense, Peer-to-peer systems, Resource Burning

Document Type

Thesis

Degree Name

Computer Science

Level of Degree

Doctoral

Department Name

Department of Computer Science

First Committee Member (Chair)

Jared Saia

Second Committee Member

Shuang Luan

Third Committee Member

Valerie King

Fourth Committee Member

Maxwell Young

Download

Share

COinS