Quantum Computer vs Bitcoin

[haltingprobability]

@nullius, @haltingprobability

Thank you guys for your posts, I find it much easier to learn about cryptography and comp science from examples and discussions rather than just raw theory, and this is exactly the kind of replies I wanted to see when I posted my question.

Now, I got more questions.

1. Would it be possible and would it make sense to add more digital signature algorithms and more hash functions with various key/hash sizes?

For example, shorter keys, signatures and hashes would result in addresses that have smaller transaction sizes, so people could optionally use them to save up on fees. Longer keys, signatures and hashes would provide some additional security for paranoid people, at costs of higher fees.

These could be added to Script as new opcodes and you can use P2WSH to implement a smart-contract that uses them.

2. RIPEMD-160 is not the only hash function in Bitcoin's Script, there's also SHA256. Does this mean that even now we can create our own P2SH outputs with more bits of security than the standard addresses that useRIPEMD-160?

You can use a script to hash-lock a transaction multiple times over. This would not really add any security, however, it would just be a silly way to subsidize miners with needless transaction fees.

[Xylber]

Quantum computers is definitely not a threat to Bitcoin. These computers cost millions of DOLLARS and undoubtedly be able to spread.

Well, but goverments, Google, Microsoft, all of them can use quantum computers.

[haltingprobability]

Quantum computers is definitely not a threat to Bitcoin. These computers cost millions of DOLLARS and undoubtedly be able to spread.

Well, but goverments, Google, Microsoft, all of them can use quantum computers.

That's why abutingting's argument is a non sequitir. QC is not a direct threat to Bitcoin for a variety of reasons - the cost of quantum computing is a part of the reason that FUD about QC is ridiculous, but not because anyone is being "priced out" of quantum computing.

[Jean1948]

I just think that the relationship are directly proportional.  To be more specific, if Quantum Computers evolve to common use, the security encryption will also evolve to match.  The quantum computing technology is not one faceted, meaning it's not only for breaking encryptions, it can be used to create more sophisticated levels encryption.

[mlgblockchain]

I just read about Quantum Computer on google. But honestly, I didn't get a clear picture. Can anybody help me out here with some simple words? I read the replies on this thread as well. But everybody is using "fake science" or similar words. What is the reality here?

[haltingprobability]

I just read about Quantum Computer on google. But honestly, I didn't get a clear picture. Can anybody help me out here with some simple words? I read the replies on this thread as well. But everybody is using "fake science" or similar words. What is the reality here?

The word "computer" has been changed by the transistor, integrated circuits, personal computers and the Internet. 50 years ago, the word "computer" had a lot more mystique and referred to a much broader class of systems. Today, the word "computer" refers to a very definite kind of system, the kind you're using to view this post. Prior to the rise of the digital computer, there were many types of computers, including mechanical computers and analog electronic computers. Analog computers are very efficient for specialized problem solving.

Quantum computers are best thought of as a very noisy analog computer. On a digital computer, we ask a question just once, and it either calculates the answer or hangs. On an analog computer, we pose a problem within the computer's domain and then we set it solving. Usually, the analog computation proceeds "directly" to the solution, that is, with a minimum of wait time. But the results of the analog computation are subject to limits of precision imposed by physical measurement - to get more digits of accuracy, you require finer measurement and more lossless action within the mechanism or circuit. For a quantum computer, we have the same measurement problem as with analog computers, plus the solutions it gives do not have the property that digital computers have - either correct or it hangs. Rather, the quantum computer will return a "distribution" of answers over repeated computations that hopefully clusters tightly around an average value, which we take to be the solution.

Imagine you're a physicist running simulations on some difficult problem of physics. Your options:

- Build a digital simulation (requires a lot of programming). Once finished, set the simulator running and walk away. When you come back, either the simulator will have solved your problem (exactly) or it will have hung.

