Hacker News new | comments | show | ask | jobs | submit login
Peter Todd (Bitcoin core dev) set up a SHA-1 “Pinata” and it's been claimed (twitter.com)
130 points by j_s on Feb 23, 2017 | hide | past | web | favorite | 33 comments

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

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?

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.

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

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

Unless it is SHA-1 hash :)

How much BTC did he get?

2.48 BTC, valued at 2800 USD at the moment.

~$2860 USD. Fairly good payoff for probably setting up a Google Alert and a small amount of scripting.

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.

FWIW while I created the bounty, the bulk of that 2.48 BTC was donated by people other than me.

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.

BitBet: A SHA1 collision will be found before the end of 2017


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

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.

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.

Applications are open for YC Winter 2019

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact