Pepe's Party Computation

Moving from a centralized gaming industry to a decentralized future in which individuals can shape the roadmap games are taking. "Pepe's Party Computation" uses zk-SNARKS and two-party computation to solve trustless self-policing and decentralized fog-of-war.

Description

The ultimate goal of this project is to give power back to the gaming community by building a fully decentralized game server. Due to the cost of building games and maintaining the expensive infrastructure necessary for running them, the game market has been aggregated into a few big game studios. The users are at the wits of the game studios when changes are made to games and they have no control over the roadmap the game will take. Pepe’s Party Computation addresses this problem by creating a fully decentralized game, which will eventually allow users to fork the game, creating their own versions and running it without any infrastructure required, as all the gaming logic is computed and verified by the clients participating in the game without any need for central servers. Technically, this is not a trivial problem. In centralized games, the game server is responsible for verifying that each player is following the rules of the game by taking the role of an all-knowing supervisor. In addition, the game server plays a crucial role in creating a fog-of-war, passing information only to players with the required access privileges. Most notably, this applies to the player's location on the map. Both of these functions seem difficult, if not impossible, to perform on the client side. The reason for this is that the clients cannot be trusted to self-police themselves to adhere to the game rules and also, by definition, cannot have all the information for creating and distributing information for a fog-of-war. However, it turns out that both of these problems are solvable from an information-theoretic point of view, using modern advanced cryptographic primitives. This is exactly what Pepe’s Party Computation archives in a basic form. More detailed information follows in the next section. Pepe’s Party Computation uses a combination of zk-SNARKS and Two-Party Computation to create a sequence of game states that can afterward be proven to have been correct and fair. For this prototype, the game works in coordinated rounds where the $j$-th player has the state $S^{(j)}_i$ in the $i$-th round. The player then commits to their currents state using a hash $h^{(j)}_i := \mathrm{pedersen}(S^{(j)}_i)$ from a collision-resistant hash function which they sign $s^{(j)}_i := \mathrm{sig}(h^{(j)}_i, sk^{(j)})$ and send to the other player along with a zk-Proof $\pi^{(j)}i$, verifying the state transition $S^(j){i-1} \to S^{(j)}i$ by using the hashes $h^{(j)}{i-1}, h^{(j)}i$ as public inputs. This allows all clients to verify the correctness of their opponent’s state transitions without revealing any information about the state itself. To conserve computational resources for the clients, the game is played optimistically with the verification being deferred to the end of the game, where the entire chain of SNARKS is verified at once. In our case, we have attached the game to a smart contract in order to allow for rewards to be issued based on a player’s in-game performance once the game outcome has been verified. To fit this arbitrarily long sequence of proofs into a single smart contract call, we can use a nice trick where pairs of adjacent transition proofs are recursively bundled together into a single proof, which takes a hash of the three hashes $\mathrm{pedersen}(h^{(j)}{i-1}, h^{(j)}i, h^{(j)}{i+1})$. Repeating this process for each layer with the public inputs from the previous layer creates a tree of proofs leaving only a single proof to be verified by the smart contract. This is to be done with a single hash as an input which is the merkle root for a merkle tree of the state transitions and proofs which was created in passing. One issue that remains to be solved under this architecture is the decentralized fog-of-war problem. In particular, here two players should only know the location of the other player if both are sufficiently close to each other. To address this issue, a two-party-computation scheme is introduced which jointly computes the Euclidean distance between both players without revealing the inputs to the opposing players. Only if the distance falls below a certain threshold, do both players start sharing their location with the other player in a tit-for-tat fashion, meaning they only send their location as long as the other player shares their location as well. The problem of the first-revel disadvantage can be evaded by not immediately sharing the exact position but rather a position area that is incrementally decreased in each iteration as long as the other player reciprocates. Using just this scheme it is still possible for players to enter inputs into the multi-party computation which are not consistent with their state commitment $h^{(j)}_i$. For the example of Yao’s garbled circuit, the state transition scheme is modified to additionally take the garbled circuit $C^{(j)}_i$ as a public input $\pi^{(j)}_i(h^{(j)}_i, C^{(j)}i$, additionally checking whether the computed distance is within a certain tolerance of $0$. The receiving player which must input their garbled position into the garbled circuit creates a similar proof by including the obfuscated position, which is sent to the other player for garbling as a public argument in their next state $S^{(j)}{i+1}$ such that the correctness of their input, too, can be verified. The proof schemes are implemented using the Noir language which allows the use of advanced cryptographic primitives using a high-level language. In the repository, you can find the circuits for verifying the state-to-state transition. The integration into the game is currently still a work in progress, particularly with the Two-Party Computation missing as this would have required the implementation of a TPC scheme in Noir.