- Build an analog simulator. You have to build a new simulator for each problem domain you want to solve. It also requires high-precision parts and cannot perform simulations to the level of precision of a digital computer. But, once built, it's much faster than a digital computer.

- Build a quantum computer. This also requires a lot of programming but you don't have to build a new quantum simulator for each problem domain since quantum computers are "general-purpose". It requires high-precision parts and other exotic measures to prevent "decoherence" (a problem that other computers do not have). It can, in principle, perform simulations to the level of precision of a digital computer but each "run" of a quantum computer is random, meaning, you don't get "the answer" on any particular run of the computer, you must run the problem repeatedly and take the average on the output. This makes quantum computers quite different from either analog computers or digital computers.

[aimexlondon]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

No. Quantum theory is fake "science" and does not exist, nor do "quantum computers".

I couldn't agree more! no such thing!

[Accessence]

Quantum computers will actually compete with traditional transistor based computers as it turns out they'll be slower in certain aspects than their transistors based counterparts. This is based on my independent analysis of quantum computing but we'll just have to wait and watch when these devices start to roll out in the market, as far as bitcoin is concerned the worst possible scenario would be a hard fork to make it 'quantum-resistant'.

[haltingprobability]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

No. Quantum theory is fake "science" and does not exist, nor do "quantum computers".

I couldn't agree more! no such thing!

Um. Wuuut?

Reality is quantum ... try it for yourself. Also.

[aurigae]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

It's something that Bitcoin's designers need to keep in mind as a "tail risk".

Quantum computers reduce the effective security of our strongest cryptographic primitives (hashes, symmetric ciphers) by about half. That is, a 256-bit hash gives about 128 bits of effective security in a world where quantum computers are used for at-scale computation. 128 bits of security is pretty good security - searching 10³⁷ gives about a 10% chance of breaking a particular hash (finding the hash preimage). 10³⁷ is 10 quadrillion quadrillion quadrillion - that's more than a billion billion times the number of hashes performed by the combined hashpower of all Bitcoin miners in order to mine a block.

The hash address is only 160 bits but it still requires 256 bits of search to break, that is, address=RIPEMD160(SHA256(pubkey)) minus a few technical details. Once you get the pubkey, we typically assume that a quantum computer will easily recover the private key from the public key. However, quantum-resistant public key encryption is still possible. Because of its quadratic advantage (theoretical) over classical computers, we have to double the key space (note that this may more than double key size). IIRC, secp256k1 is 128-bits equivalent security which we have to cut in half in a quantum-computation world - effective security is 64-bits. While 64-bits is too small for securing a large asset (such as all bitcoins), note that each address is secured by 64-bits security. So the cost of breaking all addresses in the UTXO set is at least 64 * nUTXO where nUTXO is the number of unspent transaction outputs. In other words, even with a quantum computer, you still have to break each address separately, and there are a lot of addresses.

Finally, quantum computation will actually help Bitcoin more than it will hurt it. As QC's begin to approach sufficient complexity to be able to mount serious attack against Bitcoin's cryptographic primitives, they are going to force cryptographers to revise usage across many cryptographic applications - traditional banking, government communication and data-storage, military communications systems, and so on. Quantum cryptography offers the promise of new modes of communication that are not possible with classical communication channels. Perhaps you can secure your Bitcoin address with an entangled set of qubits such that only the holder of the originally entangled qubits can prove ownership of the address. So, Bitcoin should not be having FUD about QC.

Bitcoin also need to note an attacker maybe doesent need to brute the entire keyspace if shooting for one key ie rich wallet. What are the odds of hitting a key before the entire key space is bruteforced ?  

Then theres cluster bruteforce - obviously nobody did that in a really madass large scale, at least not publicly yet. Are there even bencharks wha twould be possible? For example a botnet of really large server, 30x raids in a huge cluster. Since one of those boxes costs 50K plus, yeah one has to be serious - for that to happen the loot just has to be big enough and somebody will try.

