Topic: Can Quantum Computer's destroy Blockchain and Bitcoins[SHA-256 specifically] - page 3. (Read 1787 times)

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.

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.

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.

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.

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).

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?



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.

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 ". 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 " 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.

Quote

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.

Quote

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.

Quote

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.

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?

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.

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).

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.

In my opinion, that's the (only) reason:
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.

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

*** 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

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.

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:

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.

Large parts of the internet.

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.

bigger things than bitcoin? yeah like what?

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.

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.

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.

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).

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.

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?

you really have to love the amount of wishful thinking regarding quantum computer and its threats to btc & al.
the attitude I read here is like knowing a tsunami alert was raised, the ocean is retreating and still beachgoers are standing watching and want to see the first big wave before running for their lives  

to each his own exit strategy ...

Such risk could be significantly reduced with proper cryptography and implementation audit. Besides, Bitcoin is quite conservative where new feature took very long time of testing.


Cryptography has always been "game of cat and mouse". There's good reason why cryptography software (such as pgp) generate key with expiration date.