Censorship resistant peer-to-peer content addressable networks

摘要

We present a censorship resistant peer-to-peer Content Addressable 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²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.