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

[Kakmakr]

I am just curious... if a upgrade is done to a new hashing algorithm that are quantum resistant, will everyone need to transfer their tokens to another address to enable this protection? If they do.... will this not force Satoshi Nakamoto to shift the tokens he/she/they own too?

Some people also said that a stronger hash will slow down the transactions and also inflate the Blockchain size? Will that be the sacrifice that we will have to make to protect our tokens from a Quantum attack?

[1713909461]

1713909461

[1713909461]

1713909461

[1713909461]

1713909461

[1713909461]

1713909461

[1713909461]

1713909461

[garlonicon]

will everyone need to transfer their tokens to another address to enable this protection?

Yes. Breaking SHA-256 means that it will be possible to find another transaction for a given z-value. That means, you could start from random ECDSA signature, matching some random z, and then use SHA-256 preimage to find some transaction that can be hashed into this value.

will this not force Satoshi Nakamoto to shift the tokens he/she/they own too?

It depends if our "protection" will burn the coins or not. In case of no protection at all, if that coins will be taken by some good guy, then that person could timelock them incrementally with no keys and split into smaller amounts, then it will be the same as soft-forking coin distribution schedule.

a stronger hash will slow down the transactions and also inflate the Blockchain size?

It will slow down the transactions, you can see that on CPU-mineable coins, when they use a different algorithm than SHA-256 for building their merkle tree.

When it comes to the blockchain size, there is no need for that, because breaking SHA-256 would mean that getting some hash with more leading zeroes will be easier. So, the new hash function could require getting a lot of leading zero bits in a known way (or even getting all zeroes if possible), then the new hash could be placed in the same field (and replaced with zero bytes to be backward-compatible with old nodes if needed). The new hash function could be just SHA-3(SHA-3(x)||SHA-256(x)) instead of SHA-256(x), where SHA-256(x) is required to be zero (or to be below some old target).

Will that be the sacrifice that we will have to make to protect our tokens from a Quantum attack?

There could be more than one idea to solve that problem. Some people could think that coins should be frozen, other group could think they should be taken by the first attacker, whoever it will be, and we should build on top of that (as Ethereum Classic did); another group can propose moving the coins in a special way to affect coin distribution by splitting coins and freezing in nothing except the time. I don't know which conception will win and how many altcoins will be needed to solve that, if there will be no consensus about it.

[seoincorporation]

I am just curious... if a upgrade is done to a new hashing algorithm that are quantum resistant, will everyone need to transfer their tokens to another address to enable this protection? If they do.... will this not force Satoshi Nakamoto to shift the tokens he/she/they own too?

If a new Hash Algorithm comes for sure it will be implemented in the current blockchain as a soft fork, that way users don't need to move to a new blockchain.

This Quantum Computer's topic has been discussed in the past, and we shouldn't be worried about it. If SHA-256 gets vulned there are bigger things to worry about than bitcoin.

[larry_vw_1955]

This Quantum Computer's topic has been discussed in the past, and we shouldn't be worried about it. If SHA-256 gets vulned there are bigger things to worry about than bitcoin.

bigger things than bitcoin? yeah like what?

[o_e_l_e_o]

If a new Hash Algorithm comes for sure it will be implemented in the current blockchain as a soft fork, that way users don't need to move to a new blockchain.

Not a new blockchain, but a new address. If P2PK or reused P2PKH addresses become vulnerable to quantum attacks, then coins on such addresses will need to be moved to new addresses or be stolen.

bigger things than bitcoin? yeah like what?

Large parts of the internet.

I don't know which conception will win and how many altcoins will be needed to solve that, if there will be no consensus about it.

A consensus on this issue will be very hard to achieve. I am firmly of the opinion that we should do nothing, and if dormant coins are stolen then they are stolen. The community shouldn't get to make a decision to deprive people of their coins, even if we think those coins are lost. If you do that, bitcoin is no longer decentralized.

[garlonicon]

I am firmly of the opinion that we should do nothing, and if dormant coins are stolen then they are stolen.

Even if you will "do nothing", then the question is: who will get those coins and what that person will do next? Burn them? Just keep them untouched on a new address? Just lock that in time for N blocks? Or maybe lock in time, but splitted incrementally, into small portions? Because if millions of BTC will be moved from P2PK to some new addresses, then the question is: what will happen next?

