I always forget about the RIPEMD-160 step. 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. https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
It’s unclear to me how you would actually implement this in a quantum computer; do you have to essentially build a set of quantum gates that implement RIPEMD-160(SHA256(pubkey))? Does this imply you need enough qubits to hold all stages of the calculation in memory at the same time? I haven’t been able to figure out from wikipedia how I’d arrange qubits to do a single hashing operation. Given that it’s a lot of sequential steps, perhaps it actually takes a lot of qubits chained together?
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.
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?
I always forget about the RIPEMD-160 step. 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. https://en.bitcoin.it/wiki/Technical_background_of_Bitcoin_addresses
It’s unclear to me how you would actually implement this in a quantum computer; do you have to essentially build a set of quantum gates that implement RIPEMD-160(SHA256(pubkey))? Does this imply you need enough qubits to hold all stages of the calculation in memory at the same time? I haven’t been able to figure out from wikipedia how I’d arrange qubits to do a single hashing operation. Given that it’s a lot of sequential steps, perhaps it actually takes a lot of qubits chained together?
Actually RIPEMD-160(SHA-256(pubkey(privkey))).
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.
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.
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?