Geometry presents: a zero knowledge library for Mental Poker (and all card games)

In this short document, we present our library for trustless, decentralised card games. We keep the cryptography to a minimum; an in-depth article will follow.

Why call it Mental Poker? Mental Poker is a cryptographic problem that was first formulated in 1979 [1]. Simply put, a group of players that do not trust each other want to play a game of poker over a network. We aim to devise a protocol in which: (i) there are no physical cards, we use digitally transmitted messages instead and (ii) we must prevent cheating. As you may suspect, a solution to this Mental Poker problem can also be applied to any card game.

Agenda:

• Peek at the library's function calls
• A round of Texas Hold'Em
• A few technical notes
• Contact details

Our Library

Our library allows to play any card game and is based on a paper by Barnett and Smart [2] with improved zero knowledge (zk) arguments based on [3]. The core features are listed below.

• Define custom cards: game developers can define their own cards.
• Hide card values: every player performs a secret computation locally
• Shuffle the deck: every player performs a secret computation locally
• Reveal cards to individuals or groups: some players perform a secret computation locally
• Prevent cheating: each secret computation is proven in zero knowledge. Verification can be performed by players, an incentivised off-chain server or an on-chain smart contract.

We will briefly discuss the operations that the library enables and will then showcase how we can use these to play a round of Texas Hold'Em. If you are happy with a high-level view only, I invite you to read each header and skip directly to the indented sections labeled "a helpful analogy".

Note: we will use simplified pseudo-code snippets to give intuition into how the library calls work. In every function's arguments, anything before the ; is a public input, anything after it is secret to the player performing the operation.

Setup

Each player should generate a PlayerSecretKey and PlayerPublicKey. To register to play the game, a player publishes her PlayerPublicKey along with a zero knowledge proof that she knows the corresponding PlayerSecretKey. When every player has registered and every proof is verified, we can publicly compute an AggregatePublicKey.

This AggregatePublicKey is created in such a way that nobody knows the corresponding secret key. Anything encrypted using the AggregatePublicKey will require the collaboration of all players to decrypt.

Operations on a card

Mask
A mask operation takes a public Card, some secret Randomness and the AggregatePublicKey, and outputs a MaskedCard. For those who are curious about the cryptography, this is essentially an

$n$-out-of-

$n$ threshold encryption.

mask(Card, AggregatePublicKey; Randomness) -> MaskedCard

A helpful analogy - part 1/4.

You can think of the mask operation as taking a single card and placing it in an opaque box which we call a MaskedCard. The box is equipped with a set of padlocks - one padlock per player. Opening the box requires that each player removes their padlock.

When every card has been placed into its own box, the boxes can be stacked into a deck and passed around.

There is one problem however: the boxes have labels. Whoever put the cards in the boxes will know the mapping from box labels to card values. We fix this with the remask operation.

Important properties:

• ✅ A MaskedCard hides the value of the underlying card.
• ✅ A MaskedCard can only be unmasked by a coalition of all players.
• ⚠️ The player who performed the mask operation knows the mapping from MaskedCard to card value.
• ⚠️ Any player who learns the random value
  $\rho$ that was used can find what card was masked by brute force: simply mask all the cards with
  $\rho$, see which one yields the same MaskedCard.

Unfortunately masking is not enough to guarantee that no player can know a MaskedCard's value. To fix this, we get all other players to "remask" the MaskedCard.

Remask
The remask operation expects a MaskedCard, the AggregatePublicKey, some secret randomness and outputs a new MaskedCard for the same underlying card value.

remask(MaskedCard, AggregatePublicKey; Randomness) -> MaskedCard

A helpful analogy - part 2/4.

The remask operation can be understood as secretly replacing the label on a box with a new label. Whoever performs the remask operation knows the mapping from new labels to old labels.

Can we recover the value of the card after a remask operation? Yes! By collaborating with all the players that have masked and remasked the card before us. To guarantee that no player or group of players can cheat, we need to ensure that all players apply the remask operation.

Reveal and Unmask
After a card has been masked and remasked by all players, we finally find ourselves in situation where no sub-group of players can infer the value of a MaskedCard. How do we recover the card's value when it is time to show it?

As mentioned previously, this is a collaborative process. First each player must produce a RevealToken for the target MaskedCard using the reveal function.

reveal(MaskedCard; PlayerSecretKey) -> RevealToken

