Using SHA512 hash as random number generator for Gambling services

[bitlotto]

Back to the original topic.  I was curious about the possibility of SHA256 being "biased".  I generated 8 million random 256 bit numbers and looked at their hashes.  Distribution was random as far as I could tell.    I looked at both the rate of occurrance for each 32 but output value overall and then stratified by the input.   I stratified by both the first and last 32 bits of the input.  No detectable patterns or bias.

Look I am not a statistician (although I do work with them) so I wouldn't dare call it conclusive but at first look I could find no obvious bias in the output that would be exploitable.

One idea that may be useful for future designs is to simplify the number space.  Take say the lowest significant 32bits of the transaction hash.  With a smaller input it may be possible to more exhaustively analyze the situation.

For example rather than working with a random sample set you could analyze all 4 billion possible inputs and all 4 billion possible outputs. It eliminates the possibility that something is missed in the representative sample.

A bias that can arise from the input and turning it into a hash. Say you use lottery numbers from the "real world" and hash it. Since a lottery has only a LIMITED set of data you could calculate every combination and hash it. Then look at those hashes and see where anomalies occur. It won't be perfectly distributed. That's why I have to add block hashes too, so such analysis can't be done.

The more data you feed it though, the more evenly distributed the values should be.

[FreeMoney]

SHA256 guarantees that no two tickets will have the same hash.

That's not true.  There's no guarantee that SHA256 doesn't generate the same output for two different inputs.  In fact in general it's guaranteed that there are collisions in any hash function, since the input space is infinite and the output space is finite.  In practice of course it's incredibly unlikely that you'll ever have two tickets with the same hash.

Right, a miner who plays more than 50 coin worth is incentivised to throw out a losing hash

If he's mining in a pool, he doesn't need to have anything like 50 coins worth of lottery tickets, since the block he throws away won't cost him very much at all.

Gah, thx, how have I never thought of that.

Odd effect. If games dependent on the hash of blocks become popular it could actually start to hurt pools. Hurts bigger pools more than smaller because what you give up is something like your power/pool power times reward.

Player-miners would just need a little but of code to let them set rejection criteria and then start cashing in their teeny edge.

[nimda]

Back to the original topic.  I was curious about the possibility of SHA256 being "biased".  I generated 8 million random 256 bit numbers and looked at their hashes.  Distribution was random as far as I could tell.    I looked at both the rate of occurrance for each 32 but output value overall and then stratified by the input.   I stratified by both the first and last 32 bits of the input.  No detectable patterns or bias.

Look I am not a statistician (although I do work with them) so I wouldn't dare call it conclusive but at first look I could find no obvious bias in the output that would be exploitable.

One idea that may be useful for future designs is to simplify the number space.  Take say the lowest significant 32bits of the transaction hash.  With a smaller input it may be possible to more exhaustively analyze the situation.

For example rather than working with a random sample set you could analyze all 4 billion possible inputs and all 4 billion possible outputs. It eliminates the possibility that something is missed in the representative sample.

If we call SHA256 a pseudorandom generator G, we can test the bias of its outputs using any efficient algorithm A such that A(G(k <--^R-- 𝒦)) (the algorithm run on pseudorandom numbers) returns 0 with sufficiently higher probability (called the 'advantage') than A(r <--^R-- {0, 1}ⁿ) (the algorithm run on truly random numbers).

http://www.fourmilab.ch/random/ looks promising. I'll be back.

[cointastical]

Sorry to append to such an old post, but this is relevant:

On Bitcoin as a public randomness source
by Joseph Bonneau, Jeremy Clark, and Steven Goldfeder

- https://eprint.iacr.org/2015/1015.pdf

[adaseb]

Sorry to append to such an old post, but this is relevant:

On Bitcoin as a public randomness source
by Joseph Bonneau, Jeremy Clark, and Steven Goldfeder

- https://eprint.iacr.org/2015/1015.pdf

I read just the abstract since the entire PDF is too technical to read.

Basically they are saying that you can use the bitcoin hashes derived from blocks to use as a random number generator.

Since the bitcoin hashes are completely random, its a secure way of forming some beacons, like in the example a lottery.

Basically I don't think its really needed. When you nonce a regular SHA512 hash the results will be uniformly random.

Someone even ran a benchmark to prove this.