research-article

Recruiting new tor relays with BRAIDS

Authors:

Nicholas Hopper,

Yongdae KimAuthors Info & Claims

CCS '10: Proceedings of the 17th ACM conference on Computer and communications security

Pages 319 - 328

https://doi.org/10.1145/1866307.1866344

Published: 04 October 2010 Publication History

Abstract

Tor, a distributed Internet anonymizing system, relies on volunteers who run dedicated relays. Other than altruism, these volunteers have no incentive to run relays, causing a large disparity between the number of users and available relays. We introduce BRAIDS, a set of practical mechanisms that encourages users to run Tor relays, allowing them to earn credits redeemable for improved performance of both interactive and non-interactive Tor traffic. These performance incentives will allow Tor to support increasing resource demands with almost no loss in anonymity: BRAIDS is robust to well-known attacks. Using a simulation of 20,300 Tor nodes, we show that BRAIDS allows relays to achieve 75% lower latency than non-relays for interactive traffic, and 90% higher bandwidth utilization for non-interactive traffic.

References

[1]

]]M. Abe and T. Okamoto. Provably secure partially blind signatures. In CRYPTO '00: Proceedings of the 20th International Cryptology Conference on Advances in Cryptology, pages 271--286, 2000.

Digital Library

[2]

]]A. Acquisti, R. Dingledine, and P. Syverson. On the economics of anonymity. In Proceedings of the 7th International Conference on Financial Cryptography, 2003.

[3]

]]E. Androulaki, M. Raykova, S. Srivatsan, A. Stavrou, and S. M. Bellovin. PAR: Payment for anonymous routing. In PETS '08: Proceedings of the 8th International Symposium on Privacy Enhancing Technologies, pages 219--236, 2008.

Digital Library

[4]

]]The anonymizer. http://anonymizer.com/.

[5]

]]A. Back, U. Moller, and A. Stiglic. Traffic analysis attacks and trade-offs in anonymity providing systems. In IHW '01: Proceedings of the 4th International Workshop on Information Hiding, pages 245--257, 2001.

Digital Library

[6]

]]The BitTorrent Protocol Specification. http://www.bittorrent.org/beps/bep_0003.html. January 2010.

[7]

]]P. Boucher, A. Shostack, and I. Goldberg. Freedom system 2.0 architecture. White paper, Zero-Knowledge Systems Inc., 2000.

[8]

]]D. Chaum. Blind signatures for untraceable payments. In CRYPTO '82: Proceedings of Advances in Cryptology, volume 82, pages 199--203, 1983.

[9]

]]D. Chaum, A. Fiat, and M. Naor. Untraceable electronic cash. In CRYPTO '88: Proceedings of Advances in Cryptology, pages 319--327, 1990.

Digital Library

[10]

]]Y. Chen, R. Sion, and B. Carbunar. XPay: practical anonymous payments for Tor routing and other networked services. In WPES '09: Proceedings of the 8th ACM Workshop on Privacy in the Electronic Society, pages 41--50, 2009.

Digital Library

[11]

]]B. Cohen. Incentives build robustness in BitTorrent. In Workshop on Economics of P2P Systems, volume 6, 2003.

[12]

]]E. Damiani, D. C. di Vimercati, S. Paraboschi, P. Samarati, and F. Violante. A reputation-based approach for choosing reliable resources in peer-to-peer networks. In CCS '02: Proceedings of the 9th ACM Conference on Computer and Communications Security, pages 207--216, 2002.

Digital Library

[13]

]]C. Diaz, S. Seys, J. Claessens, and B. Preneel. Towards measuring anonymity. In Privacy Enhancing Technologies, 2002.

Digital Library

[14]

]]R. Dingledine, N. Mathewson, and P. Syverson. Tor: the second-generation onion router. In SSYM '04: Proceedings of the 13th conference on USENIX Security Symposium, pages 21--21, 2004.

Digital Library

[15]

]]J. R. Douceur. The sybil attack. In IPTPS '01: Revised Papers from the First International Workshop on Peer-to-Peer Systems, pages 251--260, 2002.

Digital Library

[16]

]]C. Dovrolis and P. Ramanathan. A case for relative differentiated services and the proportional differentiation model. IEEE network, 13(5):26--34, 1999.

Digital Library

[17]

]]C. Dovrolis and P. Ramanathann. Proportional differentiated services, part II: loss rate differentiation and packet dropping. In IWQOS '00: Eighth International Workshop on Quality of Service, pages 53--61, 2000.

[18]

]]C. Dovrolis, D. Stiliadis, and P. Ramanathan. Proportional differentiated services: delay differentiation and packet scheduling. In SIGCOMM '99: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, pages 109--120, 1999.

