Investigate using zkShuffle

[norswap]

Our current scheme for private information involves committing to player hands and the card remaining in player decks (via a (to be salted) Merkle root) and then proving changes to these roots via zk proofs. We also use on-chain randomness to select random cards and prove in the zk proof that the correct cards were drawn from the deck.

This has the advantage of being relatively simple and not require extra infrastructure. The disadvantage is that it limits us in terms of gameplay: game often have mechanism that manipulate the deck, such as "look at the three top cards of your deck and put them back in any order". The current zk scheme does not allow us to do this (or we need to special case for every potential effect, and it gets really complicated and expensive really fast).

An alternative exists in the form of zkShuffle, an implementation of "mental poker" by the team at p0x Labs.

I wrote some twitter threads on both system:

• current system (more or less)
• mental poker (+ geometry article)

But in brief, mental poker thresholds encrypt every card by all players (both in our case). I encrypt then shuffle, pass the shuffled deck to you, then you encrypt and shuffle. The result is a deck where nobody knows what card is where. To reveal a card publicly, all parties need to collaborate. To reveal a card only to player X, all players except X decrypt publicly, and X decrypts privately.

This system allows any card system we want BUT comes with the problem that both players need to collaborate when revealing a card. This could mean extra on-chain latency or an off-chain component (server or p2p) to aggregate the descriptions. In practice though, the El Gamal encryption scheme is expensive to compute on-chain and so zkShuffle uses zero-knowledge proof to prove the El Gamal decryption on-chain instead (also maybe there is no way to tell that a ciphertext was decrypted with the right private key? I really have no idea how El Gamal works).

But anyway, all that work has been by the good folks at p0x Labs, who are also making their system available as open source software. The tech was used to implement https://zkholdem.xyz. Some resources:

• github repo
• specs
• example use
• toy card game (!!) from the Autonomous World Hackaton

The goal of this issue is to investigate the use of zkShuffle as applied to 0xFable. No better way to learn than by doing, so basically, reimplement the system with zkShuffle — in particular, its current state with the demo game loop (draw, play creatures, attack, defend) which only needs zk for drawing & playing.

[norswap]

First thing to look for: does zkShuffle support multiple decks yet? I've been told it will, but not sure it's in right now. We need that because each player hash its own deck.

[norswap]

Important to mention that mental poker enable things that are not feasible in the current model: for instance a card could say "look at the top three cards of your deck, and put them back in any order".

We can't do this with the current zk-proofs. Or maybe we could, but we'd need custom changes for every such effect and the combination of them would be unmanageable, because in full generality you end up with a deck that is a linked list of segments, some of which are known by no one, some of which are known by one player, some of which are public. For segments known by the other player, it now also means you need the other player's involvement to play a card, which is the thing we wanted to avoid.

[Boffee]

Why isn't it sufficient to just use 2 layers of commit-reveal?

[norswap]

I'm not sure exactly what you mean, could you expand?

[Boffee]

Say we want to shuffle Player A's deck of 40 cards.

1. Player A randomly shuffles 1 - 40
2. Player A creates commitment for each of the 40 indices (can be stored as a single merkle root)
3. Player B does the same thing
4. For Player A to draw the n'th card, Player B reveals their n'th commitment
5. For Player A to play the n'th card, Player A reveals the commitment that corresponds to Player B's n'th reveal
6. If player B fails to reveal within some duration, assume they forfeit

[norswap]

As far as I understand, that's exactly how mental poker works!
But the commitment is actually (ElGamal) encryption in this case (see the Geometry article linked above)

Note that if you want to replace ElGamal by a naive hash commitment, you'd need to also add a private salt, so you'd still need the zero-knowledge proof.

Maybe we could replace this by an ECDSA signature, which can then be verified cheaply when the signed data is revealed. I will ask Shumo.

What zkShuffle adds:

• the zk proof
• the scheme is symmetric, it also allows you to reveal so that the opponent can then privately look at the top cards of your deck, whereas a scheme with hashes/ECDSA signatures is ordered: the opponent has to reveal, then you
• an off-chain component to aggregate the signatures, because we don't want the latency of doing all this commit-reveal stuff on-chain

