Fascinating stuff, thanks!

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

you claim the solution - providing a hash of it, and your address

Unless it is SHA-1 hash :)

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.

~$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.

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.

   In [1]: import binascii, hashlib

   In [2]: input1 = binascii.unhexlify('255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034
   ...: 203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706
   ...: f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017f46dc93a6b67e013b029aaa1db2
   ...: 560b45ca67d688c7f84b8c4c791fe02b3df614f86db1690901c56b45c1530afedfb76038e972722fe7ad728f0e4904e046c230570fe9d41398abe12ef5bc942be33542a4802d98b5d70
   ...: f2a332ec37fac3514e74ddc0f2cc1a874cd0c78305a21566461309789606bd0bf3f98cda8044629a1')

   In [3]: input2 = binascii.unhexlify('255044462d312e330a25e2e3cfd30a0a0a312030206f626a0a3c3c2f57696474682032203020522f4865696768742033203020522f547970652034
   ...: 203020522f537562747970652035203020522f46696c7465722036203020522f436f6c6f7253706163652037203020522f4c656e6774682038203020522f42697473506572436f6d706
   ...: f6e656e7420383e3e0a73747265616d0affd8fffe00245348412d3120697320646561642121212121852fec092339759c39b1a1c63c4c97e1fffe017346dc9166b67e118f029ab621b2
   ...: 560ff9ca67cca8c7f85ba84c79030c2b3de218f86db3a90901d5df45c14f26fedfb3dc38e96ac22fe7bd728f0e45bce046d23c570feb141398bb552ef5a0a82be331fea48037b8b5d71
   ...: f0e332edf93ac3500eb4ddc0decc1a864790c782c76215660dd309791d06bd0af3f98cda4bc4629b1')

   In [4]: input1[:8], input2[:8]
   Out[4]: ('%PDF-1.3', '%PDF-1.3')

   In [5]: hashlib.sha1(input1).hexdigest() == hashlib.sha1(input2).hexdigest()
   Out[5]: True

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.

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.