Two incentive designs for Tor

One big challenge to making Tor fast is providing incentives for users to act as relays. So far we've been getting more relays by 1) building community through interacting more with relay operators, listing the fast ones prominently in the Tor status pages, and generally making it clear that you will make the Tor network better if you do, and 2) making it really easy to configure and run a relay by adding a simple GUI interface in Vidalia and adding UPnP support. But we should also consider more direct incentive approaches, for example where Tor is faster for you if you're a relay.

There are two papers that came out in 2008 that everybody pondering incentives in Tor should read. The first is "Building Incentives into Tor", a tech report I coauthored with Johnny Ngan and Dan Wallach from Rice University (update: now it's an FC 2010 paper). The second is "Payment for Anonymous Routing", published at PETS 2008 by Androulaki et al from Columbia University.

The first paper proposes that Tor's directory authorities should spot check relays to make sure they're behaving well, and assign "gold star" flags to the good ones in the networkstatus consensus. Then relays give priority service to connections from people who have gold stars. We ran simulations of the idea for various combinations of users and strategies (selfish, cooperative, adaptive, etc), and showed that in general the performance for gold-star users stays good even with many other users and a heavy traffic load on the network. The other main goal of the design uses an economic argument: not only does it provide the (explicit) incentive to run a relay, but it also aims to grow the overall capacity of the network, so even non-relays will benefit.

However, this incentive design has a serious flaw: the set of gold-star users is public. Over time an attacker can narrow down which relays are always the ones online when a certain activity (e.g. posting to a blog) happens. One fix might be to make the gold star status persist for a few weeks after the relay stops offering service, to dampen out fluctuations in the anonymity sets. But I fear that this narrowing-down attack (also known in research papers as the "intersection attack") is still going to work really well against users who only relay traffic around the times they want good performance.

It would seem that any incentives scheme that treats currently running relays specially will fall prey to this attack. We need to find some way to greatly increase the set of people who might be getting priority service. That's where the Columbia paper comes in: they propose that Tor clients use e-cash (digital coins) to pay for high-priority circuits. The bulk of the paper is in working out how to both a) make sure users can't cheat too often, and b) make sure relays can't use the payments to trace users. They use a hybrid digital cash design, where clients don't mind identifying themselves to the first hop, but then use anonymous digital cash when paying the later hops in the circuit. Most anonymous credential schemes involve way too much computational overhead, so having one that's more practical is a great step.

Because anybody can buy the digital coins, it's not so easy to build a set of suspects when you see somebody use a high-priority circuit. Of course, once real money gets involved, things get more complex. One big problem is the bank. Actually building a centralized place where people turn dollars into bits and back is a daunting exercise, and other projects have learned the lesson that it's hard to get right. Plus there are still unsolved anonymity questions -- if we see Alice use a credit card to buy some anonymous coins, and then a few minutes later some anonymous person spends some anonymous coins, what did we learn?

On top of that are the social implications of adding money into the system. Nick keeps reminding me of sociological studies saying that rewarding volunteers with t-shirts makes them feel good about their contribution, whereas rewarding them with a small amount of cash makes them subconsciously start to value their contribution based on the cash you give them. So they're more likely to stop volunteering, as they don't feel their effort is properly appreciated. More details here, here, and here. It's hard to say how right this research is, but it seems a rough set of variables to add in if we can avoid it.

Beyond that, paying relays introduces other problems. For one, relays now have new incentives to cheat, or to minimize their traffic costs compared to the payments. How do we achieve a good decentralized network if everybody gravitates to the same cheapest hosting provider? Money can even change the legal status of relays in some cases.

So how to proceed? My current idea is a combination of the two designs. The directory authorities give out digital coins in exchange for being a good relay, and the coins can be used to build high-priority circuits. The relays track the coins just enough to prevent too much double-spending (using a coin more than once), and then discard them. Now there is no bank, and no real money involved. It's just a resource management approach.

Will a secondary market appear, where people sell their coins on eBay? Perhaps. Fine with me if so. I think that's a different situation than having the protocol itself designed to transfer dollars from users to relays.

The single-use coins make me uncomfortable, because there's a lot of crypto infrastructure and performance questions in getting all those coins right. Worse, if we're really spending coins for every circuit, we will want to rethink our current "feel free to build a bunch of circuits and just use a few" approach that we're getting even more attached to with proposal 151. In my ideal world we could give out coins (credentials) that could be used as much as you like in a given time period, so we don't need the whole anonymous cash infrastructure. But if somebody posts their credential to Slashdot, I want some way either to revoke it and/or to notice and not give that guy any more credentials in the future, and that seems hard. So it looks like it'll be single-use coins or bust.

Of course, lest I appear too optimistic, there are a few more barriers to getting this right. We need to make sure Tor's network design can scale to make use of many more relays. We've been making some progress lately at decreasing the bandwidth required for directory downloads, but many other aspects of this problem still need to be solved. We also need a better way to actually implement priority circuits: our current approach sometimes accidentally gives high priority to other circuits too. Lastly, we might find that per-circuit accounting is not sufficient to handle the load that some users want to put on the network. If so, somebody will need to start doing design and research on per-byte accounting.