Are transaction hashes predictable?

[SgtSpike]

Just curious... are transaction hashes predictable at all?

This is really a sub-question of a much broader question, which is, could the transaction hash be used to determine the winner of a lottery?  In other words, if I said, the first person to send 1 BTC to this address, and gets a transaction hash beginning with 3f, is there any way a person could abuse it to where they only actually complete the transaction if the hash begins with that 3f?

[casascius]

About the only abuse I could think of, is if someone solves a block and chooses to discard the block if they know it will cause the lottery outcome they don't want.  They would get the equivalent of another roll of the dice by doing so.

BUt they would also forfeit the 50 BTC for solving the block.  So that extra chance better be worth it.  And only the lucky miner (or pool operator) who solved the block being used in the lottery would have the opportunity to abuse this.

[DeathAndTaxes]

Just curious... are transaction hashes predictable at all?

This is really a sub-question of a much broader question, which is, could the transaction hash be used to determine the winner of a lottery?  In other words, if I said, the first person to send 1 BTC to this address, and gets a transaction hash beginning with 3f, is there any way a person could abuse it to where they only actually complete the transaction if the hash begins with that 3f?

The way you worded it is unclear.  Who is abusing what?  Why would someone only want the transaction if it begins with 3f?

If you are saying you are making a lottery and the winner is someone who sends 1 BTC and the hash begins with 3f then yes that is very exploitable.

You can't predict a hash but you can randomly attempt hashes from a pool of private keys until you find one which begins with 3f and then submit that one. 

[piuk]

You would need to exclude coinbase transactions.

[dooglus]

Just curious... are transaction hashes predictable at all?

They're as predictable as any other hash.  The algorithm used to generate the hash is known, so in that sense they're entirely predictable.  But you have to run the hashing algorithm to 'predict' them.

It would be possible to put a confirmation step in the client before sending a transaction: "this transaction with have hash xxxxxx: [send] [cancel].  Since the coins used in a transaction are randomly selected by the client, you may well be able to get a hash beginning with the required byte if you have enough private keys with funds on them, and enough patience.  Or the process could be automated.

[SgtSpike]

Just curious... are transaction hashes predictable at all?

This is really a sub-question of a much broader question, which is, could the transaction hash be used to determine the winner of a lottery?  In other words, if I said, the first person to send 1 BTC to this address, and gets a transaction hash beginning with 3f, is there any way a person could abuse it to where they only actually complete the transaction if the hash begins with that 3f?

The way you worded it is unclear.  Who is abusing what?  Why would someone only want the transaction if it begins with 3f?

If you are saying you are making a lottery and the winner is someone who sends 1 BTC and the hash begins with 3f then yes that is very exploitable.

You can't predict a hash but you can randomly attempt hashes from a pool of private keys until you find one which begins with 3f and then submit that one. 

Sorry, I really did a terrible job with wording that.  But, you got it right with your guess.

So, if I understand you correctly, the transaction hash is created when the transaction is created, not when the transaction is included in a block?  Therefore, whoever is creating the transaction can just try different combinations until the hash matches what they want?

[DeathAndTaxes]

So, if I understand you correctly, the transaction hash is created when the transaction is created, not when the transaction is included in a block?  Therefore, whoever is creating the transaction can just try different combinations until the hash matches what they want?

Correct.  Transactions have a transaction hash.  Blocks have a block hash.  For a block hash to be valid it has to be below the target which is determined by difficulty.  When we are hashing a block we are looking for a "small enough" block hash.  The transaction hashes and the merkle tree of all transactions in the block have already been determined.

[SgtSpike]

Cool, thanks for the info. 

[casascius]

I might have misunderstood the question.

If you want to gamble on the hash of the incoming transaction, it is easily exploitable.  One can calculate the hash of the payment they are about to make, and simply avoid sending it to the network if it doesn't meet the winning criteria.  They can try again, using different inputs or reordering them, rolling the dice repeatedly until they get the transaction hash prefix they want.

