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, 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:

  • 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 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

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
    β
    and sends
    XB=(H(NB))β
    to Alice together with a ZKP that
    XB
    is computed correctly based on his latest committed position
  • Alice makes her move to
    uA
    , picks a random
    α
    and sends
    XB=(XB)α
    and
    XA=(H(uA))α
    to Bob together with a ZKP that
    XB
    is computed correctly based on the message sent by Bob in the previous round and that
    XA
    is a commitment to a valid move based on Alice's latest committed position
  • Bob calculates
    XA=(XA)β
    and checks if it intersects with any of the values in
    XB
    . 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.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Source

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
    uA
    , reconstruct her polynomial
    fA
    and sends to Bob a KZG commitment
    comfA
    . Furthermore Alice encrypts her position under a set of 8 triples
    comfB,α,β
    where
    comfB
    is the latest commitment shared by Bob, the alphas are the x-coordinates corresponding to the neighbours of
    uA
    and the betas are 1. The commitment and the ciphertexts are shared with Bob together with a ZKP that
    comfA
    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
    uB
    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.

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Source