Topic: What does Quantum Computing mean for Bitcoin? - page 3. (Read 23216 times)

Grover's algorithm has nothing to do with hashing.  It is for lookups.  There is no lookup.  Miners calculate and discard hashes in realtime.  The proof of work is the amount of time it takes to complete the average number of hashes to solve the problem.

Grover's algorithm would require a lookup table for hashes.  Given the target space is 2^256 even a planetary sized storage array powered by the molten core, and with storage density billions of times higher than current solid state wouldn't even be able to store a rounding error of the 2^256 range.

TL/DR version: No.

http://en.wikipedia.org/wiki/Grover's_algorithm

Every time the difficulty goes up by a factor of 4 for classical miners, it goes up only by 2 to quantum miners.

I'm betting QBit beats transistor every time even in a random numbers competition

Or you could read the thread and see how that true.  QC has uses and it has limitations and Bitcoin isn't a viable use for QC. 

There are no know (even theoretical) algorithms to speed up brute force searches of cryptographic hashes... any hashes using QC.  None. 

QC is going to do to Bitcoin what GPUs did, in that QC will eventually become the quickest way to produce the hashes, so we'll all have to upgrade.

No you won't.  Quantum computer would provide no value for this purpose.

But we'll all have to buy Quantum machines. I'm not complaining, just saying.

Actually it probably exists and doesn't simultaneously? . Moore's curve is starting to look fairly steep right about now though? I'm guessing virtual currencies will gain from QC way more than they lose, I'm also fairly sure Bitcoin will survive and thrive with them.

You don't but don't worry most people don't.


For coins in an address haven't been spent the blockchain contains the ADDRESS not the PUBLIC KEY.

People think  Bitcoin is this:
PUBLIC KEY
PRIVATE KEY

In reality it is this:
PUBLIC ADDRESS
PUBLIC KEY
PRIVATE KEY

Either Satoshi was the luckiest developer of all time or a genius from the future.

By using the PUBLIC ADDRESS which is a hash of the PUBLIC KEY Shor's algorithm is useless.  There is no known quantum algorithm for breaking hashes, either practical or theoretical.  If you don't know what you are attacking (PUBLIC KEY) then Short's algorithm is worthless.

Bitcoin is highly quantum resistant.  Now there are some potential dangers.  If you send coins to an address that you previously sent coins to that is vulnerable (theoretically) because the public key is in the block chain from prior transaction.  Public Key + shor's algorithm + enough qbits = massive shortcut to brute forcing the private key.

Still this isn't a game ender it just will require changes in how clients use addresses.  Using addresses as a one time transaction makes all wealth immune to quantum attack.  So for example instead of giving your mining pool a static address to send payments to your wallet generates a list of 365 and uploads it to the pool server who uses each once and only once for daily payments over the next year.   So if  anything quantum attacks would simply change the WAY bitocoin is used rather than being the death blow.

Bitcoin is Bitcoin silver and Bitcoin is already quantum resistant. 

So as Litecoin is Bitcoin's silver, QBit is Bitcoin's Platinum? 

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. 

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

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

I see dead people!

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

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

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.

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.