The fact that the Bitcoin client sends the transaction immediately without confirming the hash with the user isn't much of a defense to this.  This confirmation step would be trivial to add by someone looking to exploit it.

[theymos]

Transaction hashes could be used if you have some secret data that you combine with the hash. Then the lottery manager can manipulate things, though.

Block hashes can be used for randomness pretty safely after you hash them again to remove the leading zeroes. If you have a lottery that pays out much more than the block reward you might want to combine the hashes of several consecutive blocks (and maybe also their Merkle roots), since miners could try "re-rolling" a few times.

[SgtSpike]

Transaction hashes could be used if you have some secret data that you combine with the hash. Then the lottery manager can manipulate things, though.

Block hashes can be used for randomness pretty safely after you hash them again to remove the leading zeroes. If you have a lottery that pays out much more than the block reward you might want to combine the hashes of several consecutive blocks (and maybe also their Merkle roots), since miners could try "re-rolling" a few times.

Makes sense.  A winning ticket could be the combination of characters from the current and next block hash, plus characters from the transaction hash itself.

One other question then...

The block hashes and transaction hashes are both hexidecimal.  Are there any characters that would be more likely to appear at the beginning or the end, just based on the algorithms used?  I know that certain letters/numbers at the beginning of bitcoin addresses can be harder to find, because they show up less often as results in the algorithm used to create a public bitcoin address, so I am wondering if there is any similar quirks to the hashing of blocks or transactions...?

[dooglus]

Since the coins used in a transaction are randomly selected by the client, you may well be able to get a hash beginning with the required byte if you have enough private keys with funds on them, and enough patience.

Even simpler, you can keep attempting to spend the same amount from the same private key(s), but send the change to a different new address each time.  That's enough to change the transaction hash.

[casascius]

Realistically, I am not sure that most people necessarily care that their gambling games are cryptographically provable as random.  I mean, that's nice and all, and don't stop providing cryptographic proof just because I said this.  But proof should be an advanced feature that is visible as no more than an "advanced" hyperlink in these games, so the geeks among us can check it out.  The irony I see, I suppose, is that those of us who are geeky enough to understand the cryptographic proof, already understand that gambling is a losing proposition, and will probably do it just enough to check out the site and not much further.

But I have always said that PokerStars will make Bitcoin big if they ever do poker.  That, in spite of the fact that there's already quite a few little one-man poker sites that accept Bitcoin, that probably won't make much of a difference by themselves.

The difference I suppose, is that PokerStars has an enormous marketing budget.

Secondarily, PokerStars presumably has good controls against collusion.  That doesn't mean collusion is impossible, but a one-man poker stop is never going to have as sophisticated controls just by nature.

[theymos]

The block hashes and transaction hashes are both hexidecimal.  Are there any characters that would be more likely to appear at the beginning or the end, just based on the algorithms used?  I know that certain letters/numbers at the beginning of bitcoin addresses can be harder to find, because they show up less often as results in the algorithm used to create a public bitcoin address, so I am wondering if there is any similar quirks to the hashing of blocks or transactions...?

Block hashes must start with a certain number of zeroes, and the first digits after the zeroes will also be non-random. Probably the bits at the end are random, though I would hash the hash to make sure.

Each bit of cryptographic hash output is supposed to (ideally) have an equal chance of being a 1 or a 0.

[bitlotto]

I was trying at one time to make a lottery where the winner would be instant if they had a certain string at the beginning of the hash. Until I realized that the user could just re-do the transactions over and over without broadcasting it until they got what they wanted. That's pretty much why for BitLotto no one knows the winning string till after all the transactions are in. That way no one knows what to manipulate it to.

[pc]

You might be able to do something instant-like like this:

