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, library). The idea presented here relies heavily on such primitive so I encourage you to go through the notes first.
Early proposals by Ingonyama and Yiğit Kılıçoğlu suggest looking into games such as 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:
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.
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.
ZheroTag is a peer-to-peer fog-of-war chess based on ZKP and Private Set Intersection (PSI) based on Diffie-Hellman. Here 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 be a player where is their position on the board and is a vector containing the neighbours of .
In such scenario
Here's a description of a turn performed by Alice:
Next turn will be the same with Bob and Alice roles swapped. Note that each turn requires two rounds of communications between the parties.
In the Keaki version of ZheroTag we slightly modify the defintion of player. Now , such that 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 is obtained by interpolating the evaluations (y-coordinates) 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 indicates a neighbour to Alice's position.
Here's a description of a turn performed by Alice:
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.