Multiplayer and RNG cheating

[Boucman]

example of non reversible function : f(x) = x*x

yup, two answers, +x and -x

now, with an high level polynome, the number of answers can grow very large indeed...

[Gathers]

Here is a possibility:

Make each player generate a random number with a given number of bits. Exchange these and bit-xor 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.

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.

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.)

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]

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?

[Gathers]

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?

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 text-string, for example "The number is: 38438434". Then they must disclose the right key or the decrypted message won't start with "The number is:"

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.

[Wintersmith]

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 face-to-face:

(1) Player 1 writes down a binary number on a piece of paper and places it face-down 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 one-way 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 one-way 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.

[Wintersmith]

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 player-made 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.

[Sapient]

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.

[Wintersmith]

Right, that still allows the lesser cheat of RNG prediction

No, it doesn't.

The issue with psuedo-random 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 multi-party 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.

[Ask_]

example of non reversible function : f(x) = x*x
yup, two answers, +x and -x

This function is not bijection, true, but is reversible quite easily.
It is just the that the reverse function is multi-valued.

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.

now, with an high level polynome, the number of answers can grow very large indeed

Not quite so, as the number of roots of n-th degree polynomial does not exceed n.

[Darth Fool]

I just thought of a practical improvement to the scheme which reduces the CPU and network overhead it imposes.

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]

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

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.

it would make the code less usable for other Random numbers generated in the game

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.

[Invisible Philosopher]

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 equal-probability 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 berserker-fight 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.

If we don't use this optimization, then we have to do the RNG protocol once for every swing in a combat

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 PRNG-in-combat 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.

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.

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.

[Tomsik]

Idea: Make PRNG and seed them with same value for all players on start of game, everyone get same number when nobody cheat, you don't have to send much data, it's simple and if somebody cheats everyone just get out of sync error.

[Wintersmith]

Idea: Make PRNG and seed them with same value for all players on start of game, everyone get same number when nobody cheat

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.