Can Quantum Computer's destroy Blockchain and Bitcoins[SHA-256 specifically]

[crashedanon]

Have been researching QC's and bitcoin for months. It is not clear from many sources of the World Wide Web whether or not QC is a threat to the sha256 of Bitcoin.
1.Can we if possible mine more than the specified value of BTC in less than a minute with the help of a powerfully-eligible Quantum Computer?

Agree that QC's can destroy Elliptic Curve Digital Signature Algorithm and steal our private keys. So considering all of the above threats,

2.Is it possible to fork Bitcoin and solve the following problems?

3.How to secure the SHA256 encryption and make it immutable to QC attacks?

I am pretty sure, Satoshi Nakamoto must have thought about the possible problems there has to be a solution, but exactly where?

[1714256360]

1714256360

[1714256360]

1714256360

[1714256360]

1714256360

[1714256360]

1714256360

[BlackHatCoiner]

This belongs to the Development & Technical Discussion.

1.Can we if possible mine more than the specified value of BTC in less than a minute with the help of a powerfully-eligible Quantum Computer?

Unless the computational resources are enough to find an SHA256 collision (such as 64 zeroes), it doesn't matter. The difficulty is responsible for keeping the block interval at 10 minutes on average whether there are millions of ASICs running or just a GPU.

2.Is it possible to fork Bitcoin and solve the following problems?

Yes. We theoretically can change to a quantum resistant algorithm if it ever becomes needed.

3.How to secure the SHA256 encryption and make it immutable to QC attacks?

SHA256 isn't an encryption scheme. It's just a hash function. The potential threat of quantum computing comes from solving the ECDLP. In other words, the ability to reverse a public key to private key.

[o_e_l_e_o]

I am pretty sure, Satoshi Nakamoto must have thought about the possible problems there has to be a solution, but exactly where?

There are a couple of quotes from Satoshi I am aware of which are relevant here:

SHA-256 is very strong.  It's not like the incremental step from MD5 to SHA1.  It can last several decades unless there's some massive breakthrough attack.

If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was before the trouble started, lock that in and continue from there with a new hash function.

If the hash breakdown came gradually, we could transition to a new hash in an orderly way.  The software would be programmed to start using a new hash after a certain block number.  Everyone would have to upgrade by that time.  The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used.

However, if something happened and the signatures were compromised (perhaps integer factorization is solved, quantum computers?), then even agreeing upon the last valid block would be worthless.

True, if it happened suddenly.  If it happens gradually, we can still transition to something stronger.  When you run the upgraded software for the first time, it would re-sign all your money with the new stronger signature algorithm.  (by creating a transaction sending the money to yourself with the stronger sig)

Quantum computers will not break bitcoin overnight. It will take decades of slow progress that everyone can see coming before they become a threat, and they will break many other weaker algorithms along the way. They also only provide a linear increase in the speed to find a hash collision (as opposed to an exponential increase in the speed to solve the ECDLP), and so are unlikely to be able to break SHA256. But if it ever was to become a concern, then as Satoshi has said above, we will have plenty of time to transition in an orderly way to new quantum resistant functions and algorithms.

[dkbit98]

Is it possible to fork Bitcoin and solve the following problems?

I don't see quantum computers a threat for bitcoin and with recent changes in Taproot protocol it will be possible to protect against that, if it ever happens.
If this thing ever happens it would affect all military grade encryption, banks and everything else that don't have protection for that.

How to secure the SHA256 encryption and make it immutable to QC attacks?

SH256 algorithm is secure enough for most cases, SSL Certificates is using it for all websites today.

I am pretty sure, Satoshi Nakamoto must have thought about the possible problems there has to be a solution, but exactly where?

He was not prophet to see what will happen in future on every aspect related with Bitcoin, including quantum computers.

[larry_vw_1955]

He was not prophet to see what will happen in future on every aspect related with Bitcoin, including quantum computers.

