Bitcoin Forum
December 03, 2016, 09:49:36 PM *
News: To be able to use the next phase of the beta forum software, please ensure that your email address is correct/functional.
 
   Home   Help Search Donate Login Register  
Pages: [1] 2 3 »  All
  Print  
Author Topic: Are transaction hashes predictable?  (Read 3151 times)
SgtSpike
Legendary
*
Offline Offline

Activity: 1344



View Profile
November 11, 2011, 08:39:42 PM
 #1

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?
1480801776
Hero Member
*
Offline Offline

Posts: 1480801776

View Profile Personal Message (Offline)

Ignore
1480801776
Reply with quote  #2

1480801776
Report to moderator
1480801776
Hero Member
*
Offline Offline

Posts: 1480801776

View Profile Personal Message (Offline)

Ignore
1480801776
Reply with quote  #2

1480801776
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480801776
Hero Member
*
Offline Offline

Posts: 1480801776

View Profile Personal Message (Offline)

Ignore
1480801776
Reply with quote  #2

1480801776
Report to moderator
1480801776
Hero Member
*
Offline Offline

Posts: 1480801776

View Profile Personal Message (Offline)

Ignore
1480801776
Reply with quote  #2

1480801776
Report to moderator
1480801776
Hero Member
*
Offline Offline

Posts: 1480801776

View Profile Personal Message (Offline)

Ignore
1480801776
Reply with quote  #2

1480801776
Report to moderator
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
November 11, 2011, 08:43:42 PM
 #2

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
November 11, 2011, 08:48:39 PM
 #3

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
Hero Member
*****
Offline Offline

Activity: 910



View Profile WWW
November 11, 2011, 08:53:05 PM
 #4

You would need to exclude coinbase transactions.

dooglus
Legendary
*
Offline Offline

Activity: 1988



View Profile
November 11, 2011, 09:05:52 PM
 #5

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
Legendary
*
Offline Offline

Activity: 1344



View Profile
November 11, 2011, 09:06:37 PM
 #6

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
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
November 11, 2011, 09:10:10 PM
 #7

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
Legendary
*
Offline Offline

Activity: 1344



View Profile
November 11, 2011, 09:13:28 PM
 #8

Cool, thanks for the info.  Smiley
casascius
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
November 11, 2011, 09:32:19 PM
 #9

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
theymos
Administrator
Legendary
*
Offline Offline

Activity: 2492


View Profile
November 11, 2011, 09:56:05 PM
 #10

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
SgtSpike
Legendary
*
Offline Offline

Activity: 1344



View Profile
November 11, 2011, 10:20:22 PM
 #11

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
Legendary
*
Offline Offline

Activity: 1988



View Profile
November 11, 2011, 11:56:28 PM
 #12

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
Mike Caldwell
VIP
Legendary
*
Offline Offline

Activity: 1344


The Casascius 1oz 10BTC Silver Round (w/ Gold B)


View Profile WWW
November 12, 2011, 12:04:06 AM
 #13

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.

Companies claiming they got hacked and lost your coins sounds like fraud so perfect it could be called fashionable.  I never believe them.  If I ever experience the misfortune of a real intrusion, I declare I have been honest about the way I have managed the keys in Casascius Coins.  I maintain no ability to recover or reproduce the keys, not even under limitless duress or total intrusion.  Remember that trusting strangers with your coins without any recourse is, as a matter of principle, not a best practice.  Don't keep coins online. Use paper wallets instead.
theymos
Administrator
Legendary
*
Offline Offline

Activity: 2492


View Profile
November 12, 2011, 12:31:16 AM
 #14

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.

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
bitlotto
Hero Member
*****
Offline Offline

Activity: 672


BitLotto - best odds + best payouts + cheat-proof


View Profile WWW
November 13, 2011, 05:07:24 PM
 #15

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.

*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.
pc
Sr. Member
****
Offline Offline

Activity: 253


View Profile
November 14, 2011, 12:54:33 AM
 #16

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
Legendary
*
Offline Offline

Activity: 1344



View Profile
November 14, 2011, 04:15:42 PM
 #17

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
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
November 14, 2011, 04:28:59 PM
 #18

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
Legendary
*
Offline Offline

Activity: 1344



View Profile
November 14, 2011, 04:46:00 PM
 #19

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
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
November 14, 2011, 04:50:38 PM
 #20

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.
Pages: [1] 2 3 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!