Come up with a random Secret, hash it, and publish Hash(Secret).
People submit transactions to you. You only validate a winner after a few confirmations (so it's not quite "instant")
If Hash(Secret+TransactionHash) starts with the Magic Numbers (00 or whatever), then the transaction wins.
You can then publish the Secret, so people can verify that the winning transaction in fact qualifies, and that no prior transaction qualified.

You'd need to handle if more than one winning transaction was found in the same block, perhaps by splitting the pot among them.

[SgtSpike]

You might be able to do something instant-like like this:

Come up with a random Secret, hash it, and publish Hash(Secret).
People submit transactions to you. You only validate a winner after a few confirmations (so it's not quite "instant")
If Hash(Secret+TransactionHash) starts with the Magic Numbers (00 or whatever), then the transaction wins.
You can then publish the Secret, so people can verify that the winning transaction in fact qualifies, and that no prior transaction qualified.

You'd need to handle if more than one winning transaction was found in the same block, perhaps by splitting the pot among them.

How would people know that I didn't just change the Secret if someone won so that the person wouldn't win?

[DeathAndTaxes]

How would people know that I didn't just change the Secret if someone won so that the person wouldn't win?

The published hash of secret.

Come up with a random Secret, hash it, and publish Hash(Secret).

After you announce a winner & the secret people can hash the secret themselves and compare it to the hashed secret you provided at the beginning of the "game". 

So there is no risk of you changing the secret.  The risk comes from you giving away the secret.  "Pst. try transactions until you get one which matches this secret and we will split the prize".

[SgtSpike]

How would people know that I didn't just change the Secret if someone won so that the person wouldn't win?

The published hash of secret.

Come up with a random Secret, hash it, and publish Hash(Secret).

After you announce a winner & the secret people can hash the secret themselves and compare it to the hashed secret you provided at the beginning of the "game". 

So there is no risk of you changing the secret.  The risk comes from you giving away the secret.  "Pst. try transactions until you get one which matches this secret and we will split the prize".

Got it.  So I certainly wouldn't want to give away the secret or the hashing method of the secret, but the hashed result of the secret allows people to verify that I'm not cheating them...

[DeathAndTaxes]

How would people know that I didn't just change the Secret if someone won so that the person wouldn't win?

The published hash of secret.

Come up with a random Secret, hash it, and publish Hash(Secret).

After you announce a winner & the secret people can hash the secret themselves and compare it to the hashed secret you provided at the beginning of the "game". 

So there is no risk of you changing the secret.  The risk comes from you giving away the secret.  "Pst. try transactions until you get one which matches this secret and we will split the prize".

Got it.  So I certainly wouldn't want to give away the secret or the hashing method of the secret, but the hashed result of the secret allows people to verify that I'm not cheating them...

Well two clarifications
1) you DO want to give away the hashing method.  You know Bitcoin uses SHA-256 hashes but that doesn't let you cheat.  You can't just finds a nonce from a required hash.  If you don't give away the exact hashing method then nobody can verify your work

2) You CAN still cheat.  You can't cheat by changing the secret after the fact but you CAN cheat by giving someone else (or yourself) the secret so they can only submit a winning ticket.

[SgtSpike]

How would people know that I didn't just change the Secret if someone won so that the person wouldn't win?

The published hash of secret.

Come up with a random Secret, hash it, and publish Hash(Secret).

After you announce a winner & the secret people can hash the secret themselves and compare it to the hashed secret you provided at the beginning of the "game".  

So there is no risk of you changing the secret.  The risk comes from you giving away the secret.  "Pst. try transactions until you get one which matches this secret and we will split the prize".

Got it.  So I certainly wouldn't want to give away the secret or the hashing method of the secret, but the hashed result of the secret allows people to verify that I'm not cheating them...

Well two clarifications
1) you DO want to give away the hashing method.  You know Bitcoin uses SHA-256 hashes but that doesn't let you cheat.  You can't just finds a nonce from a required hash.  If you don't give away the exact hashing method then nobody can verify your work

2) You CAN still cheat.  You can't cheat by changing the secret after the fact but you CAN cheat by giving someone else (or yourself) the secret so they can only submit a winning ticket.

Well, with #1, I was thinking that someone could attempt to find the secret.  I suppose if it's long enough though, it'd be secure.

