Multiplayer and RNG cheating
Moderators: Forum Moderators, Developers
Everyone can encrypt their number with a temporary random key. Then after everyone has exchanged their encrypted random numbers they all disclose their temporary keys. (Then everyones numbers are xor:ed or something to generate the final random number.)Elvish Pillager wrote:But what if one player waits to recieve all the other numbers, and then decides his own number based on that knowledge? You would need a trusted server to collect all the numbers before releasing them to everyone.Invisible Philosopher wrote:Here is a possibility:
Make each player generate a random number with a given number of bits. Exchange these and bitxor them all together to get the actual random number used. As long as a cheater can't deduce the random seed (and algorithm) of every other player (and as long as at least one is actually generating a [pseudo]random number!), the result will be random and unpredictable to everyone.
This can be streamlined to only require one broadcasted message per involved party for each random number if you send the encrypted random number for the next round at the same time as you disclose your key for the last round.
 Elvish_Pillager
 Posts: 8129
 Joined: May 28th, 2004, 10:21 am
 Location: Everywhere you think, nowhere you can possibly imagine.
 Contact:
But can't they create a selection of keys and then decide, after receiving all the other keys, which key to use, and thereby filter through the best result from any of the keys?
It's all fun and games until someone loses a lawsuit. Oh, and by the way, sending me private messages won't work. :/ If you must contact me, there's an email address listed on the website in my profile.
Right, so you need to make sure they send the right key. But that's easily fixed if you encrypt not just a number but a number and a short static textstring, for example "The number is: 38438434". Then they must disclose the right key or the decrypted message won't start with "The number is:"Elvish Pillager wrote:But can't they create a selection of keys and then decide, after receiving all the other keys, which key to use, and thereby filter through the best result from any of the keys?
Another thing to think about from a performance point of view is that we proberly only want to generate one "shared" random number per battle, then use that number to generate all the randomness the battle needs. If we have to exchange messages between clients before each blow a battle with multiple blows might lag if people have high latency connections. I guess this means we have to make sure every client uses the same random number generator regardless of compiler and OS, but that shouldn't be hard to do.

 Posts: 40
 Joined: November 26th, 2005, 10:09 am
 Contact:
Actually, Invisible Philosopher's protocol is quite elegant, except for the problem Elvish Pillager pointed out; luckily, it can be easily fixed. The type of RNG protocols we are have been discussing in this thread are based on what is known as a bit commitment scheme. Consider this RNG protocol which is done facetoface:
(1) Player 1 writes down a binary number on a piece of paper and places it facedown on the table so that no one else can see the number.
(2) Players 2, ..., n do the same.
(3) Everyone flips over their piece of paper, letting it be seen by all, and they XOR the numbers together to generate the result.
In this example, the paper serves as the bit commitment device; it prevents players from changing their numbers after learning what other people's numbers are. We can't use paper as a bit commitment device when communicating over a network, but a oneway hash function can serve exactly the same purpose. Here is the same protocol done using cryptography and the internet:
(1) Players j=1, ..., n each generate a random number X_j and send F(X_j) to everyone else, where F() is the oneway hash function.
(2) Each player sends their X_j to all the other players.
(3) Each player verifies that every X_j they received in step 2 hashes to the F(X_j) that they they received in step 1.
(4) To determine the result, XOR all of the X_j together.
(1) Player 1 writes down a binary number on a piece of paper and places it facedown on the table so that no one else can see the number.
(2) Players 2, ..., n do the same.
(3) Everyone flips over their piece of paper, letting it be seen by all, and they XOR the numbers together to generate the result.
In this example, the paper serves as the bit commitment device; it prevents players from changing their numbers after learning what other people's numbers are. We can't use paper as a bit commitment device when communicating over a network, but a oneway hash function can serve exactly the same purpose. Here is the same protocol done using cryptography and the internet:
(1) Players j=1, ..., n each generate a random number X_j and send F(X_j) to everyone else, where F() is the oneway hash function.
(2) Each player sends their X_j to all the other players.
(3) Each player verifies that every X_j they received in step 2 hashes to the F(X_j) that they they received in step 1.
(4) To determine the result, XOR all of the X_j together.

 Posts: 40
 Joined: November 26th, 2005, 10:09 am
 Contact:
I just thought of a practical improvement to the scheme which reduces the CPU and network overhead it imposes.
In combat we need a bunch of random numbers. Instead of doing this protocol once for every random number needed by the combat, we can just do the protocol once at the beginning of each combat and use the result as a seed value for a PRNG. The sequence of numbers the PRNG generates starting at this seed are then used to determine what happens in the combat. Since the PRNG is completely deterministic, it will generate the same sequence of numbers for all players.
Note that this works because once a combat starts there are no playermade decisions until after it is done. This is not the case in assigning traits to recruited units: after recruiting one unit, the player freely chooses what to do next.
In combat we need a bunch of random numbers. Instead of doing this protocol once for every random number needed by the combat, we can just do the protocol once at the beginning of each combat and use the result as a seed value for a PRNG. The sequence of numbers the PRNG generates starting at this seed are then used to determine what happens in the combat. Since the PRNG is completely deterministic, it will generate the same sequence of numbers for all players.
Note that this works because once a combat starts there are no playermade decisions until after it is done. This is not the case in assigning traits to recruited units: after recruiting one unit, the player freely chooses what to do next.
Right, that still allows the lesser cheat of RNG prediction, however I think it is best.
One issue: how many times an unseen opponent has cycled the RNG? If we allow them to inform you of arbitrary cycling, then they can cycle it to the desired outcome.
One issue: how many times an unseen opponent has cycled the RNG? If we allow them to inform you of arbitrary cycling, then they can cycle it to the desired outcome.
http://www.wesnoth.org/wiki/User:Sapient... "Looks like your skills saved us again. Uh, well at least, they saved Soarin's apple pie."

 Posts: 40
 Joined: November 26th, 2005, 10:09 am
 Contact:
No, it doesn't.Sapient wrote:Right, that still allows the lesser cheat of RNG prediction
The issue with psuedorandom number generators is that we don't want a player to be able to guess the values of the X that everyone else chose prior to choosing their own X_j and committing to it by broadcasting the hash F(X_j). If a player uses a PRNG to generate their X then it could theorectically be possible for others to guess the value. As people have pointed out, this issue can be solved by mixing an appropriate source of true entropy into the PRNG seed when each player goes to generate their X value.
At the beginning of each combat we will generate one truly random number using the multiparty protocol. Then we use this as seed for a PRNG; it is not possible to predict the output of the PRNG prior to knowing what seed it starts at. Once the seed has been randomly generated we want the output of the PRNG to be predictable and deterministic: that way all the players will agree on what the outcome of the combat is. However, there is no possibility of cheating because once the combat is initiated and the random seed is determined none of the players get to make any sort choices which affect the outcome of the combat.
This function is not bijection, true, but is reversible quite easily.Boucman wrote: example of non reversible function : f(x) = x*x
yup, two answers, +x and x
It is just the that the reverse function is multivalued.
Cryptography is chiefly concerned with functions which are easy to compute, while their reversions are hard (take long time) to compute. An example would be multiplication of large prime numbers.
Not quite so, as the number of roots of nth degree polynomial does not exceed n.now, with an high level polynome, the number of answers can grow very large indeed

 Retired Developer
 Posts: 2633
 Joined: March 22nd, 2004, 11:22 pm
 Location: An Earl's Roadstead
This seems to me like optimizing something before it is necessary. Since BfW is a Turn based strategy game, the overhead is going to be quite small. The optimization you are suggesting would therefore probably not be noticable, but it would make the code less usable for other Random numbers generated in the game.Wintersmith wrote:I just thought of a practical improvement to the scheme which reduces the CPU and network overhead it imposes.
"you can already do that with WML"
Fight Creeeping Biggerism!
http://www.wesnoth.org/forum/viewtopic. ... 760#131760
http://www.wesnoth.org/forum/viewtopic. ... 1358#11358

 Posts: 40
 Joined: November 26th, 2005, 10:09 am
 Contact:
