In the context of the 2020 COVID-19 pandemic, I looked at tabletop games I'd otherwise have played offline.
Several games have working implementations, but little seems implemented satisfying my (admittedly strict) set of preferences, being:
The cheating is what I'll focus on here primarily: can we build games for online play with the same expectations of randomness and privacy as offline?
The games I'll look into here are:
The goal of this exercise is to ensure that the properties of a tabletop game are transferred to an online version: That shuffling permutes the order of cards drawn in such a way that no player can influence or predict the next card, and that putting tokens in a bag erases any information of who put in what.
Attempts at manipulation must (sooner or later, depending on the game) be visible to the other players.
Out of scope are: * Enforcing game rules. As with offline versions, it is up to the players to call out illegal moves by other players. Depending on whether a random event was triggered or data revealed in the move, it may or may not be possible to revert the move and keep playing. * Attacks on the software itself. Hereafter, it is assumed that players run software that runs under their control, acts in favor of their interest, reveals any information to the players, and can not be manipulated by data it receives from other players. * Ensuring the identity of other players. It is assumed that players heave means of communicating in private with any other player. Especially, no single player can be tricked into thinking that they play with a given group, while actualy playing with a group of men-in-the-middle that can collectively deanonymize the player's moves.
A Free Software implementation used by all players, which shows a checksum that can be compared on a public channel inhabited by all players, can realistically take care of the out-of-scope items.
All of this aims for the security level taken for granted for any state-of-the-art cryptographic mechanism.
At the same time, this is still games, and allows for some "roll your crypto" you should really not do with valuable data.
Shuffling cards is tricky in that it not only requires randomness no player must be able to influence, but also must ensure that the sequence of cards is not revealed to any player without everyone knowing it.
A proposed scheme goes like this:
If it is sufficient to know that someone attempted to cheat at the end of the game,
all participants reveal their remaining numbers when the stack is through,
and everyone can check that the sequence was the one committed to earlier.
Otherwise, the committed sequence needs to be constructed as H(n0 | H(n1 | H(n2 | ...)))
(for a hash function H and the concatenation operation |),
and parties publish the hash of the remaining sequence along with any number
and thus allow immediate verification.
For combined shufflings (like Pandemic's "shuffle, then split up in equal stacks, then shuffle a single card into each stack" or "given an already shuffled deck, shuffle an open pile, and place it on the shuffled deck"), all shufflings are done independently. When a subset of shuffled cards is taken blindly, no card is drawn in the above sense. Instead, the new shuffling contains "pointers" to the yet-unrevealed cards of the original stack, so when a "take ten cards of stack A and shuffle in an 'Outbreak' card" step is executed, the cards in the new stack are "Outbreak", "first card of A", "second card of A" etc., and revealing one of them means first picking a number nb with 0 <= nb < 11 where nb = 0 means picking the outbreak, and any other nb means drawing the nb - 1th card from stack A in a second step.
If real-time cheating checks are desired, such shufflings can be achieved either by building a more elaborate merkle tree of random numbers, or by just taking the first card of a nested stack anyway. The stack is shuffled anyway, so as long as all parties agree on a sequence of events, it doesn't change a thing.
Drawing card hidden is trickier: It works as long as only one card is ever hidden, but by the time a next card is drawn, the previously drawn cards need to be known.
General methods for the multiparty generation of a secret permutation will need to be used, I couldn't come up with a shortcut.
(A reasonably secure shortcuts might be one party encrypting the set of $n$ cards with $n$ random keys and puts key labels to it, another party mixing them up, sending them to all players, each player generates an asymmetric key pair and asks through the mixing player for the key to decrypt their labelled key, which is encrypted to their ephemeral public key. That would work for full permutations, but is unusable in Blood Bound, where cards remain unused: the encrypting player would see which cards are left out.)
The approach of Studholme and Blake could provide a suitable permutation.
It is not sure whether cards can be "left over" in that scheme:
Is there a value x that player 1 can use to pad the players' public keys to the number of cards, like [(g^u1, g), ..., (g^un, g), (x, g), ..., (x, g)]? (Possibly, x = ∏ g^ui, but the security of that would still need to be shown).
Expressing a shuffling like in Blood Bound (shuffle two decks independently, pick equally many cards from each pile to reach the number of players, shuffle those together and deal) can be expressed with the padded approach: One shuffling over the number of players is taken first; they determine their team based on which half of the output they are in. Then, two more shufflings are had (one for each team), in which all players participate, but where they only evaluate their position in their own team. To avoid that they get a peek at an unused card from the opposite team, they are required to input a broken public key into the opposing team's construction. At the end of the game, they must prove that they provided a broken public key by showing that they have a private key to match the public key they sent plus/minus an agreed-on offset.
(Someone with too much time on their hands might consider developing an algorithm whose input are shuffling instructions a la "shuffle stack X, take top 3, shuffle them into stack Y, deal stack Y" and whose output are algorithm steps. In general, this might also require a Dining Cryptographers implementation.)
Privacy requires more than card drawing: it requires secure multi-party computation.
Several approaches exist there. The one presented here was made up without much of the context of those, and aims to be easily understandable by players. Its security has not been shown, and I'd appreciate feedback on it.
This calculates the sum of input numbers contributed by each player, without any player being able to determine the inputs of any other player, except if all other players conspire and reveal their own numbers. (Especially, the numbers can be zero or one for the traditional yes-or-no version of Privacy).
For each round of "passing the bag around", each player picks a random number for each other player (you might mentally note them in matrix form). They publish the sum (practically modulo omething) of all the numbers they give out (think row sums), and send the individual numbers to the respective players in private. Each player sums up the received numbers and their own input, and publishes that sum (think column sums).
The difference of the sums of the two groups of published sums is the sum of all inputs.
As any party could manipulate the output by being insincere about the published "row sum". (Insincerity about the "column sum" would just be providing a different input). To curb that, for any game with a given number of rounds, players can prepare material for more rounds, and commit to them. A random subset of those is chosen before the game, and played through with everyone opening up their numbers and inputing zeros. With a sufficient number of picks, the likeliness of tampered material being in the game can be made arbitrarily low easily.
In addition (or possibly even to remove the necessity for the above), it might be useful to, on each round, agree on a random prime, with which all participants multiply their inputs. The resulting difference can be divided back to give the sum of the original inputs. Advance tampering would thus not result in plannable offsets.
Known issues with this are: * Parties could provide out-of-range input, eg. putting in a 2 if the legal values are 0 and 1. This is risky, as it may put the total out of the plausible range, but would only be spotted of everyone else acts in the same way. * The 'opening up their numbers' part might preclude refutable means of private communication between the parties. This means that unlike in the original game (where everyone can conspire to out a single player, but the statement is only as strong as the conspirators' trust in each other), the conspirators can prove their victim's choice.
As I later found out, this is a special case of the generalized Dining Cryptographers problem.
The above tools (or, if insecure, suitable replacements) along with some straight-forward Merkle tree mechanics for when players commit to moves should be suitable to implement Pandemic, Blood Bound and most other table top games -- that is, as long as they are sufficiently turn-based and thus do not require arbitration about priority.
A notable mechanism not covered here is secretly drawing cards from a pile without predetermined order, (or dealing out cards and leaving some cards behind for later use).
A static HTML application can initialize peer-to-peer communication between clients as has beens shown. (The setup is a bit verbose, though: it requires more than sharing a link with fragment information from an initiator, but also sending information back to the "host", and that for each participant).
Using an arbitrary introduction service (a simple WebSocket server, or a BOSH backed XMPP exchange like Jitsi uses) can make the initial exchange more painless, while using WebRTC in general keeps the rest of the game out of the intro server's way and allows local use more easily.
Once players are connected to some initiator, several topologies are possible for exchanging information. The more meshed approaches provide more resilience against connection hiccups of the initiator, but at least in games where all players contribute to randomness in card drawings, the game stalls anyway until everyone is back again.
(Eventually, when building games that can continue to some extent after a netsplit, the question arises of what it is that keeps independently started games from being mergable).
With round-based games (more precisely: games in which all changes have a deterministic order, eg. by each player having an opportunity to interject at a particular point in another player's turn), the game can be described as an append-only data structure with only one party writing to it at a given time. That can expressed as a chain of resources in a RESTful environment. Conceptually, all such games could just as well be played on a file server with change notification support.
I'd like to write a small game engine based on the above, but in the interest of Getting Things Done, I'm starting an implemention that ignores the "uncheatable" and "decentralized" points altogether.
This page is part of chrysn's public personal idea incubator; go up for its other entries, or read about the idea of having an idea incubator for more information on what this is.