What does Quantum Computing mean for Bitcoin?

[sgravina]

The best quantum computation ever was the successful factoring of the number 15 into it's prime constituents, 3 and 5.  It did this really slowly.

Quantum computing is interesting and worth pursuing for many reasons, but it will never be a useful computational device.

I don't really know the future, I'm just guessing based on the unsolved problem of reading more than a few qubits of information before it is lost to the environment.  Or the unsolved problem of storing more than a few qubits of information in a device without losing it.

Beyond a few qubits, at least 2 but less than 8, you can't program a problem for a quantum computer and you can't read the result.

Sam

[1714039280]

1714039280

[1714039280]

1714039280

[kjj]

The best quantum computation ever was the successful factoring of the number 15 into it's prime constituents, 3 and 5.  It did this really slowly.

Quantum computing is interesting and worth pursuing for many reasons, but it will never be a useful computational device.

I don't really know the future, I'm just guessing based on the unsolved problem of reading more than a few qubits of information before it is lost to the environment.  Or the unsolved problem of storing more than a few qubits of information in a device without losing it.

Beyond a few qubits, at least 2 but less than 8, you can't program a problem for a quantum computer and you can't read the result.

I'm going to disagree.  The difficulties are, I think, just a matter of engineering.  Extremely difficult engineering, to be sure, but with a huge payoff.

Quantum information theory is too important to be left unused.

[ctoon6]

AFAIK cryptography is never "safe" it has many weaknesses.

1. the vault is only as secure as the key

in theory you never need to encrypt you private keys, just keep them in a place where others can not see it or access it.

2. all encryption can be broken with enough time AFAIK

3. to combat QC now, simply increase the encryption now to unrealistic heights. then you have time to reimplement the needed security once you understand the problem.

to find a private key from a public key would still probably take a while, my guess would be at best, a few days.

4. alternate chains will emerge and probably try to address these problems

and lets not forget the most important thing.

i have yet to see any real benchmark of QC doing real work, and i don't see that happening in the next 5 years.

[qbg]

2. all encryption can be broken with enough time AFAIK

Except the one time pad.

[ctoon6]

2. all encryption can be broken with enough time AFAIK

Except the one time pad.

thats not encryption, thats 2 factor verification, and it too is easily defeated

man in the middle attack
how do you handle it when you "lose" your security token?
phishing

[Quantus]

Simple question, and I am by no means well-rounded in my knowledge of quantum computing. But what I have read indicates that it is a massive hammer to all crypto algos currently in existence. Could the sudden existence of quantum computing mean the sudden uselessness of Bitcoin as a currency?

simply yes. "not if but when they come out with powerful Quantum computers it will simply Crush any and all encryption commonly used today"

[hashcoin]

With QC, far better things can be done than bitcoin.  In particular, it is possible to design quantum e-cash where transactions occur entirely offline and yet doublespending is prevented (i.e., no global blockchain that must be aware of all transactions).

http://dspace.mit.edu/handle/1721.1/52007

[ctoon6]

With QC, far better things can be done than bitcoin.  In particular, it is possible to design quantum e-cash where transactions occur entirely offline and yet doublespending is prevented (i.e., no global blockchain that must be aware of all transactions).

http://dspace.mit.edu/handle/1721.1/52007

wanna sum it all up so i don't have to read 15 pages of high level math and complicated quantum theories?

[RodeoX]

The spookiest thing about quantum (Einstien called it spooky) is that we do not know how it works. For all we know research may discover ways of accessing secure data via multidimensional exploits. It's no longer even out of the question to think that cause and effect is just a phenomena created by our feeble ability to perceive what's really going on.

I teach biology, and I often wonder if there is a quantum connection between wave colapse and the state we call "living". Right now I can't explain to my students the difference between a dead bird and a live bird.
You are going to hear a lot more about this in the future.

[neptop]

Time for some conspiracy!


I guess there are a lot of rich people and institution with serious interests in quantum computing because of what it means to security. DARPA always had some secret research in various fields for example. They have virtually unlimited funds. However with the ability to really break (as opposed to just break it by the means of finding something better than brute force) cryptography you are powerful enough to care about Bitcoins or financial institutions anymore.

[Piper67]

Heh... Richard Feynman, who was instrumental in developing quantum electrodynamics, once famously said that "if you think you understand quantum theory, you don't understand quantum theory".

I hope the same thing applies to quantum computing. 

[ctoon6]

The spookiest thing about quantum (Einstien called it spooky) is that we do not know how it works. For all we know research may discover ways of accessing secure data via multidimensional exploits. It's no longer even out of the question to think that cause and effect is just a phenomena created by our feeble ability to perceive what's really going on.