Eh, good point on #2.  That kind of puts the whole idea back to square 1.

What about something like this:

If the last two chars of the transaction hash + the last two chars of the next block hash = 3f, you win.

[DeathAndTaxes]

Well, with #1, I was thinking that someone could attempt to find the secret.  I suppose if it's long enough though, it'd be secure.

Passing is the solution.

If you just hashed a secret it would be easy to find.  

If you only hash the secret and it is number "123" it would be trivial to hash every single number until you find it.

By padding you make that impossible.
"The winning ticket is: 123  This is some random data to make brute forcing the secret impossible 37849374238947389437438942738943"

The entropy of that random sequence at the end makes brute forcing the hash impossible.

If the last two chars of the transaction hash + the last two chars of the next block hash = 3f, you win.

That certainly works as long as the prize isn't so large that once could withhold blocks and try to force a particular result.  Given block rewards are 50BTC that provide a large incentive for someone to not cheat.   If the prize is 100 BTC then is no reason to withhold a block attempting to get a larger payout from prize pool (essentially gambling your block against cheating the lottery).  On the other hand if the prize was 100,000 BTC then the block reward would be insufficient to prevent cheating.

[SgtSpike]

Well, with #1, I was thinking that someone could attempt to find the secret.  I suppose if it's long enough though, it'd be secure.

Passing is the solution.

If you just hashed a secret it would be easy to find.  

If you only hash the secret and it is number "123" it would be trivial to hash every single number until you find it.

By padding you make that impossible.
"The winning ticket is: 123  This is some random data to make brute forcing the secret impossible 37849374238947389437438942738943"

The entropy of that random sequence at the end makes brute forcing the hash impossible.

If the last two chars of the transaction hash + the last two chars of the next block hash = 3f, you win.

That certainly works as long as the prize isn't so large that once could withhold blocks and try to force a particular result.  Given block rewards are 50BTC that provide a large incentive for someone to not cheat.   If the prize is 100 BTC then is no reason to withhold a block attempting to get a larger payout from prize pool (essentially gambling your block against cheating the lottery).  On the other hand if the prize was 100,000 BTC then the block reward would be insufficient to prevent cheating.

So it'd have to be something more like 6 or 8 blocks in the future, to ensure no one can hold blocks to try and win.  But, that's not really ideal... I'd rather be able to tell someone instantly whether they were a winner or not.

[DeathAndTaxes]

So it'd have to be something more like 6 or 8 blocks in the future, to ensure no one can hold blocks to try and win.  But, that's not really ideal... I'd rather be able to tell someone instantly whether they were a winner or not.

Well you just need to work out the math.  Essentially you want the "gain" from withholding a block and continuing to look for a block that wins the lottery to be < that gain from just submitting a block.  If there is no economic incentive to rig the drawing then likely it won't be rigged.  If there is an economic incentive to rig the drawing then it will be rigged.

[dooglus]

I'd rather be able to tell someone instantly whether they were a winner or not.

If you can tell someone instantly whether they won or not, you could tell your buddy whether he was about to win or not before he made his entry.  It seems like you can't have instant decidability as well as having it be impossible for you to cheat.

[dooglus]

So it'd have to be something more like 6 or 8 blocks in the future, to ensure no one can hold blocks to try and win.

That doesn't fix the problem at all.  I just look back 6 or 8 blocks for entries I made before submitting a block instead of looking back 1 block.

[SgtSpike]

So it'd have to be something more like 6 or 8 blocks in the future, to ensure no one can hold blocks to try and win.  But, that's not really ideal... I'd rather be able to tell someone instantly whether they were a winner or not.

Well you just need to work out the math.  Essentially you want the "gain" from withholding a block and continuing to look for a block that wins the lottery to be < that gain from just submitting a block.  If there is no economic incentive to rig the drawing then likely it won't be rigged.  If there is an economic incentive to rig the drawing then it will be rigged.

