incentives.txt 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341
  1. Tor Incentives Design Brainstorms
  2. 1. Goals: what do we want to achieve with an incentive scheme?
  3. 1.1. Encourage users to provide good relay service (throughput, latency).
  4. 1.2. Encourage users to allow traffic to exit the Tor network from
  5. their node.
  6. 2. Approaches to learning who should get priority.
  7. 2.1. "Hard" or quantitative reputation tracking.
  8. In this design, we track the number of bytes and throughput in and
  9. out of nodes we interact with. When a node asks to send or receive
  10. bytes, we provide service proportional to our current record of the
  11. node's value. One approach is to let each circuit be either a normal
  12. circuit or a premium circuit, and nodes can "spend" their value by
  13. sending and receiving bytes on premium circuits: see section 4.1 for
  14. details of this design. Another approach (section 4.2) would treat
  15. all traffic from the node with the same priority class, and so nodes
  16. that provide resources will get and provide better service on average.
  17. This approach could be complemented with an anonymous e-cash
  18. implementation to let people spend reputations gained from one context
  19. in another context.
  20. 2.2. "Soft" or qualitative reputation tracking.
  21. Rather than accounting for every byte (if I owe you a byte, I don't
  22. owe it anymore once you've spent it), instead I keep a general opinion
  23. about each server: my opinion increases when they do good work for me,
  24. and it decays with time, but it does not decrease as they send traffic.
  25. Therefore we reward servers who provide value to the system without
  26. nickle and diming them at each step. We also let them benefit from
  27. relaying traffic for others without having to "reserve" some of the
  28. payment for their own use. See section 4.3 for a possible design.
  29. 2.3. Centralized opinions from the reputation servers.
  30. The above approaches are complex and we don't have all the answers
  31. for them yet. A simpler approach is just to let some central set
  32. of trusted servers (say, the Tor directory servers) measure whether
  33. people are contributing to the network, and provide a signal about
  34. which servers should be rewarded. They can even do the measurements
  35. via Tor so servers can't easily perform only when they're being
  36. tested. See section 4.4.
  37. 2.4. Reputation servers that aggregate opinions.
  38. The option above has the directory servers doing all of the
  39. measurements. This doesn't scale. We can set it up so we have "deputy
  40. testers" -- trusted other nodes that do performance testing and report
  41. their results. If we want to be really adventurous, we could even
  42. accept claims from every Tor user and build a complex weighting /
  43. reputation system to decide which claims are "probably" right.
  44. 3. Related issues we need to keep in mind.
  45. 3.1. Relay and exit configuration needs to be easy and usable.
  46. Implicit in all of the above designs is the need to make it easy to
  47. run a Tor server out of the box. We need to make it stable on all
  48. common platforms (including XP), it needs to detect its available
  49. bandwidth and not overreach that, and it needs to help the operator
  50. through opening up ports on his firewall. Then we need a slick GUI
  51. that lets people click a button or two rather than editing text files.
  52. Once we've done all this, we'll hit our first big question: is
  53. most of the barrier to growth caused by the unusability of the current
  54. software? If so, are the rest of these incentive schemes superfluous?
  55. 3.2. The network effect: how many nodes will you interact with?
  56. One of the concerns with pairwise reputation systems is that as the
  57. network gets thousands of servers, the chance that you're going to
  58. interact with a given server decreases. So if 90% of interactions
  59. don't have any prior information, the "local" incentive schemes above
  60. are going to degrade. This doesn't mean they're pointless -- it just
  61. means we need to be aware that this is a limitation, and plan in the
  62. background for what step to take next. (It seems that e-cash solutions
  63. would scale better, though they have issues of their own.)
  64. 3.3. Guard nodes
  65. As of Tor 0.1.1.11, Tor users pick from a small set of semi-permanent
  66. "guard nodes" for their first hop of each circuit. This seems like it
  67. would have a big impact on pairwise reputation systems since you
  68. will only be cashing in on your reputation to a few people, and it is
  69. unlikely that a given pair of nodes will use each other as guard nodes.
  70. What does this imply? For one, it means that we don't care at all
  71. about the opinions of most of the servers out there -- we should
  72. focus on keeping our guard nodes happy with us.
  73. One conclusion from that is that our design needs to judge performance
  74. not just through direct interaction (beginning of the circuit) but
  75. also through indirect interaction (middle of the circuit). That way
  76. you can never be sure when your guards are measuring you.
  77. 3.4. Restricted topology: benefits and roadmap.
  78. As the Tor network continues to grow, we will need to make design
  79. changes to the network topology so that each node does not need
  80. to maintain connections to an unbounded number of other nodes. For
  81. anonymity's sake, we may partition the network such that all
  82. the nodes have the same belief about the divisions and each node is
  83. in only one partition. (The alternative is that every user fetches
  84. his own random subset of the overall node list -- this is bad because
  85. of intersection attacks.)
  86. Therefore the "network horizon" for each user will stay bounded,
  87. which helps against the above issues in 3.2 and 3.3.
  88. It could be that the core of long-lived servers will all get to know
  89. each other, and so the critical point that decides whether you get
  90. good service is whether the core likes you. Or perhaps it will turn
  91. out to work some other way.
  92. A special case here is the social network, where the network isn't
  93. partitioned randomly but instead based on some external properties.
  94. Social network topologies can provide incentives in other ways, because
  95. people may be more inclined to help out their friends, and more willing
  96. to relay traffic if most of the traffic they are relaying comes
  97. from their friends. It also opens the door for out-of-band incentive
  98. schemes because of the out-of-band links in the graph.
  99. 3.5. Profit-maximizing vs. Altruism.
  100. There are some interesting game theory questions here.
  101. First, in a volunteer culture, success is measured in public utility
  102. or in public esteem. If we add a reward mechanism, there's a risk that
  103. reward-maximizing behavior will surpass utility- or esteem-maximizing
  104. behavior.
  105. Specifically, if most of our servers right now are relaying traffic
  106. for the good of the community, we may actually *lose* those volunteers
  107. if we turn the act of relaying traffic into a selfish act.
  108. I am not too worried about this issue for now, since we're aiming
  109. for an incentive scheme so effective that it produces tens of
  110. thousands of new servers.
  111. 3.6. What part of the node's performance do you measure?
  112. We keep referring to having a node measure how well the other nodes
  113. receive bytes. But don't leeching clients receive bytes just as well
  114. as servers?
  115. Further, many transactions in Tor involve fetching lots of
  116. bytes and not sending very many. So it seems that we want to turn
  117. things around: we need to measure how quickly a node is _sending_
  118. us bytes, and then only send it bytes in proportion to that.
  119. However, a sneaky user could simply connect to a node and send some
  120. traffic through it, and voila, he has performed for the network. This
  121. is no good. The first fix is that we only count if you're receiving
  122. bytes "backwards" in the circuit. Now the sneaky user needs to
  123. construct a circuit such that his node appears later in the circuit,
  124. and then send some bytes back quickly.
  125. Maybe that complexity is sufficient to deter most lazy users. Or
  126. maybe it's an argument in favor of a more penny-counting reputation
  127. approach.
  128. 3.7. What is the appropriate resource balance for servers vs. clients?
  129. If we build a good incentive system, we'll still need to tune it
  130. to provide the right bandwidth allocation -- if we reserve too much
  131. bandwidth for fast servers, then we're wasting some potential, but
  132. if we reserve too little, then fewer people will opt to become servers.
  133. In fact, finding an optimum balance is especially hard because it's
  134. a moving target: the better our incentive mechanism (and the lower
  135. the barrier to setup), the more servers there will be. How do we find
  136. the right balance?
  137. One answer is that it doesn't have to be perfect: we can err on the
  138. side of providing extra resources to servers. Then we will achieve our
  139. desired goal -- when people complain about speed, we can tell them to
  140. run a server, and they will in fact get better performance.
  141. 3.8. Anonymity attack: fast connections probably come from good servers.
  142. If only fast servers can consistently get good performance in the
  143. network, they will stand out. "Oh, that connection probably came from
  144. one of the top ten servers in the network." Intersection attacks over
  145. time can improve the certainty of the attack.
  146. I'm not too worried about this. First, in periods of low activity,
  147. many different people might be getting good performance. This dirties
  148. the intersection attack. Second, with many of these schemes, we will
  149. still be uncertain whether the fast node originated the traffic, or
  150. was the entry node for some other lucky user -- and we already accept
  151. this level of attack in other cases such as the Murdoch-Danezis attack
  152. [http://freehaven.net/anonbib/#torta05].
  153. 3.9. How do we allocate bandwidth over the course of a second?
  154. This may be a simple matter of engineering, but it still needs to be
  155. addressed. Our current token bucket design refills each bucket once a
  156. second. If we have N tokens in our bucket, and we don't know ahead of
  157. time how many connections are going to want to send out how many bytes,
  158. how do we balance providing quick service to the traffic that is
  159. already here compared to providing service to potential high-importance
  160. future traffic?
  161. If we have only two classes of service, here is a simple design:
  162. At each point, when we are 1/t through the second, the total number
  163. of non-priority bytes we are willing to send out is N/t. Thus if N
  164. priority bytes are waiting at the beginning of the second, we drain
  165. our whole bucket then, and otherwise we provide some delayed service
  166. to the non-priority bytes.
  167. Does this design expand to cover the case of three priority classes?
  168. Ideally we'd give each remote server its own priority number. Or
  169. hopefully there's an easy design in the literature to point to --
  170. this is clearly not my field.
  171. Is our current flow control mechanism (each circuit and each stream
  172. start out with a certain window, and once they've exhausted it they
  173. need to receive an ack before they can send more) going to have
  174. problems with this new design now that we'll be queueing more bytes
  175. for less preferred nodes? If it turns out we do, the first fix is
  176. to have the windows start out at zero rather than start out full --
  177. it will slow down the startup phase but protect us better.
  178. While we have outgoing cells queued for a given server, we have the
  179. option of reordering them based on the priority of the previous hop.
  180. Is this going to turn out to be useful? If we're the exit node (that
  181. is, there is no previous hop) what priority do those cells get?
  182. Should we do this prioritizing just for sending out bytes (as I've
  183. described here) or would it help to do it also for receiving bytes?
  184. See next section.
  185. 3.10. Different-priority cells arriving on the same TCP connection.
  186. In some of the proposed designs, servers want to give specific circuits
  187. priority rather than having all circuits from them get the same class
  188. of service.
  189. Since Tor uses TCP's flow control for rate limiting, this constraints
  190. our design choices -- it is easy to give different TCP connections
  191. different priorities, but it is hard to give different cells on the
  192. same connection priority, because you have to read them to know what
  193. priority they're supposed to get.
  194. There are several possible solutions though. First is that we rely on
  195. the sender to reorder them so the highest priority cells (circuits) are
  196. more often first. Second is that if we open two TCP connections -- one
  197. for the high-priority cells, and one for the low-priority cells. (But
  198. this prevents us from changing the priority of a circuit because
  199. we would need to migrate it from one connection to the other.) A
  200. third approach is to remember which connections have recently sent
  201. us high-priority cells, and preferentially read from those connections.
  202. Hopefully we can get away with not solving this section at all.
  203. 4. Sample designs.
  204. 4.1. Two classes of service for circuits.
  205. 4.2. Treat all the traffic from the node with the same service;
  206. hard reputation system.
  207. 4.3. Treat all the traffic from the node with the same service;
  208. soft reputation system.
  209. Rather than a guaranteed system with accounting (as 4.1 and 4.2),
  210. we instead try for a best-effort system. All bytes are in the same
  211. class of service. You keep track of other Tors by key, and give them
  212. service proportional to the service they have given you. That is, in
  213. the past when you have tried to push bytes through them, you track the
  214. number of bytes and the average bandwidth, and use that to weight the
  215. priority of their connections if they try to push bytes through you.
  216. Now you're going to get minimum service if you don't ever push bytes
  217. for other people, and you get increasingly improved service the more
  218. active you are. We should have memories fade over time (we'll have
  219. to tune that, which could be quite hard).
  220. Pro: Sybil attacks are pointless because new identities get lowest
  221. priority.
  222. Pro: Smoothly handles periods of both low and high network load. Rather
  223. than keeping track of the ratio/difference between what he's done for
  224. you and what you've done for him, simply keep track of what he's done
  225. for you, and give him priority based on that.
  226. Based on 3.3 above, it seems we should reward all the nodes in our
  227. path, not just the first one -- otherwise the node can provide good
  228. service only to its guards. On the other hand, there might be a
  229. second-order effect where you want nodes to like you so that *when*
  230. your guards choose you for a circuit, they'll be able to get good
  231. performance. This tradeoff needs more simulation/analysis.
  232. This approach focuses on incenting people to relay traffic, but it
  233. doesn't do much for incenting them to allow exits. It may help in
  234. one way through: if there are few exits, then they will attract a
  235. lot of use, so lots of people will like them, so when they try to
  236. use the network they will find their first hop to be particularly
  237. pleasant. After that they're like the rest of the world though.
  238. Pro: this is a pretty easy design to add; and it can be phased in
  239. incrementally simply by having new nodes behave differently.
  240. 4.4. Centralized opinions from the reputation servers.
  241. Have a set of official measurers who spot-check servers from the
  242. directory to see if they really do offer roughly the bandwidth
  243. they advertise. Include these observations in the directory. (For
  244. simplicity, the directory servers could be the measurers.) Then Tor
  245. servers give priority to other servers. We'd like to weight the
  246. priority by advertised bandwidth to encourage people to donate more,
  247. but it seems hard to distinguish between a slow server and a busy
  248. server.
  249. The spot-checking can be done anonymously to prevent selectively
  250. performing only for the measurers, because hey, we have an anonymity
  251. network.
  252. We could also reward exit nodes by giving them better priority, but
  253. like above this only will affect their first hop. Another problem
  254. is that it's darn hard to spot-check whether a server allows exits
  255. to all the pieces of the Internet that it claims to. If necessary,
  256. perhaps this can be solved by a distributed reporting mechanism,
  257. where clients that can reach a site from one exit but not another
  258. anonymously submit that site to the measurers, who verify.
  259. A last problem is that since directory servers will be doing their
  260. tests directly (easy to detect) or indirectly (through other Tor
  261. servers), then we know that we can get away with poor performance for
  262. people that aren't listed in the directory. Maybe we can turn this
  263. around and call it a feature though -- another reason to get listed
  264. in the directory.
  265. 5. Recommendations and next steps.