Canal: Scaling Social Network-Based Sybil Tolerance Schemes

摘要

There has been a flurry of research on leveraging social net-works to defend against multiple identity, or Sybil, attacks. A series of recent works does not try to explicitly identify Sybil identities and, instead, bounds the impact that Sybil identi-ties can have. We call these approaches Sybil tolerance; they have shown to be effective in applications including repu-tation systems, spam protection, online auctions, and con-tent rating systems. All of these approaches use a social net-work as a credit network, rendering multiple identities in-effective to an attacker without a commensurate increase in social links to honest users (which are assumed to be hard to obtain). Unfortunately, a hurdle to practical adoption is that Sybil tolerance relies on computationally expensive network analysis, thereby limiting widespread deployment. To address this problem, we first demonstrate that despite their differences, all proposed Sybil tolerance systems work by conducting payments over credit networks. These pay-ments require max flow computations on a social network graph, and lead to poor scalability. We then present Canal, a system that uses landmark routing-based techniques to ef-ficiently approximate credit payments over large networks. Through an evaluation on real-world data, we show that Canal provides up to a three-order-of-magnitude speedup while maintaining safety and accuracy, even when applied to social networks with millions of nodes and hundreds of millions of edges. Finally, we demonstrate that Canal can be easily plugged into existing Sybil tolerance schemes, en-abling them to be deployed in an online fashion in real-world systems.