Peer-to-peer hostless competitive games of chance?

Question

I'm wondering - have any games been ever created that are:

• peer-to-peer without one peer being designated as host
• competitive (not cooperative, players play against one another)
• provably fair (there is no possibility of any player cheating)
• Don't give any player more information than they need (for example, not revealing other players' secrets even to the running applications)

An example of such a game would be a poker game where each player and their games would only be able to know their own hand, but not the hands of other players without relying on any of them being the host of the game. I know there are a few games out there that are provably fair, but all that I know exist in a server-client configuration.

Answer 1

I don't know whether such games have been created, but they sure have been theorised. Several papers have been published on the topic. You may want to research commitment schemes which offer an explanation of how two disagreeing parties can flip a coin while being physically distant (see also this 1981 paper: Coin Flipping by Telephone).

One very thorough paper is for instance Cheat-Proof Peer-to-Peer Trading Card Games:

We propose a cheat-proof peer-to-peer protocol for implementing online trading card games. We break down actions common to all TCGs and explain how they can be executed between two players without the need for a third party referee (which usually requires an unbiased server). In each action, the player is either prevented from cheating or if they do cheat, the opponent will be able to prove they have done so. We conclude by showing how these methods are secure and how they may be intermixed for other styles of TCGs and other peer-to-peer games.

Also Cheat-Proof Playout for Centralized and Peer-to-Peer Gaming:

We propose a protocol that has provable anti-cheating guarantees, is provably safe and live, but suffers a performance penalty. We then develop an extended version of this protocol, called asynchronous synchronization, which avoids the penalty, is serverless, offers provable anti-cheating guarantees, is robust in the presence of packet loss, and provides for significantly increased communication performance. This technique is applicable to common game features as well as clustering and cell-based techniques for massively multiplayer games. Specifically, we provide a zero-knowledge proof protocol so that players are within a specific range of each other, and otherwise have no notion of their distance. Our performance claims are backed by analysis using a simulation based on real game traces.

Answer 2

Although not a game of chance, I'm developing an AIR game that is close to your requirements.

1. Developed using Flash's RTMFP multicast protocol. Neither client is considered host.
2. Physics based competitive system.
3. Verifies opponent input and disqualifies game on invalid data.
4. Does not transmit certain physics information for bandwidth/latency reasons (this disabled certain cheating methods as well).

However, please note...

I consider "no possibility of...cheating" a false statement. If you do not control all aspects (hardware & software) then cheating is possible.

Although not a game, I think the Bitcoin network is a prime example of what you are looking for.

Edit

I'm going to expand a little on your main question.

First, I can't see any game requiring "provably fair" conditions without some level of authoritative requirement. From leaderboards to micropayments, centralized systems and authority go together.

Second, the best example game I can think of is the early Pokemon games. Although the inner network logistics might not have been peer-to-peer, it follows the same principle.

Finally, the mobile platforms are especially fitted for peer-to-peer games. I consider this field to be very lacking, that is why I'm currently developing a line of peer-to-peer games.

Answer 3

A few pieces that might help, depending on use cases:

If you need to get simultaneous input from users without the possibility that one can use information to their advantage prematurely, you can use commitment scheme. Essentially this is:

1. Both player provide a hash of the action they wish to take.
2. After both have provided their commitment, both can provide their plaintext actions.
3. The plaintext can be compared with the hashes to verify that nobody changed their answer after learning the other person's action.

This can be used for a variety of things, including a shared random number (both provide an integer via commitments and xor them together after sharing to get the shared value.)

That is insufficient for a game like poker however, because it requires cards to be known to only one person, while continuing to be able to draw from the shared deck. Wikipedia has a fairly good algorithm for shared shuffling using a scheme where both players encrypt each card individually multiple times. This sets up a situation where 2 keys are required to decrypt any given card, and both players have 1. The article cites performance concerns, but I don't think AES or similar is prohibitively expensive at the scale required for 2 player poker.

If I were designing an algorithm I would have players calculate a random value at the beginning of the game to use as a seed for all of the rest of the operations and share a hash of that value. That way they can share that value after the game, and you can verify that they followed the protocol correctly, with no shenanigans.