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

I don't see the point in any "quantum resistant" coin at the moment when we are still decades away from quantum computers being a threat to elliptic curve cryptography. Whatever quantum resistant algorithm they implement today will either be completely outdated by the time it is relevant (so maybe things such as much larger signatures and transactions than necessary, far less functionality allowing for different script/address types, much more resource heavy or slower to computer/verify, etc.), or might itself be broken and completely insecure.

It would be like a video game developer building a game today which won't be released until 2045 for the PlayStation 9. They have no idea what the technology will be or what its capabilities will be 20 years in the future, and whatever they come up with today will be incredibly outdated and might not even work by the time it becomes relevant.

I think this is somebody who wants to profit from the fear of some Bitcoiners about "quantum computers hacking the blockchain!!" luring people into his shitcoin.

Iota tried this, too, but they're now worth much less than before. I wouldn't call them outright scams still, but quantum resistant cryptography has much less testing until to date than traditional algorithms, and this coin was created in 2017 so it has even less testing than "current" quantum resistant algos (they may be hardforking to newer crypto algorithm versions - but Bitcoin could do that, too, in theory, so they haven't any advantage).

Stay away.

Hello
someone else mentioned this
do you mean something like this?

https://coinmarketcap.com/cryptown/profile/xufd90jiwedh?guid=77572615

"Quantum Apocalypse"
I think it's trying .

Thanks.

For now, sure. But there is nothing stopping us from implementing script-path only taproot addresses or even just hashing P2TR addresses and creating some P2PKH-P2TR hybrid, which would allow us to use taproot addresses in a more quantum resistant way prior to the implementation of whatever full quantum resistant scheme we end up with.

You will stay in a network if you make them non-standard (that would be no-fork). You will also stay in a network if some soft-fork will make them invalid and you will use some old version.

Yes, but all P2TR addresses has an option to spend by key. And if P2PK is broken, then you can ignore a script path (that can be even some unspendable OP_RETURN) and use key path. Only P2TR coins sent to invalid public keys can be considered unspendable by consensus, for example when you send coins to bc1pqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqpqqenm (on the other hand, bc1pqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqs5pgpxg seems to be unspendable, but it may be, if you somehow reach the private key for 020000000000000000000000000000000000000000000000000000000000000001).

As are all the coins in reused addresses. As are all the coins in light wallets which send master public keys to servers to look up their balances. As are all the coins received via payment processors where the user uploads their master public key to generate new addresses for each customer. And eventually, as are all coins as soon between the time they are spent and they are confirmed.

Taproot was never designed to be quantum resistant. Still, with taproot you can use specific script-paths rather than use key-paths at no extra cost to avoid the issue of your public key being revealed.

How will I stay in a network where blocks contain transactions that I consider invalid?

It is perfectly valid. You can run a node and make P2PK non-standard in your node (and reject all transactions that create or spend any P2PK coins), you will stay in the network if you do that. If most nodes will do that, then in practice P2PK will be unspendable by any average user. It is the same as in case of Value Overflow Incident: you can run some old node with old rules, you can create a transaction that will create coins out of thin air, but your transaction will be ignored by other nodes. On the other hand, you will still stay in the network, as long as the heaviest chain moved to the new rules. So, making P2PK non-standard is a no-fork solution that can work right now. Soft-fork is just one step further, where you make P2PK invalid and reject blocks, in the same way as you reject P2TR blocks without signatures (but they were accepted in the past), and in the same way as you reject blocks creating coins out of thin air because of Value Overflow Incident.

And how would P2TR resist? We just moved to "OP_1 ". We can move to "OP_2 " in the same way (if calculating the private key for any public key will be possible and P2TR will be vulnerable) and add any rules, any algorithm we want, for example it can require lattice-based signature. The same with script, we have tapscript with OP_CHECKSIGADD, it is entirely new Script version, where we have OP_SUCCESS opcodes, and where OP_CHECKMULTISIG(VERIFY) is invalid. If only spending by key in P2TR will be vulnerable, we can force spending by script, invalidate OP_CHECKSIG(ADD) and force using some new OP_SUCCESS that can be replaced for example by OP_CHECKLATTICE.

Isn't invalid today to consider P2PK unspendable? It's currently spendable.

How would the new Scripts resist? Are you saying that we wouldn't need a resistant algorithm?

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.

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 " OP_CHECKSIG", there would be " 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.

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.

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.

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

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.

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.

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.

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

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.

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.

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.

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:


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.

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.

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/

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.