Right? the fact that he even commented on them at all is quite remarkable given that at that time, Quantum computing hadn't really gained the headlines it now commands in the "nightly news". Gotta hand it to satoshi. He knew a little about everything.

[vjudeu]

He knew a little about everything.

Yes, but "knowing a little" is not enough to solve all problems. For example, he knew enough to use ECDSA, but he didn't know for example that public keys can be compressed. He knew and wrote about decentralized mining, but he didn't know how to make it "good enough for production", so he didn't include that:

Satoshi, I figured it will take my modern core 2 duo about 20 hours of nonstop work to create ฿50.00! With older PCs it will take forever. People like to feel that they "own" something as soon as possible, is there a way to make the generation more divisible? So say, instead of making ฿50 every 20 hours, make ฿5 every 2 hours?

I thought about that but there wasn't a practical way to do smaller increments.  The frequency of block generation is balanced between confirming transactions as fast as possible and the latency of the network.

The algorithm aims for an average of 6 blocks per hour.  If it was 5 bc and 60 per hour, there would be 10 times as many blocks and the initial block download would take 10 times as long.  It wouldn't work anyway because that would be only 1 minute average between blocks, too close to the broadcast latency when the network gets larger.

As you can see, he thought what will happen when the difficulty will be higher. But he didn't know how to "instead of making ฿50 every 20 hours, make ฿5 every 2 hours" in a decentralized way. That means knowing some topic and talking about it is something completely different than doing that in practice and turning ideas into code.

[Welsh]

Yes, but "knowing a little" is not enough to solve all problems. For example, he knew enough to use ECDSA, but he didn't know for example that public keys can be compressed. He knew and wrote about decentralized mining, but he didn't know how to make it "good enough for production", so he didn't include that:

As you can see, he thought what will happen when the difficulty will be higher. But he didn't know how to "instead of making ฿50 every 20 hours, make ฿5 every 2 hours" in a decentralized way. That means knowing some topic and talking about it is something completely different than doing that in practice and turning ideas into code.

To be fair, on one person is going to be able to solve everything, that's the beauty about open source. Even if it wasn't open source, you have departments within development companies for a reason. A lot of the time its not even the coders that are coming up with the ideas, there's a department that thinks about about the improve the product, and then the developers translate that into code. So, while Satoshi might have not known everything, that really wasn't a problem. Satoshi isn't a god, and although this community, and the general Bitcoin community have sort of built in into their mind that he was some god that knew everything, that definitely wasn't the case, as with everyone.

If you look at pretty much every scientist, they've had breakthroughs which have changed how we view the world, but they've also been equally wrong in some theories. Satoshi is no different. Bitcoin is no different. The beauty of it is Bitcoin is open source, Satoshi knew if he could gather enough attention, as well as develop it enough to get the fundamentals down, he knew other people would contribute to the code. So, Satoshi might have lightly brushed the surface on a lot of things, because at the time they weren't a priority, the priority was to get the fundamentals down, plan enough in the future so that the next few years there wouldn't be too many problems, but thinking about quantum computers or even compressing public keys probably wasn't necessary at the time.

It's quite common for a developer to do the fundamentals, and then revisit, and add polish where necessary. Besides, wasting time coming up with a solution to every problem is inefficient when the project is open source, and there's likely going to be several others looking for solutions. As the saying goes two eyes is better than one, and in this case multiple brains will always trump one brain when it comes to such a huge task.

I don't see quantum computers a threat for bitcoin and with recent changes in Taproot protocol it will be possible to protect against that, if it ever happens.

Its always been possible to protect against it. Though, why protect against something which is unlikely to happen in the next decade, when you could be focusing on other things? If quantum computers happen to break Bitcoin sooner than expected, as you say multiple other industries would be in trouble too. Bitcoin, would likely be the least enticing target if a malicious user wanted to benefit from using quantum computers as a way of attack.

[kaggie]

For example, he knew enough to use ECDSA, but he didn't know for example that public keys can be compressed.
..
That means knowing some topic and talking about it is something completely different than doing that in practice and turning ideas into code.