Digital Library

[19]

]]C. Dovrolis, D. Stiliadis, and P. Ramanathan. Proportional differentiated services: delay differentiation and packet scheduling. IEEE/ACM Transactions on Networking, 10(1):12--26, 2002.

Digital Library

[20]

]]N. Evans, R. Dingledine, and C. Grothoff. A practical congestion attack on Tor using long paths. In 18th USENIX Security Symposium, pages 33--50, 2009.

Digital Library

[21]

]]D. R. Figueiredo, J. K. Shapiro, and D. Towsley. Using payments to promote cooperation in anonymity protocols. Technical Report 03--31, University of Massachusetts, 2003.

[22]

]]E. Franz, A. Jerichow, and G. Wicke. A payment scheme for mixes providing anonymity. In TREC '98: Proceedings of the International IFIP/GI Conference on Trends in Distributed Systems for Electronic Commerce, pages 94--108, 1998.

Digital Library

[23]

]]The GMP Library. http://gmplib.org/.

[24]

]]D. Goldschlag, M. Reed, and P. Syverson. Onion routing. Communications of the ACM, 42(2):39--41, 1999.

Digital Library

[25]

]]P. Golle, K. Leyton-Brown, I. Mironov, and M. Lillibridge. Incentives for sharing in peer-to-peer networks. In WELCOM'01: Proceedings of the Second International Workshop on Electronic Commerce, pages 75--87, 2001.

Digital Library

[26]

]]G. Hardin. The tragedy of the commons. Science, 162(3859):1243--1248, December 1968.

[27]

]]F. Hernandez-Campos, K. Jeffay, and F. Smith. Tracking the evolution of web traffic: 1995--2003. In MASCOTS 2003: The 11th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer Telecommunications Systems, pages 16--25, 2003.

[28]

]]N. Hopper, E. Y. Vasserman, and E. Chan-Tin. How much anonymity does network latency leak? In CCS '07: Proceedings of the 14th ACM Conference on Computer and Communications Security, pages 82--91, 2007.

Digital Library

[29]

]]M. Jakobsson. Ripping coins for a fair exchange. In EUROCRYPT, pages 220--230, 1995.

Digital Library

[30]

]]S. D. Kamvar, M. T. Schlosser, and H. Garcia-Molina. The Eigentrust algorithm for reputation management in P2P networks. In WWW'03: Proceedings of the 12th International Conference on World Wide Web, pages 640--651, 2003.

Digital Library

[31]

]]K. Loesing. Measuring the Tor network: Evaluation of client requests to directories. Technical report, Tor Project, 2009.

[32]

]]D. Mccoy, K. Bauer, D. Grunwald, T. Kohno, and D. Sicker. Shining light in dark places: Understanding the Tor network. In PETS '08: Proceedings of the 8th International Symposium on Privacy Enhancing Technologies, pages 63--76, 2008.

Digital Library

[33]

]]J. McLachlan and N. Hopper. Don't clog the queue! Circuit clogging and mitigation in P2P anonymity schemes. In FC'08: The Proceedings of the 12th International Conference on Financial Cryptography and Data Security, pages 31--46, 2008.

Digital Library

[34]

]]J. McLachlan, A. Tran, N. Hopper, and Y. Kim. Scalable onion routing with Torsk. In CCS '09: Proceedings of the 16th ACM Conference on Computer and Communications Security, pages 590--599, 2009.

Digital Library

[35]

]]S. J. Murdoch and G. Danezis. Low-cost traffic analysis of Tor. In SP '05: Proceedings of the 2005 IEEE Symposium on Security and Privacy, pages 183--195, 2005.

Digital Library

[36]

]]A. Nandi, T.-W. J. Ngan, A. Singh, P. Druschel, and D. S. Wallach. Scrivener: providing incentives in cooperative content distribution systems. In Middleware'05: Proceedings of the ACM/IFIP/USENIX 2005 International Conference on Middleware, pages 270--291, 2005.

Digital Library

[37]

]]T. Narten and R. Draves. Privacy extensions for stateless address autoconfiguration in ipv6. http://tools.ietf.org/html//rfc3041, 2001.

Digital Library

[38]

]]T.-W. J. Ngan, R. Dingledine, and D. S. Wallach. Building incentives into Tor. In FC'10: The Proceedings of Financial Cryptography, 2010.

Digital Library

[39]

]]I. Osipkov, E. Y. Vasserman, N. Hopper, and Y. Kim. Combating double-spending using cooperative P2P systems. In ICDCS '07: Proceedings of the 27th International Conference on Distributed Computing Systems, page 41, 2007.

