The Quantum Threat to Bitcoin: Implications for Miners, Nodes, and Wallets

[BlackHatCoiner]

Quantum computers could potentially break the cryptographic primitives underpinning SHA-256

How could they do that?

To maintain the security of the network, Bitcoin would need to transition to a quantum-resistant PoW algorithm, such as one based on quantum-resistant cryptographic primitives like lattice-based cryptography or hash-based signatures.

Sounds like you're parroting information. The concern with quantum computers comes by solving the ECDLP in a polynomial time, which in theory can be done using Shor's algorithm and a functional quantum computer. The quantum resistant cryptographic primitives you mentioned do not apply to a broken SHA256, but to secp256k1.

This migration process could be initiated by wallet software providers or done manually by users

It could only be initiated by the users. The people who write the wallet software cannot just move other people's coins without a valid signature.


Now tell me. To which LLM did I respond?

[tromp]

Proof-of-Work is completely dependent on a secure hash algorithm.

It's not. The Hashcash [1] Proof-of-Work system is. There are other PoW not based on hashing [2].

Miners would be affected because the current Proof of Work (PoW) algorithm in Bitcoin relies heavily on SHA-256 for mining.
Quantum computers could potentially break the cryptographic primitives underpinning SHA-256, which would render the current mining hardware and strategies obsolete.

While you ponder about quantum attacks on SHA256, which are considered extremely unlikely, you overlook the fact that Bitcoin's PoW algorithm, namely Hashcash [1], is itself known to be vulnerable to quantum attack, independent of the choice of hash function in Hashcash (SHA256D in bitcoin).

Using Grover's algorithm [3] for quadratic speedup, a quantum computer can find a hash pre-image with 2*k leading 0s in (very) roughly the same amount of time that a classical computer needs to find one with only k leading 0s.

[1] https://en.wikipedia.org/wiki/Hashcash
[2] http://cryptorials.io/beyond-hashcash-proof-work-theres-mining-hashing/
[3] https://en.wikipedia.org/wiki/Grover%27s_algorithm

[WatChe]

This is always the case. Why? Because all algorithms are based on unsolved math problems, for example "elliptic curve discrete logarithm problem" (ECDLP). As long as it is unsolved, we can use elliptic curves in the same way as today. But once someone will find a mathematical solution, you need to find another problem, and build a new system around that. Also, for that reason, humans should never know the answer for every problem, because then you can no longer build any new crypto-based system.

Quantum computing is not a new thing, quantum computing algorithms like Shor's algorithm [1] that solves discrete logarithm problems and integer factorization in a polynomial time are launched in 1994.
RSA is based in integer factorization while Diffie-Hellman Key Exchange is based on Discrete Log Problem. Quantum computing is targeting the unsolved problems (hard problems) on which these security protocols stand.
One we have quantum computers of 4000 Qubits, things will get tough for current security protocols.

[1]https://www.geeksforgeeks.org/shors-factorization-algorithm/

[j2002ba2]

One we have quantum computers of 4000 Qubits, things will get tough for current security protocols.

You are off several order of magnitudes. If they somehow make quantum error correction work, then it's more like 15000*4000 = 60M qubits.

For 256-bit ECDLP the lowest logical qubit count is around 2330, giving 35M physical qubits.

There is a big problem - one also needs 126G Toffoli gates.

Additionally, the algorithm has to perform 116G time steps. If the time step is 1ps, then there might be even a correct result! With 1ns we are looking at 116 seconds runtime, enough for decoherence. AFAIK right now the time step is several hundred nanoseconds. This is several hours runtime. No result possible.

Wait a moment!
Error correcting Toffoli gates needs additionally at least 15 logical qubits. This is 225K qubits per Toffoli gate.
All together 28.35 * 10¹⁵ qubits.

Even if the above is off by orders of magnitude, for now, all quantum hope is lost.

[WatChe]

Even if the above is off by orders of magnitude, for now, all quantum hope is lost.

Same thing was said about every new technology including Bitcoin.  

There is no reason for any individual to have a computer in his home
Ken Olsen, founder of Digital Equipment Corporation, 1977

First 2-qubit quantum computer was demonstrated in 1998 and last year IBM rolled out there 400 Qubit-Plus Quantum Processor and Next-Generation IBM Quantum System Two (IBM). The pace may be slow but quantum computing is a reality.

Moreover US president has already signed quantum Computing Cyber security Preparedness Act in final days of 2022.

[bkelly13]

...

-  First, they'll try to attack old P2PK transactions, as they provide the public key. Satoshi's coins are the prime example for that. We will thus see slowly Satoshi's money moving (be it because Satoshi himself moves them with P2[W]PKH/P2TR txes, or because the quantum hacker moves them). An attacker will need years for that step alone, so they'll be focusing on coins where it's unlikely that thay'll be moved.

How do "we" know which coins are Satoshi's? 

[digaran]

How do "we" know which coins are Satoshi's? 

"We" don't know exactly, but there are some speculations stating that he mined the first 20,000 blocks, untouched to this day.

[vjudeu]

How do "we" know which coins are Satoshi's?

We don't. If you explore coinbase transactions from the past, you can notice that there is a field called "extraNonce". Because it is not resetted, it is incremented, and by looking at such numbers, you can conclude that if one block has extraNonce equal to 1035, and some next block has extraNonce equal to 1039, then you can guess that both blocks were mined by the same miner.

http://satoshiblocks.info/

See? Those blue lines are used to collect all such cases. Also, you can see some green lines, that are similar, and also can show you, which coins can be owned by another single miner. However, all of that is not a proof, that Satoshi is the person behind it. The only strong implication is that if you can identify such line, then you can guess, that all blocks on a single line, were mined by a single miner.

However, this is similar to checking, which mining pool mined which block. This is just something you can get from exploring coinbase transactions. This is not a 100% proof, but rather a guess. Because, guess what: you can also run some solo miner, and put "Mined by AntPool" string inside. And then, if you release such solo-mined block, with your own address in the coinbase output, then people would see that and think "so, it was mined by AntPool, right?". Maybe. Or maybe not. We don't know, we can only guess.

he mined the first 20,000 blocks

Not exactly. People think he mined those blocks from those blue lines. But if you think he mined every single block, then you are wrong. There are many green dots, and it can show you, that many blocks were mined by other people. Also, because the slope of some green lines is different, people concluded that those miners had different hashrates. You can re-mine some old, CPU-mined blocks, to confirm, what was the exact algorithm for mining some old blocks.