Bitcoin Forum

There are some gambling sites usign hashing algorithms to generate a random number based on information from the blockchain.

For instance, http://SatoshiDice.com does a hmac_sha512(secret, transactionhash) to create a hash, and the first four bytes of that hash are used to determine the "lucky number" from 0 to 65,535.   Bets are placed on whether that lucky number will be below a certain level, with levels being

less than 64,000
less than 48,000
less than 32,768
less than 32,000
less than 24,000
etc,, down to
less than 4
less than 2
less than 1

Is the resultant four bytes of the hmac_sha512 hash truly random?

 - http://tools.ietf.org/html/rfc6234

BitLotto is another that uses the results of hashing based on the bet's transaction hash to determine the winner:
 - http://bitlotto.com   (Method for determining the winner: http://bitlotto.com/details.html )

Using the blockchain as a way to verify that cheating isn't occurring is a radical concept for gaming, but I'm not entirely convinced there are no advantages that can be gained by someone attempting to cheat.  BitLotto's approach seems to be more than adequately secure (hash message includes transaction id plus results of an event that happens after the transaction id was created.)  This one I'm not quite as sure about though the odds to the house are big enough that even finding a slight advantage probably wouldn't be profitable enough for the cheater to profit.

More discussion on the Satoshi Dice game here:
 - http://www.reddit.com/r/Bitcoin/comments/segz0/anyone_want_to_run_my_bitcoin_casino

[Update: These sites return the winnings to the same address from where they were sent.  Do not send bets using a hosted EWallet service like your account at Mt. Gox, PayTunia or InstaWallet, etc, as someone else will be the recipient of your winnings.  Only use a Bitcoin client like the Bitcoin.org client, or a Javascript wallet like BlockChain.info/wallet or StrongCoin.]

It works but since the secret is known to at least one person it does have the risk of people cheating who know the secret.
 
Truly random - No. Completely unpredictable and unique - Yes.

One thing to remember is that the tickets don't actually have to be random. They COULD be 1 to however many tickets. The only important part is that they are unique. SHA256 guarantees that no two tickets will have the same hash.

Hashing the tickets with another hash that DERIVES from truly random data guarantees that no one, no matter how much computing power they have, can gain ANY advantage. Each resulting hash will be unique and impossible to predict. And since they are all unique and the formula for sorting them is known, no one can cheat. For example in BitLotto, the winners end hash will likely have 00's in the front. There is no way to know what hash to create for the tx because the hash that will be added to it doesn't exist yet. It won't exist till all tickets are sold. And that is what makes it so secure. Using a "secret" stops the players from cheating but depends on the security of that secret. BitLotto used to use that for one draw a while ago but we wanted something that not even us could cheat even if we wanted to. We now have a system that no one, no matter how much computing power or inside knowledge, can cheat. The evidence is all in the blockchain.

In other words the way we use SHA256 ensures we have an single unpredictable winner. And that is essentially all a draw needs to contain. The mega millions numbers help ensure that at the end, the winner is unpredictable and random and can't be cheated.

Whoa, I didn't know you were using Mega Millions numbers. Why not use the hash of a block 20 blocks after the draw closes?

For one, the delay is no good -- lotto players want to know, with as little delay as possible, if they've hit the jackpot.

Using a block hash means the result is one that has the poentital to be be manipulated.  If the miner with big bets on BitLotto finds a valid hash and then discards it because it doesn't also result in a winning lotto ticket, then the results are going to end up being different.  The result in that case was manipulated.

So instead by using Mega Millions numbers as data that then gets hashed then this risk of manipulation no longer exists.

Right, a miner who plays more than 50 coin worth is incentivised to throw out a losing hash, seems like there should be a remedy, but I can't think of it. Using multiple block hashes still leaves the last one being the only one that matters from the player/miner point of view.

It says the MM numbers come a few hours later anyway.

It seems that no matter what, the last block can be manipulated if someone really wanted. Granted, if they did, they'd only get a TINY advantage for it would be likely that someone else would submit the next block. And who's to say they'd even be the one who would get the opportunity to throw a block out. It is a small risk but I wanted my lottery to be impossible to manipulate. Getting data from outside the blockchain seemed to be the only way to accomplish this.

It is small for an ordinary user (negative really since you forfiet the block reward), but could be arranged to be larger, a pool owner with 500BTC in tickets for example.

I understand using MM now, but I hope someone will come up with a a bitcoiny way.

Me too! Once the jackpot gets big enough it's pretty hard to have a verifiable random number that can't be manipulated. I don't mind using Mega Millions though as people can understand that easily how it's beyond my control! ;)

Here's a thread on the topic:
 - http://crypto.stackexchange.com/questions/767/how-to-fairly-select-a-random-number-for-a-game-without-trusting-a-third-party

And here's more detail:
 - http://crypto.stackexchange.com/questions/767/how-to-fairly-select-a-random-number-for-a-game-without-trusting-a-third-party#comment1303_770

hope you dont mind Stephen, Im sending most new additions to my list to this post. Helps admins get an idea of what users hope to see for random number selection.

How can a person like me implement this hashing random no generator for my lottery? I'll need someone who can volunteer to help me set it up (as I currently have no programming experience,specialty is professsional filmmaking.)

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.


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.

Ya, I should have said practically. ;)
Let's just say it would be pretty amazing to see and not something I'm going to worry about! ;)

