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

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

I just don't understand why would any government attack bitcoin network, that would be a huge scandal because millions of people have savings in bitcoin, there are tons of bitcoin related businesses, there are lots of multi millionaires and billionaires in crypto world, they can't just ruin their life so easily.


First of all, such a rapid development and attack can't happen overnight. If technology advances to such extent, it will happen in a timeframe that will give us enough time to be ready and adapt to new changes and make quantum resistant bitcoin. If it happens otherwise and this technology comes out of nowhere, then not only bitcoin but whole world wide web will be destroyed because you have to think about not only bitcoin but other websites, absolutely every email/account will get hacked, every content management system will get hacked, it will be like the intense earthquake in virtual world.
So, that won't happen, relax and chill guys.

You can take it like that NSA developed SHA256 for security of data. They may have the algorithms to break the SHA256 but there is more profit in not revealing that they have algorithm to break SHA256.
If Quantum computing becomes a reality we have bigger things to worry about then security of our wallets since nothing will be spared by this new computing model.

I am not familiar with tech related stuff behind the scene of various block chain / hash functions, but I know they are separate from EC, while DSA depends on them.
IMO, if proof of work is compromised, it will remain secret because there is much greater benefits by both having a successful network and a backdoor to this network, so I doubt if anyone is stupid enough to try and attack when they can own everything.

In the case of mining operations, I had similar concerns until  vjudeu  replied and explained some solutions to some of the problems.
IMHO, nothing is more important than EC and safety of private keys, because that's supposed to be a safe vault inside user's houses, whatever happens to them, means someone broke in and stole from them, that kind of event has no turning back, but if way before that ever happens we could have plans and suggestions ( operational code ) in place as an upgrade, then people could be ready for anything.
It would be like when governments fortify their cash reserve vaults with new material and tech, it's a normal and expected change.

But again when you think about it, why would anyone interrupt the process of his own money printing machine if they can break EC?  As a conclusion, I doubt we see anything compromising crypto system any time soon because their profit depends on the safety of such systems.

---

Who says different addresses in the same wallet have no connection? Maybe you need to think about the reason as to why mixers exist. Sha256 is unrelated to privacy concerns about connecting addresses/ wallets.

And about transition to new algo/ network, I'm not an expert, so I don't know.

my question is less about how likely it is or if it would be fast. It's more about a possbile transition.
Lets say it get broken some distant time in the future (sha256 and EC), but slowly and the public is aware of it:
Now people would start migrating to stronger encryption all over the internet and also bitcoin would introduce an update with a more secure algorithm.
Now all coins on old addresses would possibly be in danger, because over time people could get access to it. At first it would take really long to do but it will get faster.

How could a possible transition look like? Or would it be the end of bitcoin.
Normally if you want your coins safe you would send them to a new wallet that has its sk/pk generated by the new algorithm. But everybody would need to do that and that would flood the mempool if every living owner of btc would suddenly try to move his coins.


right now you can have multiple addresses on one wallet without any connection between them. My question was if breaking sha256 would make it possible to connect them.

Actually, it's used in both private keys and elliptic curve. Modern wallet software uses SHA256 to calculate checksum of the mnemonic, and it is also used to calculate k value in signatures by following the RFC 6979 standard.

If SHA is compromised, then shit has hit the fan, to put it in laymen terms. It is used in every single corner of cryptography, but even if it wasn't, Bitcoin would still not survive, as Proof-of-Work is completely dependent on a secure hash algorithm. It's orders of magnitude worse than being able to work out a private key in a time span of a month.