The issue is the second point. It was pretty obvious that public keys can be compressed, but whether that created an intrinsic failure while implementing this was at stake.  Also, without the compression there may be other fun mathematics possible.

For some things that Satoshi did not comment on, I believe it to be more of a caution of implementing carefully, knowing that there are limitations to an individual and even organisations debugging code. The main principles were his insight, while implementations in all code requires a larger community and prolonged testing (which bitcoin has been successful at).

[larry_vw_1955]

It's quite common for a developer to do the fundamentals, and then revisit, and add polish where necessary. Besides, wasting time coming up with a solution to every problem is inefficient when the project is open source, and there's likely going to be several others looking for solutions. As the saying goes two eyes is better than one, and in this case multiple brains will always trump one brain when it comes to such a huge task.

in other words, satoshi got the ball rolliing. that was a huge achievement in and of itself. he put enough pieces of the puzzle together to get people working on it to where it is today.

question is: what if satoshi never existed? would we have any cryptocurrencies at all right now?

[vjudeu]

question is: what if satoshi never existed? would we have any cryptocurrencies at all right now?

It is quite philosophical, because in the whitepaper you have many inefficient things, like "The only way to confirm the absence of a transaction is to be aware of all transactions". For a long time, people thought that "A Peer-to-Peer Electronic Cash System" will have similar properties as cash. So, people didn't expect that nodes will have to collect the whole history of the coin, since its inception, up to what happened 10 minutes ago. Rather, people thought you will have some kind of file stored offline and you will just share that with others. And many people thought, how to protect that kind of design from double spending. Some people may even thought about something similar to Bitcoin, but they rejected that idea, because it is too inefficient.

[dkbit98]

This Quantum topic cracking Bitcoin is showing up from time to time, and one student Mark Webber from Ion Quantum Technology Group at the University of Sussex is nowclaiming that we are decades away from something like this happening.
There is just one catch... quantum computers need to be a million times larger than they currently are before cracking Bitcoin SHA-256 algorithm
And even if this happens sometime in future, everything will be affected by this because SHA-256 is used all over the world.
https://www.newscientist.com/article/2305646-quantum-computers-are-a-million-times-too-small-to-hack-bitcoin/

[BlackHatCoiner]

[...]

This is not the only reason. Satoshi didn't just solve double-spending; he envisioned a decentralized cryptocurrency, realized that there's a solution to a problem which was considered unresolved at that time, and did everything needed to see this envision become true.

The creation of Bitcoin required dedication on a high degree. Not sure how many enthusiasts in this idea would be willing to devote hundreds of hours on working on it and talking about it.

[d5000]

There is just one catch... quantum computers need to be a million times larger than they currently are before cracking Bitcoin SHA-256 algorithm
[...]
https://www.newscientist.com/article/2305646-quantum-computers-are-a-million-times-too-small-to-hack-bitcoin/

It's not your fault, but the New Scientist's (are they that bad?): they confused SHA-256 with ECDSA in their article. In the original paper abstract we can see the following:

Finally, we calculate the number of physical qubits required to break the 256-bit elliptic curve encryption of keys in the Bitcoin network within the small available time frame in which it would actually pose a threat to do so.

Source: https://avs.scitation.org/doi/10.1116/5.0073075

So what they're talking about is already known: Quantum computers with millions of qubits could break ECDSA-256.

I don't know if everybody in this thread knows the difference:
- ECDSA is used for the public key cryptography. A quantum computer who "cracks ECDSA-256" with Shor's algorithm could calculate the private key once he knows the public key. So what Webber says makes actually sense totally: normally, if you use Bitcoin as you should and don't reuse addresses, you only publish the public key when you spend coins, so the attacker has only 10 minutes on average to break the keys. His numbers are confirmed approximately in this other document.*
- SHA-256 is the algorithm which is used to create the address, hashing the public key. It seems to be difficult to find SHA-256 collisions with quantum computers so the danger actually is much lower than the risk that ECDSA could be broken.