Just thought of something though - a person wouldn't necessarily have to mine x number of blocks in a row in order to "cheat" with this scheme, they just have to find the perfect hash in the future block selected that would match their transaction hash to win the lottery.

Eh, I don't like it.  Even basing it on both block hashes and transaction hashes, it's still full of holes and messy as all getout.

[DeathAndTaxes]

Just thought of something though - a person wouldn't necessarily have to mine x number of blocks in a row in order to "cheat" with this scheme, they just have to find the perfect hash in the future block selected that would match their transaction hash to win the lottery.

Eh, I don't like it.  Even basing it on both block hashes and transaction hashes, it's still full of holes and messy as all getout.

You can't find perfect hash without hashing.  There is no shortcut.  If there was I could find solution to every single block in a millisecond.

The only way an attacker can attack the lottery is by mining.  When mining against a block you hash a nonce, check it, if valid publish, if not valid try another nonce.  On average it takes quadrillions of attempts to find a solution to the block.

There is no shortcut.  Even if a miner knew that hash x gets him 1000 BTC he can't find x without randomly trying hashes until he finds it.

Hashes by definition are one way transactions (something) -> (hash).  You can't go (hash)->(something).  If you can then SHA-256 is broken and Bitcoin is in serious trouble.

[bitlotto]

The higher the prize the more someone may try cheating by manipulating what blocks they submit. I decided to add real world data from the mega millions lottery to eliminate any cheating for my lottery. Cheating block hashes would be pretty hard though. It would have to be worth the effort as they would be throwing away 50 BTC every time they didn't submit the block AND they would be racing to do it before someone else submitted one. It would be tricky. Not impossible though. 

[RandyFolds]

Transaction hashes could be used if you have some secret data that you combine with the hash. Then the lottery manager can manipulate things, though.

Block hashes can be used for randomness pretty safely after you hash them again to remove the leading zeroes. If you have a lottery that pays out much more than the block reward you might want to combine the hashes of several consecutive blocks (and maybe also their Merkle roots), since miners could try "re-rolling" a few times.

You need to use MegaMillions or Powerball values in the hash. Then you rely on an already never-been-hacked ultra-secure method to generate the winning number. If they hacked the lottery, $300 million is gonna be their goal, not our chump change.

e:^^damn, beat to the punch again.
2nd e: beat to the punch twice. goodness. my speed reading is only in my mind, apparently.

[SgtSpike]

Just thought of something though - a person wouldn't necessarily have to mine x number of blocks in a row in order to "cheat" with this scheme, they just have to find the perfect hash in the future block selected that would match their transaction hash to win the lottery.

Eh, I don't like it.  Even basing it on both block hashes and transaction hashes, it's still full of holes and messy as all getout.

You can't find perfect hash without hashing.  There is no shortcut.  If there was I could find solution to every single block in a millisecond.

The only way an attacker can attack the lottery is by mining.  When mining against a block you hash a nonce, check it, if valid publish, if not valid try another nonce.  On average it takes quadrillions of attempts to find a solution to the block.

There is no shortcut.  Even if a miner knew that hash x gets him 1000 BTC he can't find x without randomly trying hashes until he finds it.

Hashes by definition are one way transactions (something) -> (hash).  You can't go (hash)->(something).  If you can then SHA-256 is broken and Bitcoin is in serious trouble.

Actually.... that's a good point.  As long as the entry fee is lower than the block reward, it should be fine.  No one is going to throw away a block when they have equal chances of winning just by buying another ticket.

The higher the prize the more someone may try cheating by manipulating what blocks they submit. I decided to add real world data from the mega millions lottery to eliminate any cheating for my lottery. Cheating block hashes would be pretty hard though. It would have to be worth the effort as they would be throwing away 50 BTC every time they didn't submit the block AND they would be racing to do it before someone else submitted one. It would be tricky. Not impossible though.  

Real-world data is a nice touch.  Easily verifiable, indisputable, and no one can modify it.

[finway]

Nnonce is the ticket.   000000 is the proof

