Censorship Resistant Peer-to-Peer Content Addressable Networks
Amos Fiat, Jared Saia, Thomas Hobbes, Rene Descartes, Francis Bacon, Benedict Spinoza, John Milton, John Locke, David Hume, Jean-jacques Rousseau, Immanual Kant, Giovanni Casanova, Stuart Mill, Emile Zola, Jean-paul Sartre, Honore De Balzac, A. Dumas Pere, A. Dumas, Gustave Flaubert · 2001
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^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(ln n) memory in each node. We also give a variant of our scheme that has the property that it is highly spam resistent: 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.