---
tags: mental_poker
---
# 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](https://en.wikipedia.org/wiki/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`](https://github.com/arkworks-rs) 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]](mailto:[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