Whanaungatanga: Sybil-proof routing with social networks
Decentralized systems, such as distributed hash tables, are subject to the Sybil attack, in which an adversary creates many false identities to increase its influence. This paper proposes a routing protocol for a distributed hash table that is strongly resistant to the Sybil attack. This is the firs...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Published: |
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/46819 |
| _version_ | 1811095538203885568 |
|---|---|
| author | Lesniewski-Laas, Chris Kaashoek, M. Frans |
| author2 | Frans Kaashoek |
| author_facet | Frans Kaashoek Lesniewski-Laas, Chris Kaashoek, M. Frans |
| author_sort | Lesniewski-Laas, Chris |
| collection | MIT |
| description | Decentralized systems, such as distributed hash tables, are subject to the Sybil attack, in which an adversary creates many false identities to increase its influence. This paper proposes a routing protocol for a distributed hash table that is strongly resistant to the Sybil attack. This is the first solution to this problem with sublinear run time and space usage. The protocol uses the social connections between users to build routing tables that enable Sybil-resistant distributed hash table lookups. With a social network of N well-connected honest nodes, the protocol can tolerate up to O(N/log N) "attack edges" (social links from honest users to phony identities). This means that an adversary has to fool a large fraction of the honest users before any lookups will fail. The protocol builds routing tables that contain O(N log^(3/2) N) entries per node. Lookups take O(1) time. Simulation results, using social network graphs from LiveJournal, Flickr, and YouTube, confirm the analytical results. |
| first_indexed | 2024-09-23T16:19:07Z |
| id | mit-1721.1/46819 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:19:07Z |
| publishDate | 2009 |
| record_format | dspace |
| spelling | mit-1721.1/468192019-04-10T11:56:26Z Whanaungatanga: Sybil-proof routing with social networks Lesniewski-Laas, Chris Kaashoek, M. Frans Frans Kaashoek Parallel and Distributed Operating Systems dht security sybil overlay distributed hash table Decentralized systems, such as distributed hash tables, are subject to the Sybil attack, in which an adversary creates many false identities to increase its influence. This paper proposes a routing protocol for a distributed hash table that is strongly resistant to the Sybil attack. This is the first solution to this problem with sublinear run time and space usage. The protocol uses the social connections between users to build routing tables that enable Sybil-resistant distributed hash table lookups. With a social network of N well-connected honest nodes, the protocol can tolerate up to O(N/log N) "attack edges" (social links from honest users to phony identities). This means that an adversary has to fool a large fraction of the honest users before any lookups will fail. The protocol builds routing tables that contain O(N log^(3/2) N) entries per node. Lookups take O(1) time. Simulation results, using social network graphs from LiveJournal, Flickr, and YouTube, confirm the analytical results. 2009-09-28T21:00:08Z 2009-09-28T21:00:08Z 2009-09-24 http://hdl.handle.net/1721.1/46819 MIT-CSAIL-TR-2009-045 Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 Unported http://creativecommons.org/licenses/by-nc-nd/3.0/ 14 p. application/pdf application/postscript |
| spellingShingle | dht security sybil overlay distributed hash table Lesniewski-Laas, Chris Kaashoek, M. Frans Whanaungatanga: Sybil-proof routing with social networks |
| title | Whanaungatanga: Sybil-proof routing with social networks |
| title_full | Whanaungatanga: Sybil-proof routing with social networks |
| title_fullStr | Whanaungatanga: Sybil-proof routing with social networks |
| title_full_unstemmed | Whanaungatanga: Sybil-proof routing with social networks |
| title_short | Whanaungatanga: Sybil-proof routing with social networks |
| title_sort | whanaungatanga sybil proof routing with social networks |
| topic | dht security sybil overlay distributed hash table |
| url | http://hdl.handle.net/1721.1/46819 |
| work_keys_str_mv | AT lesniewskilaaschris whanaungatangasybilproofroutingwithsocialnetworks AT kaashoekmfrans whanaungatangasybilproofroutingwithsocialnetworks |