# Keaki ZheroTag

### Motivations

Keaki's goal is to facilitate/accelerate the exploration of what can be built using Extractable Witness Encryption for KZG Commitments and Efficient Laconic OT (WE-KZG, for brevity) ([notes](https://www.leku.blog/kzg-we/), [library](https://github.com/brech1/keaki)). The idea presented here relies heavily on such primitive so I encourage you to go through the notes first.

Early proposals by [Ingonyama](https://medium.com/@ingonyama/cryptographic-fog-of-war-9b8785ba744a) and [Yiğit Kılıçoğlu](https://docs.google.com/document/d/1NKlXGp6SA32hZcv-NY0PsTs4kYVaMOUi36wuCUvgoPs/edit#heading=h.nn6shegjqj20) suggest looking into games such as [fog-of-war chess](https://www.chess.com/terms/fog-of-war-chess) (or dark chess). Build such game in a peer to peer and trustless manner forces you to solve many challenges. One player should be able to prove to the other player the correctness of their move without revealing the move itself. At the same time, a player should be able to probe his (limited) view under the conditions that:

- Nothing beyond the view is revealed to the player
- The opponest shouldn't learn anything about the view of the player

In practice, developing such games requires zero knowledge proofs for verifiable computations and MPC for performing computation on hidden data coming from different parties.

The goal of Keaki ZheroTag is to demonstrate how WE-KZG can reduce the number of interactions between the players at each turn (round complexity). Optimizing for other targets such as execution runtime (computation complexity) or amount of data being shared between the parties (communication complexity) is beyond the scope of this experiment.

We define a **round** as a single phase of communication in which all parties (2, in the context of our game) can simultaneously send messages to other parties.

1. Some number of parties perform *some* computation
2. Parties exchange data between each other
3. Some number of parties perform *some* computation
4. Parties exchange data between each other

The previous example protocol contains two rounds of communications (step 2 and step 4). The notion of round is strictly connected to the concept of state dependency. The data being sent by the one party as part of a communication round must be dependent of the previous step of computation. Likewise, the data being received by one party as part of a communication round must be used as input to the following step of computation.

### What is ZheroTag

[ZheroTag](https://github.com/kilyig/ZheroTag) is a peer-to-peer fog-of-war chess based on ZKP and Private Set Intersection (PSI) based on Diffie-Hellman. [Here](https://docs.google.com/presentation/d/1OL8yg962QT-DHgDD-zecBKWVpN6b9eNND8x9Lz6F8Rc/edit) you can find more about the game dynamics.

The fundamental component of the game is the **turn** of a player (in this case of Player A) which is defined as "Player A makes a move and updates Player B's view. Player B opens their view. If Player A is in their view Player B wins, otherwise it's Player B turn".

Let $P=(u, N)$ be a player where $u$ is their position on the board and $N$ is a vector containing the neighbours of $u$.

    - - - y y y
    - - - y B y
    - - - y y y
    x x x - - -
    x A x - - -
    x x x - - -

In such scenario $A=\{(4,1), [(3, 0), (4, 0), (5, 0), (5, 1), (5, 2), (4, 2), (3, 2), (3, 1)]\}$

Here's a description of a turn performed by Alice:

- Bob picks a random $\beta$ and sends $X_B = (H(N_B))^{\beta}$ to Alice together with a ZKP that $X_B$ is computed correctly based on his latest committed position
- Alice makes her move to ${u_A}'$, picks a random $\alpha$ and sends ${X_B}' = (X_B)^{\alpha}$ and $X_A = (H({u_A}'))^{\alpha}$ to Bob together with a ZKP that ${X_B}'$ is computed correctly based on the message sent by Bob in the previous round and that $X_A$ is a commitment to a valid move based on Alice's latest committed position
- Bob calculates ${X_A}' = (X_A)^{\beta}$ and checks if it intersects with any of the values in ${X_B}'$. If it does, Bob won the game, if it doesn't, next is Bob's turn. In order to claim the win, Bob must provide a ZKP of valid intersection

Next turn will be the same with Bob and Alice roles swapped. Note that each turn requires **two rounds of communications** between the parties.

<figure align="center">
<img src="https://hackmd.io/_uploads/ByMte0rnA.png" height="850">
<figcaption>
<a href="https://sequencediagram.org/index.html#initialData=actor%20Alice%0Aactor%20Bob%0A%0Agroup%20Alice's%20turn%0ABob-%3EAlice%3A%0AAlice-%3EBob%3A%0ABob-%3EBob%3A%20win%3F%0Aend%0Agroup%20Bob's%20turn%0AAlice-%3EBob%3A%0ABob-%3EAlice%3A%0AAlice-%3EAlice%3A%20win%3F%0Aend%0A%0A" target="_blank">Source</a>
</figcaption>
</figure>

### Keaki ZheroTag

In the Keaki version of ZheroTag we slightly modify the defintion of player. Now $P=f$, such that $f$ is a polynomial of degree 35 built by interpolating 36 points obtained by flattening the board matrix into an array of length 36. In such scenario $A$ is obtained by interpolating the evaluations (y-coordinates) $[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0]$ corresponding to x-coordinates from 1 to 36 (or, for efficiency reasons, at the roots of unity to the power from 1 to 36). Note than an evaluation of $1$ indicates a neighbour to Alice's position.

Here's a description of a turn performed by Alice:

- Alice makes her move to ${u_A}'$, reconstruct her polynomial $f_A$ and sends to Bob a KZG commitment $com_{f_A}$. Furthermore Alice encrypts her position under a set of 8 triples $com_{f_B}, \alpha, \beta$ where $com_{f_B}$ is the latest commitment shared by Bob, the alphas are the x-coordinates corresponding to the neighbours of ${u_A}'$ and the betas are 1. The commitment and the ciphertexts are shared with Bob together with a ZKP that $com_{f_A}$ is a commitment to a valid move based on Alice's latest committed position and that the ciphertexts are computed correctly
- Bob generates 8 opening proofs from his latest committed state for the x-coordinates corresponding to the neighbours of ${u_B}$ and trial decrypts the ciphertexts provided by Alice. If he's able to retrieve Alice's position, it means that Alice is in Bob's view and therefore he won. If he's not able, next is Bob's turn. In order to claim the win, Bob must provide a ZKP of valid decryption

Next turn will be the same with Bob and Alice roles swapped. Note that each turn now requires only **one round of communication** between the parties.

<figure align="center">
<img src="https://hackmd.io/_uploads/Hyfq8CHnA.png" height="850">
<figcaption>
<a
href="https://sequencediagram.org/index.html#initialData=actor%20Alice%0Aactor%20Bob%0A%0Agroup%20Alice's%20turn%0AAlice-%3EBob%3A%0ABob-%3EBob%3A%20win%3F%0Aend%0Agroup%20Bob's%20turn%0ABob-%3EAlice%3A%0AAlice-%3EAlice%3A%20win%3F%0Aend%0A" target="_blank">Source</a>
</figcaption>
</figure>