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

Researching for months but didn't somehow come across this?


...

Thirdly, there's no HD standard. Most wallet software have adopted BIP39, Electrum & Armory have their own (AFAIK), etc. But the protocol recognizes no deterministic keys; that's something the Bitcoin community - and specifically some developers - have invented unofficially and nonconsensually. Therefore, such change is beneficial subjectively, because you can't include all wallet software's HD rules nor there is a "neutral" list of those software.

And even if there was such list, you're burdening full node's cost, because it now has to verify computationally expensive functions such as PBKDF2 and HMAC-SHA256, that can be deliberately abused to establish an attack successfully. For example, I can provide a zero-knowledge proof of my HD wallet in which I used millions of PBKDF2 rounds to generate.

Interesting. I wonder how would this be done technically, is this mechanism described anywhere? My doubt is about how "the blockchain" (i.e. the Bitcoin client in combination with the blockchain data) can know about HD seed phrases / master public keys. All what is stored on the blockchain (from my knowledge) are signatures, public key hashes and (in the case of P2PK) public keys, can you derive information about the HD "master key" from one of these elements?

Are there any puzzle or Crypto vendors for your Bitcoin Crypto Grafix.
You believe you won't take any keys and you'll catch them at another party?
So think we are far behind and your attacks will be successful, think about it .

That's not entirely true. It would be possible to lock some coins in a way in which the original owner could move them but a quantum attacker reversing the ECDLP could not steal them. This would be done by requiring some proof, ideally a zero knowledge proof, of possession of the seed phrase or master private key which was used to derive the relevant private key. The true owner who had derived the private key in an HD wallet would be able to provide this proof, while a quantum attacker who had obtained the private key from the public key would not.

The downside to this approach is two-fold, though. Firstly, it only protects reused HD addresses, and does nothing for the 1.73 million BTC in P2PK addresses. Secondly, there is no way of knowing which addresses were generated in an HD manner and which were not, which would mean some coins being locked forever and being irrecoverable by anyone, the true owner included.

exactly.

I think that Satoshi thought about it and made the same decission like you described it here. Let them move 

If they're "lost", i.e. nobody has access to them anymore, there would be no way to protect them with the exception of harsh methods like the blocking of these addresses/utxos (something similar Ethereum did when TheDAO was exploited).

I personally would be against this - I'd rather be ok if they're "stolen" and dumped, even if this meant a sudden price crash. Distribution afterwards would probably be better, and I expect only short term price turbulences. Take into account that if these coins were mined by a single entity (most likely Satoshi) then there is always the danger that they're suddenly moved and be sold, either because Satoshi himself is selling them, or because his computer was hacked (he should have had some knowledge how to secure his data, but nothing is impossible). This danger would then be gone forever, so I expect a quick price recovery. (Anyway, quantum computers would have to solve each address separately, and at first they would be rather slow with that task. So the dumping process could be pretty long - at least if the "dumpers" wanted to maximize profit - and maybe thus the amounts would be too low to generate much panic)

What will we make with early mined coins that haven't been moved since ~2010, eg. Satoshi's coins?

Just wanted to add a thought I had some days ago (have thought about it and I see no drawback until now).

Like garlonicon wrote in this post, most of we'd need to make Bitcoin "quantum-resistant" is to extend Bitcoin Script with mechanisms to handle other public key cryptosystems than ECDSA.

While there's surely a long way to go to get this implemented in the Bitcoin protocol, one could imagine an extension protocol for tokens based on the OP_RETURN mechanism, like OmniLayer, supporting interesting quantum-resistant cryptosystem candidates first, which would be possible much faster (they could simply copy/paste parts of the algo of this shitcoin which was promoted in this thread by a certain FUDster ). You could then not only create Tether-like centralized tokens which are quantum resistant, but also in theory an 1:1 pegged Bitcoin stablecoin - the easiest way would be using a proof-of-burn scheme, where each bitcoin burnt would entitle its owner to create one unit of the quantum-resistant Bitcoin stablecoin (we could call it QBitcoin).