These tokens are unique to each player and to each card, and can only be derived by knowing the right secret key. Importantly a RevealToken leaks no information about the secret key that was used to produce it.

When every player has released their RevealToken for a target MaskedCard, anyone can collect them and apply unmask. This returns a publicly readable Card.

unmask(MaskedCard, Vec<RevealToken>;) -> Card

A helpful analogy - part 3/4.

When a player provides a RevealToken for a MaskedCard, they are effectively removing their lock from that specific box. Once all players have removed their padlocks, we can use the unmask function to open the box and recover the card that had been hidden.

To make the game trustless we need to be able to convince all the players that these operations are performed correctly without revealing their secret inputs. Our library provides functions to prove and verify each of these operations in zero knowledge.

Operations on a deck

Shuffle and remask

shuffle_and_remask(
    Vec<MaskedCard>, MasterPublicKey;
    Vec<Randomess>, Permutation
)-> Vec<MaskedCard>

shuffle_and_remask does exactly what it says: take a deck of MaskedCard, change the order and apply remask to each of them. Similarly to the remask operation, all players must apply shuffle_and_remask to guarantee that no sub-group can collaborate to cheat.

A helpful analogy - part 4/4.

When shuffling a deck of physical cards, it is enough to turn them face down and change their order. In our case, recall that a MaskedCard is like a locked labeled box. If we only change their order, players will still be able to read the labels. To get the same effect as shuffling a deck of cards, we need to change the order of the boxes and apply new labels.

Split
COMING SOON. This is just a special case of a shuffle.

A Round of Texas Hold'Em

We will now see how these function calls can be used to play a round of Texas Hold'Em.

Game setup

	Texas Hold'Em	Mental Texas Hold'Em
1.	Gather a group of players around a table	Players each run the key generation algorithm, publish their public key and prove in zk that they own the corresponding secret key. A master public key is computed.
2.	Bring a deck of 52 standard cards.	Publicly encode each card value to a Card. mask all 52 Card with a public randomness value and publish all proofs.

An Example Round

	Texas Hold'Em	Mental Texas Hold'Em
3.	Dealer shuffles the deck	Players take turns running shuffle_and_remask and publish the proof for their shuffle.
4.	Give out the cards: top card goes to the first player, second card goes to second, etc…	Publish reveal tokens (with proofs) to allow players to see their cards: all players but the first publish a RevealToken for the first card, all players but the second publish a RevealToken for the second card, etc…
5.	Betting using physical chips	Betting using on-chain currency.
6.	Discard and reveal cards following the game rules	Following the order of the deck, ignore discarded cards. To open a card, publish reveal tokens (with proofs) and unmask cards following the game rules.
7.	Repeat 5 and 6 as required by the rules	Repeat 5 and 6 as required by the rules
8.	Final betting. Open hands and declare a winner	Final betting. Publish reveal tokens (with proofs), unmask all the cards, compare their values and declare a winner.

Throughout this description, we have omitted the verification steps. This is because these verifications might be performed by different parties (players, off-chain server, on-chain smart contract) depending on the trust model that the game developer has chosen.

Technical Notes

The library is:

• written in Rust using the arkworks ecosystem.
• based on elliptic curve cryptography. Game designers can choose the curve with which they want to work.
• compatible with Cairo and StarkNet. We have implemented the necessary finite field arithmetic to allow our types (Card, MaskedCard, AggregatePublicKey, proofs, etc…) to be represented using Cairo's native felt type.
• mostly modular. We have instantiated the card protocol from [2] with a specific encryption scheme, commitment scheme and a zk argument for a correct shuffle. Each of these can be replaced (e.g. replace the shuffle argument by a general purpose zk-SNARK).

Contact Details

Game developers please get in touch here: [e-mail]. We can help you integrate the library to your game, implement features on request and improve the library to simplify your experience.

References

1. A. Shamir, R. Rivest, and L. Adleman, "Mental Poker", Technical Memo LCS/TM-125, Massachusetts Institute of Technology, April 1979. https://apps.dtic.mil/dtic/tr/fulltext/u2/a066331.pdf
2. Barnett, Adam, and Nigel P. Smart. "Mental poker revisited." In IMA International Conference on Cryptography and Coding, pp. 370-383. Springer, Berlin, Heidelberg, 2003.
3. Bayer, Stephanie, and Jens Groth. "Efficient zero-knowledge argument for correctness of a shuffle." In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 263-280. Springer, Berlin, Heidelberg, 2012