This paper examines the impact of heavy churn on the robustness of decentralized social network-based Sybil defense (SNSD) schemes. Our analysis reveals that (i) heavy churn disintegrates the social overlay network that is fundamental to these schemes into multiple disconnected components, resulting in poor network connectivity, and (ii) a naive solution that adds links from each node to all its 2-hop neighbors improves network connectivity but comes at a significant cost of poor attack resilience of these schemes.

We propose a new design point in the trade-off between network connectivity and attack resilience of SNSD schemes, where each node adds links to only a selective few of all its 2-hop neighbors based on a minimum expansion contribution (MinEC) heuristic. Extensive evaluation through simulations shows that our approach fares as good as the naive 2-hop solution in terms of network connectivity, while making little compromise on the attack resilience. Moreover, our approach preserves the fast-mixing property that is fundamental to many SNSD schemes even at high levels of churn. This result suggests that existing and potential future SNSD schemes relying on this property can incorporate our approach into their designs with minimal changes.