[freequant]

A simple way of being sure that no-one including the operator can cheat by using the information of the target pattern is to use a pattern that hasn't yet been generated at the time the betting takes place.
The process that generates the value of reference must be random and not easily controllable by any one.
You can use for instance the N last bytes of a future block hash.
Or the hash of the close price of some large stock index.
 

[SgtSpike]

Nnonce is the ticket.   000000 is the proof

How could someone use a nonce as a ticket?  The nonce is created by the miner finding the block, and doesn't require said miner to actually purchase a ticket by sending coins to an address.  This makes no sense to me.

A simple way of being sure that no-one including the operator can cheat by using the information of the target pattern is to use a pattern that hasn't yet been generated at the time the betting takes place.
The process that generates the value of reference must be random and not easily controllable by any one.
You can use for instance the N last bytes of a future block hash.
Or the hash of the close price of some large stock index.

So what's wrong with simply using last 5 of transaction hash = last 5 of block hash in a future block?

[freequant]

A simple way of being sure that no-one including the operator can cheat by using the information of the target pattern is to use a pattern that hasn't yet been generated at the time the betting takes place.
The process that generates the value of reference must be random and not easily controllable by any one.
You can use for instance the N last bytes of a future block hash.
Or the hash of the close price of some large stock index.

So what's wrong with simply using last 5 of transaction hash = last 5 of block hash in a future block?

Nothing wrong if the number of the block that will be taken as reference is decided in advance and you close the bet before the block that precedes the chosen block is issued.
The block hash cannot be manipulated to match a given bet.
But someone can place a bet that matches a block he found right before submitting the block on the network.
If bets are tied to transactions, there is a good way to rule this out : stipulate that valid bets are bets which transaction was already confirmed at the time the reference block was found.
In that case, you don't even need a reference block. The first block that matches any of the previously confirmed transactions designates the winner.

[SgtSpike]

A simple way of being sure that no-one including the operator can cheat by using the information of the target pattern is to use a pattern that hasn't yet been generated at the time the betting takes place.
The process that generates the value of reference must be random and not easily controllable by any one.
You can use for instance the N last bytes of a future block hash.
Or the hash of the close price of some large stock index.

So what's wrong with simply using last 5 of transaction hash = last 5 of block hash in a future block?

Nothing wrong if the number of the block that will be taken as reference is decided in advance and you close the bet before the block that precedes the chosen block is issued.
The block hash cannot be manipulated to match a given bet.
But someone can place a bet that matches a block he found right before submitting the block on the network.
If bets are tied to transactions, there is a good way to rule this out : stipulate that valid bets are bets which transaction was already confirmed at the time the reference block was found.
In that case, you don't even need a reference block. The first block that matches any of the previously confirmed transactions designates the winner.

Right, we're on the same page with that one then.

[phantomcircuit]

Just curious... are transaction hashes predictable at all?

This is really a sub-question of a much broader question, which is, could the transaction hash be used to determine the winner of a lottery?  In other words, if I said, the first person to send 1 BTC to this address, and gets a transaction hash beginning with 3f, is there any way a person could abuse it to where they only actually complete the transaction if the hash begins with that 3f?

They could simply generate a ton of transactions until their hash matched.

[SgtSpike]

Just curious... are transaction hashes predictable at all?

This is really a sub-question of a much broader question, which is, could the transaction hash be used to determine the winner of a lottery?  In other words, if I said, the first person to send 1 BTC to this address, and gets a transaction hash beginning with 3f, is there any way a person could abuse it to where they only actually complete the transaction if the hash begins with that 3f?

They could simply generate a ton of transactions until their hash matched.

You seem to have missed the rest of the discussion. 

[Zotia]

I have a simple way to make it nearly impossible for anyone to cheat (including operators of large mining pools).


X = "Secret Password"
Y = hash("Secret Password")
Z = hash(hash("Secret Password"))


