## Intro:

Multiplayer board games often rely on secrecy and strategic deception. Traditionally, a trusted orchestrator manages private information, but this introduces a trust assumption that can compromise fairness.

This report marks the first milestone of our research proposal, where we explore a cryptographic approach using multiparty computation (MPC) and zero-knowledge proofs (ZKPs) to enable verifiable interactions without revealing sensitive information. This eliminates the need for a central authority while maintaining game integrity.
Our implementation leverages the Noir programming language, which allows for efficient proof generation and recursive verification. The full research proposal is available here: [NRG 2](https://github.com/orgs/noir-lang/discussions/6359)

## Report highlights:

* Found and fixed bugs in [noir-bignum library](https://github.com/noir-lang/noir-bignum/pull/76)
* Found error in proposed operations bit-size
* During the writing of the proposal, a miscalculation was made concerning required bitlengths.
* This was caused by misinterpretation of poly-logarithmic terms in Landau notations (O vs. Õ).
* Correcting this error introduces a ×3 factor in ciphertext length, growing from \~370 to 1031\.
* Found necessity of bignum-paramgen web port
* In order to develop a web client the [paramgen crate](https://crates.io/crates/noir-bignum-paramgen) must be called from within a web context.
* Coded circuits for state queries and update
* Main circuits structure defined, would enable gameplay if verified right
* Auxiliary circuits to encrypt and decrypt board data got implemented too
* WIP: automated simulation example game flow, that interoperates circuits
* TODO: combine state update validation proofs in single aggregating proof
* Found vulnerability for the proposed scheme **(Important threat to validity)**
* Ciphertext distribution is observationally uniform, only without knowledge of the decryption key.
* Knowing such a key, allows decryption of the message, and of the exact noise in the sample too.
* The encryption process outputs samples whose noise is a sum of uniformly distributed numbers.
* Malicious agents may infer private data by statistical analysis of Irwin–Hall distribution.
* The concrete feasibility of such an attack is yet to be determined, but this might be mitigated.

Alternative schemes with uniform (re)encryption, that are also potentially feasible exists, such as the one presented [here](https://crypto.stanford.edu/~dabo/papers/2dnf.pdf), but would require provable composite-order elliptic curve operations. (Note: should not be directly implemented from supersingular curves, [since there are insecure](https://fse.studenttheses.ub.rug.nl/22732/1/bMATH_2020_SmitR.pdf).) (Note 2: this type of scheme seems to also allow for offline precomputation of re-encryption parameters, potentially reducing in-game proving times.)

Link to Github:
[https://github.com/fatlabsxyz/aztec-grant-pss](https://github.com/fatlabsxyz/aztec-grant-pss)

## Mechanics

**Objective:** The objective of the game is for factions to eliminate all rival agents and secure control of the building complex. The game ends when only one faction remains.
**Setup**: Game Board: A 4x4 grid represents the building complex.
**Factions and Agents:** Each faction starts with the same number of agents, deployed strategically on designated cells within their faction’s initial set of rooms.

### Deployment Phase

**Agent Deployment:** Each faction has 4 cells to deploy agents. Deployment configurations can vary (e.g., 4 agents in one cell, 2 agents in two cells, 1 different agent in 4 different cells).

**Initial Proof and Commitment:** Factions create a cryptographic proof of their initial agent positions to prove privately they are following the rules. Each faction generates a state commitment hash representing their private deployment.

**Verification:** Each faction publishes their proof and state commitment. Other factions verify these proofs to establish a shared private state.

### Turn Cycle

*Each epoch consists of the following steps:*

**Action Phase:** The active faction commands one agent to either:

- **Move:** Shift to an adjacent room.
- **Deploy Trap:** Place a trap in an adjacent room.

**Interaction and Updates:** Other factions communicate with the active faction to detect intersections between agents and traps or rival agents.

**Note**: The interactions are conducted inside a verifiable Oblivious Transfer context (equivalent to a proof of intersection). This enables interacting parties to not reveal secret **interacting** information to each other (OT), while also generating a proof of the validity of such transfers based on their respective secret states (ZK proofs). The latter enable interacting parties (and every other external observer, in this case other players) to trust state updates proofs, while not trusting players directly.

The active faction receives feedback on:

- Whether their trap successfully eliminated an enemy agent.
- Whether their movement was successful or encountered a trap/enemy agent.

**State Updates:** All factions update their private states based on the interactions. Factions publish their new state commitments.

**Agent Verification:** Each faction proves they have at least one surviving agent by providing cryptographic proofs.

**Repeat:** The cycle continues until only one faction remains.
Here is a graphic diagram of the previously explained flow:

[Flow](https://drive.google.com/file/d/1KWoncplJ2HM6fJPrb7QloOv6fsTzOjcj/view?usp=sharing)

## Game Design

Multiple untrusting factions compete to take control over a strategically placed building complex. Each group has the same number of agents, ready to be deployed on rooms of disjoint initial sets. Every epoch, command centers instruct one agent to either move or send a trap to an adjacent room. If any agent shares time and space with a trap or some agent of another team, both get annihilated. Given respect and etiquette, agencies engage in multiparty-computation to track respective agents. After losing all of its agents, factions inform it. The dispute is settled when only one remains.

(Note: could be aquatic warfare, but nowadays it is too complex and analogies break.)
(Noir Submarines: 🎶️"In the land of UltraHonk, lived a prover, with higher speed")

## Circuit architecture

Each agency commits to its deployed agents and traps by publishing its hash, along with some salt. Ideally, verifiable MPC tools would be leveraged but existing ones only work for 3 honest parties. New circuits are proposed to engage and prove messages validity from multiple oblivious transfers. There are no theoretical upper limits to participants with this project’s design, other than proving time. And trusting others' honesty is not required. This scales linearly with the number of secret states potentially involved in the interaction. (In this case, all other players, since they might or might not have agents or traps in the room acted upon.) After having created these proofs, agencies can justify state hash updates leaking no information.
![][image2]

## Involved circuits (with abstracted details)

***π\_keypair(decryption key, entropy, pub encryption key, pub decryption key hash)***
Used to prove valid keypair generation, and use the same decryption key later.

***π\_encrypt(entropy, pub message, pub encryption key, pub ciphertext)***
Used to prove valid (message, ciphertext) pairs, for an unknown encryption key.
(Note: this is the current performance bottleneck, but can be proved offline.)

***π\_deploys(agent positions, state salt, pub state digest)***
Used to prove valid initial state, and use it as starting point for evolutions.

***π\_queries(state, salt, pub digest, π\_encrypt, pub oblivious selectors, pub queries)***
Used to prove valid oblivious transfers queries, dependent on a private state.

***π\_answers(state, salt, pub digest, π\_queries, key, pub key hash, action, pub action hash, pub answers)***
Used to prove valid oblivious transfers answers, dependent on a private state.

***π\_updates(old state, old salt, pub old digest, new state, new salt, pub new digest, π\_answers, pub report)***
Used to prove valid state updates after receiving responses from a moving team.

***π\_reports(old (state, salt, pub digest), new (state, salt, pub digest), π\_updates, key, action, pub hashes)***
Used to prove valid moving team state updates after receiving private reports from others.

## Benchmarks

(8 cores, 8 GiB, Ultrahonk, approximated milliseconds, subject to change)

| Circuit | execute (compiled) | write vk | prove | verify |
| :---- | :---- | :---- | :---- | :---- |
| ***π\_keypair*** | 130.000 (22.000) | 19.800 | 31.300 | 162 |
| ***π\_encrypt*** | 22.600 (5.230) | 3.230 | 5.300 | 94 |
| ***π\_deploys*** | 237 (226) | 544 | 739 | 93 |
| ***π\_queries*** | 527 (396) | 563 | 745 | 93 |
| ***π\_answers*** | () | | | |
| ***π\_updates*** | () | | | |
| ***π\_reports*** | () | | | |

Total expected time per turn ≈ 3 minutes
(board size x π\_encrypt \+ π\_queries \+ π\_answers \+ π\_updates \+ π\_reports)
Could potentially be lowered to \< 1 min, if π\_encrypt's are precomputed offline.

## Next steps

* Wrap up initial circuits development, and hard-code verification keys
* Explore other similar *and feasible* possible *and fun* game mechanics
* Init networking layer development, describing a messaging interface