Are transaction hashes predictable?

[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.