# Multiplayer Zero-Knowledge Sudoku

## The game

At the beginning of the day, a new sudoku puzzle is published. There is a prize for the first person/team able to solve it. When a team wins, the prize is divided equally among its participants.

Each player can share their progress of their sudoku puzzle at any given time with their teammates. Once a team has found a solution to the puzzle, they can submit their answer and create a proof of their solution, without revealing their solution.

The participants in the game remain anonymous and their game will be stored in the Taiga blockchain encrypted. Furthermore, the blockchain will not reveal which application (a sudoku game in this case) was run.

## Motivation

The game highlights the intent-centric architecture of Taiga, which enables counter-party discovery and settlement in a private manner.

The architecture of Taiga works for any application. Thus, the sudoku game serves as a great example of a non-token application.

We will show how the privacy of the system works and its execution model.

## Design

For any Taiga application, we need to define three validity predicates:

- Send VP
- Only propose changes to teammates
- Receive VP
- Only accept changes if the proposed change comes from a teammate
- Application VP
- Check that all rows, columns, and squares are valid, that is, they contain all numbers from 1 to 9

## Execution model

The initial state of the game is the given sudoku puzzle.

The execution model works as follows: each user runs a Taiga instance, which consists of a gossip network, in which intents are solved, and a chain network, where the final, solved intents, i.e. notes, are stored encrypted in transactions.


An intent is the smallest unit of execution in the gossip network.


<!--  -->

The equivalent of an intent, in the chain network, is a note.


In an intent, a user (e.g. Carol) gives permissions to the solver to create a solution (i.e. a note) on her behalf if conditions (VPs) are met. More explicitely, a solver can create a note using Carol's credentials in which she gives A to Bob if and only if Bob gives B to her.

#### Setup

At the beginning of the game, each user issues automatically an intent from their current initial state of the game (A) to any state as long as it is different, it follows the rules of sudoku and comes from a teammate (B), so that their intents can be matched some time in the future.

For our purposes, we'll illustrate the game for a team of 3 users: Alice, Bob and Charlie.


#### Proposal

At each moment in the game, any user can submit an intent, i.e. propose a new state to his team members. In intent language, he proposes a state transition from A to B, where A is their shared current state and B is the proposed state, that is, a (partially) solved sudoku game with a few numbers changed.

Practically, a user (e.g. Alice) submits three intents that will potentially match with the previous three intents that were sent at the beginning of the game.


The solver needs to find a matching intent, that is, another intent that looks for any state as long as (1) it is different, (2) it follows the rules of sudoku and (3) comes from a teammate and offers no change in return (an identity function).

In this particular case, the solver doesn't need to be a third party, but could easily be each one of the team members.

Once the intents are matched, every user issues a new intent as it happened at the beginning of the game, waiting for an update.

<!-- Since a mutiplayer sudoku game is not a bartering application, the solver doesn't need to match intents. In fact, there doesn't need to be a solver in this context - in a sense the user is the solver (his Receive VP in particular). -->

## Privacy

- What information is revealed to the solver?

## Open questions

- If the game is on the browser, do all players live in the same node?
- Do users need to run two networks? Is the data in the gossip network ephemeral?
- The notes that solvers create, do they all go to the chain?
- Does the evolution of the game happen solely in the gossip network and only a solved puzzle is submitted to the Taiga chain or is each partial solution submitted to the chain network?

## Implementation

Currently on https://github.com/anoma/taiga/tree/alberto/halo2-sudoku