Are transaction hashes predictable?

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

[1715028891]

1715028891

[1715028891]

1715028891

[1715028891]

1715028891

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