Whanau: A Sybil-Proof Distributed Hash Table
Whānau is a novel routing protocol for distributed hash tables (DHTs) that is efficient and strongly resistant to the Sybil attack. Whānau uses the social connections between users to build routing tables that enable Sybil-resistant lookups. The number of Sybils in the social network does not...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
USENIX Association
2011
|
| Online Access: | http://hdl.handle.net/1721.1/61338 https://orcid.org/0000-0001-7098-586X |
| _version_ | 1811094205500489728 |
|---|---|
| author | Kaashoek, M. Frans Lesniewski-Laas, Christopher Tur |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kaashoek, M. Frans Lesniewski-Laas, Christopher Tur |
| author_sort | Kaashoek, M. Frans |
| collection | MIT |
| description | Whānau is a novel routing protocol for distributed
hash tables (DHTs) that is efficient and strongly resistant
to the Sybil attack. Whānau uses the social connections
between users to build routing tables that enable
Sybil-resistant lookups. The number of Sybils in the social
network does not affect the protocol’s performance,
but links between honest users and Sybils do.When there
are n well-connected honest nodes, Whānau can tolerate
up to O(n/ log n) such “attack edges”. This means that
an adversary must convince a large fraction of the honest
users to make a social connection with the adversary’s
Sybils before any lookups will fail.
Whānau uses ideas from structured DHTs to build
routing tables that contain O([sqrt]n log n) entries per node.
It introduces the idea of layered identifiers to counter
clustering attacks, a class of Sybil attacks challenging for
previous DHTs to handle. Using the constructed tables,
lookups provably take constant time. Simulation results,
using social network graphs from LiveJournal, Flickr,
YouTube, and DBLP, confirm the analytic results. Experimental
results on PlanetLab confirm that the protocol
can handle modest churn. |
| first_indexed | 2024-09-23T15:56:30Z |
| format | Article |
| id | mit-1721.1/61338 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T15:56:30Z |
| publishDate | 2011 |
| publisher | USENIX Association |
| record_format | dspace |
| spelling | mit-1721.1/613382022-10-02T05:13:26Z Whanau: A Sybil-Proof Distributed Hash Table Kaashoek, M. Frans Lesniewski-Laas, Christopher Tur Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Kaashoek, M. Frans Kaashoek, M. Frans Lesniewski-Laas, Christopher Tur Whānau is a novel routing protocol for distributed hash tables (DHTs) that is efficient and strongly resistant to the Sybil attack. Whānau uses the social connections between users to build routing tables that enable Sybil-resistant lookups. The number of Sybils in the social network does not affect the protocol’s performance, but links between honest users and Sybils do.When there are n well-connected honest nodes, Whānau can tolerate up to O(n/ log n) such “attack edges”. This means that an adversary must convince a large fraction of the honest users to make a social connection with the adversary’s Sybils before any lookups will fail. Whānau uses ideas from structured DHTs to build routing tables that contain O([sqrt]n log n) entries per node. It introduces the idea of layered identifiers to counter clustering attacks, a class of Sybil attacks challenging for previous DHTs to handle. Using the constructed tables, lookups provably take constant time. Simulation results, using social network graphs from LiveJournal, Flickr, YouTube, and DBLP, confirm the analytic results. Experimental results on PlanetLab confirm that the protocol can handle modest churn. National Science Foundation (U.S.) (FIND program) Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory (T-Party Project) Quanta Computer (Firm) 2011-02-24T22:33:27Z 2011-02-24T22:33:27Z 2010-04 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/61338 Lesniewski-Laas, Christopher and M. Frans Kaashoek. "Whānau: A Sybil-proof Distributed Hash Table." 7th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2010, April 28-30, 2010, San Jose, Calif. https://orcid.org/0000-0001-7098-586X en_US http://www.usenix.org/events/nsdi10/index.html 7th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2010 Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf USENIX Association MIT web domain |
| spellingShingle | Kaashoek, M. Frans Lesniewski-Laas, Christopher Tur Whanau: A Sybil-Proof Distributed Hash Table |
| title | Whanau: A Sybil-Proof Distributed Hash Table |
| title_full | Whanau: A Sybil-Proof Distributed Hash Table |
| title_fullStr | Whanau: A Sybil-Proof Distributed Hash Table |
| title_full_unstemmed | Whanau: A Sybil-Proof Distributed Hash Table |
| title_short | Whanau: A Sybil-Proof Distributed Hash Table |
| title_sort | whanau a sybil proof distributed hash table |
| url | http://hdl.handle.net/1721.1/61338 https://orcid.org/0000-0001-7098-586X |
| work_keys_str_mv | AT kaashoekmfrans whanauasybilproofdistributedhashtable AT lesniewskilaaschristophertur whanauasybilproofdistributedhashtable |