Fog of war chess

# Fog of war chess ## Game state For ease, assume that the game state is a 8x8 matrix. Each troop can only view the positions that it can attack in the next move. Thus a player can only view the positions that all of its troops can attack. Assume the following game state 000$\alpha$0000 00000000 00000000 00000000 00000000 00000$\beta$00 00000000 00000000 Where $\alpha$ and $\beta$ are player A's and player B's troops, respectively. We call A's item state as: 000$\alpha$0000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 We call A's view state as: 00v0v000 00vvv000 00000000 00000000 00000000 00000000 00000000 00000000 We assume that each troop can only move to one of its neighbouring positions. Thus its view state is limited to the neighbouring positions. Simliarily B's item state is: 00000000 00000000 00000000 00000000 00000000 00000$\beta$00 00000000 00000000 And B's view state is: 00000000 00000000 00000000 00000000 0000vvv0 0000v0v0 0000vvv0 00000000 ## Encode game state as BFV plaintext Due to the particalar (BFV) encryption scheme we use it is much easier (& efficient) to store the item/view state as vector of {0,1} instead of a matrix. Thus we concatente row vectors of matrix starting with row 0. For example, A's item state is encoded as: 000$\alpha$0000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 **A's item state** [0001000000000000000000000000000000000000000000000000000000000000]$^T$ **A's item state encoded as BFV plaintext** Smilarily A's view state is encoded as: 00v0v000 00vvv000 00000000 00000000 00000000 00000000 00000000 00000000 **A's view state** [0010100000111000000000000000000000000000000000000000000000000000]$^T$ **A's view state encoded as BFV plaintext** ## >1 troop per player No modifications are required to allow each player to have >1 troops in the game. ## >1 and troops with various powers Like chess, it is desirable have troops with various powers (ex, Knight, Bishop, Queen, etc.). To do so, 1. We assign each troop type an $id$. Thus, item state changes to a vector of [0] + {id} 2. As before, in view state we set to 1 all the blocks that can be attacked by all the troops in aggregate. Note: Circuit that generates proof of valid item (/view) state transition may become more complex in this case. ## Move Let there be two players A and B. Assume that we are at the $i^{th}$ move of the game and it is A's turn to make a move. A's $(i-1)^{th}$ state - Item state: [0001000000000000000000000000000000000000000000000000000000000000]$^T$ View state: [0010100000111000000000000000000000000000000000000000000000000000]$^T$ B's $(i-1)^{th}$ state -[](https://)B's $(i-1)^{th}$ state -[](https://) Item state: [0000000000000000000000000000000000000000000000000000000000000001]$^T$ View state: [0000000000000000000000000000000000000000000000000000001100000010]$^T$ For $i^{th}$ move, A must satisfy following conditions: 1. Move from $i-1^{th}$ state to $i^{th}$ state is valid. 2. View state corresponding to $i^{th}$ state is valid After making the move locally, A encrypts its Item state using pk as $itemCt^A_{i}$ and View state using pk as $viewCt^A_{i}$. A then generates proof $\pi^A_{i}$ that proves all of the following: 1. Item state encrypted as $itemCt^A_{i}$ is a valid state transition from i-1^th item state to i^th item state. 2. View state encrypted as $viewCt^A_i$ corresponds to Item state i. A then sends $itemCt^A_{i}$, $viewCt^A_{i}$, and proof $\pi^A_{i}$ to server. Server verifies proof $\pi^A_{i}$ and accepts $itemCt^A_{i}$, $viewCt^A_{i}$. Now both A and B must update their view. For A to view whether any of B's troop are in its updated view, 1. B retrieves A's $viewCt^A_{i}$. Multiplies it with its $itemCt^B_{i-1}$ to produce a ciphertext that is equal to 1 at positions where $i^{th}$ view state of A intersects with posotions of items B's $i-1^{th}$ state. Let's call this ciphertext as $intersectCt^{B \rightarrow A}_{i}$. 2. B generates it secret share to decrypt $intersectCt^{B \rightarrow A}_i$ as $ss^{B \rightarrow A}_i$. Generates proof $\pi^{B \rightarrow A}_{intersect}$ that proves secret share to decrypt $intersectCt^{B \rightarrow A}_i$, $ss^{B \rightarrow A}_i$, is generated correctly. 3. B then sends the proof $\pi^{B \rightarrow A}_{intersect}$ with hash $hash(intersectCt^{B \rightarrow A}_i)$ as public input and secret share $ss^{B \rightarrow A}_i$ to the server. 4. Server verifies the proof and stores the secret share. 5. A knows its $viewCt^A_{i}$. It retrieves B's $itemCt^B_{i-1}$ from server, multiplies it with $viewCt^A_{i}$ to produce $intersectCt^{B \rightarrow A}_{i}$. 6. A checks $hash(intersectCt^{B \rightarrow A}_{i})$ matches hash sent by B to server. If it does not match, then B is dishonest. A must abort (Note: A can challenge. This will inevitably require server to compute ciphertext multiplication to resolve the disbute and punish B. But one cannot do this on-chain. It will be too expensive. A fraud proof type approach will be necessary to resolve the dispute. This is left as a future work). 7. A generates its own secret share to decrypt $intersectCt^{B \rightarrow A}_{i}$ to learn whether any of B's players are in its view. For B to view whether any of A's troop are in its view after A's move, 1. A retrives B's $viewCt^B_{i-1}$ and multiplies it with its updated item state ciphertext, $itemCt^A_{i}$, to produce $intersectCt^{A \rightarrow B}_{intersect}$. 2. A then generates its secret share $ss^{A \rightarrow B}_i$ to decrypt $intersectCt^{A \rightarrow B}_i$ and generates a proof $\pi^{A \rightarrow B}_{intersect}$ that proves that secret share has been generated correctly. 3. A then sends the proof $\pi^{A \rightarrow B}_{intersect}$, $hash(intersectCt^{A \rightarrow B}_i)$ as public input to proof, and secret share $ss^{A \rightarrow B}_i$ to the server. Server verifies the proof and stores the secret share. 4. B has its $viewCt^{B}_{i-1}$. It retrives A's updated $itemCt^A_{i}$ from the server. Multiples the two ciphertexts to produce $intersetCt^{A \rightarrow B}_i$. 5. Checks $hash(intersectCt^{A \rightarrow B}_i)$ matches the corresponding hash sent by A to the server. If match returns false, then A is dishonest. B must abort. 6. B generates it own secret share to decrypt $intersectCt^{A \rightarrow B}_i$. Then decrypts $intersectCt^{A \rightarrow B}_i$ to learn positions of A's troops, if any, that are in its view. We are now done with A's move. It is B's turn. We repeat the same procedure as above with A and B swapped. ## Attack Let's say after A's move, it B's turn. By mistake A made a bad move and one its troops is in B's view. This implies B can attack A's troop. Let's say position of A's troop is $x$. If B chooses to attack A's troop, in addition to instructions required to make a move, B must also: 1. Generate proof $\pi^i_{attack}$ that proves (a) $intersectCt^{A \rightarrow B}_i$ decrypts to a vector with position $x$ set to 1 (b) B's update item state has one of its troops at position $x$. 2. B sends postion $x$ and proof $\pi^i_{attack}$ to the server (Note: this is in addition to necessary data B needs to send to the server to make a valid move). Server verifies the proof, increases B's winning point by 1. In next move, A's state transition function must take into account that it has lost troop at position $x$. ## To dos 1. Add API for multi-party BFV to Janmajayamall/BFV 2. Figure out circuits that generate proof for item/view state transitions. 3. Figure out circuits that generate proof for correct BFV encryption, correct secret share in distributed decryption. 4. We rely on a neutral 3rd party to assure that opssition's item/view state ciphertexts are available to the player. In practice, we can replace neutral 3rd party with a DA layer. We still need to figure out interaction between DA layer and smart contract that verifies the proof.