Protécol  ZeroTrust PeertoPeer Pokémon Battle Protocol
20230116
Pokémon battles are a partialknowledge nondeterministic turntaking game. They're also great fun! Online battle simulations such as Showdown use a thirdparty server to enforce the rules: deciding which moves are valid, which random numbers are generated, and which player wins^{1}. 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 peertopeer 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^{2}.
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 nonrepudiable  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 channelsecuring 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 thirdparties to verify the identify of the players involved in the game, and therefore generate leaderboards etc. It's good practice to generate a onetime 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 nonce before the game starts. The hash is unique to the team and the nonce, so can only be regenerated if the same team and nonce 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 nonce (a number used only once) is inside the hash, the opponent cannot reverse the hash by bruteforcing 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^{3}.
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 HsiaoYing Lin and WenGuey 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^{4} to generate a number in the expected range.
As Awerbuch and Scheideler note in Robust Random Number Generation for PeertoPeer 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 zerotrust peertopeer 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 realworld 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 antiforfeiting 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.

They do have a pretty neat protocol, though. ↩︎

Moves have a total ordering within the turn, and their effects are applied sequentially. This means that it's always possible to determine which Pokémon is affected, and therefore faints, first. ↩︎

I don't know how evolutions, and therefore moveset changes, work in competitive battles. EDIT: lcnPylGDnU4H9OF informed me that evolutions can't occur during battles. The only possible moveset changes are by Dynamaxing, which can still be committed to at the start of the battle. ↩︎

PseudoRandom Number Generator ↩︎