noir-lang
[NRG#2 Proposal] Multiplayer games with shared map but private pieces #6359
Pablo-Dallegri
started this conversation in
[NRG#2] Private Shared States
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
Summary
An interesting mechanic of some multiplayer board games is the ability to execute strategies without revealing information about them until necessary. To do this, players must convince each other that their actions follow the game rules, while keeping them private. Some actions might even affect multiple players, while keeping others oblivious of the interaction details. Usual implementations of such games, require to trust private information to an orchestrating agent, who then reveals only necessary fragments. In this proposal, a solution is presented to avoid such trust assumption by a combination of multiparty computation (oblivious transfers) and zero-knowledge proofs.
Methodology
Kind of games that are in scope
Concretely, the intent is to implement a position-based shared board game for multiple players who take turns, and were pieces may have a designated type (such as four-player chess, Hexxagon(1993) or Hive), but with the twist that each player privately knows the position of its pieces. That is, in each move a player can choose a piece (or set of pieces) of its own to engage in one of multiple possible movements (according to the game rules), potentially affecting or depending on other players private pieces. As an additional mechanic, the neighborhoods of owned pieces could be revealed to the player who is about to take an action.
(Game mechanics are still to be decided and are subject to change in favor of better gaming experiences.)
Updates to private shared state
To keep track of the board state, after each turn, each player publishes a commitment to their pieces positions and types (using some game and turn specific salt), along with a validity proof of its construction.
At the start of the game, every player should have enough information to compute such proofs. Later, to privately compute how the board state changes with each turn, the moving player commits to some specific private action (with a proof of its validity according to game rules), and then engages in multiparty computation with every other player to find out who should be informed about what changes to their private states.
Since the moving player does not want to reveal its movement in the process if not needed, and must not learn other players pieces that are unaffected, a private set intersection must be computed between the potentially affected area determined by the move, and the piece set of every other player. Furthermore, validity proofs of such computations must be generated, so each involved player can later justify modifying its own private state to some other player that remains oblivious of the details of the interaction. From now on, the former will be referred to as "provable secret query" and the latter as "provable state update". In both cases, some inputs must be kept private, so zk-proofs are required.
Provable secret queries circuit
One possible way to implement provable secret queries could be to verify an homomorphically encrypted computation. That is, to send an encrypted representation of the area affected by the move, wait for the other parties to compute homomorphically, and receive encrypted representation of the intersection with opponent pieces, along with proofs of valid computations. Unfortunately, with our limited knowledge of all the existing homomorphic protocols, circuits that verify such computations can't be currently generated with manageable performance for a gaming context, because to achieve effective privacy (security parameter λ=128) they do either require constraining exponentiation to very long exponents (e.g. Paillier, 3072 bits), or require tensor products between binary decompositions of very long factors (e.g. Cheon-Stehlé 4.1, (λ+log λ)² = 18225 bits). And none of these cases is solved using Noir's big number arithmetic libraries.
After discarding the provable homomorphic computation option, our preliminary research advanced by considering raw multiparty computation primitives such as garbled circuits, to later discover that plain 1-2 oblivious transfers appears to be enough when using the previously mentioned Cheon-Stehlé homomorphic encryption scheme 3.1 just for the "cheap" verifiability of its asymmetric encryption and decryption procedures (only modular addition (~400) and product (2) operations of ~370 bits are needed, with no need to operate over the binary decomposition, so chunk representation can be exploited). Although far from optimal, future research may yield performance gains leveraging alternative encryption schemes. Using this verifiable oblivious transfer approach the protocol must be computed for each position on the board, and each piece type, scaling linearly in both.
To summarize, the proposed protocol for provable secret queries to be researched and implemented, consists of typical Oblivious Transfer messaging (adding message selector and encrypted noise, obliviously sending selected message plus noise), but where each message is accompanied with a proof justifying its validity as protocol message.
As mentioned previously these proofs of affected pieces get aggregated by each player to privately update their states in a provable way, showcasing a nice use case of Noir’s recursive verification.
Assumptions
Timeline and Deliverables
Weeks 1 to 5
By the end of week five the provable secret query protocol circuits are working, and stable.
Depending on the above point, verifiable private state update circuits, also stable by week five.
A local simulation of consensus among players on valid evolution of the shared state is made.
Weeks 6 to 7
After these weeks, details of the networking layer are worked out, implemented and operative.
The protocol is secure against eavesdroppers, so messages over a public medium might suffice.
(Message verifiability enables "on-chain" rankings or similar, but are out of scope for now.)
Having a functional core, some time will be dedicated to experiment on enabled game mechanics.
Weeks 8 to 12
By week twelve, a graphical web client enabling gameplay by mostly clicking stuff is created.
Also, a static explainer presenting the game mechanics to newcomers could be made available.
Team
Pablo Dallegri:
Joel Acosta:
Francisco B:
Start Date: 11/11
Questions:
Beta Was this translation helpful? Give feedback.
All reactions