PBMX is a framework to creating secure and fair games that can be played over mail.
The main concern is supporting games that feature information that is secret, unknown, or unavailable without the need for a trusted third party. Secret information is information known to only a subset of the players; this could be e.g. in a game of poker, the contents of a player's hand. Unknown information is information that no player knows; in a game of poker, the contents of the deck are unknown. Unavailable information is information that no player can obtain, even at the end of the game; in a game of poker, the contents of the deck are not only unknown but also unavailable, because revealing it even after the game is over could show whether a player was bluffing or not.
In order to achieve this, PBMX provides cryptographic primitives for hiding information and for proving that the hidden information is as expected, i.e. no cheating happened. As an example, a player can produce a shuffled deck of cards and the other players can verify that the shuffle does indeed have the correct cards in it without actually knowing their order; were the original player to sneak in a fifth ace, the other players would be able to tell that cheating happened without having to check the contents of the shuffled deck.
The other main concern of PBMX is the ability to play such games without real-time interaction, over a variety of transports. E-mail would be a convenient and typical transport, but an attempt is made to fit the constraints of snail mail.
Token: the abstraction of a card's face. It is merely a 64-bit unsigned integer. Games built using PBMX need to encode the in-game meanings as token values.
Mask: the abstraction of a face-down card. It is a token encrypted with a shared key, so that it cannot be decrypted unless all players cooperate in doing so. Masks are usually generated with a random factor so that masking the same token doesn't always produce the same mask.
Stack: the abstraction of a stack of cards. It is an ordered sequence of masks, and can represent a face-down deck or, by using some of the primitives below, also a face-up pile or a player's hand.
Roll: the abstraction of a die roll. It is the combination of random masks generated by each of the players, which is later revealed to produce a public random value.
Clearmask: encrypts a token without a random factor (i.e. the random factor is zero). This produces a mask that doesn't actually hide a token value, but can then be used for any operations that use masks. It can also be used to model face-up cards.
Remask: modifies the random factor of a mask. This produces a different mask that still encodes the same token value, without unmasking the value. A remasking operation also produces a proof of correctness that can be used to verify that the token value was not changed by the operation. This doesn't have a physical equivalent, but it is a useful building block for higher-level protocols.
Unmask share: computes a player's share for decryption of a mask. Players cooperate to decrypt a mask by publishing their shares. A mask can be decrypted by anyone who knows all those shares. It is possible for one player to withhold their own share, thus allowing that player and only that player to decrypt the mask, which is useful to model a player's hand of cards.
Shuffle: reorders and remasks a stack as a single operation. This directly models a physical shuffling of a deck. Publishing the proofs of correctness of the remasks would reveal the order, so this primitive uses a specialized proof that guarantees the tokens in the result are the same as in the original stack without revealing the order.
Shift: cyclically shifts and remasks all masks in a stack. The physical equivalent of this is "cutting the deck": we take a number of cards from the top, and without changing their relative order, we move them to the bottom. Like with a shuffle, this primitive needs its own specialized proof of correctness that doesn't reveal the length of the shift. While in a physical game, this is used to thwart attempts to "stack the deck" by the person shuffling, in a PBMX game this isn't needed. However, shifts are still useful for building higher-level protocols.
Mask entropy: encrypts a random number to provide entropy for a roll. Once all players have provided an entropy mask, the masks are added together, which can then be decrypted as a regular mask would to produce shared random bits. As long as one of the players uses unbiased masks, the result is guaranteed to be free of bias.
Entangle: combines two masks into a single mask in such a way that it encodes both tokens (this is possible because mask can actually encode up to 254 bits and tokens are only 64-bit long). Anyone can produce such an entangled mask, and each pair of masks has only one possible entangled mask. Like remasking, this doesn't a physical equivalent, but is provided as a building block for higher-level protocols.
Players in a PBMX game communicate their actions by trading blocks containing a series of descriptions of primitive operations. Each block is signed by the player issuing it, and contains a link to the block or blocks that precede it. This is done for validation purposes, but also to enable players to take actions concurrently: the links establish which state of the game they operate on. These links form a structure similar to a blockchain, although not quite since it can contains both forks and joins and all branches are considered as part of the structure.
PBMX is agnostic of the communication channel; all that is required of a channel is the ability to broadcast these blocks to all players.
Before the game can start, each player needs to generate a private/public key pair. The public key is then published in a block and broadcast to the other players. All blocks issued by one player are signed with the private key held by that player. Once all players have broadcast their public key blocks, they can compute a shared public key by adding together all the public keys.
Typically one player sets up the initial game state by publishing a block that with clearmasks for all the game tokens. Which player does this is to be determined beforehand by the players themselves. The block can include any other operations needed before the game starts, like shuffles (see below).
The shuffle primitive does not hide the order of the shuffle from the player performing it, only from the other players. In order to have a shuffle that all players can trust to actually be random and unknown, a cooperative procedure is necessary. The first player shuffles the original stack, then the next player shuffles the result of that, and the next one shuffles the result of that, and so on, until all players have applied a shuffle primitive. This protocol guarantees that no player can decide the order of the shuffle, and that as long as one of the players uses unbiased random orders, the result is guaranteed to be free of bias. A similar protocol can be used to perform hidden shifts.
When a player gets cards added to their hand, this is represented by simply moving the appropriate mask to the stack that represents their hand, and then all the other players publish their decryption shares for that mask. The player whose hand it is doesn't publish their shares, but still computes them in order to have a complete set of shares and thus be able to actually know the cards in their hand. The other players have all but one share so they can't know those cards.
Tokens that are masked can be moved from one stack to another, or from on position to another in the same stack without changing the masks. However, this has the sometimes undesired property of anyone being able to track the movement of that token across stacks. This could give players more information than one should in some games.
Consider this scenario: Alice looked at the top card of the deck, and Bob drew that into his hand. Now if Alice gets to pick a card from Bob's hand without looking, she can take recognized the card that was on top of the deck because it has the same mask.
In situations such as these it may be necessary to perform some operation that hides the location of the tokens, e.g. Bob could simply perform a shuffle of his hand before Alice picks the card.
When a face-down card is to be made visible to everyone, this is as simple as having everyone publish their decryption shares for the corresponding mask.
Note that some of those shares may have already been published previously and don't need to be republished. This might be the case when the card is in a player's hand: if all but one share were already published to reveal that mask to that player, then only the final share needs to be published. However, in a game where players may have shuffled their hands to avoid tracking (see above), the previous decryption shares are not useable for the shuffled masks, so all players would need to publish shares for the shuffled mask.
Revealing a card to only one player is easy: all the other players publish their decryption shares for that mask. If the card needs to be revealed to a second player, the first player would have to publish their decryption share as well. Since PBMX assumes a broadcast channel, this would make all shares public, therefore revealing the card to everyone. Instead, someone can remask the card and then all players but the first one can publish the shares for that original mask, and all players but the second one can publish the shares for the second mask. This way each of the two players gets a different complete set of decryption shares, but every other player has only two incomplete sets.
Suppose a game where at points a card gets shuffled into the deck, but face-up. In this manner, its position becomes unknown, but only until it becomes the top card, at which point it becomes visible to everyone.
PBMX supports scenarios like this with entanglements. For this particular case, one would create a separate stack with two kinds of tokens: "visible" and "not visible". If the order of the main stack changes in any way, the order of the secondary stack must also be changed in the same way. If the main stack was shuffled secretly, the visibility stack is also shuffled secretly, using the same permutation, and the entangle primitive is used to prove that the same permutation was used. Then, whenever a new card ends up on top, the players reveal the top mask in the visibility stack; if it is "visible", that means the top of the main stack should be visible.
This protocol can also be used when a game needs to reveal only parts of cards. E.g. it is possible to reveal only the suit of a card by keeping tokens representing the suits alone in a separate stack and always performing entangled shuffles.