Implementing turn-based games that sometimes reveal private game state

Cryptography
1

Hello everyone,

Here is a theoretical problem that I have been thinking about for the past week. Any help would be appreciated!

TL;DR: How can one implement Dark chess without relying on a third party?

Zero-knowledge tools make it possible to play some games without having to rely on and trust a third party. A common example is battleship. Both player A and player B keep the arrangements of their ships private throughout the game. When player A fires a shot on player B’s grid, player B replies with a zero-knowledge proof telling player A whether it was a hit or a miss. When it is player B’s turn to fire, it simply picks a coordinate on player A’s grid that it hasn’t picked before. When it is their turn, each player knows what their options are – they do not need to know anything about the other player’s private game state (in this case, the arrangement of their ships on the grid) to know every valid move.

This contrasts with Dark chess (playable on chess.com), where “a player does not see the entire board – only their own pieces and the squares that they can legally move to.” For a player to know which squares their pieces can move to, they frequently need to know where their opponent’s pieces are, which is private information! So, players should 1) keep the positions of their pieces private, 2) zero-knowledge prove the validity of their moves, 3) somehow reveal the positions of the pieces that can be captured by the opponent’s pieces. The catch is that the opponent’s pieces are hidden, which makes #3 nontrivial.

If there is a trusted third party, the players can just share the positions of their pieces with it and rely on it for the management of the board. The challenge is to implement Dark chess without relying on a third party. It seems to me that zero-knowledge proofs would not be enough and that we would need homomorphic encryption in some form. When player A makes a move, they can send 1) a zero-knowledge proof proving that their move is valid, 2) a homomorphically-encrypted copy of the positions of their pieces. Player B can pass #2 and the positions of their own pieces to a function, which can somehow tell only the positions of the pieces that player B is supposed to see. Now that player B has updated its board after player A’s latest move, they send a homomorphically-encrypted copy of the positions of their own pieces to player A. Player A passes this data to the same function that player B used and updates their own board.

Do we currently have the math/software tools that can implement this? Does anyone have any ideas?

1 Like
2

I was mulling over this a while ago, and I did not find a good way to implement Fog of War using cryptography.

I did come up with a different approach though:

  1. Alice asks Bob for visibility in a position.
  2. Bob has two options:
  3. Bob complies and provides the visibility data to Alice.
  4. Or Bob refuses, and challenges Alice’s claim on the position’s visibility.
  5. If Alice proves her claim, she is rewarded with a bonus, and Bob has to provide the visibility information.
  6. If Alice fails to prove her claim, Bob is rewarded with a bonus.

This kind of change makes the game more like poker and less like chess though, where players can bluff their way around. Players receive hints about their opponent’s state, so not a completely private state either.

1 Like
3

That is a very interesting approach. The option to bluff would definitely make the game more exciting.

I have been reaching out to many people since my post on this forum. Some academicians suggested me to use a variant of private set intersection (PSI), while others pointed to Zama’s work on homomorphic encryption (check out this talk).

My intermediary conclusion is that zero-knowledge proofs are not enough to solve this problem. Some combination of homomorphic encryption and multi-party computation is also needed.

4

Maybe I’m not understanding the logic behind creating Dark Chess… but would Dark Checkers exist? It might make sense to start there.

I thought there was a tutorial for BattleShips using zkApps somewhere, and there’s some discussion here on that: Discord

I also posted your question on Discord to get more thoughts on this: Discord

1 Like