Another interesting consideration that this made me think of: calldata is expensive on L2s. An ECDSA signature is 64 bytes, so posting 64642=4k bytes to L2 for the shuffle will be extremely expensive.

On the other hand, a groth16 proof is 192 bytes, but a Plonk proof might again be multiple kilobytes.

[Boffee]

Note that if you want to replace ElGamal by a naive hash commitment, you'd need to also add a private salt, so you'd still need the zero-knowledge proof.

2 different ways to generate private salt:

1. salt = sign(game id, draw index): requires signature verification (ecrecover or proof if that's cheaper)
2. merkle tree of arbitrary salts: requires merkle proof instead of signature verification. The minor issue is that a merkle proof reveals another commitment. A simple solution is to have players generate the merkle proof when the game ends (or in any other delayed fashion such that a commitment can only be used for a proof once it has been revealed).

an off-chain component to aggregate the signatures, because we don't want the latency of doing all this commit-reveal stuff on-chain

Wouldn't this mean that players can stop the game by refusing to provide the salt (or signature) with no consequence?

[norswap]

Wouldn't this mean that players can stop the game by refusing to provide the salt (or signature) with no consequence?

Yes, there is also a contract component for the unhappy case that works as you suggested. It's just that since that is there, and arguably there should be a pretty aggressive chess timer on reveals for this unhappy case, then there is really no advantage of devolving to the unhappy case and everything should always be happy case.

salt = sign(game id, draw index): requires signature verification (ecrecover or proof if that's cheaper)

I guess that one could work indeed 🤔

merkle tree of arbitrary salts: requires merkle proof instead of signature verification. The minor issue is that a merkle proof reveals another commitment. A simple solution is to have players generate the merkle proof when the game ends (or in any other delayed fashion such that a commitment can only be used for a proof once it has been revealed).

I've always stayed away from designs where people have to trust someone until a reveal at the end of the game where it's shown that they were honest or not. To keep people honest you have to have them put up a stake, and I think that gets fiddly real quick. Also what if they don't prove? Could happen to honest parties if they get disconnected. If you don't impose penalties, it's easy to cheese other players for the lulz (even if the final score is a loss for you).

[Boffee]

Yes, there is also a contract component for the unhappy case that works as you suggested. It's just that since that is there, and arguably there should be a pretty aggressive chess timer on reveals for this unhappy case, then there is really no advantage of devolving to the unhappy case and everything should always be happy case.

When it's Player A's turn to draw, how can the game know that Player B refused to provide the salt to player A if the salt is exchanged off-chain?

[norswap]

If A doesn't receive data from player B, he makes an on-chain challenge which starts B's chess timer to provide info on chain.

The client is hardwired to wait a certain time, then make the challenge. They also monitor incoming challenges so they can react as fast as possible.

So if B tries to cheese (withhold salt), he'll just make the game slower - but not immensely slower because of the chess timer. Same if A tries to cheese (bogus challenges).

I don't know if that's what zkShuffle does, but that's how I would build it.

[Boffee]

The optimistic approach I see lol.

an off-chain component to aggregate the signatures, because we don't want the latency of doing all this commit-reveal stuff on-chain

Hmm, can the reveal be bundled with which ever action ends the turn (defend and pass?) in fable? Could work if the opponent can't react to the action that ends the turn. Should much easier to implement than key exchange, and zero latency overhead.

[norswap]

You could do this when you know an action will happen, indeed at the end of the turn you know the opponent will draw a card. But if he has an extra "draw a card" effect, then this doesn't work.

Also there is no need for key exchange, just use the Ethereum key.

(Unless you're talking about salts, but we need those for randomness anyway, & probably other things.)

[MatteoMer]

Hey, would be happy to try a first implementation!

From what I've seen so far: multiple decks don't really seems to be a problem, but we need to adapt the code a bit.
Something that might be a bit more challenging is that they're only handling decks of 5, 30 and 52 cards so far, so that's in conflict with the actual rules (64 cards), but I think for my implementation I'll stick to 30 cards since it's a POC, and that easily be changed later.

[norswap]

Let's goooo! 🚀
And yeah, 30 cards is perfectly acceptable for a prototype!