From The Source - Roll20 RNG Testing

UPDATE: Roll20 now uses QuantumRoll to generate "truly random" dice rolls. Read more on the wiki: https://wiki.roll20.net/QuantumRoll

But wait ... you don't think you can simply look at a big statistical report without any prior knowledge do you? Of course not! you need to read P-Values and the Null Hypothesis before delving into the arcane mysteries of the dieharder reports.

Ok, that was an invigorating read wasn't it?! Now on to the results:

• AES_OFB - The benchmark / gold-standard RNG built into dieharder
• Roll20 RNG - The cryptographically secure pure JS RNG used in Roll20
• https://gist.github.com/edalquist/4757300

• We can't prove that a RNG is good
• We can prove than a RNG is bad
• There is a catch, since a good RNG is RANDOM sometimes it might appear bad but actually be good
• So we run each test with a lot of data a lot of times and measure the statistical distribution of the result using some math that is over my head and end up with the P-Value
• P-Values very close either bound (1 or 0) are suspect and flagged as WEAK in the test suite

Just a little bit more for those interested in the guts of RNG in Roll20:

• We don't use JavaScript's Math.random(), the important details of its behavior are undefined in the JS spec and as a result it behaves differently on different OS/Browser combos.
• We do use a cryptographically secure RNG implemented 100% in JavaScript
• A high-quality server-side entropy source is used to seed each browser-side RNG, ensuring people get different RNG sequences
• The RNG accounts for modulo bias which is really important for applications like Roll20 that want a constrained random number
• http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modulo_bias
  

Soooooooo.... you say you rolled a 'few' times and it came up with random numbers? tsss. dicey. verrry.... dicey. But Ok, i hope i have good streaks all the time. Or my players will have em.... or not.... and.... euhm... yes... it keeps nagging... are you sure that 64 trillion times is enough?

Grinn... i predict the weather more accurate then i can predict these dice. :) thanks for explaining. now i can't sleep... :)

Akimotos said:

 are you sure that 64 trillion times is enough?

Thank you for posting this Eric! it is more than a bit over my head, but I appreciate the work done to ensure the system is solid.

Entrails?

Yes, but when will you create an RNG test that says your RNG gen is good enough?

Good job guys, look forward to those bug fixes (the few weaknesses)

I'm sorry Eric, you may pull one over on everyone else who doesn't understand the mathematical concepts behind RNG analysis. But you and I know you're not telling people the whole truth by leaving out any discussion of the Mydicehateme Principal, developed in the late 70's by Wolfgang Mydicehateme, and later confirmed by Dr. Effthat Dissisbullcrap of MIT. You can find more information on Wikipedia. Expose the truth. This math is a fraud on all Roll20 users.

David, I think Eric pointed out that RNGs in general will show up with a few 'weak' areas and that during testing those 'weak' areas change from test to test. The thing to take away from this is that a weak area is only weak it if is weak across multiple test sequences. Of course, I am not a coder and if I am incorrect I am sure Eric will correct me.

- Gauss

*laughs*

- Gauss

David C. said:

Yes, but when will you create an RNG test that says your RNG gen is good enough?

Good job guys, look forward to those bug fixes (the few weaknesses)

As for the second ... I'm guessing you didn't complete the assigned reading from the original post :)

Melvin McSnatch said:

I'm sorry Eric, you may pull one over on everyone else who doesn't understand the mathematical concepts behind RNG analysis. But you and I know you're not telling people the whole truth by leaving out any discussion of the Mydicehateme Principal, developed in the late 70's by Wolfgang Mydicehateme, and later confirmed by Dr. Effthat Dissisbullcrap of MIT. You can find more information on Wikipedia. Expose the truth. This math is a fraud on all Roll20 users.

I skipped the reading because I attempted to write an RNG tester myself a couple years back, and read Knuth instead. No, I'm not kidding, and yes, you really should just use dieharder.

First, yay for nerds being nerdy about randomness!

Those test results are spectacular. In fact, those results are so good, I'm guessing a TRNG (clock skew, atmospheric noise, radioactive decay, take your pick) would perform worse (if only slightly). I would like to know how exactly the server-side seed is generated. Do you guys use www.random.org 's atmospheric noise, or the common /dev/random noise you find in most computers? How often is that seed generated? Do you know if your seeds have a uniform distribution or a normal curve? Theoretically, none of this should matter, but the seed is as important as the generator.

