Bankrupting Sybil Despite Churn

A Sybil attack occurs when an adversary pretends to be multiple identities (IDs). Limiting the number of Sybil (bad) IDs to a minority permits the use of well-established tools for tolerating malicious behavior, such as protocols for Byzantine consensus and secure multiparty computation. A popular technique for enforcing this minority is resource burning; that is, the verifiable consumption of a network resource, such as computational power, bandwidth, or memory. Unfortunately, prior defenses require non-Sybil (good) IDs to consume at least as many resources as the adversary, unless the rate of churn for good IDs is sufficiently low. Since many systems exhibit high churn, this is a significant barrier to deployment. We present two algorithms that offer useful guarantees against Sybil adversary under a broadly-applicable model of churn. The first is GoodJEst, which estimates the number of good IDs that join the system over any window of time, despite the adversary injecting bad IDs. GoodJEst applies to a broad range of system settings, and we demonstrate its use in our second algorithm, a new Sybil defense called ERGO. Even under high churn, ERGO guarantee (1) there is always a minority of bad IDs in the system; and (2) when the system is under attack, the good IDs burn resources at a total rate that is sublinear in the adversary's consumption. To evaluate the impact of our theoretical results, we investigate the performance of ERGO alongside prior defenses that employ resource burning. Based on our experiments, we design heuristics that further improve the performance of ERGO by up to four orders of magnitude over these previous Sybil defenses.