Sign in to follow this  
AuthenticOwl

Unpredictable, ubiquitously rng seed

Recommended Posts

I was contemplating how to create a game that could be played by mail/email... the easiest thing would be to create it such that there is no randomness involved in gameplay... chess for example is a great PBM (play by mail) game b/c there is no dice, no drawing, etc. But... Personally I prefer my games to have at least some rng. The problem with rng over PBM is obviously synchronization or the RNG. However, if both players used the same seed and rolled values in the same order then both players would obtain the same results despite a lack of data communication. First I thought to just use the current date (or some operation based on the current date) as the seed. The issue with this is that a player could theoretically choose their actions, then since they already know the seed test the results... if they come out unfavorably they could re-order their actions and choose the order that is most advantageous. So, the goal is to find a value which is unknown to each player until after actions have been choosen. One option I had considered was, at the beginning of the game players agree on a company in the stock market... turns would be due before midnight and the following morning the stocks opening price would be the seed. Unfortunately stocks are not traded on the weekend, so players would be limited to only playing on weekdays. Can anyone think of an rng seed source that would produce a new unpredictable seed value at least once a day that could be found by any one with an internet connection and also does not require the users to synchronize when they look up the value? The source should also be reliable (i.e supplied from some site/source that is unlikely to disappear).

Share this post


Link to post
Share on other sites
There are several web sites and companies that do dice rolls online, then email or otherwise give the results to everyone.

You could use that for your seed. Whatever the daily third-party dice roll email says to use, you use. Nobody can predict what it will be that day, although they could peek ahead once the roll is known.

Share this post


Link to post
Share on other sites

@Tom Slooper: Sry, thx.

 

@Valrus: That site looks like a winner. In particular http://services.swpc.noaa.gov/text/daily-particle-indices.txt

 

@fastcall22: But if both players provide a chosen salt to each other the player who first receives their opponents salt could choose a salt that makes the final value most advantageous to themselves. The third party source still needs to be unpredictable unless the trading of actions where synchronized.

Share this post


Link to post
Share on other sites
The salt solution can be made to work using a cryptographically secure hash function, like MD5 (EDIT: or SHA-3 if you are paranoid), and a couple of extra messages. So each player picks a secret salt, computes its hash and sends it to the other player. Once a player has received the hash of the other player's salt, they reveal what their original salt was. When a player receives the salt from the other player, it's easy to verify that its hash is indeed what had been sent originally. Edited by Álvaro

Share this post


Link to post
Share on other sites

Hi

 

As far as I can tell:

 

Given that I know the algorithm of the game and how it process the random number into game data.

 

I could create a table of seeds and the next few random numbers each seed will create.

 

If I want particular outcome I could chose a seed from my table that gives useful random number for my case.

 

If I have a big table it could be impossible for the opponent to identify if the seed was "prepared" or not.

 

Sisofys.

Edited by Sisofys

Share this post


Link to post
Share on other sites

When a player receives the salt from the other player, it's easy to verify that its hash is indeed what had been sent originally.

Unfortunately this still suffers the out-of-order problem, where a player can decide his seed based on what the other player had sent.

the player who first receives their opponents salt could choose a salt that makes the final value most advantageous to themselves

In that case, perhaps a third party should act as a mediator, and hold all players' actions until he has received all players' actions.

Share this post


Link to post
Share on other sites

the player who first receives their opponents salt could choose a salt that makes the final value most advantageous to themselves

In that case, perhaps a third party should act as a mediator, and hold all players' actions until he has received all players' actions.

Just be sure to control how many can send back information if it's complex? Idk, just my two cents.

Edited by Madolite

Share this post


Link to post
Share on other sites

When a player receives the salt from the other player, it's easy to verify that its hash is indeed what had been sent originally.

Unfortunately this still suffers the out-of-order problem, where a player can decide his seed based on what the other player had sent.

the player who first receives their opponents salt could choose a salt that makes the final value most advantageous to themselves

In that case, perhaps a third party should act as a mediator, and hold all players' actions until he has received all players' actions.


I am not sure you understand what I proposed. First you exchange the hash of the salt, keeping the salt secret. Then you exchange the salt, and you can verify that the other side didn't cheat because you can verify the hash matches, so the other player's salt had been selected before you gave them your own salt.