Digital Library

[40]

]]J. Reardon and I. Goldberg. Improving Tor using a TCP-over-DTLS tunnel. In Proceedings of the 18th USENIX Security Symposium, 2009.

Digital Library

[41]

]]M. Reiter, X. Wang, and M. Wright. Building reliable mix networks with fair exchange. In ACNS'05: The Proceedings of the Third International Conference on Applied Cryptography and Network Security, pages 378--392, 2005.

Digital Library

[42]

]]M. K. Reiter and A. D. Rubin. Crowds: Anonymity for web transactions. ACM Transactions on Information and System Security, 1(1):66--92, 1998.

Digital Library

[43]

]]R. L. Rivest and A. Shamir. PayWord and MicroMint: Two simple micropayment schemes. In Proceedings of the International Workshop on Security Protocols, pages 69--87, 1997.

Digital Library

[44]

]]A. Serjantov and G. Danezis. Towards an information theoretic metric for anonymity. In Privacy Enhancing Technologies, pages 41--53, 2002.

Digital Library

[45]

]]C. E. Shannon. A mathematical theory of communication. SIGMOBILE Mobile Computing and Communications Review, 5(1):3--55, 2001.

Digital Library

[46]

]]R. Snader and N. Borisov. A tune-up for Tor: Improving security and performance in the Tor network. In NDSS'08: Proceedings of the Network and Distributed Security Symposium, 2008.

[47]

]]C. Tang and I. Goldberg. An improved algorithm for Tor circuit scheduling. Technical Report CACR 2010-06, University of Waterloo, 2010.

Digital Library

[48]

]]Tor partially blocked in China. Tor Project. https://blog.torproject.org/blog/ tor-partially-blocked-china. October 2009.

[49]

]]Tor Directory Protocol, Version 3. Tor Project. http://gitweb.torproject.org/tor.git?a=blob_plain;hb=HEAD;f=doc/spec/dir-spec.txt. January 2010.

[50]

]]Relay Flags. Tor Project. http://git.torproject.org/checkout/metrics/master/out/dirarch/relayflags.csv. November 2009.

[51]

]]Computing Bandwidth Adjustments. Tor Project. http://gitweb.torproject.org/tor.git?a=blob_plain;hb=HEAD;f=doc/spec/proposals/161-computing-bandwidth-adjustments.txt. November 2009.

[52]

]]Tor Path Specification. Tor Project. http://gitweb.torproject.org/tor.git?a=blob_plain;hb=HEAD;f=doc/spec/path-spec.txt. January 2010.

[53]

]]The Tor Project. https://www.torproject.org/.

[54]

]]Y. Tsiounis. Efficient electronic cash: new notions and techniques. College of Computer Science, 1997.

[55]

]]E. Vasserman, R. Jansen, J. Tyra, N. Hopper, and Y. Kim. Membership-concealing overlay networks. In CCS'09: Proceedings of the 16th ACM Conference on Computer and Communications Security, pages 390--399, 2009.

Digital Library

[56]

]]C. Viecco. UDP-OR: A fair onion transport design. In HOTPETS'08: Proceedings of Hot Topics in Privacy Enhancing Technologies, 2008.

[57]

]]L. Xiong and L. Liu. PeerTrust: Supporting reputation-based trust for peer-to-peer electronic communities. IEEE Transactions on Knowledge and Data Engineering, 16:843--857, 2004.

Digital Library

[58]

]]R. Zhou and K. Hwang. PowerTrust: A robust and scalable reputation system for trusted peer-to-peer computing. IEEE Transactions on Parallel and Distributed Systems, 18(4):460--473, 2007.

Digital Library

Cited By

Dai XWu QLi BQin BFan JDeng FZhai M(2025)R2E: A Decentralized Scheme for Rewarding Tor Relays With CryptocurrenciesIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.339134522:1(164-178)Online publication date: Jan-2025
https://doi.org/10.1109/TDSC.2024.3391345
Tan RTan QWang HXie YZhang P(2024)P-I2Prange: An Automatic Construction Architecture for Scenarios in I2P Ranges2024 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN60899.2024.10651444(1-10)Online publication date: 30-Jun-2024
https://doi.org/10.1109/IJCNN60899.2024.10651444
Meng XLiang M(2024)Node Selection-Based Anonymous Network Performance Optimization Method2024 9th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS61882.2024.10602902(456-461)Online publication date: 19-Apr-2024
https://doi.org/10.1109/ICCCS61882.2024.10602902
Show More Cited By

Index Terms

Recruiting new tor relays with BRAIDS
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Scalable onion routing with torsk
CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