[haltingprobability]

Note that I made a mistake on the size of the secp256k1 key space - it is greater than 2²⁵⁵, not approximately 2¹²⁸.

Bitcoin also need to note an attacker maybe doesent need to brute the entire keyspace if shooting for one key ie rich wallet. What are the odds of hitting a key before the entire key space is bruteforced ?  

"entire key space is bruteforced" --> It's difficult to give a good metaphor for how huge the secp256k1 keyspace is... it's effectively infinite.

The birthday paradox tells us that the average time to collision for an n-bit hash function is 2^n/2, in our case, 2¹²⁸. Fortunately, 2¹²⁸ is large enough that it can also be treated as "effectively infinite". At this writing, the hash rate is 8.4x10¹⁸ hashes per second. The average time to collision if you could test public keys at this rate (you can't) would be 585 billion years.

Then theres cluster bruteforce - obviously nobody did that in a really madass large scale, at least not publicly yet. Are there even bencharks wha twould be possible?

See above. If you owned all the hashing equipment in the entire Bitcoin network and could somehow use that equipment to test keys at the same rate as the hashrate, it would take 585 billion years to brute force any key. Clusters are powerful systems for computation but their compute power only grows linearly with cluster-size - a cluster of 10,000 nodes is only 10x as powerful as a cluster of 1,000 nodes. The difficulty of breaking cryptosystems grows exponentially in the number of bits of security (assuming there are no mathematical breaks).

For example a botnet of really large server, 30x raids in a huge cluster. Since one of those boxes costs 50K plus, yeah one has to be serious - for that to happen the loot just has to be big enough and somebody will try.

I think your arithmetic is off by more than you realize.

[aurigae]

Thank you!

See above. If you owned all the hashing equipment in the entire Bitcoin network and could somehow use that equipment to test keys at the same rate as the hashrate, it would take 585 billion years to brute force any key.

Im just curious but not a professional obviously, that was the first post ive read which puts it in some context

[Alonzo C]

Short answer: No
Long answer: Bitcoin's proof of work algorithm is secure because they would have to use grovers algorithm to crack sha256 which would take O(2^sqrt(n)) time instead of O(2^n) which is a good speed up but still not enough to crack sha256 (it may give miners using quantum hardware an advantage). However elliptic curves are vulnerable to attack by shor's algorithm so a new signature function would be needed for example lamport signatures, however they will not protect people who have not moved to the new signature scheme before quantum computers are created. On the upside addresses which have not had their public keys revealed are safe₁ because of the hash function protects the key but this protection is not present in the early bitcoin accounts because they did not used hashed keys for example satoshi's coins and all other coins pre-2012 which have not been put in a quantum secure could be at risk.

1: but the coins cannot be moved without comprising them
PS: If quantum computers hit the world by surprise we have more to worry about than bitcoin

[Hamphser]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

Nope, Quantum Computer cant really easily decrypt cryptocurrencies and as being said its much harder to solve out 2x than on x2 which have been mentioned on previous pages of this thread which I do completely agree. This is why I don't really see that these computers would really be a big threat. If it can affect then it would not be on major thing for sure and besides this apparatus is costly.

[swogerino]

Quantum computers is definitely not a threat to Bitcoin. These computers cost millions of DOLLARS and undoubtedly be able to spread.

Well, but goverments, Google, Microsoft, all of them can use quantum computers.

You can choose to fight back with the little tools at our disposal. TAILS Linux operating system is an OS which has Electrum included and you can keep the seed in a safe place and restore it every time your run TAILS. This operating system doesn't leave any trace on your computer unless you want to, when it connects to the internet it only connects through TOR browser so government cannot do that much to stop anyone from using Bitcoin or be a threat to your Bitcoins.

Quantum computers are not build to be a threat to cryptocurrencies but to help aid NSA and other security agencies do their job better.

[Yabuy92]

I heard that Quantum Computer can destroy bitcoin.
Is it possible?

Quantum computers could crack Bitcoin, but fixes are available now,actually there is good news about this. its proof-of-work isn't as vulnerable to “quantum speedup” as people think, and the signature can be replaced with something more quantum-resistant before the day of reckoning.

[lemonmob]

Quantum computers are the best medium you can use in order for you to get and mine as much Bitcoins as you can. You need to understand that quantum computers are the best there is.

[Vigme86]

So the general consensus is somewhere along the lines of "if quantum computing cracks Bitcoin, there will be bigger and more serious problems to worry about"?

Pretty close. Here are the facts:

...

3) For certain kinds of problems, QC can provide quadratic speedup, which is a massive speedup. For symmetric ciphers, this probably just means you double your key size - where 128 bits of security used to be sufficient, now you need 256. No big deal. The real problem is with public-key encryption. But lay-people often forget that the quantum speedup blade cuts both ways. We can build encryption systems which take advantage of quantum speedup and make quantum cryptanalysis of PKE quadratically more difficult, mooting the theoretical advantage that cryptanalysts get from quantum speedup. In fact, this is why Bitcoin uses the public-key hash instead of the public-key itself and recommends against address-reuse; in the event of working, at-scale QC, your coins are still secured behind 128-bit-equivalent security as long as you don't reuse addresses or publish the public-keys for your addresses.

