A proof-of-work random number generation system for Pokémon [closed]

Question

(The original question that was here was considered too confusing, unclear, and rambling. You can still view it in the edit history, but the content is no longer useful by itself, and cannot be reasonably reconstructed into a question suitable for this site. The question object is still here by decision of a moderator, as a placeholder to preserve any reputation gained by the answerers of this question while it was still active, as well as to preserve the original question content in case any new questions are built upon this one.)

Answer 1

Fundamentally, all you can do is make it "hard" to roll a character. For example, if it takes about five seconds of computation to roll a character, that will annoy ordinary users as they wait 5 seconds, but it will limit cheaters to 12 rolls per minute. Of course, cheaters can always get their hands on more computing power, and the delays will annoy non-cheaters.

You can always limit users to a fixed number of rolls, say 5,000. At least that will limit cheaters to their pick of 5,000 characters. For legitimate users, just roll your counter over and re-issue characters. If a user notices, he's likely a cheater.

The software needs a license key which is can prove it owns without disclosing it. So that needs to be a public key of some kind. The combination of the license public key and a number in a limited range should be the PRNG's seed.

So, in sum:

1. When the software is licensed, issue a public/private keypair to the software. Sign the public key with the licensing private key.

2. To roll a character, combine a number from 0 to 5,000 (or whatever cap you choose) with the public key and use this to seed the PRNG. Sign the public key and the random number with the private key and combine that with the license signature.

3. To verify a character, use these steps:

A) Confirm that the signature of the software's key is valid using the licensing public key.

B) Confirm that the signature of the licensee's public key and index is valid using the software's key.

C) Roll the character using the index and licensee's public key and make sure the stats match.

That will limit each licensee to 5,000 characters.

Answer 2

Here is one simple solution.

After a new user installs the Pokemon software, before the new user can use that software (for tournament-eligible activities), they must register it with a central tournament server. The tournament server gives the user's software a random 128-bit seed $S$, and remembers this seed. The Pokemon software now creates a cryptographic-strength PRNG, seeded by $S$. At any point during game play that requires a new random number, the random number is obtained by pulling another output from the PRNG.

This allows off-line gameplay. If the user then wants to participate in a tournament server, they can later re-connect to the tournament server and prove that the Pokemon characters they generated have suitable stats by demonstrating that they were generated from the PRNG, using the seed $S$ that was assigned to them. Since the cryptographic PRNG is a deterministic function, this provides limited leeway for the sort of attacks you are talking about.

I can't tell if breeding really requires any special handling. If it does, here's one way to handle it: when you breed a new child, generate a 128-bit value $S'$ from the parent's PRNG. Then, use $S'$ as the seed for a PRNG associated with the child. This way, each Pokemon character has its own PRNG associated with it, seeded using a value that was in turn generated from some other PRNG (namely, it's parent's PRNG -- except in the case of parentless characters, which have their seed generated by the global PRNG, which in turn was seeded using the value $S$ obtained at registration time from the central server).

Does this do the trick?

Answer 3

It is hard to tell from this question, but I suspect that you may have managed to confuse yourself about what problem you have: i.e., that you've gotten caught up in a particular mechanism, and would benefit from taking a moment to step back and look at the actual requirements. I found it hard to extract the actual requirements from your question.

In these situations, it's always a good idea to ask yourself the question: What is my threat model? What kinds of threats do you need to defend against? What kinds of attack vectors are possible for an attacker?

For instance, a crucial question is: do you trust the game software that is running the game? It sounds like you want to say that you don't trust the software, but that leads you to an unsolvable problem.

Or, to put it another way, it seems like there's a simple solution to your problem. Your game software can generate truly random numbers using a suitable random number source (e.g., /dev/urandom or CryptGenRandom). There doesn't seem to be any reason to use a deterministic PRNG, and no reason for the random numbers to be derived from untrusted user inputs. Doesn't this solve all your problems? Why are you going into such complicated stuff, when there's a much simpler way to generate random numbers that also happens to eliminate the issues you're worried about? Is there some requirement that I'm missing?

If you're about to say "but the user could modify the game software's RNG to bias its output", my response will be "yes, that's always possible, and nothing you will ever do will ever be able to stop that". Realistically, you can't prevent reverse-engineering of your software. The user who is running your software could always run a modified version of your software that gives them better stats, and no amount of cryptography is ever to make that impossible. But in any case, these are the kinds of questions you should be working out when you think through your threat model.

I confess I had a hard time understanding what proof-of-work has to do with trusting that the random numbers you generate are trustworthy.