We introduce Torsk, a structured peer-to-peer low-latency anonymity protocol. Torsk is designed as an interoperable replacement for the relay selection and directory service of the popular Tor anonymity network, that decreases the bandwidth cost of ...
Safely Measuring Tor
CCS '16: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security

Tor is a popular network for anonymous communication. The usage and operation of Tor is not well-understood, however, because its privacy goals make common measurement approaches ineffective or risky. We present PrivCount, a system for measuring the Tor ...
Inferring Application Type Information from Tor Encrypted Traffic
CBD '14: Proceedings of the 2014 Second International Conference on Advanced Cloud and Big Data

Tor is a famous anonymity communication system for preserving users' online privacy. It supports TCP applications and packs application data into encrypted equal-sized cells to hide some private information of users, such as the running application type ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '10: Proceedings of the 17th ACM conference on Computer and communications security

October 2010

782 pages

ISBN:9781450302456

DOI:10.1145/1866307

General Chair:
Ehab Al-Shaer
University of North Carolina, Charlotte, USA
,
Program Chairs:
Angelos D. Keromytis
Columbia University, USA
,
Vitaly Shmatikov
University of Texas at Austin, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 October 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '10

Sponsor:

SIGSAC

CCS '10: 17th ACM Conference on Computer and Communications Security 2010

October 4 - 8, 2010

Illinois, Chicago, USA

Acceptance Rates

CCS '10 Paper Acceptance Rate 55 of 325 submissions, 17%;

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

38
Total Citations
View Citations
505
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dai XWu QLi BQin BFan JDeng FZhai M(2025)R2E: A Decentralized Scheme for Rewarding Tor Relays With CryptocurrenciesIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.339134522:1(164-178)Online publication date: Jan-2025
https://doi.org/10.1109/TDSC.2024.3391345
Tan RTan QWang HXie YZhang P(2024)P-I2Prange: An Automatic Construction Architecture for Scenarios in I2P Ranges2024 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN60899.2024.10651444(1-10)Online publication date: 30-Jun-2024
https://doi.org/10.1109/IJCNN60899.2024.10651444
Meng XLiang M(2024)Node Selection-Based Anonymous Network Performance Optimization Method2024 9th International Conference on Computer and Communication Systems (ICCCS)10.1109/ICCCS61882.2024.10602902(456-461)Online publication date: 19-Apr-2024
https://doi.org/10.1109/ICCCS61882.2024.10602902
Halpin H(2024)Simulation of Mixmining Reward Parameters for the Nym MixnetUbiquitous Security10.1007/978-981-97-1274-8_24(363-379)Online publication date: 13-Mar-2024
https://doi.org/10.1007/978-981-97-1274-8_24
Basyoni LErbad AMohamed AGuizani M(2022)QDRL: QoS-Aware Deep Reinforcement Learning Approach for Tor's Circuit SchedulingIEEE Transactions on Network Science and Engineering10.1109/TNSE.2022.31795699:5(3396-3410)Online publication date: 1-Sep-2022
https://doi.org/10.1109/TNSE.2022.3179569
Dopmann CFranck VTschorsch F(2021)Onion Pass: Token-Based Denial-of-Service Protection for Tor Onion Services2021 IFIP Networking Conference (IFIP Networking)10.23919/IFIPNetworking52078.2021.9472207(1-9)Online publication date: 21-Jun-2021
https://doi.org/10.23919/IFIPNetworking52078.2021.9472207
Zhang YXia Y(2021)A Dynamic Selection Algorithm of Tor Relay Based on Client Bias2021 22nd Asia-Pacific Network Operations and Management Symposium (APNOMS)10.23919/APNOMS52696.2021.9562506(41-44)Online publication date: 8-Sep-2021
https://doi.org/10.23919/APNOMS52696.2021.9562506
Jansen RJohnson A(2021)On the Accuracy of Tor Bandwidth EstimationPassive and Active Measurement10.1007/978-3-030-72582-2_28(481-498)Online publication date: 30-Mar-2021
https://doi.org/10.1007/978-3-030-72582-2_28
Dinh TRochet FPereira OWallach D(2020)Scaling Up Anonymous Communication with Efficient Nanopayment ChannelsProceedings on Privacy Enhancing Technologies10.2478/popets-2020-00482020:3(175-203)Online publication date: 17-Aug-2020
https://doi.org/10.2478/popets-2020-0048
de Vos MPouwelse J(2020)ConTribProceedings of the 1st International Workshop on Distributed Infrastructure for Common Good10.1145/3428662.3428789(13-18)Online publication date: 7-Dec-2020
https://dl.acm.org/doi/10.1145/3428662.3428789
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten