Mark_Friedenbach comments on A proposed inefficiency in the Bitcoin markets - Less Wrong

3 Post author: Liron 27 December 2013 03:48AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (138)
Tags: reasoning markets bayesian rationality bitcoin efficient applied

Comments (138)

You are viewing a single comment's thread. Show more comments above.

Comment author: [deleted] 02 January 2014 09:27:22AM *  2 points [-]

do you have to essentially build a set of quantum gates that implement RIPEMD-160(SHA256(pubkey))?

Actually RIPEMD-160(SHA-256(pubkey(privkey))).

Does this imply you need enough qubits to hold all stages of the calculation in memory at the same time?

That's a massive understatement. Grover's algorithm can be used to reverse either RIPEMD-160 or SHA-256 with sqrt speedup. In principle it should also handle RIPEMD-160(SHA-256(x)), just with a lot more qubits. Shor's algorithm can be used to reverse the pubkey-from-privkey step. I'll hand-wave and pretend there's a way to combine the two into a single quantum computation [citation needed].

It's ... a lot of qubits. And you still need 2^80 full iterations of this algorithm, without errors, before you are 50% likely to have found a key. Which must be performed within ~10 minutes unless there is key reuse. So really it's of zero practical relevance in the pre-singularity foreseeable future.

The bitcoin wiki claims that it's strictly more profitable to mine than to search for collisions, but it seems to me that that's a function of block reward vs. value of address you're trying to hack, so I don't know if I believe that

Technically you are correct. But in no conceivable & realistic future will it ever be more profitable to search for collisions then mine bitcoins, so for practical purposes the wiki is not wrong.

Comment author: lavalamp 03 January 2014 02:25:55AM 0 points [-]

Thanks for the explanation, it seems like I'm not wildly misreading wikipedia. :)

It seems like the more qubits are required for this attack, the more likely we are to have a long warning time to prepare ourselves. The other attack of just cracking the pubkey when a transaction comes through and trying to beat the transaction, seems vastly more likely to be an actual problem.

Do you have any idea how I'd go about estimating the number of qubits required to implement just the SHA256(SHA256(...)) steps required by mining?

Powered by Reddit Powered by Reddit