Protécol - Zero-Trust Peer-to-Peer Pokémon Battle Protocol

2023-01-16

Pokémon battles are a partial-knowledge nondeterministic turn-taking game. They're also great fun! Online battle simulations such as Showdown use a third-party server to enforce the rules: deciding which moves are valid, which random numbers are generated, and which player wins¹. But a malicious third party server could skew the odds against you, and an unreliable third party might not always be available to let you play - a peer-to-peer protocol would intead let two players battle directly with each other without relying on a third party to enforce the rules. It would also let you play the game asynchronously, for example by email or avian carrier.

But without a third party, what's to stop your opponent from cheating? Answer: a cryptographic protocol!

Properties of the game

Let's unpack the game of Pokémon a bit. Two players compete against each other by creating a team of up to six Pokémon, who battle against each other. Each player send one Pokémon at a time into the field, which can then play one of four possible moves, affecting the status and/or HP (Health Points) of their opponent's Pokémon. A player wins if all their opponent's Pokémon faint first².

Partial information

Information is partial - for example, the Pokémon in your opponent's team, their move sets, and max HP are not revealed to you at the start of the game. This lets your opponent cheat by not actually deciding upon their team, move sets, or stats at the start but choosing as they go along based on what you've played before. Absurdle demonstrates this concept well; it's an adversarial version of Wordle which, instead of choosing a word at the start for you to guess, picks a word to align with as few of your guesses as possible.

We will use a commitment scheme to solve this, so each player is forced to decide upon their team beforehand.

Additionally, since each player decides upon a move before the turn starts, your opponent could wait until you've decided upon your move before deciding upon theirs. We therefore need another commitment scheme, so that each move is made independently without knowledge of your opponent's move.

Nondeterminism

Some moves are nondeterministic - whether the move succeeds or the amount of damage it inflicts is decided by a random factor. This lets your opponent cheat by choosing or influencing the generated numbers to suit them, causing your moves to miss more often. We can use a distributed random number generation algorithm to solve this, where the number is guaranteed to be random even if your opponent is biased.

Verifiability

Finally, games should be verifiable and non-repudiable - this means that if a third party wants to check who won, a loss can't be claimed as a win, and you can't pretend you didn't play at all.

So how do we enforce these properties?

Channel security

Firstly, the two players need to be able to communicate through a secure channel. In our case, this means that each player knows that they're actually talking the the other player that they're intending to battle - authenticity. They also need to know that the moves they make aren't being tampered with en route - integrity.

We can solve this using any number of channel-securing protocols over the internet, such as TLS. This relies upon each player having an asymmetric key pair, with a public and private key each. We could alternatively implement this by signing messages using a tool like GnuPG or age. We're going to assume from here on that all communications happen in such a channel.

Within the channel, each move in the game needs to be signed by each player's private key - this allows third-parties to verify the identify of the players involved in the game, and therefore generate leaderboards etc. It's good practice to generate a one-time session key per player at the beginning of each game, preventing cryptanalysis (extracting information about their key) by the repeated playing of games.

Verifying move correctness

At the start of the game, neither player knows which Pokémon the other has, nor which moves they are capable of. This makes it difficult to check during the game whether a certain move is a valid play. We therefore use a commitment scheme to make each player commit to a certain Pokémon team at the beginning, without revealing any information about the team. At the end of the game, it can be checked that the only moves that were played are those committed to at the start.

This is done by publishing a hash of the team and a n-once before the game starts. The hash is unique to the team and the n-once, so can only be regenerated if the same team and n-once is input into the same hashing algorithm. Therefore it can be verified at the end of the game that the moves that were made were part of the initial team.

Also, because the n-once (a number used only once) is inside the hash, the opponent cannot reverse the hash by brute-forcing every team combination.

Certain optimisations can also be made to check obedience to the rules while in play - the opponent is guaranteed to be cheating if they use a move that their particular Pokémon cannot play, or if one of their Pokémon plays more than four types of move in a game³.

Verifying move outcomes

It's also hard to check what the valid outcome of a move should be. Even for simple moves that only inflict damage, the amount of damage inflicted depends on the stats of both the attacking and defending Pokémon, both of which are initially secret. The formula for calculating damage (in Gen 1 games) is as follows:

The important variables are A and D - the effective attack and defence stats of the Pokémon involved. The challenges in generating the random number random are discussed in section Nondeterministic moves.

All other parts of the formula are public knowledge, known to each party. Therefore, even if A and D were kept secret, a rearrangement of the formula after the damage is calculated would be enough to reveal the stat's true value As a result, there's no point trying to keep these stats secret when a move involving them is made - they should instead be communicated, so that each player can calculate the damage.

Verifying move ordering

Moves are made in a certain order, according to several factors including the attacking Pokémon's speed stat. The speed of a Pokémon is initially secret, although an estimation of it can be inferred by observing the order of play. It is then important to compare which move was the fastest, without revealing the precise speed stat of each Pokémon.

This is an instance of Yao's Millionaires' problem, and can be solved by a number of algorithms. The solution presented by Hsiao-Ying Lin and Wen-Guey Tzeng depends on the idea of constructing two sets, one for each number a and b, where the sets have a common element if and only if a > b.

Nondeterministic moves

The damage that Pokémon move inflicts, alongside whether it succeeds at all, are determined partially at random. However, neither player can trust their opponent to generate a truly random number, since the move's outcome and success can be influenced by choosing a good number.

We therefore employ a distributed random number generation algorithm. In this algorithm, each player A and B commits a number, n_a and n_b respectively. They commit the number by publishing its hash. Then once both commitments have been made, each player reveals their number, and computes

x = n_a ⊕ n_b

where ⊕ is bitwise XOR.

x_n can be used as a seed in a PRNG⁴ to generate a number in the expected range.

As Awerbuch and Scheideler note in Robust Random Number Generation for Peer-to-Peer Systems, this is a secure algorithm:

The XOR operation has the nice property that as long as at least one [number] is chosen uniformly at random and the other numbers are independent of it, x is distributed uniformly at random

However, they note that adversaries can wait for their opponent to reveal a number, and choose not to reveal their own. If the protocol can be made to restart, they can bias the game by only accepting advantageous numbers. This isn't a problem in Pokémon, since to not reveal a number halts the entire game, and this is our intended outcome in the case of tampering.

What might be an issue is if neither player can be trusted to actually generate a random, or even different, number each time. In this case, the number chosen will always be the same, making the game perfectly predictable. I believe that without an authoritative source of randomness, this is not a solvable problem; if a random number were chosen based on any of the previous game state, then this can simply be computed by each player, making the game predictable again.

Conclusion

I've presented the outline of a zero-trust peer-to-peer Pokémon battle protocol which implements the basics of Pokémon battle mechanics. However, I haven't made a proof of concept or attempted to formalise or verify the correctness of this protocol.

There's still a lot left of other related ideas think about, too.

Supporting doubles battles would require changes to the commitment schemes to support more players.

Implementation details, such as designing clients to show all calculable statistics, will be important. It would also be possible to write a program that speaks Protécol over the internet and the Pokémon link cable protocol to real GameBoy hardware, allowing online battles between players using real-world copies of the GameBoy games. Maybe DNS spoofing the defunct Nintendo servers could allow for similar battles on later consoles (I believe this approach was taken for certain closed Nintendo online services).

It would also be interesting to consider anti-forfeiting schemes, where a third party could do liveness checks - if a player doesn't sign a move in a certain period of time, the game can be considered forfeit.