1) The person conducting the lottery makes up X and keeps it secret.  (Make sure it is a very long password).  
2) The person conducting the lottery keeps Y secret.
3) The person conducting the lottery posts Z publicly.  Z is not yet used for anything.
4) Specify to everyone who is going to be betting what block hash will be used.
5) Bets are taken.  (No more bets are taken before or after this step).
6) Wait for the block to be created and wait for 6-12 blocks after that.
7) Use Y and the block hash to produce a random number that is used to determine the result of the lottery.
8) The person conducting the lottery publicly posts Y (and optionally X).  If the hash of Y doesn't produce Z, the person conducting the lottery is shown to be cheating.  (However, the person conducting the lottery could just run away with your BTC without needing to make a fake X/Y/Z, so this is not something I need to protect against).



If the hashing method and secret password are sufficiently strong, then I only weakness I see is that if the person conducting the lottery is also the operator of a large mining pool the he could choose to forfeit valid blocks to alter the results of the lottery.






After writing this post, I realized there might be an even easier way -- use asymmetric encryption.
-Keep the private key private and the public key public.
-Encrypt the block hash with private key.
-Verify the result with public key.
-Use the same key set every time (since your private key will not be revealed).

[bitlotto]

I have a simple way to make it nearly impossible for anyone to cheat (including operators of large mining pools).

Your methods mostly stop the users from cheating. There would be nothing that prevents the operator from cheating either by not submitting blocks or even sharing the secret password/key with a small percentage of people. I tried that method to. Ultimately I ended up moving to using mega million numbers for the "cheat proof" element.

Using block hashes is good enough AS LONG as the reward is smaller than the block reward. Even if the prize was bigger it would make more sense for someone to mine for 50 BTC than to throw away a block for a slim chance of winning 100 BTC. BUT as the prize gets really big it becomes an issue. 

[SgtSpike]

I have a simple way to make it nearly impossible for anyone to cheat (including operators of large mining pools).

Your methods mostly stop the users from cheating. There would be nothing that prevents the operator from cheating either by not submitting blocks or even sharing the secret password/key with a small percentage of people. I tried that method to. Ultimately I ended up moving to using mega million numbers for the "cheat proof" element.

Using block hashes is good enough AS LONG as the reward is smaller than the block reward. Even if the prize was bigger it would make more sense for someone to mine for 50 BTC than to throw away a block for a slim chance of winning 100 BTC. BUT as the prize gets really big it becomes an issue. 

I don't think it becomes an issue no matter what size the lottery is.

Think about it.  If the prize is 100,000 BTC, and the tickets are 1 BTC each, then for a lottery that is set up properly, there'll be a less than 1/100,000 chance that the block hash will match a transaction hash that a miner might try to match (say, their own entry).  So a miner would have to come across a block that both matches the difficulty criteria AND matches the 1/100,000 chance in order to win on their own ticket.  And no one is going to throw away a 50 BTC block on the off chance that they might find another block with the right 1/100,000 hash.

As long as the ticket cost is less than the block reward, there's no reason to worry about a miner purposefully trying to alter the outcome of a lottery.

[DeathAndTaxes]

I don't think it becomes an issue no matter what size the lottery is.

Think about it.  If the prize is 100,000 BTC, and the tickets are 1 BTC each, then for a lottery that is set up properly, there'll be a less than 1/100,000 chance that the block hash will match a transaction hash that a miner might try to match (say, their own entry).  So a miner would have to come across a block that both matches the difficulty criteria AND matches the 1/100,000 chance in order to win on their own ticket.  And no one is going to throw away a 50 BTC block on the off chance that they might find another block with the right 1/100,000 hash.

As long as the ticket cost is less than the block reward, there's no reason to worry about a miner purposefully trying to alter the outcome of a lottery.

The only issue would come from lottery where reward rolls over if their is no jackpot winner but the tickets are good for one drawing only (like all traditional real world state lottos).  In that instance it is possible for each ticket to have a greater than 1 NAV (i.e. a 1 BTC ticket could be worth 1.2 BTC).  A creative miner then could submit a large number of tickets and attempt to mine blocks until he wins. 