If the threat becomes real at some point and Bitcoin extends its Script language to support a quantum-secure algorithm, then it should be possible to "merge" the QBitcoin with the "old" upgraded Bitcoin. This would be a way to ensure QBitcoin's peg with Bitcoin holds, although maybe not absolutely necessary.

I write this mostly because if someone is really worried about quantum computers then this could be possibly a straightforward path for Bitcoin to achieve quantum resistance step by step, without having to wait for a complete, thoroughly-tested implementation - and no shitcoin is really needed.

By the way, I wonder if Simplicity, if it gets included into Bitcoin, could provide the necessary functions for "quantum resistant addresses"? In the whitepaper it's mentioned that it's "expressive enough to represent any finitary function", so wouldn't "quantum computer resistant cryptography" be a possible use case?

I started this thread a few months ago to understand what others think of the same question. I, myself have been around this specific question for a long time and I think technology itself has a solution to this particular problem, Technology cannot destroy technology itself unless they both have an understanding conscious that thrives being "ON TOP".

In that case, it is going to be a long marathon[which might be never ending] in the case of: Quantum Computers --> (running for) Bitcoin.

I think this is what gets to fork bitcoin and improve it for the larger mass to adopt it [It is particularly a slow process]. Exactly how the internet was Born and raised.

I know it exists on Bitcoin blockchain. I thought about similar challenges in the context of this altcoin, quantum computers and instant break. Because without any "in between" step, it looks like bogosort way of sorting.

See https://bitcointalksearch.org/topic/bitcoin-challenge-transaction-1000-btc-total-bounty-to-solvers-updated-5218972

I wonder if there is any puzzle-like challenge for breaking Bitcoin cryptography on your chain. Are there any "in between" steps or do you believe that one day you will break no keys and another day you will catch them all? Because if there is any such challenge, then it may be possible to see, how far we are from that, and also check, how successful are your attacks (and check if they are real or not).

This is a very common misconception that people do when talking about the security threat of quantum computers to btc & co. The main issue is not about the encryption algorithm, but instead of signature algorithm as it was mentionned in the link.

If a paper says the threat is non existent or is centuries away, feel free to believe them. But ask the authors how much money they will bet on their timeline and I am happy to bet against them

This doesn't say much, just that:
Where did you conclude that once SHA256 is broken, we'll upgrade to SHA384? If SHA256 becomes broken, which is a doomsday scenario, we shouldn't use neither SHA384 nor SHA512 as they all belong to SHA-2.

There's also a paper that explains why quantum computing isn't a problem for bitcoin, let me put it right here: https://arxiv.org/pdf/1710.10377.pdf.
Also, this thread: I don't believe Quantum Computing will ever threaten Bitcoin.

Some educative information from QRL THE QUANTUM RESISTANT LEDGER. Follow the links:

It's going to affect Bitcoin

Bitcoin's developers have already planned for this

Bitcoin will just hard/softfork

If they can break SHA_256, we’ll upgrade to SHA_384

But if you don’t reuse addresses, you’re safe because BTC only exposes the hash of your public key if you have never transferred BTC from that address

Quantum computing is a long ways away, there's no need to bother

If ECDSA will be broken, banks and the whole internet is broken. Blockchain is the least we’ll need to worry about then.

More info here.

Aha, so tell me, how to create N-of-N multisig without knowing any public key. Of course, you can combine OP_CHECKSIGADD with OP_HASH160 or OP_HASH256, but it will take much more space and will be much less private. You will not get a single Schnorr signature in this way. You will have to at least reveal all public keys. Also, spending by key can be locked in Taproot and we can force TapScript in a future soft-fork when needed. Another way is introducing new SIGHASHes.

