I'm really interested in the comment about someone else running a bot that tries a double-spend based on the answer in the original transaction. It sounds like it didn't work, but it could have. Is there a way to set up these sorts of automated challenges in a way that isn't vulnerable to that?
The script is just checking that the spender knows 2 pieces of data that are different but have the same SHA1 hash. I can't see a way to do that that can't be easily replayed by somebody else spending to a different address.
As soon as the transaction is broadcast, you reveal your 2 pieces of data that are different but have the same SHA1 hash.
Either by using interaction (with a ZKCP) or by using a two phase redemption and a covenant (https://blockstream.com/2016/11/02/covenants-in-elements-alp... which requires OP_CAT and friends which are disabled but could easily be reenabled after the segwit improvement to Bitcoin).
It's possible in Ethereum. You set a two-step process, in the first step you claim the solution - providing a hash of it, and your address. In the second step (in the next block), you provide the solution, and a smart contract can only send money to the address you provided in the first step.
(And to not put too fine a point on it: the existing track record of ethereum smart contracts suggests that if such a bounty had been created there it would have simply been stolen due to contract/vm flaws by now.)
In addition to the zero knowledge proof points discussed below, one could (if they had the mean) to not publish the tx but include it in a block that they work on privately. It's not fool proof (once you announce the block, you've only given yourself one block worth of proof of work lead and an attacker could copy your proof and include it in a competing chain)
Before anyone has the bright idea of running off and betting on "Yes", check the FAQ about how BitBet keeps your BitCoins if you bet on a closed contract: https://bitbet.us/faq/
(Not pointing this out to be critical. With a bit of thought, the policy makes enough sense to me, for various reasons. Pointing this out to prevent people from doing silly things, and because it's an interesting document on its own.)
When you send Bitcoins you are not really sending them to any recipient but you place them in the block chain and attach a challenge. Everyone who can solve a challenge can spend the coins associated with this challenge.
Usually the challenge is to prove that you have the private key to a public key included in the challenge so that the public key can function as an address for you and only you can spend the coins because only you have the private key.
But in this case Peter Todd placed 2.48 BTC in the block chain with the challenge to provide two different but otherwise arbitrary pieces of data yielding the same SHA-1 hashes. Someone now used the collision generated by Google to spend those coins.
Yes, challenge and response are just small programs. Every transaction is essentially just two small programs, one that solves the current challenge proving that you are allowed to spent the coins and a new challenge to be solved by the next one who wants to spent the coins.
So the way to "collect" those coins is to post the solution to the hash collision and, as a followup challenge, something encrypted with your public key so only you can decrypt it later on. Correct?
Yes. And in this case you have to be quick and maybe need some luck. Because everyone could try to get those coins you have to be the one that gets his transaction included in the block chain first.
If Google had not publish the collision but you found it yourself, miners could still just steal the collision from your transaction, throw your transaction away and spend the coins themselves.
Actually everybody could just watch all new transactions, steal your collision once they see it and try to front-run you. So this kind of challenge is not really a good idea in general, at least not in this simple form.
With normal transaction this is not an issue because there you only reveal a signature proving that you know the private key, you do not reveal the private key itself and therefore others can not sign their own transaction and try to front-run you.
[...] and, as a followup challenge, something encrypted with your public key so only you can decrypt it later on.
That is not entirely correct, as mentioned above this works by signing and not encrypting. Everybody and especially miners have to be able to verify your transaction but they could not do that if you simply encrypted something. Well, they could if you published the private key but then you get into said front-running issue.
No. Bitcoin uses "scripts" to validate transactions. It is a small turing-incomplete language with specialized operators that let you perform comparisons and such. This script was set up such that you could spend the coins if you could make a hash collision in SHA1.
So it was claimed by reusing the collision data from shattered.io: https://bitcointalk.org/index.php?topic=293382.msg17950195#m... Pretty cool.
I'm really interested in the comment about someone else running a bot that tries a double-spend based on the answer in the original transaction. It sounds like it didn't work, but it could have. Is there a way to set up these sorts of automated challenges in a way that isn't vulnerable to that?
I can't see how you'd do it for a case like this.
The script is just checking that the spender knows 2 pieces of data that are different but have the same SHA1 hash. I can't see a way to do that that can't be easily replayed by somebody else spending to a different address.
As soon as the transaction is broadcast, you reveal your 2 pieces of data that are different but have the same SHA1 hash.
Either by using interaction (with a ZKCP) or by using a two phase redemption and a covenant (https://blockstream.com/2016/11/02/covenants-in-elements-alp... which requires OP_CAT and friends which are disabled but could easily be reenabled after the segwit improvement to Bitcoin).
Fascinating stuff, thanks!
It's possible in Ethereum. You set a two-step process, in the first step you claim the solution - providing a hash of it, and your address. In the second step (in the next block), you provide the solution, and a smart contract can only send money to the address you provided in the first step.
It's possible in Bitcoin too and not just for the kind of trivial program you could plausible execute in a public blockchain. https://bitcoincore.org/en/2016/02/26/zero-knowledge-conting...
(And to not put too fine a point on it: the existing track record of ethereum smart contracts suggests that if such a bounty had been created there it would have simply been stolen due to contract/vm flaws by now.)
Unless it is SHA-1 hash :)
Discussed in https://www.reddit.com/r/Bitcoin/comments/1mavh9/trustless_b...
You'd need a system supporting zero knowledge proofs.
Excellent post, thanks for linking to it.
In addition to the zero knowledge proof points discussed below, one could (if they had the mean) to not publish the tx but include it in a block that they work on privately. It's not fool proof (once you announce the block, you've only given yourself one block worth of proof of work lead and an attacker could copy your proof and include it in a competing chain)
ZKCP is a much more robust solution.
How much BTC did he get?
https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2c...
2.48 BTC
~$2860 USD. Fairly good payoff for probably setting up a Google Alert and a small amount of scripting.
2.48 BTC, valued at 2800 USD at the moment.
BitBet: A SHA1 collision will be found before the end of 2017
https://bitbet.us/bet/1351/a-sha1-collision-will-be-found-be...
One of the "no" bets was for ~7.4 BTC (~$8500 USD). Interesting that somebody was willing to lay down that much.
There was also an 8 BTC (~$9250 USD) bet placed on "Yes" two days before the collision announcement.
even knowing about these things in advance, the risk that the site loses your funds is so great that it's not very attractive to bet on these things.
The site publishes the bitcoin txids + addresses so it is trivial to verify whether they are paying out the winnings.
I think the issue is that like any other outfit that holds bitcoin they may just "lose" them and vanish.
Until they don't. Other betting sites have 'lost' everyone's coins.
Before anyone has the bright idea of running off and betting on "Yes", check the FAQ about how BitBet keeps your BitCoins if you bet on a closed contract: https://bitbet.us/faq/
(Not pointing this out to be critical. With a bit of thought, the policy makes enough sense to me, for various reasons. Pointing this out to prevent people from doing silly things, and because it's an interesting document on its own.)
Apparently this was the winning script: https://blockchain.info/tx/8d31992805518fd62daa3bdd2a5c4fd2c...
If you 'unhexlify' both hex strings on that page, you can see that the first 320 bytes of each PDF from shattered.io were used as input.
This thread seriously need a ELI5... or ELI don't have a degree in Mathematics.
When you send Bitcoins you are not really sending them to any recipient but you place them in the block chain and attach a challenge. Everyone who can solve a challenge can spend the coins associated with this challenge.
Usually the challenge is to prove that you have the private key to a public key included in the challenge so that the public key can function as an address for you and only you can spend the coins because only you have the private key.
But in this case Peter Todd placed 2.48 BTC in the block chain with the challenge to provide two different but otherwise arbitrary pieces of data yielding the same SHA-1 hashes. Someone now used the collision generated by Google to spend those coins.
Can everyone place a custom challenge in the Bitcoin blockchain?
Yes, challenge and response are just small programs. Every transaction is essentially just two small programs, one that solves the current challenge proving that you are allowed to spent the coins and a new challenge to be solved by the next one who wants to spent the coins.
So the way to "collect" those coins is to post the solution to the hash collision and, as a followup challenge, something encrypted with your public key so only you can decrypt it later on. Correct?
Yes. And in this case you have to be quick and maybe need some luck. Because everyone could try to get those coins you have to be the one that gets his transaction included in the block chain first.
If Google had not publish the collision but you found it yourself, miners could still just steal the collision from your transaction, throw your transaction away and spend the coins themselves.
Actually everybody could just watch all new transactions, steal your collision once they see it and try to front-run you. So this kind of challenge is not really a good idea in general, at least not in this simple form.
With normal transaction this is not an issue because there you only reveal a signature proving that you know the private key, you do not reveal the private key itself and therefore others can not sign their own transaction and try to front-run you.
[...] and, as a followup challenge, something encrypted with your public key so only you can decrypt it later on.
That is not entirely correct, as mentioned above this works by signing and not encrypting. Everybody and especially miners have to be able to verify your transaction but they could not do that if you simply encrypted something. Well, they could if you published the private key but then you get into said front-running issue.
FWIW while I created the bounty, the bulk of that 2.48 BTC was donated by people other than me.
I have no idea what's going on. Is this bad for bitcoin?
No. Bitcoin uses "scripts" to validate transactions. It is a small turing-incomplete language with specialized operators that let you perform comparisons and such. This script was set up such that you could spend the coins if you could make a hash collision in SHA1.