*However there is a scenario which could become reality much earlier: a hacker cracking Satoshi's coins or other "lost" coins which were mined and then forgotten. The reason is that many of them used P2PK coinbase transactions, this means that the public key is stored on the blockchain. So an attacker can use a quantum computer of 2619+ logical qubits** and let it work during several years and he might eventually find a billion dollar treasure.

**2619 is the absolute minimum of "logical" qubits to break ECDSA-256 according to this source. However, for each "logical"  qubit you need several physical qubits due to the need for error correction (see also: this short explanation). "Bigger" circuits with millions of qubits are faster, but you might build a "slow" QC with "only" dozens of thousands of qubits and try to crack lost coins in P2PK UTXOs and succeed.

[dkbit98]

It's not your fault, but the New Scientist's (are they that bad?): they confused SHA-256 with ECDSA in their article.

Yeah, well I am taking everything that I read or hear with some reserve, and I don't trust anything because I can't verify most things for myself.
Thanks for great explanation.

*However there is a scenario which could become reality much earlier: a hacker cracking Satoshi's coins or other "lost" coins which were mined and then forgotten. The reason is that many of them used P2PK coinbase transactions, this means that the public key is stored on the blockchain. So an attacker can use a quantum computer of 2619+ logical qubits** and let it work during several years and he might eventually find a billion dollar treasure.

Don't give hackers any bad ideas, but for this to even happen they would first need to create that much much stronger quantum computer, and they would need to wait for years to crack the old lost coins.
I am not saying this is totally impossible, but it's highly unlikely we are ever going to see this happening during our lifetime, and lost coins have become modern day treasure hunting and anything that was once lost can be found again, in theory.

[o_e_l_e_o]

I am not saying this is totally impossible, but it's highly unlikely we are ever going to see this happening during our lifetime

I disagree. The internet itself isn't even 40 years old, and now it is ubiquitous and we are dependent on it for almost everything in our lives. There's no telling where quantum computers will be in another 40 years. There is a big difference between having a quantum computer which can crack a private key and double spend a transaction in the 10-60 minutes during which it is unconfirmed, and having a quantum computer which could crack a P2PK address if given months or even years to work on it.

And obviously, as a community we will need to be a step ahead of the game and address this before it becomes a real possibility. I am fairly certain that during my life I will see bitcoin move to a quantum resistant algorithm or have some other quantum resistant feature added to it. What we do about the vulnerable P2PK coins is another matter.

[BlackHatCoiner]

And obviously, as a community we will need to be a step ahead of the game and address this before it becomes a real possibility.

So, aren't we starting to discuss about it by tomorrow morning? Changes on Bitcoin take time. We should definitely address this before it becomes a real possibility, but so far I've understood that you can't just propose a change which interferes to the base protocol and lock its function at some point in the future.

Consensus requires harmony. Lots of users have gathered to sing the Bitcoin songs, but the more users means the more talk and time to agree on changing to another playlist.

What we do about the vulnerable P2PK coins is another matter.

I don't like hard forks, but I assume this can be tackled that way without damaging the owners of those addresses.

[o_e_l_e_o]

We should definitely address this before it becomes a real possibility, but so far I've understood that you can't just propose a change which interferes to the base protocol and lock its function at some point in the future.

I am by no means an expert on the matter, but my understanding is that a lot of quantum resistant algorithms are still in their infancy. There is no point discussing and settling on a quantum resistant algorithm or other upgrade now when it won't be needed for ~20 years, when in 20 years the landscape will have changed so much that whatever we have settled on will be vastly outdated. Everyone is pretty much in agreement that if a change to deal with quantum computers is needed then it will happen. What form that change will take will depend entirely on when and specifically what the threat from quantum computing is, which we won't know until much closer to the time.

I don't like hard forks, but I assume this can be tackled that way without damaging the owners of those addresses.

