Volume 3 (2007) Article 1 pp. 1-23
Censorship Resistant Peer-to-Peer Networks
by
Published: January 21, 2007
[PDF (297K)]    [PS (603K)]    [PS.GZ (176K)]
[Source ZIP]
Keywords: peer-to-peer, content addressable network (CAN), distributed hash table (DHT), censorship, spam, fault-tolerant, butterfly network, routing, Byzantine, probabilistic method, expander graphs
ACM Classification: F.2.2
AMS Classification: 68W15

Abstract: [Plain Text Version]

We present a censorship resistant peer-to-peer network for accessing $n$ data items in a network of $n$ nodes. Each search for a data item in the network takes $O (\log n)$ time and requires at most $O (\log ^{2} n )$ messages. Our network is censorship resistant in the sense that even after adversarial removal of an arbitrarily large constant fraction of the nodes in the network, all but an arbitrarily small fraction of the remaining nodes can obtain all but an arbitrarily small fraction of the original data items. The network can be created in a fully distributed fashion. It requires only $O (\log n)$ memory in each node. We also give a variant of our scheme that has the property that it is highly spam resistant: an adversary can take over complete control of a constant fraction of the nodes in the network and yet will still be unable to generate spam.