Topic: The Quantum Threat to Bitcoin: Implications for Miners, Nodes, and Wallets (Read 851 times)

Given the almost exponential rate of technological evolution, vulnerabilities might surface sooner than we anticipate.
I don't think these algorithms will take hundreds of years to become weak, but we still have some time to prepare.
However, we're in an era where research is stagnating—either experts have too much money and focus on other things,
or they don't have enough and investigating these matters becomes unappreciated work. This should be taken very seriously.

The community needs to be proactive to avoid a "Titanic effect" and not underestimate the risks out of arrogance or lack of
appreciation for experts.

Merit given for that link 'The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime'
That is the 1st paper on QC I've seen that emphasized that all efforts to-date have been research test beds built to test ideas on how quantum circuits will/do operate - they are NOT functional 'Quantum Computers" that are capable of doing anything other than that 1-specific series of tests. Now if only mainstream & social media would realize that and quit making it sound like QC's are just around the corner and coming soon to a BestBuy near you...

Per the paper:

In short the progression has been:
a. 1st 'Quantum Computers' (per how media covered it and repeated as each breakthrough was announced) were to see if a single quantum gate (QG) can actually be made.

b. Once a single QG was made the next ones were to find what does it actually do. How can it be manipulated? The QG's officially became known as 'Qubits'.

c. Next were to see if multiple qubits could be made on a single chip and connected to each other.