I teach biology, and I often wonder if there is a quantum connection between wave colapse and the state we call "living". Right now I can't explain to my students the difference between a dead bird and a live bird.
You are going to hear a lot more about this in the future.

a "real" answer
living is nothing more than chemical reactions and electrical impulses, all working together to create an illusion of live and death.



heres a little something to think about
for all we know or i know, you or i could be "god" and only imagining this thing we call life on earth. we could be like in the matrix for all we know. or you might not exist at all, in theory everything could be everything, and you perception of reality could just be a "wave"

[RodeoX]

a "real" answer
living is nothing more than chemical reactions and electrical impulses, all working together to create an illusion of live and death.

You may be right. But even with our substantial knowledge of chemicals and electromagnetism we simply don't know how to get the "living state" going, or how it keeps going.
In physics a lot of discussion about unifying large and small scale theory is underway. But what about life? It seems to me that no theory of physics is complete without an explanation of the weirdest phenomena of all.

[ctoon6]

a "real" answer
living is nothing more than chemical reactions and electrical impulses, all working together to create an illusion of live and death.

You may be right. But even with our substantial knowledge of chemicals and electromagnetism we simply don't know how to get the "living state" going, or how it keeps going.
In physics a lot of discussion about unifying large and small scale theory is underway. But what about life? It seems to me that no theory of physics is complete without an explanation of the weirdest phenomena of all.

imagine the entire world as a perfect sphere, now take a nail and scratch it, thats how much we know about organic and biological chemistry. the possibilities are endless as carbon is one of the trickiest elements we know of today.

life as we know it may have been created or seeded by extraterrestrials. so the question is probably best answered by them. at least thats my theory, how they were made up to the "god" to answer.
but we can never be sure until we know of a way to make life, depending on how complex it is, life may be made every day, and just dies off due to bad conditions or it could be so complex it only happens once every billion years or so by small chance.

according to Wikipedia
Life is a characteristic that distinguishes objects that have signaling and self-sustaining processes.
Death is the termination of the biological functions that sustain a living organism.

[caston]

This was posted to slashdot about a von Neumann quantum computer:

http://www.technologyreview.com/computing/38495/?p1=A1

[neptop]

according to Wikipedia
Life is a characteristic that distinguishes objects that have [...] self-sustaining processes.

I see dead people!

[caston]

I would be more interested in what reversible computing may do for bitcoin.

[cbeast]

Perhaps Mentats will one day be bred to combine Hawala with Bitcoin.

[etotheipi]

Sorry to revive an old thread, but I feel I have to contribute, as I have studied Quantum computing, cryptography and Bitcoin all extensively.  I've been considering writing a series on the topic, but I never quite found time to do it.  The least I can do is respond to this thread.

First and foremost, QCs are useless for breaking a public-private keypair if they don't have the public key, and Bitcoin addresses are actually hashes of the public key. The attacker only sees the public key the first time the owner spends coins.  Therefore, if you use each address exactly once, by the time the attacker with the QC sees your public key, the coins have already been sent to another address with an unknown public key.   I don't know if this was an intentional security mechanism, but it adds a high degree of quantum resistance that may actually save the network.  (NOTE:  actually this isn't true for coinbase transactions which usually include the person's full public key, but there's no reason the miners can't switch to regular BTC addresses)

The QC would have to have a faster connection to your computer than your computer has with the rest of the network, then when you broadcast a tx, they have to crack your public key instantaneously and broadcast a replacement transaction to a significant number of nodes before the original transaction propagates.  This would be have to be a highly targeted attack -- still a stretch even if the person with the QC controls a significant number of your peer connections -- and still requires the QC to be fast enough to compute your private key nearly instantaneously.   This would only feasibly succeed if they control all your peer connections.  However, there's a variety of other attacks the person can execute if they control all of your peers...

The other angle is if the person with the QC also controls a significant portion of the global hashrate.  With a classical computer, they can only double spend against you (sometimes), but with a QC they can now also spend your coins.  If they can solve for your private key quickly after you broadcast a tx, there's a chance they can build a new branch of the chain fast enough that discards your transaction and includes one of their own.  However, if someone has enough computing power to do this, the network/community is going to have serious problems regardless of whether QCs are involved.

Secondly, hashing is effectively secure against QCs.  QCs wouldn't break the algorithm itself, but Grover's algorithm can be used on any pure-guessing problem to cut it's compute time down to sqrt of the original problem.  If you are trying to find someone's public key based on their bitcoin address (the hash of it), it will take a classical computer 2^256 guesses, but it will take the QC 2^128 guesses.  This is still wildly infeasible (for reference, the entire bitcoin network has produced about about 2^70 hashes total over the course of 2 years --- approximately 1 quadrillionth of the number of computations required to reverse your public key from your BTC address).