Share this post


Link to post
Share on other sites

Hi.

Working a bit on Alvaros proposal.

Maybe something like this could work?

 

Suppose we have Player A and Player B

Player A
Decides to do:
Action A, Action B, Action C
In order to succeed upon these actions he need to roll a d6.

We want to make sure that Player A is not able to simulate the d6 before sending the mail, and is not able to find a seed that gives him the
results he wants.

Send information about Action A, Action B, Action C and in addition a number (PartialSeedA)
which can be a random number decided at the location of Player A and that Player B never need to create.

Encrypt: "Player A Name:" + PartialSeedA
in a part of the Mail with the Action A, Action B and Action C.

 

Player B
Decides to do:
Action D, Action E and need in the same way to roll d6.

Send information about Action D, Action E and in addition a number (PartialSeedB)
which can be a random number decided at the location of Player B and that Player A never need to create.

Encrypt "Player B Name:" + PartialSeedB
in a part of the Mail with the Action D, Action E.

-

When Player A receives the mail about actions from Player B he knows that Player B cannot do more manipulation to the seed and also not to change actions.
So Player A sends an decrypt key regarding his own PartialSeedA.
Player B decrypts the seed from Player A's mail and the text showing his name proofs that the encryption/decryption is "real".

 

In the same way Player B receives mail from Player A and sends his own decryption key to Player A.

 

Both players have now decrypted PartialSeedA and PartialSeedB - both combine these two into one new number that can be used as a seed.

 

If this protocol works smile.png it does probably not work so well for many players...

 

Both players' game logic now use the same seed to generate d6 results to resolve the Actions.

 

Sisofys

Edited by Sisofys

Share this post


Link to post
Share on other sites
I think that would work, but there is no point in using encryption and transmission of keys when a simple hash would do just fine. I'll give you an example:

I came up with a random 128-bit number (just and example; we could use any other length), whose hexadecimal representation is 266debcafafc93719c31d9013135b9be. Then I typed this in a Linux shell:

> echo 266debcafafc93719c31d9013135b9be | md5sum
cd288a7dac2b740d2426db919dee809a -

So in my first message I would send "cd288a7dac2b740d2426db919dee809a" to all other players. When I have received similar messages from all other players, I would send "266debcafafc93719c31d9013135b9be" to all other players. When I receive similar messages from other players, I would run md5sum on them to verify that their hashes match what I received initially. Then I would compute the XOR of the numbers for all the players, and use the result to seed some PRNG.

Share this post


Link to post
Share on other sites