Of course, the heaviest Proof of Work could be used in normal circumstances to handle that, but not in this case. Why? Because if you will ever see 128 or more leading zero bits in block hashes, then it would mean SHA-256 is probably no longer collision-resistant, when it comes to the birthday attack. And then, there could be no consensus about the next hash function.

As a practical experiment, you can modify Bitcoin Core and replace 64-round SHA-256 with 16-round SHA-256. Then, you can try some attacks and see what could happen. Or you can cast 32-bit values into 8-bit values and make it four-step hash function (to get the same size), then you can try another kind of attacks.

What do you mean by "slow down the transactions"?

If SHA-256 will be too weak, then we could need some slower hash function (especially if we would like to make it backward-compatible and prove everywhere that SHA-256 is really broken). The new hash function could be bootstrapped from scratch, but then is it still the Bitcoin we know? By reusing zero bits in SHA-256, we could prove that our change is really needed. For example:

Code:

blockHeader=00004020b97d5e09984585663a48d8de73233254ab2ee13bd72f07000000000000000000a48018a3bd388812511e9d068d9cd711a82b78d3918482cd2ee3c9bbd0b2b70b283ee75e357f141704176980
SHA-256(SHA-256(blockHeader))=1364440dfe0d0b04ceaab68f57c93355f32d1c68030000000000000000000000
SHA-3(SHA-3(blockHeader))=a1fcfdd3bbff69a084f63db6c0cd46e8779fab414e788346df15e8e9f60ed953
endian256(SHA-256(SHA-256(blockHeader)))=000000000000000000000003681c2df35533c9578fb6aace040b0dfe0d446413
endian256(SHA-3(SHA-3(blockHeader)))=53d90ef6e9e815df4683784e41ab9f77e846cdc0b63df684a069ffbbd3fdfca1
oldTarget=000000000000000000147f350000000000000000000000000000000000000000
difficulty=0x17147f35
maskedBytes=0x17 (first byte from difficulty)
maskOld=000000000000000000ffffffffffffffffffffffffffffffffffffffffffffff
maskNew=ffffffffffffffffff0000000000000000000000000000000000000000000000
maskedOld=endian256(SHA-256(SHA-256(blockHeader)))&maskOld=000000000000000000000003681c2df35533c9578fb6aace040b0dfe0d446413
maskedNew=endian256(SHA-3(SHA-3(blockHeader)))&maskNew=53d90ef6e9e815df460000000000000000000000000000000000000000000000
finalHash=maskedOld|maskedNew=53d90ef6e9e815df46000003681c2df35533c9578fb6aace040b0dfe0d446413

[zatoshi_zakamoto]

*** Q-DOOMSDAY IS ARRIVING FAST ***

1M qubit quantum chip by 2024. All these fallacies "we are decades away" should be put to rest very soon enough

Wafer Scale Quantum Chip Prototype Delivers 1M Qubits by 2024
By Francisco Pires published about 13 hours ago

It is a quantum renaissance for fabrication industries from a 2-qubit computer in 1998 to 1 million by 2024.

https://www.tomshardware.com/news/wafer-scale-quantum-chip-prototype-delivers-1m-qubits-by-2024

There are already good already out there who are tackle this issue. Make your choice. In the brave new world of post quantum, old unsafe blockchains/coins are garbage:

-Tidecoin (TDC)
-Arielcoin
-QRL
-QANX
etc

[PrivacyG]

If Quantum MIGHT become a threat to Bitcoin and it IS possible to create an algorithm resistant to Quantum Computing, is there a reason we do not make Bitcoin stronger yet?  I have seen answers in this thread.  Most say the resources and time better be spent on something we need now rather than a decade from now.  But if there is a way to make Bitcoin stronger NOW, why not do it?  As in.  Why continue using today's algorithm when there may be or already is a better one behind the curtains?

-
Regards,
PrivacyG

[BlackHatCoiner]

But if there is a way to make Bitcoin stronger NOW, why not do it?

In my opinion, that's the (only) reason:

Whatever quantum resistant algorithm they implement today will either be completely outdated by the time it is relevant

So, even if we used a stronger algorithm today, it wouldn't last long 'til it was also considered unsafe in the long term. I don't know when will it be relevant, but it should definitely take a long time until someone solves the discrete logarithm problem within 10 minutes.

Let alone, it'd make the system less efficient.

[o_e_l_e_o]

None of the quantum resistant algorithms I am aware of are easily scalable right now, although I admit I am not an expert on them by any means. If we consider Lamport signatures, for example, then the signature for a message consists of 256 numbers, with each of those numbers being 256 bits longs, resulting in a signature of 65,536 bits, or 8 kilobytes. Even if we ignore the fact that Lamport public keys are twice as large as the signatures, you would be reducing the average number of transactions per block to a few dozen, which is obviously completely unsustainable.

There are no post-quantum algorithms which are as efficient as ECDSA, at least not yet. Prematurely forking to a specific algorithm would bring a number of significant drawbacks immediately for a potential improvement in the far future, but more likely we would just have to fork again closer to the time since the algorithm we ended up with would need to be replaced by something either more secure, more efficient, or likely both.

[garlonicon]

If Quantum MIGHT become a threat to Bitcoin and it IS possible to create an algorithm resistant to Quantum Computing, is there a reason we do not make Bitcoin stronger yet?

The main reason is that there is no consensus how to switch and to what algorithms. To introduce a new soft-fork, someone has to make some proposal, get it discussed, create a BIP for that, and go through the same process of soft-forking as changes like Segwit and Taproot did. It's not something that will be introduced tomorrow, because some people think it is a good idea. It's something that will take a few years at least. But you can start that process if you have some ideas how to switch and into what exactly we should switch.

What I described above may be acceptable when it comes to block headers, but we also have other hashes. And in that case, we would need re-hashing everything that uses SHA-256. Here comes the first question: what function should be used in that re-hashing? SHA-3? A combination of some new function and SHA-256? Also, the current solution will be less efficient that it may be in the future, because if it is publicly known how to create any preimage for SHA-256, then you can use that knowlegde and require such solution in every hash. As I mentioned, you can replace 64-round SHA-256 with 16-round SHA-256 and try to protect it somehow, for example with SHA-3. Then you will see, what can be attacked, how to attack, and you can start designing soft-fork to some new hash function; it is not that obvious, how to make it "soft", that's the lack of proposals and the lack of consensus about it, someone has to build it.

Many computer systems are based on unsolved mathematical problems. Hash functions we use today have some properties that makes them strong. If they will ever be broken, we will have one more solved mathematical puzzle and at least one more open mathematical question. The new hash function will be probably designed, based on such attacks, so it is hard to know the weakness upfront, because you don't know what needs to be protected.

Just be the change you want to see and propose something. I described above how any new hash function could be introduced in block headers, but that's only the small part of the solution (also it has a nice property that if you can reach SHA-256 with all zeroes, then it is the same as putting your new hash function directly in the same field, so it is kind of "gradual activation" with backward-compatibility, similar to how we have new transaction hashes for Segwit). There are many things to design if you seriously think about it, and the lack of detailed and well-discussed proposal is what stops us from switching.

Let alone, it'd make the system less efficient.

It is possible to build some network with re-hashed blockchain that will switch only after seeing a proof of breaking SHA-256. The Script is enough to describe both collision attack and preimage attack, also second preimage attack can be handled. So, technically you can protect yourself and convince people to use your software (having some working code covered with tests and running on some test network is the bare minimum if you want to ever see that on mainnet).

[BlackHatCoiner]

It is possible to build some network with re-hashed blockchain that will switch only after seeing a proof of breaking SHA-256.

I wasn't talking about the hash function, but asymmetric cryptography. How's a rehashed blockchain useful? Say we switched to SHA-3; wouldn't that eliminate the work that is done in previous blocks?

Also, how's that related with efficiency?

[garlonicon]

I wasn't talking about the hash function, but asymmetric cryptography.

Fixing asymmetric cryptography without touching hash functions is far easier. You can use ECDSA to spend coins from old addresses and move them for example to "OP_2 <newPubKey>". Then, that address type could require lattice-based signature or anything-based signature you want. Also, if you don't want to introduce a new address type, then you can require spending by TapScript instead of spending by key and redefine any OP_SUCCESS to OP_CHECKLATTICE and make scripts like "<newSignature> <newPubKey> OP_CHECKLATTICE". It could be OP_CHECKANYTHING, it could be based on the new algorithm. It would work if you can break ECDSA, but if you cannot break SHA-256.

But yes, that case has the same problem: there is no consensus, no proposal, no BIP, so it should be made first.

How's a rehashed blockchain useful?