That progress is gradual. You will not fully break SHA-256 tomorrow if you don't even know how to make MD5 preimage. And you will not break 256-bit regular keys without breaking easier 120-bit keys first. For now, 64-bit key is not yet touched, and it is still possible to grab 0.64 BTC by checking 2^64 private keys. Also, we can observe SHA-256 resistance just by watching block hashes. If quantum computers would be real, the attacker could silently mine new blocks and get more coins than breaking any keys.

In the past, the whole progress was gradual. What makes you think that it would be totally different this time?

Edit: one more thing: if you know how to do things in the right way, you can propose a BIP for that, right? Because for now, I can see no BIPs related to quantum-resistance that are ready to be implemented. So, you have two choices: you can complain about things on forums or you can fix it (or switch to a coin that fixed it if BTC will not adopt your solution), so why don't you fix that?

yeah sure, we are 100 billions years away from quantum computers ... no worry
and by the way, thanks to Taproot, little effort is required to know address public key, but I guess you did not pay any attention to that 'detail'!

So rather good luck to you, you will need it much more than I do ...
And feel FREE to keep betting against science and technology progress. You will indeniably end up on the WRONG side of history

Good luck. First, try to find 120-bit private key from transaction puzzle (or 64-bit private key with unknown public key and known address). There are many challenges that are far easier than regular 256-bit keys, and you will quickly see, how far we are from quantum computers if you try to break any of them.

why waste time mining BTC when you can do much better with a quantum computer?

that's a very poor use case ... Instead, I will aim to hack all big wallets, starting with Satoshi wallet (980, 000 BTC) and other big wallets, then start dumping them asap ...