At the risk of repeating myself overmuch (reply #6), This is a solved problem.

 

Tools like Secure Dice Roller already exist if you need occasional random numbers securely transferred to your friend.

 

You want a 32-bit random number seed?  Roll 8d16 and you've got a 32 bit number. If you need a 64-bit seed roll 16d16.

 

 

The number is sent to multiple people and can be verified if you don't trust your friends not to cheat with a forged email.

Share this post


Link to post
Share on other sites


The problem with using services like that is that sometimes they fail and there isn't much you can do about it.

 

They aren't the only one. Google finds dozens of them. If one goes out, send an email to the group "The dice site is down, rolling the numbers on this other site."

 


Also, the mathematician in me finds it inelegant to use external entities for something that can be solved without them.

 

Sounds like NIH syndrome.  The goal is to have random numbers delivered to a group of people.  One option is 30 seconds in Google and another 30 seconds on the site, another option is many hours of effort.  

 

For me, the answer is simple: roll the dice and play the game already. 

Share this post


Link to post
Share on other sites

The problem with using services like that is that sometimes they fail and there isn't much you can do about it.

 
They aren't the only one. Google finds dozens of them. If one goes out, send an email to the group "The dice site is down, rolling the numbers on this other site."
 
 
 

Also, the mathematician in me finds it inelegant to use external entities for something that can be solved without them.

 
Sounds like NIH syndrome.  The goal is to have random numbers delivered to a group of people.  One option is 30 seconds in Google and another 30 seconds on the site, another option is many hours of effort.  
 
For me, the answer is simple: roll the dice and play the game already.



I guess our difference of opinion comes from us having different mental pictures of what the game will look like. If it is literally people sending emails and doing everything by hand, sure an external service might make sense. But since the players are supposed to seed a PRNG and extract numbers from it, I figured there would be software involved and the exchange of messages can be automated. If you do this with an external service, it's not as easy as telling people what other service to use: You would need to patch the software.

I am not generally guilty of NIH syndrome: It's relying on external services that I object to. Besides the reliability issue, if the stakes in the game are high enough one player could bribe the external entity into producing whatever numbers she wants. If there is an easy cryptographic solution to the problem, introducing a party that needs to be trusted seems wrong. Granted, I am used to thinking about these problems in contexts where there are millions of dollars at stake (institutional trading), so my biases might be inappropriate for casual games.

Share this post


Link to post
Share on other sites
Thank you for all the suggestions. There are a lot of good ideas for various situations.

Currently, my plan is as follows:
Player A chooses their actions and sends the choices to player B.
Player B chooses their actions and send the choices to player A.

Choices are due before a set time. If both players receive the other players choices before the deadline then, after the deadline the players retrieve a seed from a source where the seed was generated at or after the deadline.
If either player does not receive the opponents choices before the deadline the game is either forfeit with the player who did send their orders winning or the players choose a new deadline.

This mean that, using the space weather site provided above, only one communication each way is required per day which can be sent at any point throughout the day and that communication does not need to have any non-game data piggy backing on it.

As far as the die rolling sites are concerned, they are likely very good in situations where the randomization is simple (You are using the value chosen directly) and the number of randomized choices is small.

As Far as context goes, I am thinking of the game being a war game where each player can give an order to every unit under their control per turn, which is why players would have an entire day to consider and record their actions, then the next moring when they start the game the player feeds their own and their opponents action list which determines the state of the game for their next set of moves.

I will likely end up sending the start state of the game along with the move set to ensure that the game remains in sync... but still the primary goal of requiring only a single email per day be sent would be fulfilled.



@FROB: Actually, I just re-read your suggestion... and realized that it is good no matter the number or complexity because as you said, it is only choosing the seed... this could be a very good solution esp. considering the turn lengths need not be restricted by the schedule of a third party site. The only wrinkle would be determining Who and when the dice rolling site be used... perhaps something like:
At the beginning of the game choose a player as host.
All players must submit their action lists to the host player
Once the host player receives the actions chosen by all other player he sends his actions to all other players then requests a die roll from the die roll provider site.

Share this post


Link to post
Share on other sites
Isn't it a problem that if I receive the other player's move I can pick my move in response? You can still solve that problem with my two-step approach (I am sure I am not the first person to think of it, but I don't know of a better name).

Share this post


Link to post
Share on other sites

With most pbm/pbem that I have played there would be a host (or host program) and a client (or client program).  As an example; The Vga Planets host program would set the seeds for the battles once the turn files were in and being processed by the host program.  Once you received your new turn file, each player would see the same seeded battles play out.

Even if there wasn't a host program, why do you think you would have to show one players actual move to the other player?  You could simply have a image (e.g. red light/green light) to tell if the other player has made their move.  Once both players locked in their moves you could then have whoever is acting as the host process get both moves and then create a random seed for the results of that turns actions.

Edited by TheRelic

Share this post


Link to post
Share on other sites

Isn't it a problem that if I receive the other player's move I can pick my move in response? You can still solve that problem with my two-step approach (I am sure I am not the first person to think of it, but I don't know of a better name).

 

It's called a commitment scheme.

Share this post


Link to post
Share on other sites

Isn't it a problem that if I receive the other player's move I can pick my move in response? You can still solve that problem with my two-step approach (I am sure I am not the first person to think of it, but I don't know of a better name).

 
It's called a commitment scheme.


Oh, yes, thanks! I asked a friend of mine that used to work in cryptography and he gave me the same name.

Share this post


Link to post
Share on other sites

I hadnt even considered that, having been focused on the rng algorithm.

so, along with this commitment scheme.

 

 1) Players choose their actions 

 2) the file is encrypted with a locally random number as the key.

 3) players share key when they have the other players actions. In order to prevent collusion each player would need to have the encrypted actions of all other players, not just the player they are sharing with. 

 

so in order to have simultaneous action resolution with accurate information (the results of your last action), each player (except the last to commit actions) must use two communications per turn?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this