Sybilproof transitive trust protocols

ABSTRACT

We study protocols to enable one user (the principal) to make potentially profitable but risky interactions with another user (the agent), in the absence of direct trust between the two parties. In such situations, it is possible to enable the interaction indirectly through a chain of credit or "trust" links. We introduce a model that provides insight into many disparate applications, including open currency systems, network trust aggregation systems, and manipulation-resistant recommender systems. Each party maintains a trust account for each other party. When a principal's trust balance for an agent is high enough to cover potential losses from a bad interaction, direct trust is sufficient to enable the interaction. Allowing indirect trust opens up more interaction opportunities, but also expands the strategy space of an attacker seeking to exploit the community for its own ends. We show that with indirect trust exchange protocols, some friction is unavoidable: any protocol that satisfies a natural strategic safety property that we call sum-sybilproofness can sometimes lead to a reduction in expected overall trust balances even on interactions that are profitable in expectation. Thus, for long-term growth of trust accounts, which are assets enabling risky but valuable interactions, it may be necessary to limit the use of indirect trust. We present the hedged-transitive protocol and show that it achieves the optimal rate of expected growth in trust accounts, among all protocols satisfying the sum-sybilproofness condition.

REFERENCES

• 1: Alice Cheng , Eric Friedman, Sybilproof reputation mechanisms, 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.1080202]
• 2: 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
• 3: Epinions, 2009. http://www.epinions.com.
• 4: E. Friedman and P. Resnick. The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 10(2):173--199, 2001.
• 5: Jason D. Hartline , Tim Roughgarden, Optimal mechanism design and money burning, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374390]
• 6: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 7: N. Kiyotaki and R. Wright. On money as a medium of exchange. Journal of Political Economy, 97(4):927--954, 1989.
• 8: N. Kocherlakota. Money is memory. Technical report, Federal Reserve Bank of Minnesota, 1996.
• 9: R. Landa, D. Griffin, R. Clegg, E. Mykoniati, and M. Rio. A sybilproof indirect reciprocity mechanism for peer-to-peer networks. In Proceedings of IEEE Infocom '09, 2009.
• 10: R. Levien. Attack-Resistant Trust Metrics. PhD thesis, University of California, Berkeley, 2004.
• 11: D. Reeves. Blog article, 2006. Available at http://blog.yootles.com/2006/11/07/yootles-triviaquestion/.
• 12: Daniel M. Reeves , Bethany M. Soule , Tejaswi Kasturi, Yootopia!, ACM SIGecom Exchanges, v.6 n.2, p.1-26, January 2007 [doi>10.1145/1228621.1228623]
• 13: Paul Resnick , Rahul Sami, The influence limiter: provably manipulation-resistant recommender systems, Proceedings of the 2007 ACM conference on Recommender systems, October 19-20, 2007, Minneapolis, MN, USA [doi>10.1145/1297231.1297236]
• 14: Paul Resnick , Rahul Sami, The information cost of manipulation-resistance in recommender systems, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454033]
• 15: Ripplepay, 2009. http://www.ripplepay.com.
• 16: M. Yokoo, Y. Sakuri, and S. Matsubara. The effect of false-name bids in combinatorial auctions: New fraud in internet auctions. Games and Economic Behavior, 46:174--188, 2004.
• 17: Philip Zimmermann, Pretty good privacy: public key encryption for the masses, Building in big brother: the cryptographic policy debate, Springer-Verlag New York, Inc., New York, NY, 1995

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Economics, Theory

Keywords:
indirect reciprocity, open currency, recommender system, reputation system, sybilproof, transitive trust