It might speed things up. If we don't use this optimization, then we have to do the RNG protocol once for every swing in a combat; if there are any berserkers around, that can be a lot of swings. Then again, you may be right.Darth Fool wrote:Since BfW is a Turn based strategy game, the overhead is going to be quite small. The optimization you are suggesting would therefore probably not be noticable
Well, the optimization is only used for combat and nothing else. We would have to write a chunk of additional code to handle the random numbers in combats, but I don't think it would be anything huge. I suppose, however, that it would be more KISS to not mess with any optimization unless we really need to.Darth Fool wrote: it would make the code less usable for other Random numbers generated in the game

 Posts: 873
 Joined: July 4th, 2004, 9:14 pm
 Location: My imagination
 Contact:
The hash function should be one in which it is hard or impossible for a cheater to find a hash collision, because any collision is almost certainly enough to allow the cheater to manipulate the results by waiting for everyone else to send their random numbers before deciding which preimage of the hash the cheater gave to send.
Enough bits in the random number have to be done at once so that a cheater can't just prepare hashes of all possible random numbers and look up which one is designated by another player's hash.
Suppose we use 31 bits, which is how many rand() generates, AFAIK (though rand() is probably not unpredictable to an attacker, so it wouldn't be an appropriate RNG to use, and I don't know if 31 bits would be enough to account for the aforementioned reason). [complicated scheme] A normal swing's chance to hit comes in tenths (multiples of 10%), so there only need to be 10 equalprobability choices, requiring log[2] 10, approximately 3.32, bits per swing (I'm sure there's some way to extract such amounts of information...). Most fights have at most 9 swings total (e.g. Duelist melees Elvish Fighter), about 29.9 bits, still less than 31. That seems quite efficient enough. If a berserkerfight has to exchange 30 times as much information, that's still not a huge amount and is simpler than having a standardized PRNG for the purpose. [/complicated scheme] Then again, using a PRNG might be simpler than properly extracting fractional bits, and of course using the protocol for each random number needed is the simplest.
Enough bits in the random number have to be done at once so that a cheater can't just prepare hashes of all possible random numbers and look up which one is designated by another player's hash.
Suppose we use 31 bits, which is how many rand() generates, AFAIK (though rand() is probably not unpredictable to an attacker, so it wouldn't be an appropriate RNG to use, and I don't know if 31 bits would be enough to account for the aforementioned reason). [complicated scheme] A normal swing's chance to hit comes in tenths (multiples of 10%), so there only need to be 10 equalprobability choices, requiring log[2] 10, approximately 3.32, bits per swing (I'm sure there's some way to extract such amounts of information...). Most fights have at most 9 swings total (e.g. Duelist melees Elvish Fighter), about 29.9 bits, still less than 31. That seems quite efficient enough. If a berserkerfight has to exchange 30 times as much information, that's still not a huge amount and is simpler than having a standardized PRNG for the purpose. [/complicated scheme] Then again, using a PRNG might be simpler than properly extracting fractional bits, and of course using the protocol for each random number needed is the simplest.
There's nothing to stop the protocol being used with as many bits will be needed for the whole combat, at once, except that it would probably be just as complicated to implement as the PRNGincombat technique anyway. If combats sometimes being laggy (since they're shown in real time) is a problem, the protocol could be repeated before the animation as many times as are needed, if it's simpler to do it that way.Wintersmith wrote:If we don't use this optimization, then we have to do the RNG protocol once for every swing in a combat
Only the PRNGs used for the special combat optimization would need to be the same. If two players have different main RNGs, it is no problem (in fact, it's fine if some of them are even "true" random number generators, albeit unlikely to happen). The important thing is that a cheater not be able to predict players' main RNGs from the sequence of random numbers the player has already generated and exchanged.Gathers wrote:Another thing to think about from a performance point of view is that we proberly only want to generate one "shared" random number per battle, then use that number to generate all the randomness the battle needs. If we have to exchange messages between clients before each blow a battle with multiple blows might lag if people have high latency connections. I guess this means we have to make sure every client uses the same random number generator regardless of compiler and OS, but that shouldn't be hard to do.

 Posts: 40
 Joined: November 26th, 2005, 10:09 am
 Contact:
No one can fix the outcome of a particular random number, true. However, since the PRNG is deterministic everyone can see in advance what the sequence of "random" numbers will be and can alter their play accordingly.Tomsik wrote:Idea: Make PRNG and seed them with same value for all players on start of game, everyone get same number when nobody cheat