Introduction

Anonymous publication and storage services allow individuals to speak freely without fear of persecution, yet such systems remain poorly understood. Political dissidents must publish in order to reach enough people for their criticisms of a regime to be effective, yet they and their readers require anonymity at the same time. Less extreme examples involve cases in which a large and powerful private organization, such as the Church of Scientology, attempts to silence its critics by attacking either the critics themselves or those who make the criticism publically available. Additionally, the recent controversy over Napster and Gnutella has highlighted both a widespread demand for anonymous publication services for non-political purposes, and the consequences of such services failing to provide the anonymity expected.

Systems meeting these needs are just starting to be deployed, and the exact requirements and design choices are not yet clear. Recent events have highlighted some shortcomings of already deployed systems; the identification and removal of Napster users who downloaded Metallica songs [25] and the Gnutella Wall of Shame [11] are two examples. These shortcomings are driving the development of a new generation of anonymous publication services, such as Freenet [10], which focus specifically on providing anonymity.

It is in this spirit that the Free Haven Project aims to design, implement, and deploy a functioning distributed anonymous storage service. We distinguish storage from publication in that storage services focus less on availability and more on persistence of data. In the process, we hope to clarify some of the requirements for such systems and highlight design choices. We recognize that such services raise significant moral and legal issues which are outside the scope of this paper; for our consideration of these issues, we refer to the first author's thesis [12].

Here we present a design for a system of anonymous storage and begin investigating the requirements for such a system. In particular, we recognize that a system must meet some standard of reliability and utility before it can be useful. Our design operates on a basic unit of data called a document. Our requirements for reliably processing these documents are covered in section 2.

We also show that it is not enough simply to talk about ``anonymous'' storage and publication. In section 3, we enumerate the many different kinds of anonymity which cover different aspects of the system, all important for the realization of a truly anonymous system.

Free Haven meets these requirements with a design based on a community of servers called the servnet. Each server, or servnet node, holds pieces of some documents; these pieces are called shares. In addition, each servnet node has a persistent identification or pseudonym which allows it to be identified by other servnet nodes or potential Free Haven users. Section 4 describes the design of the Free Haven system and the operations that it supports, including inserting and retrieving documents.

We chose to use a network of pseudonymous servers in order to give each server a reputation. This reputation allows servers to be ``paid'' without needing the robust digital cash scheme required for systems such as Anderson's Eternity Service [2]. Servers form ``contracts'' to store given shares for a certain period of time; successfully fulfilling the contract gains the server trust and the ability to store some of its own data on other servnet nodes. This gives an incentive for each server to behave well, as long as cheating servers can be identified, which we illustrate in section 4.9. The idea is similar to the ``give up space now, get space forever'' scheme used in Intermemory [9], but allows servers to lose trust if they start behaving badly. In section 4.11 we discuss the ``trust network,'' which is the system that keeps track of trust in each servnet node.

Some of these ``contracts'' are formed when a user inserts data into the servnet. Most of them, however, will be formed when two servers swap shares by trading. Trading allows the servnet to be dynamic in the sense that servnet nodes can join and leave easily and without special treatment. To join, a servnet node starts building up trust by storing shares for others. To leave, a node trades away all of its shares and then disappears. The benefits and mechanisms of trading are described in section 4.7.

Naturally, such a system has powerful adversaries which can launch a range of attacks. We describe some attacks on the Free Haven design in section 5 and show how well the design does (or does not) resist each attack. We then compare our design with other systems aimed at anonymous storage and publication using the kinds of anonymity described in section 7, allowing us to distinguish systems which at first glance look very similar. We conclude with a list of ``challenges'' for anonymous publication and storage systems, each of which reflects a limitation in the current Free Haven design.