Tic-Tac-Toe example with Kombucha

[querolita]

We would like to have a number of circuits written using our kombucha circuit writer for different purposes: examples in the readme file, a blogpost, documentation, etc. A visual set of circuits related to games is interesting as they are normally well-known and are friendlier for a broader audience than something more mathematical in nature.

The idea would be to simulate a 2-party interaction where players are playing a tic-tac-toe game. The goal of the winning party would be to prove that they won the match by encoding the witness (the state of the board) in our circuit.

[fabrizio-m]

If I understand correctly it will be a circuit to verify that some board represents a winning state, right? Will it require ZK? could the board be a Merkle root as public input?

[querolita]

Yes, you're right. In the best case, it would be zero knowledge. This should be obtained with the zk rows at the end of the gates. Regarding the specific strategy, whatever helps you think how to model it should be fine. But using merkle trees may be too complex and would require to write plenty of auxiliary methods (which, on the other hand, we may want to have at some point, but likely not necessary for this example).

[mimoo]

If I understand correctly it will be a circuit to verify that some board represents a winning state, right?

you could also have a circuit that takes a state, and returns a new state that also changes who can play next. And at each transition the circuit could check if someone won.

[fabrizio-m]

I think we have two simple options:

• winning state verification.
• transition verification.

And then the more complex of a complete game, I can think of a way without recursion but without perfect ZK:

• Players are identified with knowledge of discrete log.
• Some input will be the turn, incremented by one every turn, one player takes even turns and the other odd turns.
• Circuit receives two states and checks transition, winner and correct player.
• The state will be $3^9$, and adding 9 turns to it $9 * 3^9$, so it can fit in a single field element and committed with a Pedersen hash, players will have to agree in some random number and keep it secret for ZK.
• So public inputs will be two Pedersen hashes for each state, and a public key for each player and the winning state, 9 in total.

And at the end there will be about 9 proofs, I think that it has an acceptable complexity, but maybe for examples it could be better to have a few simpler circuits instead of one for a complete game.

[fabrizio-m]

It should have perfect ZK now that I think about, initially I put the turn as a public input but later move it to the game state so the number of turns should be secret now, the problem is that without recursion someone can count the number of proofs and get the number of turns, it could be padded but will make everything more complex.

[github-actions[bot]]

Stale issue message