Making p2p accountable without losing privacy

ABSTRACT

Peer-to-peer systems have been proposed for a wide variety of applications, including file-sharing, web caching, distributed computation, cooperative backup, and onion routing. An important motivation for such systems is self-scaling. That is, increased participation increases the capacity of the system. Unfortunately, this property is at risk from selfish participants. The decentralized nature of peer-to-peer systems makes accounting difficult. We show that e-cash can be a practical solution to the desire for accountability in peer-to-peer systems while maintaining their ability to self-scale. No less important, e-cash is a natural fit for peer-to-peer systems that attempt to provide (or preserve) privacy for their participants. We show that e-cash can be used to provide accountability without compromising the existing privacy goals of a peer-to-peer system.

We show how e-cash can be practically applied to a file sharing application. Our approach includes a set of novel cryptographic protocols that mitigate the computational and communication costs of anonymous e-cash transactions, and system design choices that further reduce overhead and distribute load. We conclude that provably secure, anonymous, and scalable peer-to-peer systems are within reach.

REFERENCES

• 1: E. Adar and B. A. Huberman. Free riding on gnutella. First Monday, 5(10), 2000.
• 2: Kostas G. Anagnostakis , Michael B. Greenwald, Exchange-Based Incentive Mechanisms for Peer-to-Peer File Sharing, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.524-533, March 24-26, 2004
• 3: Nazareno Andrade , Miranda Mowbray , Aliandro Lima , Gustavo Wagner , Matei Ripeanu, Influences on cooperation in BitTorrent communities, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080198]
• 4: N. Asokan, V. Shoup, and M. Waidner. Optimistic fair exchange of digital signatures. IEEE Journal on Selected Areas in Communications, 18(4):591¿-610, Apr. 2000.
• 5: F. Bao, R. Deng, and W. Mao. Efficient and practical fair exchange protocols with off-line ttp. In IEEE Symposium on Security and Privacy, May 1998.
• 6: A. R. Bharambe, C. Herley, and V. N. Padmanabhan. Analyzing and improving a bittorrent network¿s performance mechanisms. In Proc. IEEE INFOCOM, Mar. 2006.
• 7: A. Blanc, Y.-K. Liu, and A. Vahdat. Designing incentives for peer-to-peer routing. In Proc. IEEE INFOCOM, Mar. 2005.
• 8: Jan Camenisch , Anna Lysyanskaya, Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.61-76, August 18-22, 2002
• 9: Jan Camenisch , Anna Lysyanskaya , Mira Meyerovich, Endorsed E-Cash, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.101-115, May 20-23, 2007 [doi>10.1109/SP.2007.15]
• 10: J. Camenisch and V. Shoup. Practical verifiable encryption and decryption of discrete logarithms. In CRYPTO 2003.
• 11: David L. Chaum, Untraceable electronic mail, return addresses, and digital pseudonyms, Communications of the ACM, v.24 n.2, p.84-90, Feb. 1981 [doi>10.1145/358549.358563]
• 12: D. Chaum. Blind signatures for untraceable payments. In Advances in Cryptology ¿ CRYPTO ¿82, pages 199¿-203. Plenum Press, 1983.
• 13: D. Chaum. Blind signature systems. In Advances in Cryptology ¿ CRYPTO ¿83, page 153. Plenum Press, 1984.
• 14: B. N. Chun , P. Buonadonna , A. AuYoung , Chaki Ng , D. C. Parkes , J. Shneidman , A. C. Snoeren , A. Vahdat, Mirage: a microeconomic resource allocation system for sensornet testbeds, Proceedings of the 2nd IEEE workshop on Embedded Networked Sensors, p.19-28, April 30-May 01, 2005
• 15: B. Cohen. Incentives build robustness in bittorrent. In Proc. 2nd IPTPS, Berkeley, CA, Feb. 2003.
• 16: Alan Daly , William Marnane, Efficient architectures for implementing montgomery modular multiplication and RSA modular exponentiation on reconfigurable logic, Proceedings of the 2002 ACM/SIGDA tenth international symposium on Field-programmable gate arrays, February 24-26, 2002, Monterey, California, USA [doi>10.1145/503048.503055]
• 17: R. Dingledine, N. Mathewson, and P. Syverson. Reputation in p2p anonymity systems. In P2PECON ¿03, June 2003.
• 18: Roger Dingledine , Nick Mathewson , Paul Syverson, Tor: the second-generation onion router, Proceedings of the 13th conference on USENIX Security Symposium, p.21-21, August 09-13, 2004, San Diego, CA
• 19: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 20: Bin Fan , Dah-ming Chiu , John Lui, The Delicate Tradeoffs in BitTorrent-like File Sharing Protocol Design, Proceedings of the Proceedings of the 2006 IEEE International Conference on Network Protocols, p.239-248, November 12-15, 2006 [doi>10.1109/ICNP.2006.320217]
• 21: E. Friedman and P. Resnick. The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 10(2):173-¿199, 2001.
• 22: Eric J. Friedman , Joseph Y. Halpern , Ian Kash, Efficiency and nash equilibria in a scrip system for P2P networks, Proceedings of the 7th ACM conference on Electronic commerce, p.140-149, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134723]
• 23: David Goldschlag , Michael Reed , Paul Syverson, Onion routing, Communications of the ACM, v.42 n.2, p.39-41, Feb. 1999 [doi>10.1145/293411.293443]
• 24: Philippe Golle , Kevin Leyton-Brown , Ilya Mironov , Mark Lillibridge, Incentives for Sharing in Peer-to-Peer Networks, Proceedings of the Second International Workshop on Electronic Commerce, p.75-87, November 16-17, 2001
• 25: GreedyTorrent. http://www.greedytorrent.com/.
• 26: J. Ioannidis, S. Ioannidis, A. D. Keromytis, and V. Prevelakis. Fileteller: Paying and getting paid for file storage. In Financial Cryptography, 6th International Conference, 2002.
• 27: David Irwin , Jeff Chase , Laura Grit , Aydan Yumerefendi, Self-recharging virtual currency, Proceedings of the 2005 ACM SIGCOMM workshop on Economics of peer-to-peer systems, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080192.1080194]
• 28: M. Jakobsson. Ripping coins for a fair exchange. In EUROCRYPT ¿95, 1995.
• 29: S. Jun and M. Ahamad. Incentives in bittorrent induce free riding. In P2PECON ¿05, Aug. 2005.
• 30: Eric J. Friedman , Joseph Y. Halpern , Ian Kash, Efficiency and nash equilibria in a scrip system for P2P networks, Proceedings of the 7th ACM conference on Electronic commerce, p.140-149, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134723]
• 31: Jon Kleinberg , Prabhakar Raghavan, Query Incentive Networks, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.132-141, October 23-25, 2005 [doi>10.1109/SFCS.2005.63]
• 32: Arnaud Legout , Nikitas Liogkas , Eddie Kohler , Lixia Zhang, Clustering and sharing incentives in BitTorrent systems, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 33: Harry C. Li , Allen Clement , Edmund L. Wong , Jeff Napper , Indrajit Roy , Lorenzo Alvisi , Michael Dahlin, BAR gossip, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 34: N. Liogkas, R. Nelson, E. Kohler, and L. Zhang. Exploiting bittorrent for fun (but not profit). In Proc. 5th IPTPS, 2006.
• 35: T. Locher, P. Moor, S. Schmid, and R. Wattenhofer. Free Riding in BitTorrent is Cheap. In Proc. 5th Workshop on Hot Topics in Networking (HotNets-V), Nov. 2006.
• 36: Sergio Marti , Hector Garcia-Molina, Identity Crisis: Anonymity vs. Reputation in P2P Systems, Proceedings of the 3rd International Conference on Peer-to-Peer Computing, p.134, September 01-03, 2003
• 37: Sergio Marti , Hector Garcia-Molina, Taxonomy of trust: categorizing P2P reputation systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.4, p.472-484, 15 March 2006 [doi>10.1016/j.comnet.2005.07.011]
• 38: Ralph C. Merkle, A Digital Signature Based on a Conventional Encryption Function, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.369-378, August 16-20, 1987
• 39: N. Michalakis, R. Soulé, and R. Grimm. Ensuring content integrity for untrusted peer-to-peer content distribution networks. In Proc. 4th USENIX/ACM NSDI, Apr. 2007.
• 40: A. Nandi, T.-W. J. Ngan, A. Singh, P. Druschel, and D. S. Wallach. Scrivener: Providing incentives in cooperative content distribution systems. In Middleware 2005, Nov. 2005.
• 41: Torben P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.129-140, August 11-15, 1991
• 42: M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy, and A. Venkataramani. Do incentives build robustness in bittorrent? In Proc. 4th USENIX/ACM NSDI, Apr. 2007.
• 43: M. Reiter, X. Want, and M. Wright. Building reliable mix networks with fair exchange. In Applied Cryptography and Network Security: Third International Conference, 2005.
• 44: Rosetta@Home. http://boinc.bakerlab.org/rosetta/.
• 45: Michael Stonebraker , Paul M. Aoki , Witold Litwin , Avi Pfeffer , Adam Sah , Jeff Sidell , Carl Staelin , Andrew Yu, Mariposa: a wide-area distributed database system, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.1, p.048-063, January 1996 [doi>10.1007/s007780050015]
• 46: R. Thommes and M. Coates. Bittorrent fairness: analysis and improvements. In WITSP ¿05, December 2005.
• 47: V. Vishnumurthy, S. Chandrakumar, and E. G. Sirer. Karma: A secure economic framework for p2p resource sharing. In P2PECON ¿03, 2003.
• 48: Michael Walfish , J. D. Zamfirescu , Hari Balakrishnan , David Karger , Scott Shenker, Distributed quota enforcement for spam control, Proceedings of the 3rd conference on Networked Systems Design & Implementation, p.21-21, May 08-10, 2006, San Jose, CA
• 49: Bryce Wilcox-O'Hearn, Experiences Deploying a Large-Scale Emergent Network, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.104-110, March 07-08, 2002
• 50: Bo Zhu , Sushil Jajodia , Mohan S. Kankanhalli, Building trust in peer-to-peer systems: a review, International Journal of Security and Networks, v.1 n.1/2, p.103-112, September 2006 [doi>10.1504/IJSN.2006.010827]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Data encryption standard (DES)**

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Economics, Security

Keywords:
anonymity, e-cash, incentives, peer-to-peer, privacy