Probabilistic event resolution with the pairwise random protocol

ABSTRACT

Peer-to-peer distributed virtual environments (DVE's) distribute state tracking and state transitions. Many DVE's - such as online games - require ways to fairly determine the outcome of probabilistic events. While trivial when a trusted third party is involved, resolving these actions fairly between adversaries without a trusted third party is much more difficult. This paper proposes the Pairwise Random Protocol (PRP), which uses secure coin flipping to enable adversaries to fairly determine the result of a probabilistic event without a trusted third party. Three different variations of PRP are presented, and the time impact and network overhead are examined. We conclude that PRP enables DVE's to distribute the work of determining probabilistic events between adversaries without loss of security or fairness, and with acceptable overhead.

REFERENCES

• 1: IEEE standard for distributed interactive simulation - application protocols. IEEE Std 1278.1--1995 (1996), -.
• 2: Pagdin, Frances A. and Taylor, Ian C. Virtual Reality - a new therapeutic medium (2001). http://members.kabsi.at/t01/twa/article.html. Accessed 10-January-2008.
• 3: LINDEN RESEARCH, INC. Second Life: Official site of the 3D online virtual world. Second Life. http://secondlife.com/. Accessed 3-April-2009.
• 4: BLIZZARD ENTERTAINMENT. World of Warcraft Community Site (2009). http://www.worldofwarcraft.com. Accessed 3-April-2009.
• 5: BLIZZARD ENTERTAINMENT. World of Warcraft Surpasses 11 Million Subscribers Worldwide (October 2008). http://www.blizzard.com/us/press/081028.html. Accessed 3-April-2009.
• 6: Jeff Yan , Brian Randell, A systematic classification of cheating in online games, Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games, October 10-11, 2005, Hawthorne, NY [doi>10.1145/1103599.1103606]
• 7: Steven Daniel Webb , Sieteng Soh, Cheating in networked computer games: a review, Proceedings of the 2nd international conference on Digital interactive media in entertainment and arts, September 19-21, 2007, Perth, Australia [doi>10.1145/1306813.1306839]
• 8: George Yee , Larry Korba , Ronggong Song , Ying-Chieh Chen, Towards Designing Secure Online Games, Proceedings of the 20th International Conference on Advanced Information Networking and Applications, p.44-48, April 18-20, 2006 [doi>10.1109/AINA.2006.333]
• 9: Christian Mönch , Gisle Grimen , Roger Midtstraum, Protecting online games against cheating, Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, October 30-31, 2006, Singapore [doi>10.1145/1230040.1230087]
• 10: Pritchard, Matt. How to Hurt the Hackers: The Scoop on Internet Cheating and How You Can Combat It. Gamasutra (July 2000). http://www.gamasutra.com/features/20000724/pritchard_pfv.htm. Accessed 3-April-2009.
• 11: Nathaniel E. Baughman , Marc Liberatore , Brian Neil Levine, Cheat-proof playout for centralized and peer-to-peer gaming, IEEE/ACM Transactions on Networking (TON), v.15 n.1, p.1-13, February 2007 [doi>10.1109/TNET.2006.886289]
• 12: Chris GauthierDickey , Daniel Zappala , Virginia Lo , James Marr, Low latency and cheat-proof event ordering for peer-to-peer games, Proceedings of the 14th international workshop on Network and operating systems support for digital audio and video, June 16-18, 2004, Cork, Ireland [doi>10.1145/1005847.1005877]
• 13: Shunsuke Mogaki , Masaru Kamada , Tatsuhiro Yonekura , Shusuke Okamoto , Yasuhiro Ohtaki , Mamun Bin Ibne Reaz, Time-stamp service makes real-time gaming cheat-free, Proceedings of the 6th ACM SIGCOMM workshop on Network and system support for games, p.135-138, September 19-20, 2007, Melbourne, Australia [doi>10.1145/1326257.1326281]
• 14: Yeung Siu Fung, Hack-proof synchronization protocol for multi-player online games, Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games, p.47-es, October 30-31, 2006, Singapore [doi>10.1145/1230040.1230057]
• 15: Fabio Reis Cecin , Rodrigo Real , Rafael de Oliveira Jannone , Claudio Fernando Resin Geyer , Marcio Garcia Martins , Jorge Luis Victoria Barbosa, FreeMMG: A Scalable and Cheat-Resistant Distribution Model for Internet Games, Proceedings of the 8th IEEE International Symposium on Distributed Simulation and Real-Time Applications, p.83-90, October 21-23, 2004 [doi>10.1109/DS-RT.2004.21]
• 16: Lu Fan , Hamish Taylor , Phil Trinder, Mediator: a design framework for P2P MMOGs, Proceedings of the 6th ACM SIGCOMM workshop on Network and system support for games, p.43-48, September 19-20, 2007, Melbourne, Australia [doi>10.1145/1326257.1326265]
• 17: Patric Kabus , Wesley W. Terpstra , Mariano Cilia , Alejandro P. Buchmann, Addressing cheating in distributed MMOGs, Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games, October 10-11, 2005, Hawthorne, NY [doi>10.1145/1103599.1103607]
• 18: Knutsson, Björn, Lu, Honghui, Xu, Wei, and Hopkins, Bryan. Peer-to-Peer Support for Massively Multiplayer Games. In INFOCOM 2004: Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies (2004), IEEE.
• 19: Manuel Blum, Coin flipping by telephone a protocol for solving impossible problems, ACM SIGACT News, v.15 n.1, p.23-27, Winter-Spring 1983 [doi>10.1145/1008908.1008911]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Gaming

General Terms:
Algorithms, Security

Keywords:
bit commitment, cheating, distributed virtual environment, fairness, network games, pairwise random protocol, secure coin flipping, security