Visible to the public Peace Through Superior Puzzling: An Asymmetric Sybil Defense

TitlePeace Through Superior Puzzling: An Asymmetric Sybil Defense
Publication TypeConference Paper
Year of Publication2019
AuthorsGupta, Diksha, Saia, Jared, Young, Maxwell
Conference Name2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
ISBN Number978-1-7281-1246-6
Keywordsabstract-A common tool, Algorithm design and analysis, asymmetric Sybil defense, attack scenarios, attacker, composability, computational complexity, computational puzzles, computer network security, distributed computing, Metrics, pubcrawl, resilience, Resiliency, spending rate, Sybil attack, sybil attacks, Sybil defense algorithm, Sybil participants

A common tool to defend against Sybil attacks is proof-of-work, whereby computational puzzles are used to limit the number of Sybil participants. Unfortunately, current Sybil defenses require significant computational effort to offset an attack. In particular, good participants must spend computationally at a rate that is proportional to the spending rate of an attacker. In this paper, we present the first Sybil defense algorithm which is asymmetric in the sense that good participants spend at a rate that is asymptotically less than an attacker. In particular, if T is the rate of the attacker's spending, and J is the rate of joining good participants, then our algorithm spends at a rate f O($\surd$(TJ) + J). We provide empirical evidence that our algorithm can be significantly more efficient than previous defenses under various attack scenarios. Additionally, we prove a lower bound showing that our algorithm's spending rate is asymptotically optimal among a large family of algorithms.

Citation Keygupta_peace_2019