Latest Quantum Computer available commercially - D-Wave Quantum Computer
Costs: $15,000 (That too un-configured for Bitcoin Mining, coding will cost additional man's salary)

Quantum Computer Operation: Well you will probably need a room or at least superconductors which would be cooling down your 2000Qubic chip down to the -273 degree celsium.

If you have money then it's fine, buying computer worth $15 million wont be big deal for you. The question is would you be able to maintain the temperature below zero degrees all the time? Imagine the power consumption required to do that one.

Forget about break even point, you wont be able to recover the yearly power consumption out of the bitcoin mining.

If you start to inject the market with heavy supplies of bitcoin, assuming you are mining 1000x others, then ideally the supply will easily fill up the demand and might reduce in the pricing.

For example, Supercomputer in China, named Tianhe-2 use 18 megawatts of electricity.

In conclusion even if we use it, it wont be beneficial at all.

they're trying to develop it but new things aren't always so solid. you need time to try and crack them. like years and years. no one broken RSA in decades so it's pretty solid. but you can't say the same thing about most of this new stuff.

https://www.linkedin.com/pulse/post-quantum-almost-standard-completely-cracked-lessons-roger-grimes

you also have some mineable new blockchain based on NIST round 3 quantum resistant signature algorithms:
-Doge protocol https://dogeprotocol.org/
-Tidecoin https://tidecoin.org/
-Arielcoin https://arielcoin.org/

And QRL based on quantum resistant algorithm called XMSS:
https://www.theqrl.org/

start mining & accumulating till the day (soon in the future, maybe by 2025...) when quantum threat wipes out 99.99% of crypto market caps (BTC, ETH, etc)

It's NOT a token project. It's a brand new blockchain. True that it's being supported by a token right now. But according to their roadmap, token holders will swap their tokens for native coins on the new L1 quantum resistant Qanplatform blockchain.

what do you think of the token $QANX ? QANPLATAFORM

they said to have a solution for this.

thanks!

It is simple. If you want to do it in backward-compatible way, then it will be always slower than the current implementation. You will have new_computing_time=old_computing_time+upgraded_version. If that "upgraded version" is positive, then the total computing time will always be greater than today. For example, if old_computing_time=1 and upgraded_version=0.1, then it is ten times faster. But as long as the old version is not broken, it is 10% slower.

The mailing mention NTRU would make node perform extra validation, yet NTRU implementation show it's far faster than ECC-NIST (closest one to cryptography which Bitcoin use). Can someone explain why?


Source: https://tbuktu.github.io/ntru/

Don't worry, people know about it and there are some discussions on our mailing list: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-April/020209.html

So, you think that not even the devs working on Bitcoin Core wouldn't see it coming in time of implementing Quantum resistance algorithms? I am sure they are aware and they are bright enough to see it coming. I mean, the technology must be developed, software must be developed and I don't believe that can be hidden from everyone up to a point that nobody will see it coming!

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

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!

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.

Well, it's not just that. Another problem is these Post Quantum algorithms aren't really vetted in the sense like AES encryption is or say Elliptic Curve is. They dont have decades of trying to crack them so they might even be vulnerable to a normal computer to say nothing of a Quantum Computer. Bitcoin might be better off sticking to what it has than going with a shiny new object that ends up being cracked by a pentium 4 laptop running for a weekend or two. There's nothing magic about post quantum crypto it's still a game of cat and mouse. No one can prove anything... As long as they keep trying to rely on complexity, they're in trouble. Complexity should be in quotation marks that is.

With recent Taproot update, actually it's 4x effort. Native SegWit have prefix bc1q while Taproot have prefix bc1p.


Alternatively don't store private key without coin.

Sure, but I'm just pointing out how infeasible this would all be. Compression would save some time, but I also glossed over that for each and every key you would also need to perform an elliptic curve multiplication, four hash functions, and a hex to Base58 conversion, all just for the legacy addresses. And then of course you would need to look the address up against a full node to see if it contains any coins. And even if you someone managed to compress a billion private keys in to the space usually occupied by a single private key (32 bytes), you're still looking at needing an entire galaxy filled with Dyson spheres to have the energy to do something like this.

Plus: You would need to find a way to transfer information unbelievably fast. Even if one planet in one of those galaxies found a collision, they had to somehow share it with others. Good luck on that too! 

BTW, that's just for one type of addresses. If you wanted both Legacy (1) and SegWit (3, bc1) you'd have to triple the effort.

You could find ways to compress all this, though. For instance, private key 1 doesn't need to take 32 bytes.

2²⁵⁶ private keys * 32 bytes each = 3.7*10⁵⁴ yottabytes.

Current estimates for the amount of data ever created in the entire world are less than 0.2 yottabytes.

So even if there were 1 billion galaxies, each with 1 billion planet Earths, and each Earth produced a billion times more data than us, and each Earth had been churning out this much data for a billion years, you still need a computer which can handle a billion billion times more data than that all at once.

Good luck.

What I was imagining was a computer that tried all possible outcome for private keys in one run.

At once. No queue.

QC is actually a way for brands like Microsoft to get funds from investors. Quantum computer cannot exist in the first place because of the number of qubits required to solve a cryptographic problem is much and they are fragile too. The qubits cannot stay in some environments. It depends on weather conditions.

Even ignoring that it will be decades before there is a quantum computer which can solve the ECDLP, it will be many more years between one can that solve the ECDLP over a period of weeks and one which can solve the ECDLP in less than the 10 minutes required to attempt to double spend an unconfirmed transaction.

I don't think we should intervene here. We have absolutely no way of knowing which coins are simply being held long term by their owners and which coins are lost or otherwise inaccessible. The network and the community absolutely shouldn't be taking decisions to deprive the rightful owners access to their coins, even if the inaction of these owners to move their coins to a quantum resistant address will result in their coins being stolen.

the problem here is not sha256
The problem is that the private key of the pubkey entering sha256 is broken.
if ECDLP of secp256k1 is decrypted.
then we can talk about this apocalypse.
In this case, the blockchain and all values are 0 and cannot be moved.
If we want to move the values, we can do it according to the priv key, but we can't because it breaks. I think new blockchain movable with losses. bitcoin can suffer serious damage from this. Unclaimed coins can be used.

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.

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?

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

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.

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.

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.

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.

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.

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

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

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



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.

This belongs to the Development & Technical Discussion.

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.

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

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.

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?