Collectible Card Game Headquarters

Or, How I Learned To Stop Cheating And Love Cryptography

I had an idea today of how to implement network play in a way that:
a.) Does not require a central server
b.) Prevents 'active cheating' (altering things that should not be alterable)
c.) Prevents 'passive cheating' (peeking at things that should be hidden)
d.) For all players (no 'hosting player runs gdb' kind of holes)

The basic idea is to use cryptographic commitments in order to 'lock in' secret information, without revealing it. To explain, I will begin with a trivial design that only fulfills a.) and b.) and then extend it to fulfill c.) and d.)

A cryptographic commitment is a tool by which you can prove you knew something before you revealed it - i.e. 'commit' to it - similar to getting an envelope post-dated.

As an example, let's say I know "The combination for the safe is 4423". I don't want to reveal it right now, but I want people to believe me two weeks from now when I claim I had been sitting on this for two weeks. A trivial (read: do not use this for actual security) commitment scheme is simply a hash - like SHA256. So I take the hash H("The combination for the safe is 4423") = random_looking_value, and reveal that. Later, when I reveal "The combination for the safe is 4423", people can hash it and check against the hash I gave them in order to verify that I knew it back then. This works because finding two things with the same hash value is exceedingly difficult.

So, let's begin with a trivial network play system - each player runs a separate instance of Forge. When the game starts, they completely synchronize their state - the contents of each players' library, hand, etc. All information is known to all Forge instances. As play continues, each command ("play card 3 in player 1's hand") goes to both instances, and if something would desynchronize the state (such as shuffling) then the full data gets sent. Each player has a 'check for cheating' button, which when pressed makes the two instances compare their state. If there are differences, they start yelling. This satisfies b.)

However, since each instance has all the data, any player can just attach a debugger and pull out things like what cards the other is holding.

In order to resolve this, instead of synchronizing secret state (library, face-down cards, hand) each player instead sends a commitment of those things.

Specifically, the player sends an ordered list of per-card commitments - so the library would be an array that goes something like:
( commit('Forest'), commit('Llanowar Elves'), commit('Darksteel Citadel'), ... )

This is where the trivial commitment scheme I laid out before ('just hash it') fails: Because there are a limited number of cards to choose from, some would have the same hash (basic lands especially) and the other players could also brute-force it by hashing every possible card and comparing. This would reveal too much. The solution is to use a random nonce (number used once) for each, concatenated with the card. A 16-byte nonce is generally considered sufficient. Thus, it becomes
( commit( nonce1 + 'Forest' ), commit( nonce2 + 'Llanowar Elves' ), ... )
When a card ceases to be secret, then the player must reveal both the card and the nonce, and the other players verify it.

When a card becomes secret is slightly tricky though. In real-life play turning a Morph creature facedown again doesn't really make it any particular secret what it is - we've already seen it. Thus, it doesn't matter much that when the player generates a new commitment for it, we can still follow the 'secret' card around since the nonce stays the same.

But when a formerly-known card would be shuffled into the library, that becomes a big problem. Because of that, when randomizing any group of secret cards, all cards in the group must be assigned new nonces and re-commited - otherwise the randomization would not actually hide anything.

At the end of the game, all secret data must be revealed, and a final comparison run.

With this system in place, each Forge instance only has access to public information, its own secret information, and commitments over the other instances' secret information - this fulfills c.) and d.)

Thoughts?

EDITED TO ADD:
Comparing the state deserves more attention than I gave it. In order to do so securely, it's necessary to prevent the other players from just replaying your state back at you. In order to do so efficiently, you don't want to send the entire state over.

I'll define state-comparison in a pairwise manner:
1.) Players A and B each serialize their state into a canonical form (i.e. the same state always results in the same sequence of bits). This should probably serialize _all_ secret data as commitments, rather than the actual data (even for themselves).
2.) Each player commits that state, generating their own nonce.
2.) Each player sends the other the nonce and commitment from step 2
3.) Each player uses the other's nonce to commit their own state. If the received commitment and the new commitment match, the states match.

This only sends one hash and one nonce across the network, and prevents spoofing.

However, it does require hashing the state twice - if this is large, it may be a performance issue. To reduce this, each player could instead hash the state without a nonce as step 1.5, and commit to that hash instead. That allows each player to only hash the (potentially large) state once.

