(cont. from Substack blog)
The following describes, in simple terms, our approach for a trustless, decentralised implementation of among us. Details are given only when they are necessary to provide clarity. All else can be deduced from this description.
The game setup follows the approach mentioned in our blog post on deniability and Mental Mafia. We need to assign the roles of either Brainwashed Unit or Sentient Unit without trusting a central party and with only the player discovering their assigned role. Here we’ll give a simplified form of that approach. For a more detailed description you may read the original Geometry post.
To begin, the player generates a key pair where $K_i$ is the user’s respective public key for use in the shuffle. These keys are added to a public table $R_{key}$ onchain. Once all the keys are added, the first shuffle can begin.
Here is where the MACI operator comes into play. Along with all players $P_i, i \in 1...N$ we have an operator $O$ with a private key $k_w$ and corresponding public key $K_w$.
The first player initalises an array of roles $R_{role}$ and computes the aggregate public key $K_{agg}$ using keys from both players and operator. Then they shuffle this array of roles and encrypt it using the aggregate public key plus a masking factor. This is posted onchain with a proof of correct encryption and shuffle, verified by the contract.
Subsequent shuffles use a slightly different operation to “remask” the cards such that tracking the encrypted state becomes impossible as each player scrambles with their masking factor. The ith shuffled array of remasked roles $R_{role}^{i}$ is also posted onchain with a proof of correct shuffle, verified by the contract.
Once all players have remasked, the operator finally performs a remask operation in the same way as the players. Now we have an array which is shuffled and fully encrypted. The contract then assigns an index to each player in the array. We leave out details on how this could be done for simplicity’s sake.
Next, $\forall j \neq i, j\in 1...N$, $P_i$ will compute a reveal token for $P_j$ which it encrypts with the operator’s public key $K_w$ and a proof that it is a valid reveal for that specified card. They publish the token and proof onchain, where the proof is validated.
Once all the reveal proofs are validated, the operator $O$ will generate its own reveal token. It will also collect the encrypted reveal tokens and compute an aggregate reveal token. It then will send this aggregate token to the respective player along with a proof which the player validates client-side. (note: we can use designated verifier proof here to ensure the player cannot pass on this proof to others). Now only the player $P_i$ may peek at their role using their private key.
The operator does not learn anything about the roles of each player. However, if the operator were to be controlled by a player, they could still collude with other players by sharing the intermediate reveal tokens and thus allowing for proofs of “not Brainwashed Unit” to be validated between players.
In Tonk Attack, the “task round” involves the secret killing of a player. Furthermore, to prevent leaking information, we also need to obfuscate which players are legitimately completing their tasks.
Again, we will rely on the operator to mediate some of the game logic. Onchain, we can have an indexed Merkle Tree where each leaf is a tuple $(role, K_i^{target})$. Call this the “valid actions tree.” Furthermore, we can expand our algorithm so that the operator would also share a merkle path with each player during the role reveal. This Merkle path would correspond to a similar indexed Merkle Tree of tuples $(r_i, K_i)$ where $r_i$ is the $i$-th encrypted role, s.t. $unmask(r_i, k_i)=role$. This allows each player to post a “proof of role” without necessarily revealing who they are to anyone, including the operator.
First, a player will generate a proof of correct action: