---
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.
![](https://i.imgur.com/AOgONdG.png)
### 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.
> ![Mask Diagram](https://i.imgur.com/yDSHA1U.png)
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.
> ![](https://i.imgur.com/Do4kXwG.png)
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.
> ![](https://i.imgur.com/yJbWsUi.png)
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.
> ![](https://i.imgur.com/mUCrPVV.png)
**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: [nico@geometry.xyz](mailto:nico@geometry.xyz). 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

This short document outlines how to emulate witness encryption using threshold cryptography - and more specifically, threshold identity-based encryption (IBE). The ideas presented here are heavily inspired but the tlock construction from [GMR23]. Disclaimer: I have not done a thorough review of the existing literature, if you are aware of existing constructions that work in the same way please let me know! Background Witness Encryption. The witness encryption paradigm is the following: given an instance of some hard problem, one can encrypt a message using the instance such that it may only be decrypted by someone who knows the problem's solution (the witness). Threshold IBE. Identity-based encryption (IBE) is a class of cryptographic primitives where public keys are some publicly known string (the identity) and the private key is derived to match that public key. Originally, IBE schemes relied on a trusted third party to derive the private key. The Boneh-Franklin IBE scheme [BF01] is of particular interest because private keys are computed by the trusted third party as a BLS signature of the identity.

5/12/2023(Cross-post from the Geometry notebook) Edit 21/02. Remove the need for a commitment to $\mathbf{q_C}$ in the verifier key; improved strategy for higher degree custom gates thanks to feedback from Nat Bunner and Lev Soukhanov. As shown in Nova [KST22], incrementally verifiable computation (IVC) can be realised using a folding scheme and a zkSNARK. In this article, we present a folding scheme for a variant of the PLONK arithmetization [GWC19]. We then extend our relaxed PLONK arithmetization to accept custom gates of degree 2 and circuits with higher gate arity. Finally we outline avenues for future work including folding higher degree gates, supporting lookup gates and designing an IOP for the relaxed PLONK arithmetization. ⚠️ This article is a condensed version of the Sangria technical note. See the full version for proofs and extended discussions. We assume the reader is familiar with IVC and Nova. Suggested preliminary viewing and reading: Justin Drake's ZK Whiteboard Session and this Lambdaclass blog entry. Preliminaries

4/7/2023
Published on ** HackMD**