...

I'm sorry to short your message but I would know at the underlined sentence if I have good understood the point.
The fact that Public Key and Bitcoin Address are different is not a safeguard against Quantum computing, because when you sign a transaction you are revealing on the blockchain your Publickey, so that Adress can be exposed to QC attack, is that correct?

My doubt is when you speak about "address-reuse": what do you mean with that? I have a cold storage paper wallet ecrypted via BIP0038 where I periodically put some cash into that. I've never spent BTC on that but there is not a single but multiple input transactions, so there are multiple utxo transactions on the blockchain. Until I don't spend bitcoin is it still secured or not? Should I use a cold storage paper wallet for every transaction?

Thanks in advance

[nullius]

3) For certain kinds of problems, QC can provide quadratic speedup, which is a massive speedup. For symmetric ciphers, this probably just means you double your key size - where 128 bits of security used to be sufficient, now you need 256. No big deal. The real problem is with public-key encryption. But lay-people often forget that the quantum speedup blade cuts both ways. We can build encryption systems which take advantage of quantum speedup and make quantum cryptanalysis of PKE quadratically more difficult, mooting the theoretical advantage that cryptanalysts get from quantum speedup. In fact, this is why Bitcoin uses the public-key hash instead of the public-key itself and recommends against address-reuse; in the event of working, at-scale QC, your coins are still secured behind 128-bit-equivalent security as long as you don't reuse addresses or publish the public-keys for your addresses.

...

I'm sorry to short your message but I would know at the underlined sentence if I have good understood the point.
The fact that Public Key and Bitcoin Address are different is not a safeguard against Quantum computing, because when you sign a transaction you are revealing on the blockchain your Publickey, so that Adress can be exposed to QC attack, is that correct?

My doubt is when you speak about "address-reuse": what do you mean with that? I have a cold storage paper wallet ecrypted via BIP0038 where I periodically put some cash into that. I've never spent BTC on that but there is not a single but multiple input transactions, so there are multiple utxo transactions on the blockchain. Until I don't spend bitcoin is it still secured or not? Should I use a cold storage paper wallet for every transaction?

Thanks in advance

In this particular context (but see below), “address reuse” means reuse of an address from which you have spent.  Transactions to your address contain the public keys of whoever sent you the money—not your public key.  But the only information revealed in the blockchain when you receive money is the Hash160 (RIPEMD160 of SHA256) of your public key.  That is what haltingprobability referred to as the “public-key hash” in the portion you underlined.

