Bitcoin Forum
October 21, 2017, 09:38:42 PM
 News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 Home Help Search Donate Login Register
 Pages: 1 [2]  All
 Author Topic: Using SHA512 hash as random number generator for Gambling services  (Read 13366 times)
bitlotto
Hero Member

Offline

Activity: 672

BitLotto - best odds + best payouts + cheat-proof

 May 18, 2012, 10:06:33 PM

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.

*Next Draw Feb 1*  BitLotto: monthly raffle (0.25 BTC per ticket) Completely transparent and impossible to manipulate who wins. TOR
TOR2WEB
Donations to: 1JQdiQsjhV2uJ4Y8HFtdqteJsZhv835a8J are appreciated.
1508621922
Hero Member

Offline

Posts: 1508621922

Ignore
 1508621922

1508621922
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
FreeMoney
Legendary

Offline

Activity: 1246

Strength in numbers

 May 19, 2012, 12:57:03 AM

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.

Play Bitcoin Poker at sealswithclubs.eu. We're active and open to everyone.
nimda
Hero Member

Offline

Activity: 784

0xFB0D8D1534241423

 September 01, 2012, 02:30:46 PM

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}n) (the algorithm run on truly random numbers).

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

I recommend asking me for a signature from my GPG key before doing a trade. I will NEVER deny such a request.
 Pages: 1 [2]  All