The next step for me is to run my dice through an RNG test; I stopped using online die rollers because they're too good statistically. My group has seen far too many sessions where the GM gets 4 crits across an encounter, and the players rarely roll above a 5 (on a d20). I'd rather a die that had a 7% chance of rolling 15 and a 3% chance of rolling a 20 than a die that was guaranteed to roll all sides evenly.

Well you'll just have to trust that it is a very good source of entropy from a well tested RNG with a uniform distribution which meshes well with our RNG's desired seed pattern. Every time a user loads the Roll20 app new seed data is generated and fed into the RNG as well as as much entropy as we can gather from the user's browser.

Running dice through a test would be interesting but considering a simple run of dieharder using the defaults requires over 323 billion random numbers it would be rather hard to test a physical source. Even the Dice-O-Matic can only generate 1.33 million rolls a day which would require 666.2 years to run through the full suite of tests.

David B. said:

I'm guessing a TRNG (clock skew, atmospheric noise, radioactive decay, take your pick) would perform worse (if only slightly). 

Eric D. said:

David C. said:

Yes, but when will you create an RNG test that says your RNG gen is good enough?

Good job guys, look forward to those bug fixes (the few weaknesses)

So your first point isn't actually possible as far as I can tell.

As for the second ... I'm guessing you didn't complete the assigned reading from the original post :)

The first one is more of a joke, hence the cross out, because it's fallacy in its own right.

And I understand that the test may show up strong sometimes and weak other times, but there still always room for improvement.  I have no idea how complex the code is you have, so I don't really ever expect it to get updated as it works fine.  Dice are as inconclusive as anything else, but I do look forward to that weighted dice RNG

But really, there is no perfect RNG.

Okay, my brain ran off screaming for the hills after trying to read the article on P values and only returned after promises of mindless killing on the Xbox for most of this weekend. Good job on being through though! It's always interesting to see how stuff works in the background.

Troy W. said:

Okay, my brain ran off screaming for the hills after trying to read the article on P values and only returned after promises of mindless killing on the Xbox for most of this weekend. Good job on being through though! It's always interesting to see how stuff works in the background.

EDIT BY EricD: Lets keep the flaming to a minimum please

The best place to brush up on this stuff is the classic: The Art of Computer Programming Vol 2 : Semi-Numerical Algorithms by Donald Knuth.

The section on RNGs is comprehensive and enlightening. Your brain may still turn to jelly though, depends on your current SAN and the luck of the roll.

Yeah "fixing" the RNG algorithm is something for groups of people with PhD's in lots of arcane math and computer science fields. We're simply using a well known cryptographic RNG algorithm and the tests were done to verify we didn't screw up our implementation of said well known algorithm. As awesome as all the Roll20 devs are writing a from scratch RNG is probably out of our area of expertise :)

Ryan B. said:

David C. said:

Yes, but when will you create an RNG test that says your RNG gen is good enough?

Good job guys, look forward to those bug fixes (the few weaknesses)

EDIT BY EricD: Lets keep the flaming to a minimum please

Well, you actually can make really superb Random Number Generators and as Eric pointed out, you need math wizards for it, which I expected them to be, since expectations are a great thing to have. 

EDIT BY EricD: Lets keep the flaming to a minimum please

Ennera said:

David B. said:

I'm guessing a TRNG (clock skew, atmospheric noise, radioactive decay, take your pick) would perform worse (if only slightly). 

This is impossible. A true random number generator is going to produce truly random values; any electronic RNG is going to be psudo-random. 

Eric D. said:

Well you'll just have to trust that it is a very good source of entropy from a well tested RNG with a uniform distribution which meshes well with our RNG's desired seed pattern. Every time a user loads the Roll20 app new seed data is generated and fed into the RNG as well as as much entropy as we can gather from the user's browser.

Running dice through a test would be interesting but considering a simple run of dieharder using the defaults requires over 323 billion random numbers it would be rather hard to test a physical source. Even the Dice-O-Matic can only generate 1.33 million rolls a day which would require 666.2 years to run through the full suite of tests.