W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
A Sybil attack occurs when an adversary controls multiple system identifiers (IDs). Limiting the number of Sybil (bad) IDs to a minority is critical for tolerating malicious behavior. A popular tool for enforcing a bad minority is resource burning (RB): the verifiable consumption of a network resource. Unfortunately, typical RB defenses require non-Sybil (good) IDs to consume at least as many resources as the adversary. We present a new defense, ERGO, that guarantees (1) there is always a bad minority; and (2) during a significant attack, the good IDs consume asymptotically less resources than the bad. Specifically, despite high churn, the good-ID RB rate is O(TJ+J), where T is the adversary's RB rate, and J is the good-ID join rate. We show this RB rate is asymptotically optimal for a large class of algorithms, and we empirically demonstrate the benefits of ERGO.
W.C. Tang, H. Rosen, et al.
SPIE Optics, Electro-Optics, and Laser Applications in Science and Engineering 1991
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology
George Markowsky
J. Math. Anal. Appl.
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998