Still even then it would require a significant amount of hashing power to be a plausible attack and would only be viable when the lotto award is greater than average chance to win (i.e. 1 in 10,000 chance to win jackpot on 1 BTC ticket but jackpot is estimated to be 11,800 BTC). 

[SgtSpike]

I don't think it becomes an issue no matter what size the lottery is.

Think about it.  If the prize is 100,000 BTC, and the tickets are 1 BTC each, then for a lottery that is set up properly, there'll be a less than 1/100,000 chance that the block hash will match a transaction hash that a miner might try to match (say, their own entry).  So a miner would have to come across a block that both matches the difficulty criteria AND matches the 1/100,000 chance in order to win on their own ticket.  And no one is going to throw away a 50 BTC block on the off chance that they might find another block with the right 1/100,000 hash.

As long as the ticket cost is less than the block reward, there's no reason to worry about a miner purposefully trying to alter the outcome of a lottery.

The only issue would come from lottery where reward rolls over if their is no jackpot winner but the tickets are good for one drawing only (like all traditional real world state lottos).  In that instance it is possible for each ticket to have a greater than 1 NAV (i.e. a 1 BTC ticket could be worth 1.2 BTC).  A creative miner then could submit a large number of tickets and attempt to mine blocks until he wins. 

Still even then it would require a significant amount of hashing power to be a plausible attack and would only be viable when the lotto award is greater than average chance to win (i.e. 1 in 10,000 chance to win jackpot on 1 BTC ticket but jackpot is estimated to be 11,800 BTC). 

Hmmmm... not sure that I agree, but let's see what the calculations say.

If a miner bought 1,000 tickets for 1 BTC each on a 1 in 10,000 chance jackpot, then he technically has a 1 in 10 chance of the next block matching one of his tickets.  Now also say he has 10 GH/s of hashing power, so he has about 1 in 800 chance of finding the next block.  In total then, his chances of himself finding a block that matches one of his tickets is 1 in 8,000.

In order for him to toss his block and find another one, the jackpot would need to be at least 50 * 8,000, or 400,000 BTC.  Otherwise, it wouldn't be worth it given his chances - he would rather take the 50 BTC from finding a block.

Even if he had 100 GH/s of hashing power, the jackpot would need to be at least 50 * 800, or 40,000 BTC, in order for him to toss his block.

If he had bought half the tickets AND had 100 GH/s of hashing power, the jackpot would need to be at least 50 * 160, or 8,000 BTC, in order for him to toss his block.

That last scenario might be what you were envisioning.  I don't think the jackpot has to necessarily be greater than the odds, but it just depends on how much hashing power the miner in question has.  I suppose the NAV would have to be low enough to ensure that it wouldn't be worth tossing a block even to the person with the greatest amount of hashing power, no matter how many tickets are bought.  To protect against Tycho using his 3500 GH/s of hashing power maliciously, for instance, the jackpot would need to be less than 228 BTC with 1 in 10,000 odds.

Tell me if I'm wrong, but this makes sense to me at any rate.

[theymos]

You could also hash the end block hash a few quadrillion times to make it impossible for miners to predict the result in a reasonable timeframe.

[SgtSpike]

You could also hash the end block hash a few quadrillion times to make it impossible for miners to predict the result in a reasonable timeframe.

True.  If you had 30 minutes of hashing post-block, it would pretty much guarantee no blocks would be tossed in the name of the lottery.  Chances are, another block would be found in those 30 minutes, so no miner would hold it while quadrillion-hashing it to find out whether it contains the correct hash.

The downside is, you'd have to set a specific block number or date/time interval as the "lottery" block.  I would like to see a solution where the block that a transaction is included in is the block that determines whether that person is a winner.  It'd be more or less as "instant win" as one could get with a lottery based on the block chain.  Simply browsing over to blockexplorer, then clicking on the transaction hash and comparing it to the block hash would be ideal.