I was told that people on here are more likely to enter my lottery if I use this method of random selection.What I don't get is why am I 'effectively' forced to use a system which:
a.completely confuses me in how to set it up/how it works
b.Why hasn't there a really simple explaination been made as to how it works (I thought bitcoin was meant to simplify things not complicate them.I'm from the mainstream so why cant things be simplified to the extent that the man on the street can say in confidence I want to embrace BTC with open arms instead of saying hmm,is this for me? type of moment).
c.Why can't other methods be satisfactory even though I know in the real world no one seems to complain about fairness issues so much? This is the only place here I see people complain about methods that traditionally worked (in real life,just look at the national lottery in UK-thats the method I want to use yet people say that's not random enough for my lottery.I'm really at a loss now)
d.My earlier questions about this haven't been answered.I want my queries addressed otheriwse I lose complete trust in a system that claims to make things better (straight and good quality answers = good business).

I don't want trolls but I like people who can understand things from an average man's point of view.My question is how can I make my lottery successfull on here? As people keep making suggestions about things I don't understand and I'm really thinking I should move this lottery thing elsewhere (unless the people here can show me compelling reasons to keep it on here).

I wonder where else I can move my business to online? I can't use SC as that's a waste of time/limited app support. Is there a section on here that can help people be successful in the BTC business line of things? (trade perhaps?)

a) You aren't being forced.  people have a right to use the services they wan't.  Complaining that customers want something different than you are offering has to be the most pointless whine ever.  Wouldn't you agree?  Either you offer what people wan't or you don't and run the risk of losing customers/business.

b) How much are you offering to pay?  Oh nothing?  So rephrased "Why hasn't someone else done the work to educate me so I can profit and stuff? Why damn it?  Don't people understand I want to be profitable?"

c) The UK lottery is much less likely to cheat than you are.  The anonymous nature of Bitcoin changes things.  Sure if you had the political and economic backing of the United Kingdom you likely would have an easier time convincing people your drawings are random.

d) Ok.  Feel free to lose confidence then.

I don't think he meant it that way D&T .I'm sure he's just a little frustrated with the slow progress of his business.Once things pick up for him,it'll all be good.Right now I think he's not sure where he's going with his lotto at the minute but all good businesses initially struggle to get going,then once they do,it's good.

Only replying to clarify what I meant by that.I don't mind freedom of choice.I was simply at a loss of how to do thing properly.I'm sure you can understand Deathand taxes.The initial frustration you have when you can't understand why things are the way they are.I do feel that people should be more open to feedback from a different perspective instead of trying to defend something.Secondly I'm not sure where you got the idea I need to offer to pay for something.Thirdly people expect thing to be explained in a way that they can understand.it is a right for all people to have (equal) oppourtunities (where I live,anyone who thinks different is just seen as silly but that's a separate matter).Forth you could have been a little more helpful by linkng me to a post on here that answers the questions I was asking.This why people ask questions beacuse they wish to learn something not to be critiqued at all.Fifth I have the right to be skeptical of anything that doesn't sound 100%.

I do accept however that the anonymous nature of bitcoin can complicate things as to checking that things are as they should be (ie no cheating/double spend attacks) but still I still think that from examples I've seen there are two clear approaches:1.Decentralised (where everything is done without a central server making sure things are ok and instead relies on peers with other methods-may not be easy for everyone to use/understand) and 2. Centralised (the system I'm more familiar with as I know the clear port of call if something goes wrong and easy for guys like me to use.Trust is heavily placed in a central place though meaning if that person is unscrupulous however,this can really cause problems.)

If you can understand my position,I'd like to hear from you again.

a. Randomness on a computer is a difficult subject; especially if you need to demonstrate no cheating.  
c. Other methods work too. Just saying you will use a random number will always have skeptics. It is simple though. I've seen Bitcoin lotteries come and go where the players are to "just trust" that the operator isn't cheating. The problem is that it is VERY easy to run a lottery and fake who wins that way. The operator could play themselves and just keep getting new random data until they win and post a screenshot of the winner and take all the funds.

BitLotto was created with a design that makes any such manipulation impossible. Even if I wanted to skew the results in my favor, I can't. The cheat-proof method does add a little complexity but it's actually not too complicated. (For those you can't understand it, they just base their opinion on people they trust who do understand it) You could just use regular tickets and a bunch off lottery balls. I wanted something that was unique to Bitcoins. With Bitcoin a completely anonymous, yet cheat-proof lottery can be run. That is something unique and in my opinion pretty cool! That's why I made BitLotto.

Are you really just curious how BitLotto works? If so, please reply in my BitLotto thread and I'll discuss it there if you want. That will help keep this thread on topic.

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.

Bitlotto thanks for the more helpful explaination about the fact that randomness thing.I have a generally good rep so it's safe for those to trust me. If only someone with the spare time could help me implement the system (just to satisfy the people who continue to raise this as an issue of my lotto even though I've deomstrated countless times that I'm not here to scam)

Other methods do work but as you say bitlotto,it always has skeptics (I don't know why but it just does). I think I will have to rebuild the PR for my lotto (thanks to gorgo1 for that tip by the way)

I think a PM would probably be better on discussing how to implement the measures in a way that's easy to understand for me (coding is too much for me.I'm better off as a professional filmmaker though rather than code stuff) as well as finally putting the cheating issue to rest as this is sinking my PR. I wanted to originally emulate the selection system based on UKs national lottery as it's much easier to administer for me (yay) while keeping the cheaters at bay (plus I love that style as it is on my lotto ticket for the euro millions lottery) but bitcoin is a completely different environment to the UKs national lottery so other methods have to be used (this is what happens with decentralisation,if there's no good way of verifying like with advanced maths,then cheating is an issue without a centralised entity)

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.

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.

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.

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.