(For the sake of simplicity, I here assume only P2PKH and P2WPKH addresses.  What do these stand for?  “Pay To (Witness) Public Key Hash”.)

But this discussion misses the point that the security of public keys is just fine.  It seems that you missed this upthread:

There are excellent reasons to avoid address reuse; but this is not one of them.  I say this as a paranoid security nut:  The security of publicly disclosed public keys is just fine.  That is why they are called public keys.  The only exception I would here make is if you have coins which you intend to potentially leave in cold storage for decades.  Then, yes, you will want the extra security margin of the key being unpublished.

Bingo.

Do you intend to leave the coins in cold storage for decades?  If so, then I recommend that you do what you said you’re doing:  Use the addresses for receiving only.  Not that I expect for secp256k1 to be broken:  If storing something for decades (or longer), I prefer some extra security margin “just in case”.

Otherwise, there is no reason to worry about revealing the public key.  secp256k1 is secure.  You may rely on it.

But there is another, very different reason to avoid reuse of addresses for both sending and receiving:  Privacy.  Blockchain analysis is already easy enough for experts.  Address reuse of all kinds makes it trivial.

To start with, for a bare modicum of privacy, use one HD wallet with the seed and keys generated (and backed up!) on an airgapped computer; and from that wallet, use a different address every time you receive money.  This recommendation has nothing to do with the security of your money against attacks on public keys.

[Vigme86]

...

...

In this particular context (but see below), “address reuse” means reuse of an address from which you have spent.  Transactions to your address contain the public keys of whoever sent you the money—not your public key.  But the only information revealed in the blockchain when you receive money is the Hash160 (RIPEMD160 of SHA256) of your public key.  That is what haltingprobability referred to as the “public-key hash” in the portion you underlined.

(For the sake of simplicity, I here assume only P2PKH and P2WPKH addresses.  What do these stand for?  “Pay To (Witness) Public Key Hash”.)

But this discussion misses the point that the security of public keys is just fine.  It seems that you missed this upthread:

There are excellent reasons to avoid address reuse; but this is not one of them.  I say this as a paranoid security nut:  The security of publicly disclosed public keys is just fine.  That is why they are called public keys.  The only exception I would here make is if you have coins which you intend to potentially leave in cold storage for decades.  Then, yes, you will want the extra security margin of the key being unpublished.

Bingo.

Do you intend to leave the coins in cold storage for decades?  If so, then I recommend that you do what you said you’re doing:  Use the addresses for receiving only.  Not that I expect for secp256k1 to be broken:  If storing something for decades (or longer), I prefer some extra security margin “just in case”.

Otherwise, there is no reason to worry about revealing the public key.  secp256k1 is secure.  You may rely on it.

But there is another, very different reason to avoid reuse of addresses for both sending and receiving:  Privacy.  Blockchain analysis is already easy enough for experts.  Address reuse of all kinds makes it trivial.

To start with, for a bare modicum of privacy, use one HD wallet with the seed and keys generated (and backed up!) on an airgapped computer; and from that wallet, use a different address every time you receive money.  This recommendation has nothing to do with the security of your money against attacks on public keys.

I had not seen the upthread, indeed, but I meant what I said, it's on a long-time basis (maybe not decades, let's say some years) and I'm currently storing my big savings in btc on a paper wallet generated on an offline computer and encrypted via BIP0038 (actually big for me , maybe for you guys could be a ridiculous sum).
I have always bought my mBTC on different exchanges and then sent to my Address, I've never verified what kind of transactions the exchanges have made, but I suppose it was a P2PKH (is there a way to know that ?). I do that because I've read on "Mastering Bitcoin" this is the way Antonopoulos stores 95% of its bitcoins.

HD Wallet? I've Electrum on my phone but it's just for some bucks I'm not able to move due high fees level of these days, anyway seed is backed up and I have downloaded BIP0032 program to found every private key from that one.

Anyway thanks again for your answer