It is needed if SHA-256 is broken. In that case, you could change old transactions in old blocks and trick not-yet-synchronized nodes by feeding them with your own transactions that has the same hash. Also, z-value in any OP_CHECKSIG-based signature is just SHA-256 of a modified transaction, so by breaking SHA-256 you can generate some random ECDSA signature, you will get random z,r,s combination that will be valid for a given Q public key, and then you can find a preimage for that z-value, create a transaction, add your signature and broadcast it.

Say we switched to SHA-3; wouldn't that eliminate the work that is done in previous blocks?

That's why my description above is a combination of SHA-2 and SHA-3 (you can put any 256-bit hash function here, the algorithm is the same). Of course to do it in a soft-fork way, we would need two difficulties: one for SHA-2 and one for some new hash function. Then, after fully breaking SHA-2 we will have new block headers that will hash to all zeroes in SHA-2 and to some non-zero value in the new function. Then, soft-forked new difficulty will stop the attackers, because their zero hashes will be non-zero under new function, so miners will produce a lot of headers that will be zero in SHA-2, but only some of them will be small enough in SHA-3. You can use the same data in that combined hash, it would work, as described in the example above.

Also, how's that related with efficiency?

If that change would be done in a soft-fork way, then for each hash you would need to compute SHA-2 as today and some new hash function. That is obviously slower than today, but has a nice property of "gradually activating", so it is "soft". But the above method is acceptable only for block headers, for merkle root it should be done differently, because you don't have any "difficulty" in a single transaction hash or the hash of anything else not used for mining.

[larry_vw_1955]

bigger things than bitcoin? yeah like what?

Large parts of the internet.

so why isn't the rest of the internet worried about this issue as much as bitcoin users? i guess they are just keeping their head in the sand thinking its someone elses problem to solve and when we finally "get there" someone else will have solved it?

A consensus on this issue will be very hard to achieve. I am firmly of the opinion that we should do nothing, and if dormant coins are stolen then they are stolen. The community shouldn't get to make a decision to deprive people of their coins, even if we think those coins are lost. If you do that, bitcoin is no longer decentralized.

that's an interesting opinion. expect a dip in price if that happens but people shouldn't complain if it did happen. after all. they are valid coins. just because no one expected them to be used doesn't mean they shouldn't be able to be.

[garlonicon]

so why isn't the rest of the internet worried about this issue as much as bitcoin users?

Because they don't use any blockchain. If you have just some software, you can change things in backward-incompatible way, if you have v1.0 of your software, you can just switch to v2.0 and do things in a completely different way. For example, if you store UNIX time as a 32-bit number, you can just extend it to 64-bit number. In case of a blockchain, it would be backward-incompatible, so it will be rejected, and finally accepted only if nobody has any better, backward-compatible idea.

