An outline of a protocol for implementing a decentralized version of zk Mafia with no trusted third party.

## Setup
The game setup requires building a Semaphore membership group, creating a deck with the desired distribution of roles, shuffling & dealing the cards, allowing each user to peek at their role, and setting up the state that must be tracked & updated during gameplay.

### Creating the game
_a user clicks "Start new game"_
1. a new Semaphore group is created (set parameters at this point)
1. the player joins the game (all steps from [Joining the game](#joining-the-game) below)

### Joining the game
_a user clicks "Join game" for a game which has been created but for which gameplay has not yet started_
1. the player creates a Semaphore id
1. the player is added to the Semaphore membership group
1. the player generates a key pair for use in the shuffle; They publish`pub_key` and prove that they own the corresponding `secret_key`.
1. `pub_key` is added to the [player roles table](#player-roles-table). (encrypted card value will be added later; alternatively, we could save `pub_key` elsewhere and generate the table when all data is available)
1. `pub_key` is added to the [player status table](#player-status-table) as an `active` player

**Note:** this may change a bit according to the implementation of the [private action round](#Players-private-action-round)

### Assigning roles
_trigger action TBD_
Once this stage is initiated, no new players can join.

#### Create the deck
1. the deck is generated according to the desired settings for role distribution and specialized roles.
1. the [valid actions table](#valid-actions-table) is generated.
1. The contract computes the aggregate public key `pub_key_agg`
1. A player uses `pub_key_agg` to mask each card & publishes a proof that each card was masked correctly.
1. The contract verifies the proofs so all players agree on the initial deck (or all players could verify for themselves).

##### Questions
- how to define the roles in the game (e.g. ratio of Mafia to non-Mafia, other special roles, etc). It might make sense for the person who starts the game to specify something up front, but there are some limitations, e.g. if only 4 people join and they deside to start the shuffle instead of waiting then it probably doesn't make sense to have any roles beyond Mafia/Villager.

#### Shuffle the deck
1. The first player does a shuffle and remask of the deck, outputting an accompanying proof.
1. The contract verifies the proof of correct shuffle (or all players could verify for themselves).
1. Repeat for all players

#### Deal the cards / Assign the roles
1. Each player receives a masked card.
1. For every card except the one they received, each player computes a reveal token and proof that it is a valid reveal for the specified card and publishes the token and proof.
1. The contract uses the list of reveal tokens to create the encrypted card for each player which is encrypted only by their own masking. It updates (or creates) the mapping of `pub_key` to encrypted card in the [player roles table](#player-roles-table).
1. The reveal proof for each of the reveal tokens is verified. This could be done by the contract during the above step or each player could verify the reveal proofs for their own card.
1. Each player peeks at their own role.

#### Mafia reveal to each other
TBD

## Game play
The game proceeds in a series of rounds. In each round, the following happens:
1. The players take a private action round, which may or may not result in the deactivation of a player.
2. the contract updates the active players, checks the endgame condition, and updates state.
3. The players take a public vote, which results in the deactivation of a player.
4. the contract updates the active players, checks the endgame condition, and updates state.

### Players: private action round
Each player does the following:
1. Selects a (valid) action, which is a tuple of (`role`, `pub_key`), where `role` specifies a role that can take a single action (e.g mafia can kill or a doctor can save) and `pub_key` specifies the target of the action. If the player does not have a special role, they will select a _nonaction_ (null, null). All actions (including the _nonaction_) must exist in the contract's table of valid actions.
2. Creates a [proof of valid action](#proof-of-valid-action), which proves that the player's action is a valid action in the game and the player has the correct role to take it.
3. Sends (action, proof) as signal to Semaphore using a relay to obfuscate the source.

#### Proof of valid action
This is a zk proof where the player proves:
- They know the private key which corresponds to a specific public key `pub_key`. (This is the same proof they did when generating the key during setup)
- `ciphertext` decrypts to a specific card `role`.
- (`pub_key`, `ciphertext`) is in the [player roles table](#player-roles-table)
- the action taken is a valid action that matches the card's `role`, by checking that (`role`, `target_pub_key`) exists in the [valid actions table](#valid-actions-table), where `role` is the role that the `ciphertext` decrypted to above

#### Questions for the private action round:
**Question:** How to mask the action when sending to Semaphore so its not viewable in calldata? (how do they do this for voting?)
**Answer:** We can refer to the "private voting use case" docs from Semaphore V2 and solve it similarly. The steps above will need to be adjusted accordingly. https://semaphore.appliedzkp.org/docs/V2/use-cases/private-voting#generate-a-private-identity

**Question:** For a "detective" role, how to query and reveal a player's role?

### Contract: after the private action round
The contract does the following to identify the outcome of the players' round:
1. Uses semaphore to verify that a player's signal is valid (player is a member of the group, has not acted yet in this round, etc).
2. Verifies the player's [proof of valid action](#proof-of-valid-action).
3. After actions have been received and verified for all players, computes the result of the action round (e.g. person killed by Mafia, or no one, e.g. if kill/save balance out)

The contract then makes the required state updates:
- deactivate the specified player, if one was specified
- remove from the Semaphore membership group
- update status in contract to inactive
- update the table of valid action pairs
- remove all action pairs that target a player who has been deactivated
- action pairs involving an action that only a deactivated player could take should _not_ be removed, since this would leak information (e.g. if there was a doctor and the doctor was removed, the action to save someone should still exist. No one will be able to take it because no one will be able to prove it's valid for them.)
- check endgame conditions

### Players: public voting round
1. Each user sends a vote to the contract. This vote just needs to be another player's public key.

### Contract: after the public voting round
The contract does the following to identify the outcome of the players' vote:
1. Once all votes are received, tally the votes for each player and choose the player with the most votes. If there's no single player with the most votes, repeat the round (?).

The contract then makes the required state updates:
- deactivate the specified player (same process above, but one will always be specified in this case)
- update the table of valid action pairs (same process as above)
- check endgame conditions
- if the game is not over, update the external nullifier for the next round

## Endgame
The game ends when there are too few of one of the cohorts (mafia/non-mafia) remaining.
- All mafia are dead.
- Mafia outnumber the non-Mafia.

## State management

### Player roles table
A table mapping the public key of each player to their encrypted card (unmasked except for last unmasking).

### Valid actions table
A table of all valid action pairs (e.g. (action, player)). There must be exactly one _nonaction_, e.g. (null, null)

### Player status table
Keep track of player status mapping `pub_key` to `active` or `inactive` status. This could alternatively be managed in the roles table.

## References:
- Role assignment
- https://geometry.xyz/notebook/mental-poker-in-the-age-of-snarks-part-1
- https://github.com/geometryresearch/mental-poker/blob/main/barnett-smart-card-protocol/examples/round.rs
- Private actions
- https://semaphore.appliedzkp.org/
- https://semaphore.appliedzkp.org/docs/V2/use-cases/private-voting

## Notes:
- we need a relay for users to send their votes so that the source is obfuscated when the info goes to Semaphore
- in order to avoid non-Mafia users being able to prove they're not mafia (e.g. in a side channel), we could just give everyone a "not mafia" card