A matchmaking server exists just to set up two players and establish NAT punchthrough (if I ever don't want to host it anymore, I should release the spec and the matchmaking server source code)
Once players are connected, the clients must not be aware of hidden state for other players (hand, deck order, etc) or for themselves (deck order, etc)
Each player instead sends a hash of each card and its state to each opponent's client
e.g., player A hashes every card in their deck and sends all the information about the card order to their opponents by sending them the ordered hashes
player A has in their hand "bolt", "shock", "land"
player B's client sees "{hash1}", "{hash2}", "{hash3}"
when player A plays bolt player B receives the card's full information, including that it was in position 0 in the hand player B hashes the information and confirms that it matches "{hash1}" at position 0 in the hand
this ensures that player A's client didn't generate "bolt" when it was convenient, maliciously
in order for a rainbow table (hash -> card lookup) to impossible, cards must include a salt in the form of a randomly generated UUID (which should exist anyway to differentiate two copies of the same card in the same game from each other)
this allows for the game to be played from an initial state entirely trustlessly on a P2P connection without an authoritative server (I think)
The above algorithm allows Player A to know the order of all of their own cards (thanks for the feedback! you know who you are!).
To rectify this, one potential solution is the following algorithm:
- Player A generates their half of a PRNG seed (see below) and sends it to player B
- Player A hashes all cards in their deck and sends the (unordered) list to player B
- Player B generates their half of the seed and sends it to player A
- Player B shuffles player A's deck and stores the resulting order, but does not send that order to Player A
- When Player A needs to draw, they request the next card from Player B
In this way:
- Player A doesn't know the order of their own cards because the order is kept on Player B's client
- Player B doesn't know the order of Player A's cards because they don't know which hash is which card
- At the end of the game, all state from the game is shared and Player A can validate that the seed they were given at the beginning of the game from Player B is in fact the seed that was used to shuffle the deck (they replay the game using all the information and ensure that the replayed game matches what they saw during actual gameplay with limited information)
in order to get the initial state (e.g. shuffled initial state) and to ensure that RNG is not tampered with, the RNG for shuffling and things should be handled by every client, e.g. each client comes up with 1/nth of a random seed, and the number is then generated using the combined seed. Every client uses the same PRNG implementation and can check the completed seed and guarantee that
- their portion of the seed shows up in the expected portion of the completed seed
- the completed seed when placed into the shared PRNG implementation generates the results that the other client calculated (e.g., same deck order after shuffling)
this is vulnerable to an attack where player A receives player B's portion of the seed then maliciously generates the player A portion to generate the desired result. Could potentially mitigate this by alternating small portions of the seed, e.g., a 64-bit seed where player A generates the first bit, then player B generates the second, player A generates the 3rd, etc. This means that once the malicious player has n-1 bits, they only have two outcomes to choose from when generating the last bit, which isn't perfect, but does mitigate the effects to some degree. (e.g., when shuffling there ~60! possibilities, and selecting between 2 is not a massive advantage, but it is more problematic for a card that might randomly select targets and there are only ~2 legal targets).
Could potentially have a handshake for RNG generation where each client generates their portion of the seed, sends a hash to the other parties, then each client sends its actual original seed (and each other client validates that the given seed portion matches the hash given earlier) this would guarantee that each client generates their seed before they see the other clients' seeds. Just need to be sure each seed portion is large enough that it can't be rainbow table'd (64-bits should be enough)
seed generation can take place in parallel/asynchronously with the game, and store a queue of mutually validated seeds that are then consumed when RNG is needed, rather than performing the entropy/RNG generation as they are needed (prevents round-trip latency being introduced whenever PRNG is needed)