In order to do this for more than two players, simply repeat steps 2 and 3 for each pair. That is where the above optimization would really help, because otherwise the entire state would need to be hashed for each pairwise comparison. With the optimization, the intermediate nonce-less hash can be cached, reducing the computation needed significantly.

Hi! This is a very interesting subject, and it's great to read about it. I'm not an active Forge dev, so I can't say anything for forge. However, your descriptions are equally applicable to other games; if there is little response in this forum, maybe the Magic Rules Engine Programming forum is the right one. (I think when moving a thread, a reference to the topic stays in the original forum, right?)

I see one problem with your approach; there are three types of information in Magic: public, private and hidden. Public and private you handle correctly, but hidden poses a problem; none of the players can commit to hidden information, because that information is not visible to any player, am I right here? Do you have an idea how to resolve this without resorting to a separate trusted server?

Is there hidden information other than "Library-style", i.e. face-down unordered cards, where at least one player knows what cards are contained? If this is the only type, then a simplification would be to get rid of the notion of it being an unordered list and instead just saying that selecting one (the "top") card returns all cards with the same probability. This means that it's enough for the players to generate a random number together when it's time to draw a card, instead of keeping the order of cards secret from the owner after shuffling.

Possible complications are of course when cards are put on top or at the bottom of the library, and probably many more I didn't think of...

Multiverse uses something similar to this, but without any of the anti-hacking security features (ie anyone using a memory viewer can see what cards everybody has). It does so by making every player run their own (identical) private servers, which get synchronized after everyone has joined the game. After that, the only things players send each other is their input (for example, "Activate ability X or object Y"). It gets sent to each player (including yourself), whose private server handles the message.

The only thing the actual server does is make sure those messages get sent, and collect data. The master server hosts its own gamestate for debugging reasons, but it doesn't ever send it to the players after the game starts (it only sends the gamestate out when a player's deck is loaded, to make sure everyone's playing with the same "set" of cards).

It doesn't seem there is much interest forge-wise, can someone maybe move this thread to Magic Rules Engine Programming?

silly freak wrote:It doesn't seem there is much interest forge-wise, can someone maybe move this thread to Magic Rules Engine Programming?

I wouldn't say there isn't interest in applying something like this to Forge. It's mostly that Max, our main guy that's been preparing Forge for network support, has been oddly absent from the forums for several weeks. Hopefully this conversation could be picked back up for Forge's sake when he returns.

With that in mind, could you maybe just repost your OP in the Magic Rules Engine Programming section. That way this thread could still remain for discussing this idea as it pertains specifically to Forge's network play implementation.

Sure, will repost the OP. I did forget about the hidden state - and while the trivial solution is to have a third system, there are ways of doing it without that. They're more cryptographically-intensive, though, and require making some assumptions about hiddenness.

If it can be assumed that hidden state starts at a shuffle and something that was once public or private can never become hidden without a shuffle, there's a simple solution: https://en.wikipedia.org/wiki/Mental_po ... encryption

In fact, there's a C++ library that implements the appropriate cryptography - http://www.nongnu.org/libtmcg/

I'm not sure how feasible either rewriting that in Java or using JNI to make use of it would be, though.

EDITED TO ADD: Just found a paper where Jif (a JVM-based cryptography framework) was used to implement mental poker: http://www.cs.cornell.edu/~aslan/jifpoker/

Since they provide the code under the 3-clause BSD license, it can be used directly!

I'll update my original message with this when I cross-post it.

Out of curiosity, is there any particular thread that focuses specifically on the progress of network play development? That's a feature I'd like to keep my eye on. I think it's also worth saying that there are probably a good number of Forge users who would like network play but don't contribute actively to the forums or development (like myself).

As far as this topic goes - while I think anti-cheating and encryption methods are good for discussion, I believe it over-complicates the initial implementation of network play. I personally prioritize playing with my friends before keeping them from cheating. It shouldn't be too hard to implement a basic peer-to-peer connection over http, synchronize the initial state of the game mat, then send and receive updates only during play. After that, you can tunnel the connection inside HTTPS and encrypt (el-cheapo 32bit for performance) or obfuscate the contents of RAM to lock out 99% of hackers. And frankly, if they're enterprising enough to crack that, then they've earned the right to cheat and offend all of their friends

There is noone to develop multiplayer now.

I've lost interest in this project, don't know who else would be developing multiplayer