d. After several iterations of 'c' it was found that data error rate was a huge stumbling block and there things sat for over 10 years. Good part is that during that time, evolution of 'c' led from only 4 qubits on a chip to the current number of qubits available on a test system (IBM's Quantum has 127 qubits). Now enough qubits are available to start building and testing logic circuits needed for operations - things like adders, multipliers, NAND & NOR operators, etc. but quantum data error rate remained a huge problem.

e. Current level of development: Google's Sycamore and Willow chips finally cracked the error rate issue.

f. Next comes addressing other problems such as quantum state stability and lifetime and how to make bigger arrays of qubits. Both are still in very early research stage.

g. Once all that is resolved only then will the 1st real QC be able to be built.

That is where we now stand - at point 'e'. Testing the bits & pieces of what will one day become a true Quantum Computer capable of working on actual real-world computational problems.

In addition we could see in this article from Google Quantum AI that this quantum computer named Willow is only using 105 qubits. However, according to this academic article published in 2022, it's almost one million times below the number of qubits needed to break a Bitcoin public key, so we are not even talking of an address hashed with RIPEMD-160 and SHA-256 from a public key, and then encoded with Base58Check. It means those figures only concern addresses already used to send funds(because of their public key available on the blockchain).
https://doi.org/10.1116/5.0073075

I suggest you perhaps read https://bitcointalksearch.org/topic/m.64833837 dealing with so called "Quantum Computers". In short - we are still a LONG way from QC's. All to-date are test beds for the technology needed to eventually make them. They are not by any stretch of the imagination 'computers'.

Google announces  Willow, quantum chip.

https://scottaaronson.blog/?p=8329&continueFlag=86a666619f5897003da1fae21f589db6


https://twitter.com/adam3us/status/1866480523800932364

https://eprint.iacr.org/2011/191.pdf
winternitz signatures

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.

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.

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

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

Same thing was said about every new technology including Bitcoin.  


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.

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.

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/

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

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

How could they do that?

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.

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?

If there were a successful quantum attack on SHA-256, which is the hashing algorithm used in Bitcoin, it would have significant implications for the Bitcoin network and its infrastructure. Here's how it might affect miners, mining hardware, Bitcoin wallets, and the need to migrate funds:

Miners and Mining Hardware:

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.
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.
Miners would need to upgrade their hardware and software to adapt to the new algorithm, which might require significant investments.

Bitcoin Wallets:

Existing Bitcoin wallets that use classical public-key cryptography could become vulnerable to quantum attacks if a quantum computer becomes capable of breaking these algorithms.
Users might need to transition to quantum-resistant wallet software or generate new quantum-resistant addresses.
It's essential to note that not all wallets would be equally vulnerable; those that use post-quantum cryptographic techniques would be more secure.

Migration of Funds:


Depending on the severity of the quantum threat and the actions taken by the Bitcoin community, there might be a need to migrate funds from old addresses to new quantum-resistant addresses.
This migration process could be initiated by wallet software providers or done manually by users, depending on the circumstances and the transition strategy chosen by the Bitcoin developers and community.
The migration would involve creating new quantum-resistant keys and transferring Bitcoin holdings to these new addresses. Users would have to follow guidelines provided by wallet developers or the Bitcoin community to ensure a secure transition.


In summary, a successful quantum attack on SHA-256 would necessitate significant changes to the Bitcoin network, including a transition to a quantum-resistant PoW algorithm, upgrades to mining hardware and software, and a potential migration of funds to new quantum-resistant addresses. The specifics of these changes would depend on the nature and timing of the quantum threat, as well as the response of the Bitcoin community and developers. It's crucial for users to stay informed about developments in quantum computing and the Bitcoin ecosystem to take appropriate actions to protect their holdings.

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.

Another important thing to note is that if the true owner of some coins can do something to move them, then it is technically possible to steal those coins, if someone else will repeat those steps. Which means, we are never at "it doesn't exist" stage, unless you send your coins to a Script, where nobody can move them, including yourself, for example OP_RETURN.

To this date, it is still true. For now, it comes gradually, because for example chainwork can show you, how far people are, when it comes to breaking SHA-256. For public keys, currently there is no provably fair puzzle, but you can make some assumptions, based on that famous centralized puzzle (it is centralized, because if you want to build it in a truly trustless way, then you need something like DLEQ, where the creator of the puzzle could not move the coins, without solving it).

As more informed members mentioned previously, there is no "one" solution, equation or algorithm that could have the answer to all the problems, meaning if POW is compromised, it would only work to generate blocks e.g, 10× faster than others with the same hash rate, so there will not be any all in one solution to manipulate everything.

If there hasn't been any exploitation of EC keys and hash functions, there are 2 reasons, 1- it doesn't exist, 2- it exist, we are not just ready to advance to that stage yet, as you know the universe has a God who controls everything, we just have to hope it comes gradually giving time for safe transition.  Humanity deserves financial decentralization, and that could only be achieved by having publicly available difficult to crack equations/algorithms.

Well, i don't think that it can remain a secret. If one entity has the resources and techniques to compromise the proof of work, then they should not remain in belief that none other can do it. What if they keep it a secret, in vision of owning everything , while the other party comes and takes away all.

By the way, once the POW is compromised, the price will automatically fall to Zero even before any party have any chance to sell.

There is currently in the region of 200,000,000 unspent UTXOs. With optimally somewhere around 10,000 outputs being spent per block, then we are looking at 20,000 blocks which is ~139 days of no other transactions to move everything to a quantum resistant algorithm, assuming all outputs were being moved to the new algorithm. If you want to move every coin to the new quantum proof address at once like this, then yes, that's a real concern.

There are a number of caveats to this, though, which mean in reality it won't be as bad as this. Assuming we will have plenty of time (in the order of several years) to move across to the new algorithm, then it easy for a large part of this to take place passively with no additional load on the mempool. That is to say, whenever in the next few days, weeks, months, or years, I plan to spend certain outputs, then I simply direct any change to a new quantum proof address instead of back to an old address. Any transactions which are going to be happening anyway, such as depositing coins to an exchange or paying a service, can similarly take up no additional block space once those exchanges and services move to the new algorithm. Indeed, given enough time, then the only coins we need to consider are dormant coins being held long term, since all coins being actively transacted will end up on the new algorithm anyway.

And even then there are proposals for other things we can do for those dormant coins to stop them being stolen should we run out of time. One such proposal is to lock any coins before they become vulnerable to theft, but provide a mechanism for the true owner to access them by proving a zero knowledge proof of (for example) the seed phrase or master chain code involved in the generation of these addresses.

Elliptic curves are independent, indeed. But, bitcoin isn't merely using elliptic curves. There are standards followed as the one I outlined, where to sign a message you hash your private key with your message to generate a pseudorandom k value, which will then be used to verify the signature.

Yes, but look at it in the other way: bitcoin is a continuous trouble for them. They strongly support the ability to manipulate the money supply, perhaps to the extent that causing the destruction of a few billion dollars is justifiable.

Agreed.

There is a vast thing in your favor - NIST has been working on the development of quantum resistant algorithms for several years, and their efforts are  not in vain. Some of those algos are already on the testing phase^[1].

The advances in quantum computing makes the subject matter to be a quite real thing that may happen in the nearest future ^[2].

AI-quantum would be a real threat^[3], IMHO.


*************************************************

[1]. NIST Announces First Four Quantum-Resistant Cryptographic Algorithms
[2]. Quantum-resistance in blockchain networks
[3]. "The Next Computing Revolution is with AI-Quantum" ft. Michio Kaku