Two incentive designs for Tor

by arma | January 17, 2009

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.

Comments

Please note that the comment area below has been archived.

January 17, 2009

Permalink

Why not just go the I2P route and enable relays by default?

Sure, there are downsides to doing this, but are they really greater then having to create an entire complex incentive system like the one you discuss?

I constantly run Tor on my laptop because I like for it to be readily available to me, but I don't run as a relay because I move between several LANs on a daily basis, and I don't want to harm the network. It is my opinion that the goal should be to make it harmless for people to run relays on computers that aren't guaranteed to have high uptime, and then make that the default. It seems like this would be a much more elegant solution.

This is just my opinion, of course.

It already is harmless to run a relay that isn't up all the time. Tor will
automatically use it for cases that can handle unstable relays, and
won't use it for the cases that need stable relays.

For your more general question, see
https://www.torproject.org/faq#EverybodyARelay
and also Section 4.2 of
https://svn.torproject.org/svn/tor/trunk/doc/roadmaps/2008-12-19-roadma…

January 22, 2009

Permalink

Is there any option for a proxy to remain active for a certain period. Like if I want to remain connected to one proxy for 2 minutes or 5 minutes. Can it be set.
loking forward for the answer
Thanks

May 14, 2009

Permalink

You could consider the coins more like an advanced bit bucket, and give them a lifetime of say, 1 week, Being that, the longer you maintain gold start status the more coins you accrue, or have it related to amount of bandwidth transferred, but also allow some type of tag in router id so that you can have router "groups" this would allow for some interesting options, chiefly being, you could have people with tor processing "groups" to, as an rpg player would say "farm coins" where they will more likely setup a farm because coins have a short lifetime, instead of only contributing when they want high speeds. Setting up access control for this type of group could be tricky but it would also allow them to handle any coin \ cash exchange themselves to sell \ rent out their coins to others. Also you could have coins with a short lifespan and coins with a long lifespan, the latter being more so to add a "ranking" for their farm then for bandwidth, as nothing gets people working harder then competition.

June 14, 2009

Permalink

Hello,

The idea are interessant but will be not better to have : 1) become reward when give some bandwitch and GB to can be more speed , 2) with coins for peoples who have not the possibility to give enough speed .

I am impatient to can just a bit more speed, the problem are for me , when i use nx client for exemple, i need min 10 KB more to can run in remote...

For the moment i can't Torify it...

July 07, 2009

Permalink

People in countries that have more internet infrastructure would always win the gold status.

August 10, 2010

In reply to by Anonymous (not verified)

Permalink

is that a bad thing? some people will contribute more to the network. they will be rewarded more. everybody already has free access to tor. some people need better service. why not give them the option of getting better service by making the network better for everybody?

February 09, 2010

Permalink

Here's my idea:
-TorProject has a public key, and they RSA sign the current date/time; Anyone who has paid Torproject can *authenticate* (bear with me).. and obtain the latest key value.

-Due to this authentication, the value should be rounded, e.g. to the nearest hour, etc, so that many people will get the same key, and everyone is (fairly) anonymous.

-People who haven't paid Torproject can't get them directly, but can still sniff values *from the traffic they carry*, the more traffic you carry, the more likely you are to know a recent key.

-So having a recent key doesn't mean you have paid, you might have just sniffed it; but either way, a recent key proves you have been somehow helpful (i.e. if you sniffed it from traffic, then you carried traffic).

-Then, nodes can prioritize traffic based on the presence of a key, and on how recent the key is.

-Note that this still works even if you don't have any money involved, and you just have Torproject giving them out randomly to various nodes which are online.

-And, you can also include other organizations, e.g. some charity might also have a recognized key, and the charity gives out keys, too.

-It's along the lines of digital coins, except that everyone who sees a coin can copy it for themselves, and double spending is ENCOURAGED, but they eventually fade away to become worthless.

-also, by using the time, and RSA signing, it means anyone can verify them, without the need for a centralized server (except for the issuing, which can also be decentralized)

-To stop wide-spread replication (_post your latest value here_) maybe some kind of centralized revocation, etc might work, but it can also be decentralized: every time you see a particular key, it becomes less meaningful (i.e. if you see the 10pm key 100 times, but the 9pm key 3 times, then the 9pm actually becomes more prioritized even though it's older)

March 29, 2010

Permalink

My primary concern is being able to successfully and consistently hide my ip address and login information at various sites without the risk that an attacker will be able to steal my information for the purpose of identity theft or any other kind of theft.I bring this up because recently my banking information was stolen and my account cleaned out. I'm not exactly sure how it was done but I suspect spyware was used then it the gathered information to log into my account and perform an illegal transfer. I have since put a block on all transfers but it bothers me greatly that this person was able to steal my information so easily. I wasn't using TOR at the time because it was having trouble connecting to the network and perhaps this theft might not have happened if I had used TOR. What I want to see are faster connections , a debug feature and perhaps a compatability wizard to account for the various operating systems that are currently in use. The bottom line is that I want to be able to completely hide beyond all recognition my identity and any information that could potentially put me at risk for theft of any kind.

April 19, 2010

Permalink

Major moment which must not be lost from attention -- it is consequences for a physical person, which is an operator of tor exit node. There are precedents which logically cannot be explained ( http://news.cnet.com/8301-13739_3-9779225-46.html and linked article http://itnomad.wordpress.com/2007/09/16/tor-madness-reloaded/ ). But nevertheless they take place and some operators of tor exit nodes will ANSWER by the OWN HIDEs in similar histories. Which person in right mind will go for it, if he/she knows about possible consequences. There is such "phenomenon" as lawlessness of guys in blue uniform. It is not explainable from the point of view of logic and common sense.

While there is no protection from such events, when the operator of tor exit node remains one on one with lawlessness of official force, and he will not gain any help & use in that particular moment in life neither from transparent and honest relationships with the internet provider, nor from constitution or human rights, or other nonsense, there is no special sense to discuss expansion of tor network by means of commoners.

This is a REAL problem.

August 18, 2010

Permalink

Are any of you aware of the bitcoin project? www.bitcoin.org the idea is anonymous untraceable crypto-cash. So far it's in its infancy but worth thinking about for your digital coins.