A few months ago, on a particularly long bus ride across the US to EthDenver, a friend asked me a seemingly simple question: How to play poker trustlessly?

Now, since poker is a hidden information game, you might be tempted to say "just use zk", unfortunately, zk is mostly useless here. Because you don't need to prove anything until the end, where you end up revealing your cards anyways.
No the real problem with poker is shuffling the cards, and revealing specific cards to specific players at the right time.
The only solution I could find at the time was to have a dealer algorithm in MPC that would shuffle the deck and encrypt each players' cards with their key. This seemed to make sense because we're dealing with a shared private state (the deck) so MPC feels natural.

However, as I found out a bit later, there’s [a much easier solution](https://zkholdem.xyz/wp-content/themes/zkholdem-theme/zkshuffle.pdf)
And here’s how it works:

note: Players might cheat by not following the protocol correctly. In the following, you can assume each player is zk proving their contribution.

First just assume we have access to a special encryption scheme, with the following property:

$$Enc(k_1, Enc( k_2, m)) = Enc(k_1+k_2, m) = Enc(k_2, Enc( k_1, m))$$

In other terms order of encryption doesn’t matter, which means if you want all players to encrypt something, the first player to encrypt doesn’t have to be the last to decrypt.

---
This allows us to have the following protocol for $n$ players and $m$ cards:
### Setup:
$P_1$ takes an ordered vector $(C_j)_{j \leq m}$ of all cards in the game and applies a random permutation $\phi_1$, he then encrypts each item with his key $k_1$ and sends the result to $P_2$.
$P_2$ applies their permutation $\phi_2$, encrypts it with $k_2$ and passes on the list to $P_3$
…
(all players do the same)
...
$P_n$ gets the list from $P_{n-1}$, applies $\phi_n$, encrypts it and sends the result to all players.
All players now have a fully shuffled and encrypted deck:
$$(Enc(\sum_{i\leq n}k_{i},\ C_{ \phi^{-1}(j)})_{j\leq m}$$

All cards are encrypted with the aggregate key $\sum_{i\leq n}k_{i}$ and ordered according to $\phi = \phi_n\circ \phi_{n-1}\circ...\circ\phi_1$ the overall permutation you get by combining all individual shuffles

### Game:
When the game starts each players needs to be able to decrypt their cards and nothing else, but the cards are encrypted with everyones keys.
So for $P_1$ to get the first 2 cards, $P_n$ decrypts the first two cards of the shuffled deck, and sends them to $P_{n-1}$ which decrypts them and sends them to $P_{n-2}$.
All players do the same until $P_1$ gets the first two cards with the only encryption remaining being his own.
Once we’ve done this with all players, the betting phase can begin.
To decrypt the flop, turn and river, we proceed similarly, by having all players sequentially decrypt the next cards.

---

The reason I make a distinction between setup and game is that you can precompute the setup, and just shuffle as many decks as you want before the game even starts. In case a player is eliminated, he can publish his key, and the others can keep playing without him needing to be online.

The main issue we encounter in this protocol is latency during the card decryption phase, as we must wait for all the players to pass the card.
If $l_i$ is the latency between player $P_i$ and $P_{i+1}$ then a decrypting round will take at least $\sum_i l_i$.
However you can do better, by having a slightly longer Setup phase you can reduce playtime latency to $max(l_i)$. Here's how it works:

### Setup:
The key insight is using position-dependent keys: instead of every player using the same key $k_i$ for all cards.

First, just do the same thing as before to get a fully encrypted, fully shuffled deck of cards.

Then each player $i$ generates a unique key for each card position: $k_{i,j} = hash(k_i, j)$ where $j$ is the card position.

Then we do another round, where this time, each player will remove their layer of encryption, and encrypt once again, except this time using a different key for each position.

We end up with the vector $(Enc(\sum_{i\leq n}k_{i,j},\ C_{ \phi^{-1}(j)})_{j\leq m}$

Same as before cards are shuffled according to the overall permutation $\phi = \phi_n\circ \phi_{n-1}\circ...\circ\phi_1$, except this time the card $C_{ \phi^{-1}(j)}$, which is at position j, is encrypted with the position specific agregate key $\sum_{i\leq n}k_{i,j}$.

### Game

This time the cards don't need to go through every player to be decrypted. For $P_1$ to get his cards, all other players just need to send their keys $k_{i,1}$ and$k_{i,2}$ to $P_1$ and he will be able to decrypt the first two cards.
We do the same for all players' cards as well as the community cards.

---

Now you might be saying "this is worthless", and I agree to a certain degree. In poker, the number of players $n$ is probably small enough that the added complexity doesn't make it worthwhile. But shuffling isn't just about poker, and we could imagine something like a consensus protocol that requires randomly distributing roles to a million validators using this protocol. the fact this is a $1$ of $n$ trust assumption makes it really interesting.