This would be most relevant for mining, but probably still safe for a while.  It takes your classical computer approximately 1^15 hashes on average to compute a new block (at current difficulty), so it would take about 100 million operations on a quantum computer -- but QCs are going to be dirt slow for a long time - it's possible that 100 million ops could take days or months on a QC.  My guess is, miners will have nothing to fear from QCs for a long time.

Thirdly The QCs can only break a public-private keypair if they have enough qubits.  However, number of qubits is going to be one of the bottlenecks of QC, the same way classical computers at one point maxed out at 4kB of RAM.  The QC needs more qubits if the encryption/signing key is longer.  This is likely to be a short term solution for internet cryptography -- use much longer keys.  For instance, switching from 256-bit ECDSA (like bitcoin uses) to 4096-bit ECDSA could add an extra decade to the security of the system (which would be more than enough time to work out alternatives).  Sure, it will take 1 minute to sign a message, but there's plenty of infrastructure that will continue to exist (both Bitcoin and otherwise). 

Fourthly there are asymmetric encryption algorithms that will continue to be secure even in the presence of QCs.  Granted, most asymmetric schemes are based on exactly the kinds of problems that QCs are good at solving (integer factorization, discrete-log), but not all of them.   There's a dozens of unused op-codes, which could be leveraged to switch the network to a quantum-resistant signature algorithm other than ECDSA.  Even the hashing algorithm can be switched.   Satoshi explicitly wanted this in the design, since there's no guarantee that today's encryption algorithms will be secure tomorrow.  He probably didn't have QCs in mind, specifically, but any algorithm could be broken by mathematicians any day.

In summary: The biggest saving grace for BTC is that it uses hashes of public keys instead of the keys themselves.  This, by itself, adds an extremely high degree of quantum-resistance to the BTC network.  Other places where QCs might cause disruption are only purely theoretical, and could take decades for the technology to develop to the level needed to actually execute the attacks.  So, if any of this is ever going to happen, we will see it coming, potentially decades in advance and can prepare accordingly. 

[ctoon6]

Sorry to revive an old thread, but I feel I have to contribute, as I have studied Quantum computing, cryptography and Bitcoin all extensively.  I've been considering writing a series on the topic, but I never quite found time to do it.  The least I can do is respond to this thread.

First and foremost, QCs are useless for breaking a public-private keypair if they don't have the public key, and Bitcoin addresses are actually hashes of the public key. The attacker only sees the public key the first time the owner spends coins.  Therefore, if you use each address exactly once, by the time the attacker with the QC sees your public key, the coins have already been sent to another address with an unknown public key.   I don't know if this was an intentional security mechanism, but it adds a high degree of quantum resistance that may actually save the network.  (NOTE:  actually this isn't true for coinbase transactions which usually include the person's full public key, but there's no reason the miners can't switch to regular BTC addresses)

The QC would have to have a faster connection to your computer than your computer has with the rest of the network, then when you broadcast a tx, they have to crack your public key instantaneously and broadcast a replacement transaction to a significant number of nodes before the original transaction propagates.  This would be have to be a highly targeted attack -- still a stretch even if the person with the QC controls a significant number of your peer connections -- and still requires the QC to be fast enough to compute your private key nearly instantaneously.   This would only feasibly succeed if they control all your peer connections.  However, there's a variety of other attacks the person can execute if they control all of your peers...

The other angle is if the person with the QC also controls a significant portion of the global hashrate.  With a classical computer, they can only double spend against you (sometimes), but with a QC they can now also spend your coins.  If they can solve for your private key quickly after you broadcast a tx, there's a chance they can build a new branch of the chain fast enough that discards your transaction and includes one of their own.  However, if someone has enough computing power to do this, the network/community is going to have serious problems regardless of whether QCs are involved.

sorry but this makes no sense to me, either because i dont understand bitcoin correctly, or you dont.

what i know says that the block chain, which EVERYBODY HAS, contains a "list" of every public key and the amount of coins associated with it. the private key of the public key allows you to sign transactions, and you can verify that because the public key will allow you to do so, because that is what makes transactions valid, because you are able to verify it because you do have the public key.

and what do peers really have to do with all of this? they at no point offer any security to the network other than hashing and ensuring your transactions get broadcast.

i do agree with you that QCing may not break bitcoin or any other cryptographic scheme, but the future is very unpredictable so for all we know, cheese could be 600% faster than the current gen cpu's.