4 ms·

Is it possible to generate BitCoins on quantum computer?

hannob 10y ago
Actually it is possible to bring the whole bitcoin system down with a (general purpose, large enough) quantum computer. The whole bitcoin system relies on ECDSA signatures, which can be broken with Shor's algorithm. You can't mine bitcoins faster with a quantum computer, because that's basically hashing, which you don't get a significant speedup. But you can steal everyone else's bitcoins.
- tromp 10y ago
  You get quadratic speedup on mining, since the HashCash proof-of-work used in Bitcoin is a perfect application of Grover's quantum database search algorithm. So while classical miners are brute forcing through a 2^70 search space, the quantum miner can find a solution in roughly sqrt(2^70) = 2^35 steps. Other proof-of-work systems can be more quantum resistant, e.g. looking for a fixed-length cycle in a huge random graph, for which no efficient quantum algorithm is known.
  - Natanael_L 10y ago
    Computing 2xSHA256 on a some hundred bytes block header with one section open for randomness will not be that easy on a quantum computer (the more complex the problem, the easier for noise to drown out the answer), not to mention you'll still need fast ASIC hardware to evaluate all QC outputs looking for valid blocks. And you must reset part of the problem (the previous block hash, at minimum) when new blocks are released, adding some latency (you need to recompute the qubit configuration before resuming). But perhaps a SIDH based proof-of-work algorithm could be implemented to further resist QC speedups. Don't know exactly how that would work. Does Grover's still apply?
- tromp 10y ago
  You cannot steal bitcoins from an address that's never been spent, since you only know the hash of the public key. There are about 2^256/2^160=2^96 possible full public keys mapping to the known key hash, so you could run Grover's algorithm to recover one in about sqrt(2^96)=2^48 steps, but given the slow cycle time of quantum computers, that's still going to be infeasible for a long time. This is why address re-use is not recommended...

Actually it is possible to bring the whole bitcoin system down with a (general purpose, large enough) quantum computer. The whole bitcoin system relies on ECDSA signatures, which can be broken with Shor's algorithm. You can't mine bitcoins faster with a quantum computer, because that's basically hashing, which you don't get a significant speedup. But you can steal everyone else's bitcoins.

tromp 10y ago
You get quadratic speedup on mining, since the HashCash proof-of-work used in Bitcoin is a perfect application of Grover's quantum database search algorithm. So while classical miners are brute forcing through a 2^70 search space, the quantum miner can find a solution in roughly sqrt(2^70) = 2^35 steps. Other proof-of-work systems can be more quantum resistant, e.g. looking for a fixed-length cycle in a huge random graph, for which no efficient quantum algorithm is known.
- Natanael_L 10y ago
  Computing 2xSHA256 on a some hundred bytes block header with one section open for randomness will not be that easy on a quantum computer (the more complex the problem, the easier for noise to drown out the answer), not to mention you'll still need fast ASIC hardware to evaluate all QC outputs looking for valid blocks. And you must reset part of the problem (the previous block hash, at minimum) when new blocks are released, adding some latency (you need to recompute the qubit configuration before resuming). But perhaps a SIDH based proof-of-work algorithm could be implemented to further resist QC speedups. Don't know exactly how that would work. Does Grover's still apply?
tromp 10y ago
You cannot steal bitcoins from an address that's never been spent, since you only know the hash of the public key. There are about 2^256/2^160=2^96 possible full public keys mapping to the known key hash, so you could run Grover's algorithm to recover one in about sqrt(2^96)=2^48 steps, but given the slow cycle time of quantum computers, that's still going to be infeasible for a long time. This is why address re-use is not recommended...