\documentclass{llncs} \usepackage{epsfig} \usepackage{graphicx} \usepackage{amsmath} \begin{document} %\title{Towards an Econymics ;-)} %\title{Open Issues in the Economics of Anonymity} %\title{Issues in the Economics of Anonymity} %\title{Topics in the Economics of Anonymity} %\title{The Economics of Anonymity} \title{On the Economics of Anonymity} \author{Alessandro Acquisti\inst{1} \and Roger Dingledine\inst{2} \and Paul Syverson\inst{3}} \institute{SIMS, UC Berkeley \email{(acquisti@sims.berkeley.edu)} \and The Free Haven Project \email{(arma@mit.edu)} \and Naval Research Lab \email{(syverson@itd.nrl.navy.mil)}} \maketitle \begin{abstract} Decentralized anonymity infrastructures are still not in wide use today. While there are technical barriers to a secure robust design, our lack of understanding of the incentives to participate in such systems remains a major roadblock. Here we explore some reasons why anonymity systems are particularly hard to deploy, enumerate the incentives to participate either as senders or also as nodes, and build a general model to describe the effects of these incentives. We then describe and justify some simplifying assumptions to make the model manageable, and compare optimal strategies for participants based on a variety of scenarios. \end{abstract} Keywords: anonymity, economics, incentives, decentralized, reputation %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} \label{sec:intro} Individuals and organizations need anonymity on the Internet. People want to surf the Web, purchase online, and send email without exposing to others their identities, interests, and activities. Corporate and military organizations must communicate with other organizations without revealing the existence of such communications to competitors and enemies. Firewalls, VPNs, and encryption cannot provide this protection; indeed, Diffie and Landau have noted that traffic analysis is the backbone of communications intelligence, not cryptanalysis \cite{diffiebook}. With so many potential users, it might seem that there is a ready market for anonymity services --- that is, it should be possible to offer such services and develop a paying customer base. However, with one notable exception (the Anonymizer \cite{anonymizer}) commercial offerings in this area have not met with sustained success. We could attribute these failures to market immaturity, and to the current economic climate in general. However, this is not the whole story. In this paper we explore the incentives of participants to offer and use anonymity services. We set a foundation for understanding and clarifying our speculations about the influences and interactions of these incentives. Ultimately we aim to learn how to align incentives to create an economically workable system for users and infrastructure operators. Section \ref{sec:overview} gives an overview of the ideas behind our model. Section \ref{sec:model} goes on to describe the variety of (often conflicting) incentives and to build a general model that incorporates many of them. In Section \ref{sec:application} we give some simplifying assumptions and draw conclusions about certain scenarios. Sections \ref{sec:alternate-incentives} and \ref{sec:roadblocks} describe some alternate approaches to incentives, and problems we encounter in designing and deploying strong anonymity systems. \section{The Economics of Anonymity} \label{sec:overview} %Anonymity can be studied from an economic perspective. The actual %protection of anonymity does not simply involve technical cleverness --- %it also requires understanding the incentives of heterogeneous parties %and solving the intricate web of their trade-offs. Single-hop web proxies like the Anonymizer protect end users from simple threats like profile-creating websites. On the other hand, users of such commercial proxies are forced to trust them to protect traffic information. Many users, particularly large organizations, are rightly hesitant to use an anonymity infrastructure they do not control. However, on an open network such as the Internet, running one's own system won't work: a system that carries traffic for only one organization will not hide the traffic entering and leaving that organization. Nodes must carry traffic from others to provide cover. %Yet those others don't want to trust their %traffic to a single entity either. The only viable solution is to distribute trust. That is, each party can choose to run a node in a shared infrastructure, if its incentives are large enough to support the associated costs. Users with more modest budgets or shorter-term interest in the system also benefit from this decentralized model, because they can be confident that a few colluding nodes are unlikely to uncover their anonymity. Today, however, few people or organizations are willing to run these nodes. In addition to the complexities of configuring current anonymity software, running a node costs a significant amount of bandwidth and processing power, most of which is used by `freeloading' users who do not themselves run nodes. Moreover, when administrators are faced with abuse complaints concerning illegal or antisocial use of their systems, the very anonymity that they're providing precludes the usual solution of suspending users or otherwise holding them accountable. Unlike confidentiality (encryption), anonymity cannot be created by the sender or receiver. Alice cannot decide by herself to send anonymous messages --- she must trust the infrastructure to provide protection, and others must use the same infrastructure. Anonymity systems use messages to hide messages: senders are consumers of anonymity and also providers of the cover traffic that creates anonymity for others. Thus users are better off on crowded systems because of the noise other users provide. Because high traffic is necessary for strong anonymity, agents must balance their incentives to find a common equilibrium, rather than each using a system of their own. The high traffic they create together also enables better performance: a system that processes only light traffic must delay messages to achieve adequately large anonymity sets. %Thus better performance attracts users both for its %convenience value and the better potential anonymity protection. But systems that process the most traffic do not necessarily provide the best hiding: if trust is not well distributed, a high volume system is vulnerable to insiders and attackers who target the trust bottlenecks. Anonymity systems face a surprisingly wide variety of direct anonymity-breaking attacks \cite{back01,raymond00}. Additionally, adversaries can also attack the efficiency or reliability of nodes, or try to increase the cost of running nodes. All of these factors combine to threaten the \emph{anonymity} of the system. As Back et al.\ point out, ``in anonymity systems usability, efficiency, reliability and cost become \emph{security} objectives because they affect the size of the user base which in turn affects the degree of anonymity it is possible to achieve.'' \cite{back01} We must balance all of these tradeoffs while we examine the incentives for users and node operators to participate in the system. \section{Analytic Framework} \label{sec:model} In this section and those that follow, we formalize the economic analysis of why people might choose to send messages through mix-nets.\footnote{Mixes were introduced by David Chaum (see \cite{chaum81}). A mix takes in a batch of messages, changes their appearance, and sends them out in a new order, thus obscuring the relation of incoming to outgoing messages.} We discuss the incentives for agents to participate either as senders or also as nodes, and we propose a general framework to analyze these incentives. In the next section we consider various applications of our framework, and then in Section \ref{sec:alternate-incentives} we examine alternate incentive mechanisms. We begin with two assumptions: the agents want to send messages to other parties, and the agents value their anonymity. How various agents might value their anonymity will be discussed below. An agent $i$ (where $i=(1,...,n)$ and $n$ is the number of potential participants in the mix-net) bases her strategy on the following possible actions $a_{i}$: \begin{enumerate} \item Act as a user of the system, specifically by sending (and receiving) her own traffic over the system, $a_{i}^s$, and/or agreeing to receive dummy traffic through the system, $a_{i}^r$. (\emph{Dummy traffic} is traffic whose only purpose is to obscure actual traffic patterns.) \item Act as an honest node, $a_{i}^{h}$, by receiving and forwarding traffic (and possibly acting as an exit node), keeping messages secret, and possibly creating dummy traffic. \item Act as a dishonest node, $a_{i}^{d}$, by pretending to forward traffic but not doing so, by pretending to create dummy traffic but not doing so (or sending dummy traffic easily recognizable as such), or by eavesdropping traffic to compromise the anonymity of the system. \item Send messages through conventional non-anonymous channels, $a_{i}^{n}$, or send no messages at all. \end{enumerate} Various benefits and costs are associated with each agent's action and the simultaneous actions of the other agents. The expected benefits include: \begin{enumerate} \item Expected benefits from sending messages anonymously. We model them as a function of the subjective value each agent $i$ places on the information successfully arriving at its destination, $v_{r_{i}}$; the subjective value of keeping her identity anonymous, $v_{a_{i}}$; the perceived level of anonymity in the system, $p_{a_{i}}$ (the subjective probability that the sender and message will remain anonymous); and the perceived level of reliability in the system, $p_{r_{i}}$ (the subjective probability that the message will be delivered). The subjective value of maintaining anonymity could be related to the profits the agent expects to make by keeping that information anonymous, or the losses the agents expects to avoid by keeping that information anonymous. We represent the level of anonymity in the system as a function of the traffic (number of agents sending messages in the system, $n_{s}$), the number of nodes (number of agents acting as honest nodes, $n_{h}$, and as dishonest nodes, $n_{d}$), and the decisions of the agent. We assume the existence of a function that maps these factors into a probability measure $p\in \left[0,1\right]$.\footnote{% Information theoretic anonymity metrics \cite{Diaz02,Serj02} probably provide better measures of anonymity: such work shows how the level of anonymity achieved by an agent in a mix-net system is associated to the particular structure of the system. But probabilities are more tractable in our analysis, as well as better than the common ``anonymity set'' representation.} In particular: \begin{itemize} \item The level of anonymity of the system is positively correlated to the number of users of the system. \item Acting as an honest node improves anonymity. Senders who do not run a node may accidentally choose a dishonest node as their first hop, significantly decreasing their anonymity (especially in low-latency anonymity systems where end-to-end timing attacks are very hard to prevent \cite{back01}). Further, agents who run a node can undetectably blend their message into their node's traffic, so an observer cannot know when the message is sent. \item The relation between the number of nodes and the probability of remaining anonymous might not be monotonic. For a given amount of traffic, sensitive agents might want fewer nodes in order to maintain large anonymity sets. But if some nodes are dishonest, users may prefer more honest nodes (to increase the chance that messages go through honest nodes). Agents that act as nodes may prefer fewer nodes, to maintain larger anonymity sets at their particular node. Hence the probability of remaining anonymous is inversely related to the number of nodes but positively related to the ratio of honest/dishonest nodes. (On the other hand, improving anonymity by reducing the number of nodes can be taken too far --- a system with only one node may be easier to monitor and attack. See Section \ref{sec:alternate-incentives} for more discussion.) \end{itemize} If we assume that honest nodes always deliver messages that go through them, the level of reliability in the system is then an inverse function of the share of dishonest nodes in the system, $n_{d}/n_{h}$. \item Benefits of acting as a node (nodes might be rewarded for forwarding traffic or for creating dummy traffic), $b_{h}$. \item Benefits of acting as a dishonest node (from disrupting service or by using the information that passes through them), $b_{d}$. \end{enumerate} The possible expected costs include: \begin{enumerate} \item Costs of sending messages through the anonymous system, $c_s$, or through a non-anonymous system, $c_n$. These costs can include both direct financial costs such as usage fees, as well as implicit costs such as the time to build and deliver messages, learning curve to get familiar with the system, and delays incurred when using the system. At first these delays through the anonymous system seem positively correlated to the traffic $n_{s}$ and negatively correlated to the number of nodes $n_{h}$. But counterintuitively, more messages per node might instead \emph{decrease} latency because nodes can process batches more often; see Section \ref{sec:alternate-incentives}. In addition, when message delivery is guaranteed, a node might always choose a longer route to reduce risk. We could assign a higher $c_{s}$ to longer routes to reflect the cost of additional delay. %In general, %the difference of $c_{s}$ and $c_{n}$ reflects the delay caused by using %the mix-net system. We also include here the cost of receiving dummy traffic, $c_r$. \item Costs of acting as an honest node, $c_{h}$, by receiving and forwarding traffic, creating dummy traffic, or being an exit node (which involves potential exposure to liability from abuses). These costs can be variable or fixed. The fixed costs, for example, are related to the investments necessary to setup the software. The variable costs are often more significant, and are dominated by the costs of traffic passing through the node. %Is this true that they are often more significant? -AA %Not necessarily. If it were just bandwidth I think we'd have more % nodes. I think a major part of the costs is dealing with abuse and % potential abuse. (To complicate things further, I think the actual % costs of dealing with abuse isn't so high for many people -- it's % the perceived cost, how much they expect they'll have to pay.) -RD \item Costs of acting as dishonest node, $c_{d}$ (again carrying traffic; and being exposed as a dishonest node may carry a monetary penalty). \end{enumerate} In addition to the above costs and benefits, there are also \emph{% reputation} costs and benefits from: being observed to send or receive anonymous messages, being perceived to act as a reliable node, and being thought to act as a dishonest node. Some of these reputation costs and benefits could be modelled endogenously (e.g., being perceived as an honest node brings that node more traffic, and therefore more possibilities to hide that node's messages; similarly, being perceived as a dishonest node might bring traffic away from that node). In this case, they would enter the payoff functions only indirectly through other parameters (such as the probability of remaining anonymous) and the changes they provoke in the behavior of the agents. In other cases, reputation costs and benefits might be valued \textit{per se}. While we do not consider either of these options in the simplified model below, Sections \ref{sec:alternate-incentives} and \ref{sec:roadblocks} discuss the impact of reputation on the model. We assume that agents want to maximize their expected payoff, which is a function of expected benefits minus expected costs. Let $S_{i}$ denote the set of strategies available to agent $i$, and $s_{i}$ a certain member of that set. Each strategy $s_{i}$ is based on the the actions $a_{i}$ discussed above. The combination of strategies $% (s_{1},...,s_{n})$, one for each agent who participates in the system, determines the outcome of a game as well as the associated payoff for each agent. Hence, for each complete strategy profile $s=(s_{1},...,s_{n})$ each agent receives the expected payoff $u_{i}\left(s\right)$ through the payoff function $u(.)$. We represent the payoff function for each agent $i$ in the following form: \begin{equation*} u_{i}=u\left( \begin{array}{c} \theta \left[ \gamma \left( v_{r_{i}},p_{r_{i}}\left( n_{h},n_{d},a_{h}^{s}\right) \right) ,\partial \left( v_{a_{i}},p_{a_{i}}\left( n_{s},n_{h},n_{d},a_{h}^{s}\right) \right) ,a_{i}^{s}\right] \, + \, b_{h}a_{i}^{h}+b_{d}a_{i}^{d}\\ - c_{s}\left( n_{s},n_{h}\right) a_{i}^{s}-c_{h}\left( n_{s},n_{h},n_{d}\right) a_{i}^{h}-c_{d}\left( ..\right) a_{i}^{d}-c_{r}\left( ..\right) a_{i}^{r}+(b_n-c_{n})a_{i}^{n} \end{array} \right) \end{equation*} \noindent where $\theta(.), \gamma(.)$, and $\partial(.)$ are unspecified functional forms. The payoff function $u(.)$ includes the costs and benefits for all the possible actions of the agents, including \textit{not} using the mix-net and instead sending the messages through a non-anonymous channel. We can represent the various strategies by using dummy variables for the various $a_{i}$.\footnote{% For example, if the agent chooses not to send the message anonymously, the probability of remaining anonymous $p_{a_{i}}$ will be equal to zero, $% a^{s,d,r,h}$ will be zero too, and the only cost in the function will be $% c_{n}$.} We note that the probabilities of a message being delivered and a message remaining anonymous are weighted with the values $v_{r_{i}},v_{a_{i}}$, respectively. This is because different agents might value anonymity and reliability differently, and because in different scenarios anonymity and reliability for the same agent might have different impacts on her payoff. In Section~\ref{sec:application}, we will make a number of assumptions that will allow us to simplify this equation and model certain scenarios. We present here for the reader's convenience a table summarizing those variables that will appear in both the complete and simplified equations, as well as one that describes the variables used only in the more complete equation above. \begin{center} \begin{tabular}{|c|cl|} \hline \multicolumn{3}{|c|}{Variables used in both full and simple payoff equations}\\ \hline \hline &$u_i$ & payoff for agent $i$ \\ \cline{2-3} &$v_{a_i}$ & disutility $i$ attaches to message exposure \\ \cline{2-3} &$p_a$ & simple case: $p_{a_i} = p_a$ for all $i$. See next table.\\ \hline number of nodes&$n_s$ & sending agents (sending nodes) \\ \cline{2-3} (other than $i$)&$n_h$ & honest nodes \\ \cline{2-3} in mix-net&$n_d$ & dishonest nodes\\ \hline dummy variables:&$a^h_i$ & $i$ is an honest node and sending agent \\ \cline{2-3} $1$ if true, $0$ otherwise&$a^s_i$ & $i$ sends through the mix-net \\ \hline &$c_h$ & of running an honest node\\ \cline{2-3} \raisebox{1.5ex}{costs}&$c_s$ & of sending a message through the mix-net \\ \hline \end{tabular} \end{center} \begin{center} \begin{tabular}{|c|cl|} \hline \multicolumn{3}{|c|}{Variables used only in full payoff equation} \\ \hline \hline &$v_{r_i}$ & value $i$ attaches to sent message being received \\ \cline{2-3} &$p_{a_i}$ & prob.\ for $i$ that a sent message loses anonymity \\ \cline{2-3} &$p_r$ & prob.\ that message sent through mix-net is received \\ \hline &$b_h$ & of running an honest node \\ \cline{2-3} benefits &$b_d$ & of running a dishonest node \\ \cline{2-3} &$b_n$ & of sending a message around the mix-net \\ \hline &$a^d_i$ & $i$ runs a dishonest node \\ \cline{2-3} dummy variables&$a^n_i$ & $i$ sends message around the mix-net \\ \cline{2-3} &$a^r_i$ & $i$ receives dummy traffic \\ \hline &$c_d$ & of running a dishonest node \\ \cline{2-3} costs & $c_r$ & of receiving dummy traffic \\ \cline{2-3} &$c_n$ & of sending a message around the mix-net\\ \hline \end{tabular} \end{center} %Paul, is the ``1'' right before ``$i$ receives dummy traffic'' correct? %Also - these tables are a great addition! I have changed the prob values in the full version, to show that we believe that the more accurate version would include sub. prob, but, given that we do not have enough info to model them that way, we keep ``normal'' probabilities in the simplified version. Should we update these two tables accordingly? Note also that the costs and benefits from sending the message could be distinct from the costs and benefits from keeping the \emph{information} anonymous. For example, when Alice anonymously purchases a book, she gains a profit equal to the difference between her valuation of the book and its price. But if her anonymity is compromised during the process, she could incur losses (or miss profits) completely independent from the price of the book or her valuation of it. The payoff function $u(.)$ above allows us to represent the duality implicit in all privacy issues, as well as the distinction between the value of sending a message and the value of keeping it anonymous: \begin{equation*} \begin{tabular}{|c|c|} \hline \textit{Anonymity} & \textit{Reliability} \\ \hline {\scriptsize \ \begin{tabular}{c} Benefit from remaining anonymous / \\ cost avoided by remaining anonymous, or \end{tabular} } & {\scriptsize \begin{tabular}{c} Benefit in sending message that will be received / \\ cost avoided by sending such a message, or \end{tabular} } \\ \hline {\scriptsize \ \begin{tabular}{c} Cost from losing anonymity / \\ \ profits missed because of loss of anonymity \end{tabular} } & {\scriptsize \begin{tabular}{c} Cost from a message not being received / \\ \ profits missed by message not being received \end{tabular} } \\ \hline \end{tabular} \end{equation*} Henceforth, we will consider the direct benefits or losses rather than their dual opportunity costs or avoided costs. Nevertheless, the above representation allows us to formalize the various possible combinations. For example, if a certain message is sent to gain some benefit, but anonymity must be protected in order to avoid losses, then $v_{r_{i}}$ will be positive while $v_{a_{i}}$ will be negative and $p_{a_{i}}$ will enter the payoff function as $\left( 1-p_{a_{i}}\right) $. On the other side, if the agent must send a certain message to avoid some losses but anonymity ensures her some benefits, then $v_{r_{i}}$ will be negative and $p_{r_{i}}$ will enter the payoff function as $\left( 1-p_{r_{i}}\right) $, while $v_{a_{i}}$ will be positive.% \footnote{ Being certain of staying anonymous would therefore eliminate the risk of $v_{a_{i}}$, while being certain of losing anonymity would impose on the agent the full cost $v_{a_{i}}$. Similarly, guaranteed delivery will eliminate the risk of losing $v_{r_{i}}$, while delivery failure will impose the full cost $v_{r_{i}}$.} With this framework we can compare, for example, the losses due to compromised anonymity to the costs of protecting it. An agent will decide to protect herself by spending a certain amount if the amount spent in defense plus the expected losses for losing anonymity after the investment are less than the expected losses from not sending the message at all. \section{Applying The Model} \label{sec:application} In this section we apply the above framework to simple scenarios. We make a number of assumptions to let us model the behavior of mix-net participants as players in a repeated-game, simultaneous-move game-theoretic framework. Thus we can analyze the economic justifications for the various choices of the participants, and compare design approaches to mix-net systems. Consider a set of $n_{s}$ agents interested in sending anonymous communications. Imagine that there is only one system which can be used to send anonymous messages, and one other system to send non-anonymous messages. Each agent has three options: only send her own messages through the mix-net; send her messages but also act as a node forwarding messages from other users; or don't use the system at all (by sending a message without anonymity, or by not sending the message). Thus initially we do not consider the strategy of choosing to be a bad node, or additional honest strategies like creating and receiving dummy traffic. We represent the game as a simultaneous-move, repeated game because of the large number of participants and because of the impact of earlier actions on future strategies. A large group will have no discernable or agreeable order for the actions of all participants, so actions can be considered simultaneous. The limited commitment produced by earlier actions allows us to consider a repeated-game scenario.\footnote{% In Section \ref{sec:model} we have highlighted that, for both nodes and simpler users, variable costs are more significant than fixed costs.} %Roger, is this the case or not? ie are traffic related costs the highest ones? -AA % I think variable costs are higher than fixed costs, but variable costs % are not solely due to bandwidth prices. see comment above -RD These two considerations suggest against using a sequential approach of the Stackelberg type \cite[Ch. 3]{fudenberg-tirole-91}. For similar reasons we also avoid a ``war of attrition/bargaining model'' framework (see for example \cite{rubinstein-82}) where the relative impatience of players plays an important role. \subsection{Adversary} Although strategic agents cannot choose to be bad nodes in this simplified scenario, we still assume there is a percentage of bad nodes and that agents respond to this possibility. Specifically we assume a global passive adversary (GPA) that can observe all traffic on all links (between users and nodes, between nodes, and between nodes or users and recipients). Additionally, we also study the case when the adversary includes some percentage of mix nodes. In choosing strategies agents will attach a subjective probability to arbitrary nodes being compromised --- all nodes not run by the agent are assigned the same probability of being compromised. This factor influences their assessment of the anonymity of messages they send. A purely passive adversary is unrealistic in most settings, e.g., it assumes that hostile users never selectively send messages at certain times or over certain routes, and nodes and links never selectively trickle or flood messages \cite{trickle02}. Nonetheless, a \emph{global} passive adversary is still quite strong, and thus a typical starting point of anonymity analyses. % FIXME say more \subsection{Honest Agents} If a user only sends messages, the cost of using the anonymous service is $c_{s}$. This cost might be higher than using the non-anonymous channel, $% c_{n}$, because of usage fees, usage hassles, or delays. To keep things simple, we assume that all messages pass through the mix-net in fixed-length free routes, so that we can write $c_{s}$ as a fixed value, the same for all agents. Users send messages at the same time, and only one message at a time. We also assume that routes are chosen randomly by users, so that traffic is uniformly distributed among the nodes.\footnote{% Reputation considerations might alter this point; see Section \ref{sec:alternate-incentives}.} If a user decides to be a node, her costs increase with the volume of traffic (we focus here on the traffic-based variable costs). We also assume that all agents know the number of agents using the system and which of them are acting as nodes. We also assume that all agents perceive the same level of anonymity in the system based on traffic and number of nodes, hence $p_{a_{i}}=p_{a}$ for all $i$. Finally, we imagine that agents use the system because they want to avoid potential losses from not being anonymous. This subjective sensitivity to anonymity is represented by $v_{a_{i}}$ (%see Section \ref{sec:model}; we can initially imagine $v_{a_{i}}$ as a continuous variable with a certain distribution across all agents; see below). In other words, we initially focus on the goal of remaining anonymous given an adversary that can control some nodes and observe all communications. Other than anonymity, we do not consider any potential benefit or cost, e.g., possible greater reliability, from sending around the mix-net. We later comment on the additional reliability issues. %These assumptions let us re-write the payoff function presented in %Section \ref{sec:model} in a simpler form: \begin{equation*} u_{i}=-v_{a_{i}}\left( 1-p_{a}\left( n_{s},n_{h},n_{d},a_{i}^{h}\right) \right) -c_{s}a_{i}^{s}-c_{h}\left( n_{s},n_{h},n_{d}\right) a_{i}^{h}-v_{a_i}a_i^n \end{equation*} Thus each agent $i$ tries to \textit{minimize} the costs of sending messages and the risk of being tracked. The first component is the probability that anonymity will be lost given the number of agents sending messages, the number of them acting as honest and dishonest nodes, and the action $a$ of agent $i$ itself. This chance is weighted by $v_{a_{i}}$, the disutility agent $i$ derives from its message being exposed. We also include the costs of sending a message through the mix-net, acting as a node when there are $n_{s}$ agents sending messages over $n_{h}$ and $n_{d}$ nodes, and sending messages through a non-anonymous system, respectively. Each period, a rational agent can compare the payoff coming from each of these three one-period strategies. \begin{equation*} \begin{tabular}{cc} Action & Payoff \\ $a_{s}$ & $-v_{a_{i}}\left( 1-p_{a}\left( n_{s},n_{h},n_{d}\right) \right) -c_{s} $ \\ $a_{h}$ & $-v_{a_{i}}\left( 1-p_{a}\left( n_{s},n_{h},n_{d},a_{i}^{h}\right) \right) -c_{s}-c_{h}\left( n_{s},n_{h},n_{d}\right) $ \\ $a_{n}$ & $-v_{a_{i}}$% \end{tabular} \end{equation*} We do not explicitly allow the agent to choose \textit{not} to send a message at all, which would of course minimize the risk of anonymity compromise. Also, we do not explicitly report the value of sending a successful message. Both are simplifications that do not alter the rest of the analysis. \footnote{We could insert an action $a^{0}$ with a certain disutility or cost from not sending any message, and then solve the problem of minimizing the expected losses. Or, we could insert in the payoff function for actions $% a^{s,h,n}$ also the payoff from successfully sending a message compared to not sending it (which could be interpreted also as an opportunity cost), and solve the dual problem of maximizing the expected payoff. Either way, the ``exit'' strategy for each agent will either be sending a message non-anonymously, or not sending it at all, depending on which option maximizes the expected benefits or minimizes the expected losses. Thereafter, we can simply compare the two other actions (being a user, or being also a node) to the optimal exit strategy.} While this model is simple, it allows us to highlight some of the dynamics that might take place in the decision process of agents willing to use a mix-net. We now consider various versions of this model. \subsubsection{Myopic Agents} Myopic agents do not consider the long-term consequences of their actions. They simply consider the status of the network and, depending on the payoffs of the one-period game, adopt a certain strategy. Suppose that a new agent with a privacy sensitivity $v_{a_{i}}$ is considering using a mix-net with (\emph{currently}) $n_{s}$ users and $n_{h}$ honest nodes. Then if \begin{equation*} \begin{tabular}{c} $-v_{a_{i}}\left( 1-p_{a}\left( n_{s}+1,n_{h}+1,n_{d},a_{i}^{h}% \right) \right) -c_{s}-c_{h}\left( n_{s}+1,n_{h}+1,n_{d}\right) $ \\ $<-v_{a_{i}}\left( 1-p_{a}\left( n_{s}+1,n_{h},n_{d}\right) \right) -c_{s},$ and \\ $-v_{a_{i}}\left( 1-p_{a}\left( n_{s}+1,n_{h}+1,n_{d},a_{i}^{h}% \right) \right) -c_{s}-c_{h}\left( n_{s}+1,n_{h}+1,n_{d}\right) $ \\ $<-v_{a_{i}}$% \end{tabular} \end{equation*} agent $i$ will choose to become a node in the mix-net. If \begin{equation*} \begin{tabular}{c} $-v_{a_{i}}\left( 1-p_{a}\left( n_{s}+1,n_{h}+1,n_{d},a_{i}^{h}% \right) \right) -c_{s}-c_{h}\left( n_{s}+1,n_{h}+1,n_{d}\right) $ \\ $>-v_{a_{i}}\left( 1-p_{a}\left( n_{s}+1,n_{h},n_{d}\right) \right) -c_{s},$ and \\ $-v_{a_{i}}\left( 1-p_{a}\left( n_{s}+1,n_{h},n_{d}\right) \right) -c_{s}<-v_{a_{i}}$% \end{tabular} \end{equation*} then agent $i$ will choose to be a user of the mix-net. Otherwise, $i$ will simply not use the mix-net. Our goal is to highlight the economic rationale implicit in the above inequalities. In the first case agent $i$ is comparing the benefits of the contribution to her own anonymity of acting as a node to the costs. Acting as a node dramatically increases anonymity, but it will also bring more traffic-related costs to the agent. Agents with high privacy sensitivity (high $v_{a_{i}}$) will be more likely to accept the trade-off and become nodes because they risk a lot by losing their anonymity, and because acting as nodes significantly increases their probabilities of remaining anonymous. On the other side, agents with a lower sensitivity to anonymity might decide that the costs or hassle of using the system are too high, and would not send the message (or would use non-anonymous channels). \subsubsection{Strategic Agents: Simple Case.} Strategic agents take into consideration the fact that their actions will trigger responses from the other agents. We start by considering only one-on-one interactions. First we present the case where each agent knows the other agent's type, but we then discuss what happens when there is uncertainty about the other agent's type. Suppose that each of agent $i$ and agent $j$ considers the other agent's reaction function in her decision process. Then we can summarize the payoff matrix in the following way:\footnote{We use parameters to succinctly represent the following expected payoffs: \begin{equation*} \begin{tabular}{c} $A_{w}=-v_{w}\left( 1-p_{a}\left( n_{s}+2,n_{h}+2,n_{d},a_{w}^{h}\right) \right) -c_{s}-c_{h}\left( n_{s}+2,n_{h}+2,n_{d}\right) $ \\ $B_{w}=-v_{w}\left( 1-p_{a}\left( n_{s}+2,n_{h}+1,n_{d}\right) \right) -c_{s}$ \\ $C_{w}=-v_{w}$ \\ $D_{w}=-v_{w}\left( 1-p_{a}\left( n_{s}+2,n_{h}+1,n_{d},a_{w}^{h}\right) \right) -c_{s}-c_{h}\left( n_{s}+2,n_{h}+1,n_{d}\right) $ \\ $E_{w}=-v_{w}\left( 1-p_{a}\left( n_{s}+1,n_{h}+1,n_{d},a_{w}^{h}\right) \right) -c_{s}-c_{h}\left( n_{s}+1,n_{h}+1,n_{d}\right) $ \\ $F_{w}=-v_{w}\left( 1-p_{a}\left( n_{s}+2,n_{h},n_{d}\right) \right) -c_{s}$ \\ $G_{w}=-v_{w}\left( 1-p_{a}\left( n_{s}+1,n_{h},n_{d}\right) \right) -c_{s}$% \end{tabular} \end{equation*} } \begin{equation*} \begin{tabular}{cccc} {\tiny Agent i / Agent j} & $a_{j}^{h}$ & $a_{j}^{s}$ & $a_{j}^{n}$ \\ $a_{i}^{h}$ & $A_{i},A_{j}$ & $D_{i},B_{j}$ & $E_{i},C_{j}$ \\ $a_{i}^{s}$ & $B_{i},D_{j}$ & $F_{i},F_{j}$ & $G_{i},C_{j}$ \\ $a_{i}^{n}$ & $C_{i},E_{j}$ & $C_{i},G_{j}$ & $C_{i},C_{j}$% \end{tabular} \end{equation*} As before, each agent has a trade-off between the cost of traffic and the benefit of traffic when being a node, and a trade-off between having more nodes and fewer nodes. In addition to the previous analysis, now the final outcome also depends on how much each agent knows about whether the other agent is honest, and how much she knows about the other agent's sensitivity to privacy. Of course, for an explicit solution we need a specific functional form for the probability function.\footnote{We have seen above, however, that privacy metrics like \cite{Diaz02,Serj02} do not directly translate into monotonic probability functions of the type traditionally used in game theory. Furthermore, the actual level of anonymity will depend on the mix-net protocol and topology (synchronous networks will provide larger anonymity sets than asynchronous networks for the same traffic divided among the nodes).} Nevertheless, even at this abstract level of description this framework can be mapped into the model analyzed in \cite{palfrey-rosenthal-89} where two players decide simultaneously whether to contribute to a public good. In our model, when for example $v_{a_{i}} \gg v_{a_{j}}$ and $v_{a_{i}}$ is large, the disutility to player $i$ from not using the system or not being a node will be so high that she will decide to be a node even if $j$ might free ride on her. Hence if $j$ values her anonymity, but not that much, the strategies $a_{i}^{h}$,$a_{j}^{s}$ can be an equilibrium of the repeated game. In fact, this model might have equilibria with free-riding even when the other agent's type is unknown. Imagine both agents know that the valuations $v_{a_{i}},v_{a_{j}}$ are drawn independently from a continuous, monotonic probability distribution. Again, when one agent cares about her privacy enough, and/or believes that there is a high probability that the opponent would act as a dishonest node, then the agent will be better off protecting her own interests by becoming a node (again see \cite{palfrey-rosenthal-89}). Of course the more interesting cases are those when these clear-cut scenarios do not arise, which we consider next. \subsubsection{Strategic Agents: Multi-player Case.} Each player now considers the strategic decisions of a vast number of other players. Fudenberg and Levine \cite{fudenberg88} propose a model where each player plays a large set of identical players, each of which is ``infinitesimal'', i.e. its actions cannot affect the payoff of the first player. We define the payoff of each player as the average of his payoffs against the distribution of strategies played by the continuum of the other players. In other words, for each agent, we will have: $u_{i}=\sum_{n_{s}}u_{i}\left( a_{i},a_{-i}\right) $ where the notation represents the comparison between one specific agent $i$ and all the others. Cooperative solutions with a finite horizon are often not sustainable when the actions of other agents are not observable because, by backward induction, each agent will have an incentive to deviate from the cooperative strategy. As compared to the analysis above with only two agents, now a defection of one agent might affect only infinitesimally the payoff of the other agents, so the agents might tend not to punish the defector. But then, more agents will tend to deviate and the cooperative equilibrium might collapse. ``Defection'', in fact, could be acting only as a user and refusing to be a node when the agent starts realizing that there is enough anonymity in the system and she no longer needs to be a node. But if too many agents act this way, the system might break down for lack of nodes, after which everybody would have to resort to non-anonymous channels. We can consider this to be a ``public good with free-riding'' type of problem \cite{cornes-sandler-86}. The novel point from a game-theoretic perspective is that the highly sensitive agents actually \emph{want} some level of free-riding, to provide noise. On the other side, they do not want too much free-riding --- for example from highly sensitive types pretending to be agents with low sensitivity --- if it involves high traffic costs. So, under which conditions will a system with many players not implode? First, a trigger strategy might be agreed upon among the many agents, so that the deviation of one single player might be met by the reaction of all the others (as described in \cite{fudenberg88}). Of course the only punishment available here is making the system unavailable, which has a cost for all agents. In addition, coordination costs might be prohibitive. This is not a viable strategy. Second, we must remember that highly sensitive agents, for a given amount of traffic, prefer to be nodes (because anonymity will increase) and prefer to work in systems with fewer nodes (else traffic gets too dispersed and the anonymity sets get too small). So, if $v_{a_{i}}$ is particularly high, i.e. if the cost of not having anonymity is very high for the most sensitive agents, then they will decide to act as nodes regardless of what the others do. Also, if there are enough agents with lower $v_{a_{i}}$, again a ``high'' type might have an interest in acting alone if its costs of not having anonymity would be too high compared to the costs of handling the traffic of the less sensitive types. In fact, when the valuations are continuously distributed, this \emph{might} generate equilibria where the agents with the highest valuations $v_{a_{i}}$ become nodes, and the others, starting with the ``marginal'' type (the agent indifferent between the benefits she would get from acting as node and the added costs of doing so) provide traffic.\footnote{Writing down specific equilibria, again, will first involve choosing appropriate anonymity metrics, which might be system-dependent.} This problem can be mapped to the solutions in \cite{bergstrom-blume--varian-86} or \cite{mackiemason-varian-95}. At that point an equilibrium level of free-riding might be reached. This condition can be also compared to \cite{grossman-stiglitz-80}, where the paradox of informationally efficient markets is described.\footnote{% The equilibrium in \cite{grossman-stiglitz-80} relies on the ``marginal'' agent who is indifferent between getting more information about the market and not getting it.} The problems start if we consider now a different situation. Rather than having a continuous distribution of valuations $v_{a_{i}}$, we consider two types of agents: the agent with a high valuation, $v_{a_{i}}=v_{H}$, and the agent with a low valuation, $v_{a_{i}}=v_{L}$. We assume that the $v_{L}$ agents will simply participate sending traffic if the system is cheap enough for them to use (but see Section \ref{sec:bootstrapping}), and we also assume this will not pose any problem to the $v_{H}$ type, which in fact has an interest in having more traffic. Thus we can focus on the interaction between a subset of users: the identical high-types. Here the ``marginal'' argument discussed above might not work, and coordination might be costly. In order to have a scenario where the system is self-sustaining and free, and the agents are of high and low types, the actions of the agents must be visible and the agents themselves must agree to react together to any deviation of a marginal player. In realistic scenarios, however, this will involve very high transaction/coordination costs, and will require an extreme (and possibly unlikely) level of rationality for the agents. This equilibrium will also tend to collapse when the benefits from being a node are not very high compared to the costs. Paradoxically, it also breaks down when an agent trusts another so much that she prefers to delegate away the task of being a node. The above considerations however also hint at other possible solutions to reduce coordination costs. We now consider some other mechanisms that can make these systems economically viable. \section{Alternate Incentive Mechanisms} \label{sec:alternate-incentives} As the self-organized system might collapse under some of the conditions examined above, we discuss now what economic incentives we can get from alternative mechanisms. \begin{enumerate} \item \emph{Usage fee}. If participants pay to use the system, the ``public good with free-riding'' problem turns into a ``clubs'' scenario. The pricing mechanism must be related to how much the participants expect to use the system or how sensitive they are. Sensitive agents might support the others by offering them limited services for free, because they need their traffic as noise. %(The revelation principle \cite{fudenberg-tirole-91} indicates %that the agent can concentrate on mechanisms where all the agents truthfully %reveal their sensitivities.) %\footnote{% %A ``mechanism'' is a game where agents send messages and a certain %allocation that depends on the realized messages (for a textbook %introduction, see \cite{fudenberg-tirole-91}). The mechanism is designed to %maximize the expected payoff --- for example of a ``principal'' agent. %According to the revelation principle the principal can concentrate on %mechanisms where all the agents truthfully reveal their types.}). The Anonymizer offers basic service at low costs to low-sensitivity agents (there is a cost in the delay, the limitation on destination addresses, and the hassle of using the free service), and offers better service for money. With usage fees, the cost of being a node is externalized. A hybrid solution involves distributed trusted nodes, supported through entry fees paid to a central authority and redistributed to the nodes. This was the approach of the Freedom Network from Zero-Knowledge Systems. The network was shut down because they were unable to sell enough clients to cover their costs. %\item \emph{Bilateral contracts}. Bilateral or multilateral contracts between %agents can lead them to agree on cooperation, and on penalties for breaching %cooperation. \item \emph{``Special'' agents}. Such agents have a payoff function that considers the social value of having an anonymous system or are otherwise paid or supported to provide such service. %The support might %also come in form of reputation, as discussed below, or in financial %form. If these agents are paid, the mechanism becomes similar to the hybrid solution discussed above, except anonymity-sensitive agents, rather than act as nodes, pass the money to a central authority. The central authority redistributes the funding among trusted entities acting as nodes. \item \emph{Public rankings and reputation}. A higher reputation not only attracts more cover traffic but is also a reward in itself. Just as the statistics pages for seti@home \cite{seti-stats} encourage participation, publicly ranking generosity creates an incentive to participate. Although the incentives of public recognition and public good don't fit in our model very well, we emphasize them because they explain most actual current node operators. As discussed above, reputation can enter the payoff function indirectly or directly (when agents value their reputation as a good itself). If we publish a list of nodes ordered by safety (based on number of messages passing through the node), the high-sensitivity agents will gravitate to safe nodes, causing more traffic and improving their safety further (and lowering the safety of other nodes). In our model the system will stabilize with one or a few mix nodes. In reality, though, $p_a$ is influenced not just by $n_h$ but also by jurisdictional diversity --- a given high-sensitivity sender is happier with a diverse set of mostly busy nodes than with a set of very busy nodes run in the same zone. Also, after some threshold of users, latency will begin to suffer, and the low sensitivity users will go elsewhere, taking away the nice anonymity sets. More generally, a low-latency node may attract many low-sensitivity agents, and thus counterintuitively provide \emph{better} anonymity than one that waits to batch many messages for greater security. %\item \emph{Micropayments for service}. Mojo Nation \cite{mojo} was %a peer-to-peer system for robustly distributing resources (e.g. file %sharing). It employed a digital cash system, called \emph{mojo}, to %help prevent abusive freeloading. Participants in the system paid mojo %to other participants in exchange for a service that uses resources. %In addition to the usual operations of `publish' and `retrieve', users %could also pay nodes to indirect traffic through them, both so they could %participate in the system from behind NATs and so they could gain some %measure of anonymity. Thus Mojo Nation reduced the potential for damage %from resource flooding attacks. Further, this credit and reputation %system allows the interactions to be streamlined based on trust built %up from past experience. % %While Mojo Nation's currency design was a fascinating idea for building a %stable economic ecosystem, the system ultimately fell apart due to more %mundane concerns such as usability and lack of funding. Even if it had %succeeded to the point of being able to offer anonymity services, though, %there would have been many more problems to face. We detail some of these in %the next section. \end{enumerate} \section{A Few More Roadblocks} \label{sec:roadblocks} \subsection{Authentication in a Volunteer Economy} Our discussions so far indicate that it may in fact be plausible to build a strong anonymity infrastructure from a wide-spread group of independent nodes that each want good anonymity for their own purposes. In fact, the more jurisdictionally diverse this group of nodes, the more robust the overall system. However, volunteers are problems: users don't know the node operators, and don't know whether they can trust them. We can structure system protocols to create better incentives for honest principals and to catch bad performance by others, e.g. by incorporating receipts and trusted witnesses \cite{mix-acc}, or using a self-regulating topology based on verifying reliability \cite{casc-rep}. But even when this is feasible, identifying individuals is a problem. Classic authentication considers whether it's the right entity, but not whether the authenticated parties are distinct from one another. One person may create and control several distinct online identities. This \emph{pseudospoofing} problem \cite{sybil} is a nightmare when an anonymity infrastructure is scaled to a large, diffuse, peer-to-peer design; it remains one of the main open problems in the design of any decentralized anonymity service. The Advogato trust metric \cite{advogato} and similar techniques rely on humans to make initial trust decisions, and then bound trust flow over a certification graph. However, so far none of these trust flow approaches have provided a clear solution to the problem. Another potential solution, a global PKI to ensure unique identities~\cite{gup}, is unlikely to emerge any time soon. \subsection{Dishonest Nodes vs.\ Lazy Nodes} We have primarily focused on the strategic motivations of honest agents, but the motivations of dishonest agents are at least as important. An anonymity-breaking adversary with an adequate budget would do best to provide very good service, possibly also attempting DoS against other high-quality providers. None of the usual metrics of performance and efficiency can identify dishonest nodes. Further, who calculates those metrics and how? If they depend on a centralized trusted authority, the advantages of diffusion are lost. Another approach to breaking anonymity is to simply attack the reliability or perceived reliability of the system --- this attack flushes users to a weaker system just as military strikes against underground cables force the enemy to communicate over less secure channels. On the other hand, when we consider strategic dishonest nodes we must also analyze their motivations as rational agents. A flat-out dishonest agent participates only to compromise anonymity or reliability. In doing so, however, a dishonest agent will have to consider the costs of reaching and maintaining a position from which those attacks are effective --- which will probably involve gaining reputation and acting as a node for an extended period of time, a cost if the goal is to generally break reliability. Such adversaries will be in an arms race with protocol developers to stay undetected despite their attacks \cite{casc-rep}. The benefits from successful attacks might be financial, as in the case of discovering and using sensitive information or a competitor's service being disrupted; or they could be purely related to personal satisfaction. The costs of being discovered as a dishonest node include rebuilding a new node's worth of reputation; but being noticed and exposed as the adversary may have very serious negative consequences for the attacker itself. (Imagine the public response if an Internet provider were found running dishonest nodes.) Thus, all things considered, it might be that the laws of economics work against the attacker as well. A ``lazy'' node, on the other hand, wants to protect her own anonymity, but keeps her costs lower by not forwarding or accepting all of her incoming traffic. By doing so this node decreases the reliability of the system. While this strategy might be sounder than the one of the flat-out dishonest node, it also exposes again the lazy node to the risk of being recognized as a disruptor of the system. In addition, this tactic, by altering the flow of the traffic through her own node, might actually reduce the anonymity of that agent. Surveys and analysis on actual attacks on actual systems (e.g., \cite {nymserver98}) can help determine which forms of attacks are frequent, how dangerous they are, and whether economic incentives or technical answers are the best countermeasures. \subsection{Bootstrapping The System And Perceived Costs} \label{sec:bootstrapping} Our models so far have considered the strategic choices of agents facing an already existing mix-net. We might even imagine that the system does not yet exist but that, before the first period of the repeated-game, all the players can somehow know each other and coordinate to start with one of the cooperative equilibria discussed above. But this does not sound like a realistic scenario. Hence we must discuss how a mix-net system with distributed trust can come to be. We face a paradox here: agents with high privacy sensitivity want lots of traffic in order to feel secure using the system. They need many participants with lower privacy sensitivities using the system first. The problem lies in the fact that there is no reason to believe the lower sensitivity types are more likely to be early adopters. In addition, their \textit{perceived} costs of using the system might be higher than the real costs\footnote{% Many individuals tend to be myopic in their attitude to privacy. They claim they want it but they are not willing to pay for it. While this might reflect a rational assessment of the trade-offs (that is, quite simply, the agents do not value their anonymity highly enough to justify the cost to protect it), it might also reflect ``myopic'' behavior such as the hyperbolic discounting of future costs associated to the loss of anonymity. See also \cite{acquisti-varian-02}.} --- especially when the system is new and not well known --- so in the strategic decision process they will decide against using the mix-net at all. Correct marketing seems critical to gaining critical mass in an anonymity system: in hindsight, perhaps Zero-Knowledge Systems would have gotten farther had it placed initial emphasis on usability rather than security. Note that here again reliability becomes an issue, since we must consider both the benefits from sending a message \textit{and }% keeping it anonymous. If the benefits of sending a message are not that high to begin with, then a low sensitivity agent will have fewer incentives to spend anything on the message's anonymity. We can also extend the analysis from our model that considers the costs and benefits of a single system to the comparison of different systems with different costs/benefit characteristics. We comment more on this in the conclusion. %Note in this case that the choice of agents with lower privacy sensitivity %between different anonymous systems with different levels of anonymity (and %monotonically associated costs) can be represented in our model as the %choice between being a node or only a user of the system. But anedoctal %evidence as well as surverys and experimental results have shown how even %those individuals who claim to care about their privacy are unwilling to pay %even small amounts to defend it - or, viceversa, are ready to trade it for %small rewards. %In light of the comments by jbash about comparing different systems, would you like to keep the previous comment in the text or not? % Difficulties in bootstrapping the system and the myopic behavior \cite{acquisti-varian-02} of some users might make the additional incentive mechanisms discussed in Section \ref{sec:alternate-incentives} preferable to a market-only solution. \subsection{Customization And Preferential Service Are Risky Too} Leaving security decisions up to the user is traditionally a way to transfer cost or liability from the vendor to the customer; but in strong anonymity systems it may be unavoidable. For example, the sender might choose how many nodes to use, whether to use mostly nodes run by her friends, whether to send in the morning or evening, etc. After all, only she knows the value of her anonymity. But this choice also threatens anonymity --- different usage patterns can help distinguish and track users. Limiting choice of system-wide security parameters can protect users by keeping the noise fairly uniform, but introduces inefficiencies; users that don't need as much protection may feel they're wasting resources. Yet we risk anonymity if we let users optimize their behavior. We can't even let users pay for better service or preferential treatment --- the hordes in the coach seats are more anonymous than the few in first class. This need to pigeonhole users into a few behavior classes conflicts with the fact that real-world users have a continuum of interests and approaches. Reducing options can lead to reduced usability, scaring away the users and leaving a useless anonymity system. % It remains to be seen whether designs and %incentives, for both system users and system components, can be structured %to meet all of these objectives sufficiently to create viable systems. \section{Future Work} There are a number of directions for future research: \begin{itemize} \item Dummy traffic. Dummy traffic increases costs but it also increases anonymity. In this extension we should study bilateral or multilateral contracts between agents, contractually forcing each agent to send to another agent(s) a certain number of messages in each period. With these contracts, if the sending agent does not have enough real messages going through its node, it will have to generate them as dummy traffic in order not to pay a penalty. \item Reliability. As noted above, we should add reliability issues to the model. \item Strategic dishonest nodes. As we discussed, it is probably more economically sound for an agent to be a lazy node than an anonymity-attacking node. Assuming that strategic bad nodes can exist, we should study the incentives to act honestly or dishonestly and the effect on reliability and anonymity. \item Unknown agent types. We should extend the above scenarios further to consider a probability distribution for an agent's guess about another agent's privacy sensitivity. \item Comparison between systems. We should compare mix-net systems to other systems, as well as use the above framework to compare the adoption of systems with different characteristics. \item Exit nodes. We should extend the above analysis to consider specific costs such as the potential costs associated with acting as an exit node. \item Reputation. Reputation can have a powerful impact on the framework above in that it changes the assumption that traffic will distribute uniformly across nodes. We should extend our analysis to study this more formally. \item Information theoretic metric. We should extend the analysis of information theoretic metrics in order to formalize the functional forms in the agent payoff function. \end{itemize} %It is clear that, given their limited tractability in closed-form terms, %some of the above extensions will need computational solutions. \section{Conclusions} We have described the foundations for an economic approach to the study of strong anonymity infrastructures. We focused on the incentives for participants to act as senders and nodes. Our model does not solve the problem of building a more successful system --- but it does provide some guidelines for how to think about solving that problem. Much research remains for a more realistic model, but we can already draw some conclusions: \begin{itemize} \item Systems must attract cover traffic (many low-sensitivity users) before they can attract the high-sensitivity users. Weak security parameters (e.g. smaller batches) may produce \emph{stronger} anonymity by bringing more users. But to attract this cover traffic, they may well have to address the fact that most users do not want (or do not realize they want) anonymity protection. %\item Reputation has a complex but critical influence on node %participation. We must investigate its role more thoroughly. \item High-sensitivity agents have incentive to run nodes, so they can be certain their first hop is honest. There can be an optimal level of free-riding: in some conditions these agents will opt to accept the cost of offering service to others in order to gain cover traffic. \item While there are economic reasons for distributed trust, the deployment of a completely decentralized system might involve coordination costs which make it unfeasible. A central coordination authority to redistribute payments may be more practical, but could provide a trust bottleneck for an adversary to exploit. \end{itemize} \section*{Acknowledgments} Work on this paper was supported by ONR.\@ Thanks to John Bashinski, Nick Mathewson, Adam Shostack, Hal Varian, and the anonymous referees for helpful comments. \bibliographystyle{plain} \bibliography{econymics} \end{document}