Timeline for A proof-of-work random number generation system for Pokémon
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 6, 2013 at 19:09 | comment | added | Joe Z. | [Hmm, so you can create a chatroom for an answer thread.] | |
| Jan 6, 2013 at 19:08 | comment | added | Joe Z. | let us continue this discussion in chat | |
| Jan 6, 2013 at 18:21 | comment | added | D.W. | @JoeZeng, that aspect of breeding doesn't seem problematic. You are just saying that some of the stats of a child are determined by the parent (copied from the parent), and some are random. So, use the PRNG only for the random ones; for the ones that are copied, copy them from the parent. When a user wants to participate in a tournament, they prove that all of their characters were generated properly, from the seed previously handed them by the tournament server. [...] To prove outputs were generated with seed $S$, the tournament server can recompute the outputs of the PRNG and compare. | |
| Jan 6, 2013 at 18:19 | comment | added | D.W. | @JoeZeng, I don't understand what you mean by brute-force, in this context. The output of the PRNG is fully determined by the seed, which is in turn fully determined by the central server (and not under the user's control). So I don't see what there is to brute-force. | |
| Jan 6, 2013 at 14:06 | comment | added | Joe Z. | (Given how many comments I'm giving, I'd propose we move this to chat, but Crypto has no chatroom. :( ) | |
| Jan 6, 2013 at 14:02 | comment | added | Joe Z. | Secondly, if the PRNG is a seeded generator as you say (instead of a cipher in counter mode like I initially proposed), how would you prove to the server that the values were generated with that seed? | |
| Jan 6, 2013 at 13:58 | comment | added | Joe Z. | As for breeding requiring special handling, it's because of this: When a Pokémon is bred, it is supposed to inherit three of the randomly generated values from the parents. See here: bulbapedia.bulbagarden.net/wiki/Breeding#Inheriting_stats So even if you use a different PRNG for each offspring, some of the generated values have to match. | |
| Jan 6, 2013 at 13:42 | comment | added | Joe Z. | @D.W. [continued] It's okay, though; trying to resolve this misunderstanding would give me more knowledge of the topic as well. | |
| Jan 6, 2013 at 13:39 | comment | added | Joe Z. | @D.W. The problem with that is that they're still very easy to brute-force. Remember that only about 36.6 bits of data are needed (in some cases even less), which is about 107 billion values on average, which would take perhaps about a day or two at most unless your algorithm is inherently really slow like Blum Blum Shub. And it might not be your density, but our mutual misunderstanding of what we're trying to accomplish (or maybe even my misunderstanding of the cryptographic concepts I'm talking about). | |
| Jan 6, 2013 at 7:57 | comment | added | D.W. | @JoeZeng, my apologies for being dense, but I did not understand any of your explanation why breeding needs special handling. As far as what is meant by a "seed", you might want to read about cryptographic PRNGs and how they work. The short version is that they generate an infinite stream of outputs $(y_1,y_2,y_3,\dots)=G(S)$ as a deterministic function of a seed $S$. Given any subset of the $y_i$'s, you cannot predict any of the other $y_j$'s or the seed $S$ better than blind guessing. | |
| Jan 6, 2013 at 5:59 | comment | added | user991 | No, he means that it's the initial state for an algorithm that outputs a stream of bits. $\hspace{1 in}$ | |
| Jan 6, 2013 at 4:33 | comment | added | Joe Z. | Okay, so, I'm not sure quite what you mean by using $S$ as the "seed" of the PRNG. Do you mean that it's sort of a global prefix to any pre-image for a CPRNG in counter mode? If so, yes, that would work, and it also has the added benefit of allowing timestamps to further reduce the attack space. If not, I'd need clarification on what sort of PRNG you're talking about, and how you'd be able to prove that they were generated from the PRNG in the first place. | |
| Jan 6, 2013 at 4:30 | comment | added | Joe Z. | The reason breeding needs special handling is because some of the generated values must match the parents' generated values - it can't be just the pre-images that match, which means that there needs to be some extra proof-of-work on the offspring. | |
| Jan 6, 2013 at 3:54 | comment | added | Joe Z. | I want to say yes, but I'll have to think it through for a while. If it does go through, this answer will probably be accepted. I'll keep you posted with any things I've thought up with comments to this answer. | |
| Jan 6, 2013 at 3:49 | history | answered | D.W. | CC BY-SA 3.0 |