Hash functions were replaced in the past. In centralized environment, it is easier to get rid of MD5 and use SHA-1 instead. The same with switching from SHA-1 to SHA-2. And it could be exactly the same in switching from SHA-2 to something else. Also, guess what: MD5 is broken only if it comes to collision-resistance, we still have no idea, how to produce a zero hash in case of MD5 (so we still don't know how to do any preimage attack on this hash function).

[o_e_l_e_o]

so why isn't the rest of the internet worried about this issue as much as bitcoin users? i guess they are just keeping their head in the sand thinking its someone elses problem to solve and when we finally "get there" someone else will have solved it?

Partly because of the answer garlonicon has given above, and partly because your average internet user is far less technically minded than your average bitcoin user. Most people are completely unaware how their computer works, how the internet works, how they communicate securely, and so on. Ask the average person the consequences of breaking SHA-256, and the response you will get is "What's SHA-256?" And the people who are working for the big tech companies on quantum resistant technologies aren't discussing their research in public forums, so we don't see it.

that's an interesting opinion. expect a dip in price if that happens but people shouldn't complain if it did happen. after all. they are valid coins. just because no one expected them to be used doesn't mean they shouldn't be able to be.

Absolutely the price would dip, but I'd much rather have a temporary dip in price than compromise the fundamentals of bitcoin itself. I also disagree strongly with the assumption that seems to be generally prevalent throughout the community that ~4 million coins are permanently lost. Just because a coin has not moved in x amount of time, does not mean it will never move. We not infrequently see coins dormant for 10 years start moving again, and a couple of years ago we saw for example a valid signature for over a hundred addresses containing thousands of bitcoin which hadn't moved since 2009 calling CSW a fraud, so we know that despite appearances many such coins are not lost and could indeed move at any time.

[mv1986]

so why isn't the rest of the internet worried about this issue as much as bitcoin users? i guess they are just keeping their head in the sand thinking its someone elses problem to solve and when we finally "get there" someone else will have solved it?

Partly because of the answer garlonicon has given above, and partly because your average internet user is far less technically minded than your average bitcoin user. Most people are completely unaware how their computer works, how the internet works, how they communicate securely, and so on. Ask the average person the consequences of breaking SHA-256, and the response you will get is "What's SHA-256?" And the people who are working for the big tech companies on quantum resistant technologies aren't discussing their research in public forums, so we don't see it.

that's an interesting opinion. expect a dip in price if that happens but people shouldn't complain if it did happen. after all. they are valid coins. just because no one expected them to be used doesn't mean they shouldn't be able to be.

Absolutely the price would dip, but I'd much rather have a temporary dip in price than compromise the fundamentals of bitcoin itself. I also disagree strongly with the assumption that seems to be generally prevalent throughout the community that ~4 million coins are permanently lost. Just because a coin has not moved in x amount of time, does not mean it will never move. We not infrequently see coins dormant for 10 years start moving again, and a couple of years ago we saw for example a valid signature for over a hundred addresses containing thousands of bitcoin which hadn't moved since 2009 calling CSW a fraud, so we know that despite appearances many such coins are not lost and could indeed move at any time.

You are bringing up some good points/facts here, but I am sure there is a substantial amount that is not accessible. "Substantial" is relative here, I know, but I believe there have been people losing or killing their hard drives without thinking about cryptocurrencies breaking trillions of dollars of market cap one day. I know a nerd who mined Bitcoin in 2011 just because some other dude from World of Warcraft told him. They didn't really trade or anything and he actually lost or threw away dozens of Bitcoin. Not a crazy amount, but just didn't bother to take care of them. I would say that that guy is a prime example for people who haven't really tried to go down the rabbit hole and conduct research on all the different angles Bitcoin brings about (socially, politically, financially, technically, culturally, etc.), didn't really pay attention to the actual emergence of a global ecosystem and then just forgot about those coins or didn't give a damn.

I also doubt it is 4 million that could be lost, but it might add up here and there quite significantly, with some losses being pretty damn painful (probably in the thousands of Bitcoin) I would imagine.

[o_e_l_e_o]

I also doubt it is 4 million that could be lost, but it might add up here and there quite significantly, with some losses being pretty damn painful (probably in the thousands of Bitcoin) I would imagine.

I agree. We've all heard and read the stories of people saying they have lost hard drives or wallets with hundreds or even thousands of bitcoin on them (although again, such stories are impossible to verify), and I'm sure the total number does add up to several hundreds of thousands. But the 4 million number we see bandied about on a lot of low quality clickbait articles is generally reached by someone saying "Look, all these coins haven't moved in 5/8/10 years, therefore they must be lost". Which, as I explained above, is highly inaccurate at best since we fairly regularly see such coins "waking up" and being moved or in some cases having a message signed from their private key(s).

Coins which are provably lost, meaning we are 100% sure they are lost and can never be retrieved (bugs, failed to be claimed by miners, OP_RETURN outputs, unspendable outputs, etc.) number only a few thousand. Anything more than that is speculation.

[darkv0rt3x]

I don't think it can. At least, in the upcoming few years, I think Quantum computers are still too expensive for someone to try such thing. I remember to watch a video quite some time ago and the video was explaining how hard it is to keep the computer running smoothly, how much energy it would spend and how would it cost, like per day, or something like that. The numbers were alarmingly high and the technology needed to keep the computer running was also large.

A part from that, I think there are already people working on Quantum resistant algorithms for when that time comes!

[zatoshi_zakamoto]

I don't think it can. At least, in the upcoming few years, I think Quantum computers are still too expensive for someone to try such thing. I remember to watch a video quite some time ago and the video was explaining how hard it is to keep the computer running smoothly, how much energy it would spend and how would it cost, like per day, or something like that. The numbers were alarmingly high and the technology needed to keep the computer running was also large.

A part from that, I think there are already people working on Quantum resistant algorithms for when that time comes!

it would clearly be a profitable operation to run a qc, hacking few 1000s of btc/eth, then silently dump them to the sheep saying "quantum threat is decades away blablablabla". you won't see it coming even if you know that it's coming. And at first, it's clear that no individual or small organization will have access to such infrastructure, but some state sponsored actors or  big tech corps (Google, IBM, Microsoft, etc) would