Applying peer-to-peer (P2P) architecture to online video games has already attracted both academic and industrial interests, since it removes the need for expensive server maintenance. However, there are two major issues preventing the use of a P2P architecture, namely how to provide an effective distributed data storage solution, and how to tackle potential cheating behaviors. Inspired by emerging blockchain techniques, we propose a novel consensus model called Proof-of-Play (PoP) to provide a decentralized data storage system that incorporates an anti-cheating mechanism for P2P games, by rewarding players that interact with the game as intended, along with consideration of security measures to address the Nothing-at-stake Problem and the Long-range Attack. To validate our design, we utilize a game-theory model to show that under certain assumptions, the integrity of the PoP system would not be undermined due to the best interests of any user. Then, as a proof-of-concept, we developed a P2P game ( Infinity Battle ) to demonstrate how a game can be integrated with PoP in practice. Finally, experiments were conducted to study PoP in comparison with Proof-of-Work (PoW) to show its advantages in various aspects.