If there is a method to do so, then I haven't heard it yet. If you have an idea, I'm keen to hear it (as I'm certain others are too). The only options I have heard are either to lock all P2PK outputs so the coins in them are permanently inaccessible and unspendable, or simply ignore them and let them be stolen by quantum computers and re-enter the circulation.

[BlackHatCoiner]

I am by no means an expert on the matter, but my understanding is that a lot of quantum resistant algorithms are still in their infancy.

I'm neither. AFAIK, a quantum computer that could break ECDLP requires a size of qubits that isn't accessible at the moment. But, that's all I know, it may be wrong.

If you have an idea, I'm keen to hear it (as I'm certain others are too).

So we have a malicious, evil man who can work out private keys by knowing the public keys? Yeah, that's worse than I thought. Probably those you said are the only solutions. Any other way I can think of damages either the owner or the system... Or both...

[Quickseller]

I am pretty sure, Satoshi Nakamoto must have thought about the possible problems there has to be a solution, but exactly where?

There are a couple of quotes from Satoshi I am aware of which are relevant here:

SHA-256 is very strong.  It's not like the incremental step from MD5 to SHA1.  It can last several decades unless there's some massive breakthrough attack.

If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was before the trouble started, lock that in and continue from there with a new hash function.

If the hash breakdown came gradually, we could transition to a new hash in an orderly way.  The software would be programmed to start using a new hash after a certain block number.  Everyone would have to upgrade by that time.  The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used.

However, if something happened and the signatures were compromised (perhaps integer factorization is solved, quantum computers?), then even agreeing upon the last valid block would be worthless.

True, if it happened suddenly.  If it happens gradually, we can still transition to something stronger.  When you run the upgraded software for the first time, it would re-sign all your money with the new stronger signature algorithm.  (by creating a transaction sending the money to yourself with the stronger sig)

Quantum computers will not break bitcoin overnight. It will take decades of slow progress that everyone can see coming before they become a threat, and they will break many other weaker algorithms along the way. They also only provide a linear increase in the speed to find a hash collision (as opposed to an exponential increase in the speed to solve the ECDLP), and so are unlikely to be able to break SHA256. But if it ever was to become a concern, then as Satoshi has said above, we will have plenty of time to transition in an orderly way to new quantum resistant functions and algorithms.

A hash function, such as SHA256 is intended to be a one-way function. That means it is possible to get the output of a function based on the input, but not the input based on the output. The problem is that it not possible to know for sure that a particular function is in fact a one-way function. To my knowledge, no one knows how to calculate the input, based on the output of a SHA256 function. That doesn't mean that someone will not figure out how to "break" SHA256 in the future.

I don't think breaking SHA256 (if it gets broken), will necessarily be done via QC. SHA256 getting broken is still a risk.

[vjudeu]

What we do about the vulnerable P2PK coins is another matter.

If P2PK coins are vulnerable, then P2TR coins also are. In both cases you reveal your public key. More than that: everything that is "ongoing", just transactions sitting in mempools are also vulnerable in exactly the same way, because when you spend your coins, you reveal your public key. Not to mention all situations, where you have any multisig, for example in the Lightning Network, where all public keys are known by all members of the channel.

I don't like hard forks, but I assume this can be tackled that way without damaging the owners of those addresses.

Making coins unspendable would be a soft-fork, because "things valid today are invalid tomorrow", that's how soft-forks work. In hard-forks "things invalid today are valid tomorrow", but we don't need that.

If ECDSA will be broken, we would need just another Scripts, nothing more than that. Instead of "<signature> <pubkey> OP_CHECKSIG", there would be "<newSignature> <newPubkey> OP_NEWCHECKSIG", probably with a better name than "new checksig". Also, it depends what will be broken and what kind of attack will be possible. Because if it will be possible to make a fake signature for a given z-value without knowing the private key and without knowing secret k-value, that's completely different situation than when it will be possible to recover any private key.