Deniability and Mental Mafia
Introducing the need for trustless third parties in onchain games
In this engineering blog, Tonk’s chief wizard Goblin Oats pulls back the curtain on our recent practical cryptographic testing. We hope it illustrates one of our core convictions - that video games are ridiculously powerful as a playground to battle-test privacy-oriented cryptography. We share our team’s journey from using ZK schemes to implement social deduction games, to implementing hidden information mechanics with multiparty computation, to discovering our need for an important research area - deniability.
Mental Mafia
“Mental Poker”, first formulated in 1979 by Rivest, Shamir and Adleman, describes the problem of playing a fair game of poker without the need for a trusted third party. We have taken Geometry’s improved Smart-Barnett protocol for Mental Poker and adapted it to the game Mafia. However, this reintroduces the pernicious specter of multiparty computation: collusion. We show one possible approach to mitigating these challenges inspired by MACI (Minimal anti-collusion infrastructure).
Who are we?
Tonk is a cryptography + gaming startup building out sensitive information channels for onchain game studios; by applying cutting-edge cryptographic primitives we turn autonomous worlds into privacy playgrounds.
“Autonomous worlds” are an important and contested topic, but in this context you can think of autonomous worlds as social worlds (especially game worlds) that run on a blockchain backend - think Minecraft on a fully P2P network.
Today, onchain game studios are constrained in their efforts to find game loops that are balanced, sustainable and fun, because they lack access to a game designer’s core weapon - hidden information mechanics. We are working to bake hidden information into worlds by using zero-knowledge proofs and other exotic cryptography to blend private state into public blockchains.
Implementing Mafia onchain
Mafia (a.k.a. “Werewolf”) is a social deduction game, played in person and hosted by a moderator, where players are secretly assigned roles as mafia or townspeople. At night, everyone closes their eyes, and the Mafia silently chooses someone to eliminate. By day, players discuss who they suspect as Mafia and vote to remove one player. The game continues with alternating night and day phases until either all mafia are eliminated, or they equal or outnumber the townspeople.
Mafia is trivial to run on a computer (e.g. the wildly successful Among Us), but incredibly challenging to run on a trustless computer where we cannot rely on trusted third party moderators.
Thus, to make “Mental Mafia”, our goal is simply to remove the moderator; we’ll use cryptography to do that. The functions of the moderator (listed below) need to be handled securely and trustlessly among the players:
We must ensure roles are correctly and randomly assigned to players.
We must selectively reveal roles only to particular players (in some versions of the game, the Mafia deliberate on who to eliminate and take collective action)
We must ensure action can be taken in the game without revealing who is taking the action.
We must reveal the role of the players eliminated through voting or actions.
If we pause to think about this for a minute, we see our standard toolkit of commit-reveal schemes and zkSNARKs may be useful, but it won’t get us all the way. That’s because the initial state needs to remain unknown to all players in the beginning. Later, players are only made aware of their role and nothing else. We cannot commit to or use proofs by themselves to generate unknown information. In order to generate unknown information, we need some form of multiparty computation (“MPC”). Even if we extend our cryptographic toolkit into the more exotic schemes like fully homomorphic encryption (“FHE”), we still rely on some MPC protocol underneath to manage the decryption key. Therefore, it seems that all roads lead to MPC.
(For an overview of different hidden information mechanics and games, and the various cryptographic techniques to achieve them, please refer to the Privacy Playgrounds Wiki).
MPC brings us back into the realm of protocol design, with malicious and semi-honest adversaries, last-mover advantages and undetectable collusion among the participants. Trust-minimized secure MPC protocols remains an active design space and absolutely critical to support the cutting-edge cryptographic methods necessary for everything from MEV to onchain social experiences.
From Mental Poker to Mental Mafia
History
We were inspired to try out Geometry’s improved Barnett-Smart protocol described in the blog post “Mental Poker in the Age of SNARKs”. In the post, Nicolas Mohnblatt describes a maliciously-secure MPC protocol for dealing poker hands through the use of verifiable l-out-of-l threshold masking functions (VTMFs) which were introduced by Barnett and Smart. If you are familiar with threshold encryption, l-out-of-l threshold masking simply means threshold encryption where every key holder needs to take a turn encrypting/re-encrypting and decrypting.
They chose to use a threshold variant of the ElGamal encryption scheme for the protocol and that is where our journey at Tonk began. At zkHack Lisbon, we bumped into Nicolas and mentioned our interest in a social deduction game. After a quick brainstorm of how we might adapt Mental Poker to Mafia, we were ready to try something out. The only trick was that we needed a library implementing the ElGamal encryption scheme, so for the hackathon, we added the encryption scheme to polygon’s Miden VM alongside Wei Jie.
Shortly afterward we won a Gitcoin grant to create a working version of the game zkMafia. This, we hope, will result in a library that stands on its own two legs - in essence, a library that allows Mafia-style social deduction and is secure enough to be used in high-stakes games. The work on this library is a collaboration with grjte from the Polygon Miden team.
We have ideas on how libraries of pure game mechanics, like our Mafia library, can combine with various IPs to create the seeds for autonomous worlds. We may speak more to this later in a separate blog post.
Techniques
Our adaption of the improved Barnett-Smart protocol is nearly identical up to the card draw where each card is a role in the game. Unlike in the poker example, we need to keep some accounting of the cards that have been drawn so that players can take actions throughout the game. This accounting may be held by each player individually or in a smart contract.
This introduces a collusion problem. If we keep some accounting of the cards that have been drawn - say, a merkle tree and a list of some encrypted information - such that players can generate proofs of correct action without revealing who they are, this also means the players can generate proofs attesting to their role, to each other. The correct strategy for each villager would be to generate proofs attesting to their role as villager and broadcast them to every participant. Those unable to generate their “proof of villager” are, by process of elimination, provably in the Mafia.
Collusion issues are pernicious in MPC scenarios and the overlaying of some external incentive mechanism illustrates the limitations of this particular protocol — it only works for games where each player is incentivized to hide their cards from each other. In order to make our protocol workable, we need to introduce a new cryptographic virtue: deniability.
You can think of deniability as the ability to lie about the use of cryptographic information. Consider the case where a journalist (Alice) and a whistleblower (Bob) are communicating using a secure encrypted channel. Their unique private keys could be coerced from them by an authoritarian power and used to prove their guilt. If they had communicated using a scheme with the property of deniability, it would be impossible to prove Alice or Bob really did send those messages. For more on deniability, see Kobi’s presentation.
Deniability in practice
MACI uses deniability to solve a similar problem. Using cryptography to ensure the correct execution of a vote is desirable, but allows voters to effectively prove their vote. If they can prove their vote, then their vote can be bought. In MACI, an “operator” is introduced to the application who will count the votes and prove the correctness of the count and the ballots using zkSNARKs.
Only the initial registry of keys is publicly visible and this allows voters to create proofs of their vote. The cast ballots are hidden by the operator. The primary trick is that a voter may cast a ballot or may take a change key action. In the scheme, a voter could create a proof of vote, but they wouldn’t be able to prove if that vote was actually counted (as it may have been for a key that is no longer valid).
The generalized MACI approach is something I think of as a “Trustless Third Party” because the execution is completely proven using zkSNARKs, but there is still a third party who maintains control over the data.
In our Mafia game, it may be possible to use a trustless operator who could obfuscate the shared game state and use zkSNARKs to take actions in the game provably on behalf of players. Granted, this operator still may collude with players in the game as the information is visible to the operator. The ideal scenario would be to create some kind of infrastructure to allow a player to host their own operator without concern. Such infrastructure needs to be trustless regarding execution and also needs to hide the information it’s executing on.
Note that a nice side effect of using such an approach at the protocol level is that we could also solve for many of the withholding problems plaguing MPC protocols in games.
Conclusion
If you are interested to explore how a trustless, blind operator might work in practice, then reach out to us at hello@tonk.gg, we’d love to hear from you!
@goblinoats
@tonk_gg
