Bitcoin Forum

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?

If we invent quantum cryptography, business will continue on.

Otherwise, everybody's secret in the world can and will be cracked.

Yes.   But pretty much also for everything you consider safe on the internet.

My brother-in-law is a physicist very involved in the world of research on quantum computing and I just asked him this question last week. All modern secure computing uses encryption based upon the same principals and if QC becomes a reality, all modern secure computing becomes insecure.

He thinks QC is a boondoggle and it reminds him of the government funded fusion research. A big money effort to something that may never happen and we are not even close.

If QC came into existence, he said we could use QC to encrypt and make this encryption impossible to crack by QC. And of course, the only 100% impossible to break encryption is one time pads.

Indeed, with QC we won't use DSA, we'll just use quantum cryptography, which will be much better than prime numbers based cryptography.

I guess it will then be easy to create a quantic cryptocurrency.  Is there a quantum computing version of proof-of-work ?

But anyway so far this is just science-fiction.  We might as well talk about space tourism to Alpha Centauri.

QC doesn't just magically break all crypto, it makes it a lot easier possibly by several magnitudes,but many things could still be considered 'safe' for daily use.

QC doesn't even magically make all crypto easier. There's a quantum algorithm for fast integer factorisation, and for a few other things, but there are also classical public-key systems which aren't known to be broken at all by QC.

I expect if it looks like someone's getting close to building a quantum computer, a lot of effort will go into the development of these systems. Making Bitcoin QC-safe might just be a matter of replacing our public-key cryptography (ECDSA) with something else.

Easier said than done.

We will have to keep secrets by not sharing them...

Yes, it's nontrivial, but it could be done. My point is that QC wouldn't be the end of Bitcoin, and that we might be able to defend against it without having any quantum technology ourselves.

The "something else" has to be something that quantum computers are not better at solving than classical computers. Quantum computers do not magically make P=NP, so there are still be problems where solutions are hard to find but easy to check, even with cheap quantum computing everywhere.

Perhaps with quantum technology it will be feasible not only to keep bitcoin alive, but to build a better bitcoin along the way.  For example, fully homomorphic encryption has recently just been shown to be possible, yet it is too slow for production use.  Perhaps something like that would be incorporated into the "next generation" bitcoin, thereby making bitcoin transactions verifiable, yet untraceable.

Somebody needs to write an article series on cryptography.

I'm currently working on a series of articles explaining the concepts used in Bitcoin, like proof-of-work and hashes. I would have to study a little bit before fully understanding exactly what quantum computers can do.

http://www.bbc.co.uk/news/science-environment-12811199

Quantum computing device hints at powerful future

One of the most complex efforts toward a quantum computer has been shown off at the American Physical Society meeting in Dallas in the US.

To answer the question: Not much. The BitCoin would just get to the 21 Million quicker.

But lets take a look at what would be needed. Considering this is an area that I am, what one could say, familiar with.  First we need ternary hardware, Russia kind of had the lead in this, and still have a few ternary computers around.  Basically it is hardware that is designed on 3 states not 2 or -0+ instead of 0101. One could run the logic on a binary system, but you loose the advantage of a ternary system. Guess who gets to use it first, The Government but hey they paid for it.  This actually start with University of Pennsylvania a long time ago. MIT has some musings on the subject.  ;D 

So the BitCoin would be safe in Quantum Computing, Hashes however, will be pretty useless. Just create a new key pair for each transaction, and get two or more confirmations, then it wont matter if the hash is cracked. It will only matter if you use the same Key pair for multiple transactions, meaning that they could crack your key pair.  But with PKC using Quantum Computing to generate Key pairs then you could just scale the system to keep the Odds of a crack off the charts.

How about using Quantum Pairing for sending and receiving between parties, instantaneously (even between Planets) and completely untraceable to boot.

A P2P Mesh network based on Quantum Pairs. Oh, baby.  ;D

There's always stuff like http://en.wikipedia.org/wiki/Unbalanced_Oil_and_Vinegar

Did you read my post (http://bitcointalk.org/index.php?topic=3008.msg70148#msg70148)??

Of course there's nothing wrong with your logic except that it's irrelevant since we're almost past it and doesn't contribute to the topic discussed at all.

I don't think quantum computing is going to come out of left field. Many of the people paying attention to Bitcoin are heavy into crypto and will have a good idea of whether there's a major advance coming up.

Once it seems that quantum cryptanalysis is a real threat, all of these folks will start moving their money out of BTC and into other areas. And at least a few of them will be interested in inventing "Qubitcoin." Once that exists, smart money will move to Qubitcoin. Once folks notice the sudden inflation, even dumb money will move to Qubitcoin. A few slow movers will likely be left holding the pieces.

I'm curious about whether a Bitcoin-like currency could be minted with intrinsic value, so that even those last few won't be totally empty-handed. Encoding some sort of useful information that can only be accessed with the private key? But really I don't think this is anywhere close to the biggest threat to crypto-currency.

I thought about this also. A true Quantum computer could end the current bitcoin system. Even though it is only theoretical now. The speed of development is impressive. A system for sending messages using wave collapse already exists!

Please explain, How?

As I see it, you would need to crack the Key Pair almost instantaneously before it got added to the chain, if another Key pair is then generated before the next transaction, you would have to start over. It would just take a minor change to the source to achieve this.

But then if we are using Quantum Computers, BitCoin could scale the PKC using the Quantum Computer. Just increase the Odds with the capability of the machines.

But if Quantum Computing becomes prevalent so would Quantum Pairing. No one would be able to see the transaction or intercept it between parties. Using a Trekie term: it is sub-space communications faster than the speed of light.

Wooah. Thats a good way to do it. It won't work every time, but you could break some keys before they are added to the chain, right? And you have a solution! Add quantum entanglement to the system and you could verify a transaction, perhaps before sending it to any nodes.

If Quantum Computing is realised the entire industry of two computers ever interchanging information in a secure manner is rewritten. The internet? Hacked. Banks? Hacked, Bitcoin? Flawed. Everything changes from the ground up at that point.

The holders of the first non-trivial quantum computers will be nothing short of mortal gods, with absolute control over the entire digital infrastructure of the world.

EDIT: Interesting Wikipedia Link (albeit usual Wikipedia caveat applies
http://en.wikipedia.org/wiki/Shor%27s_algorithm

Quantum computation renders certain public key crypto insecure.  Since bitcoin addresses are ECDSA public keys, using a quantum computer to discover the corresponding private key would give someone the ability to recreate any bitcoin address's wallet.dat file, so they could spend them.

So the crypto for transactions in bitcoin is vulnerable to QC (as is SSL which is RSA).

http://en.wikipedia.org/wiki/Elliptic_curve_cryptography#Quantum_computing_attacks

The crypto for mining bitcoins is not affected, except potentially increasing the hash rate above that of classical computers.  So the ghash network rate would grow faster with more quantum miners.  We wouldnt reach 21 million faster, as the difficulty factor would be scaled accordingly.

The ECDSA public key crypto could be changed to one not vulnerable to quantum attacks, like Unbalanced Oil and Vinegar.

http://en.wikipedia.org/wiki/Post-quantum_cryptography

Then I think that we should do this ASAP.

quantum computers are a reality, you can buy a 128qubit one for "only" 10$ million (that's small change for a large company)

http://venturebeat.com/2011/05/27/first-quantum-computer-sold/
http://www.dwavesys.com/en/products-services.html


How difficult would be change the algorithm of the public-key encryption for Bitcoin to one not vulnerable to quantum attacks?
Would we have to start from scratch or we could change the algorithm "on the fly" without losing our coins?

This text was extracted from the first chapter of the book Post-quantum cryptography ( by Daniel J. Bernstein ) (http://books.google.com/books?id=VB598lO47NAC&printsec=frontcover&source=gbs_ge_summary_r&cad=0)



This is scary... I think that we should seriously to look a way of replacing the ECDSA algorithm of Bitcoin with another "post-quantum" algorithm

D-Wave is smoke and mirrors.  It is more like 128 1-bit analog computers, as the qubits are not entangled.  Without entanglement, there is no quantum speedup over classical computation.  Even the 8-bit system they published in Nature is not entangled.

The highest number of qubits which have demonstrated entanglement is 3.

Still, not too soon to examine plans for switching bitcoin from ECDSA to something post-quantum.

Remember, when "true" quantum computers become a reality, far more than bitcoin is defeated.  HTTPS (which uses RSA) is defeated.  So basically all internet traffic (passwords, credit card numbers, etc) will be readable by anyone on the same wifi, by an employee at your ISP, or someone at your ISP's ISP, etc.

+1

yes - D-Wave is pretty much vapor-ware.  big business ego-boo: "we have the first quantum computer! (quoth Lockheed)"  and even if delivered, it's only a threat on the order that a cell-phone is.

If I can break ECDSA with a quantum computer I can steal all the money on bitcoin and make all the bitcoins disappear from day to night.
However if i can break RSA, banks and people only have to stop relying on SSL meanwhile they implement a new algorithm. ( Probably they would have to stop using credit cards for a while but they won't loose all their money at all )

So, the first problem is that a quantum computer able to break crypto is a death threat to Bitcoin, meanwhile for a bank that relies on RSA is only a major threat.

The second problem is that the first company who will own a quantum computer able to break crypto will be sure the "US Government". And in the future, when Bitcoin will be much popular than now, I am sure that the US Goverment will have strong incentives to make bitcoin disappear because the bitcoin thing is a major threat to the debt-based economic system of the dollar.

So far.. how much you think will take to the US Gov own such quantum computer and break the ECDSA system of bitcoin? 5 years perhaps?

I think the switch to quantum computer resistant crypto will be done long before the first (serious) one will see the light of day.

who cares? (although i'd be more likely to bet on 10+ years...)

in five years Bitcoin will either be worth too much to destroy - and all governments will be in the process of changing their tax-base from income-based to consumption-based...

...or Bitcoin will be worth nothing.

Creighto says here (http://forum.bitcoin.org/index.php?topic=10114.msg146009#msg146009) that the ECDSA in bitcoin is modular enough to be swapped out.

I'm guessing the upgrade would be a version which uses post-quantum private keys, but is backwards-compatible with the current ECDSA private keys.

Bitcoins received with the new version would have a post-quantum wallet file.  Any bitcoins not re-sent to a new address with the new version would be vulnerable to theft by a quantum computer.

Therefore, the first entity with access to a quantum computer could steal any coins which have not been re-sent.

This entity would be able to recover all lost bitcoins!

oh my.

now that is interesting.

Unless the network subsequently upgraded to a post-quantum version without backwards-compatibility, which would render all coins not re-sent by then as obsolete.


I don't know the technicals well enough to say with confidence that this is the only scenario.  But if the upgrade to post-quantum is compatible with the current blockchain, it seems this would be how.

would we call this "qubitcoin"?

This is the best doc I've read on qc.

http://www.obld.net/qcintro.pdf (http://www.obld.net/qcintro.pdf)

If some qc is created that is so powerful like it would solve all BTC, then likely it will be simply used as a superweapon to create bioweapons that will selectively kill entire races of people. It will also probably be used to solve the problem of fusion so some country can destroy an entire continent without any radioactive fallout. I doubt that we will have to worry about it being used to destroy bitcoin. OTOH there is a very small chance it could be used to help mankind never have any need for money at all and allow us to live in peace.

tl;dr QC > BTC

Assuming QC "suddenly" appears, and ECDSA is instantaneously crackable using Shor's algorithm, and SHA256/RIPEMD160 become vulnerable to Grover's algorithm:

• Every unspent coin, sent to an address whose pubkey is not yet revealed, is somewhat safe (80 bit security left, instead of 160 bit)
• The block chain is quite safe (128 bit security left, instead of 256 bit)
• Transactions to new quantum-computing-based addresses with corresponding keys, are safe
• ... only unspent coins sent to reused addresses will be trivially claimable by any attacker (a few bits of security left, instead of 128 bit)

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

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.

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.

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

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

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?

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.

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.

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

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"

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.

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

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

I see dead people!

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

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

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. 

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.

When someone gives you a Bitcoin address, they are giving you the hash of a public key for which they own the private key.  If you look at the way standard scripts are structured, they are designed to not just verify the signature, but verify that the public key you are providing hashes to the address in the TxOut script-- because until this point, no one has ever seen your public key, and they obviously need it to verify your signature.  Why else would you need to provide the full 64-byte public key in a TxIn script if the network already has it?    The only exception to this is coinbase/generation transactions, where it seems to be "convention" to use your public key directly in the coinbase TxOut script.  But there's no reason they have to do this...

All of this is illustrated pretty clearly in the first and third images posted in my knowledge donation thread (https://bitcointalk.org/index.php?topic=29416.0).  The first image shows a transaction that includes each type of TxIn (3) and each type of TxOut (2). 

As for the peers:  The attacker with the QC must get your public key before he can spend your coins (as we just established).  If you only use each key once, he will only see the public key after it's already too late to do anything about it (he got your public key because you broadcast a Tx that moves all the money behind that key to a different address).  He'd have to get your Tx faster than most other peers, compute your private key instantaneously (yeah right) and broadcast a replacement transaction before the original tx propagates (once a node has seen the original/legit tx, it will reject the attacker's tx).  This is extraordinarily unlikely, but his chances improve if he controls a lot of your peers:  he increases the chance that he receives your tx-with-public-key immediately, and reduces the propagation speed of the original transaction. 

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

Bitcoin is Bitcoin silver and Bitcoin is already quantum resistant. 

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.

Actually it probably exists and doesn't simultaneously? :D. 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.

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

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

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.

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. 

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

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.

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.

One time pad's will defeat quantum encryption breaking capabilities. Someone will figure out how to implement its use.

One modern example is quantum key distribution.
http://en.wikipedia.org/wiki/Quantum_key_distribution

Generate a sequence of bits using secure pseudo-random number generator.
Encode each bit of the key as quantum states in individual photons using one of those basis
Receiver chooses random basis for each bit received.
If receiver choses incorrectly that bit is lost forever.
Once receiver has collected enough bits to create a key both parties share the basis sequenced used in transmitting the bits.

Only bits where basis matched are used.  That becomes the key.

The key can't be "captured" enroute because quantum mechanics guarantee that observing the quantum state will alter it.
This altered key can be detected and alert both parties can an interception is in progress.

If no interception is in progress than both parties can be certain nobody else has the key.  The key is unbreakable by anything other than brute force as there is no known information to exploit.

Communication can then be done encrypted over normal channels.

No, though I can see why if you have not studied QC formally the wiki article is misleading.  The "database" being "input" to grover's algorithm is a quantum circuit.  Indeed the actual "database", if you view it as a string of length 2^n, is huge.  But the entire database has a very concise representation: it is just an n-input circuit (for mining, the one taking as input a nonce, computing SHA2 twice, and then checking if the value is below the target).

To be precise, Grover's algorithm solves CIRCUITSAT with n inputs in time 2^(n/2).

A more detailed intro is here:

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-845-quantum-complexity-theory-fall-2010/lecture-notes/MIT6_845F10_lec09.pdf

Also I mentioned in some other threads if QC becomes real much better architectures for money can be designed than bitcoin.  See the following and included refs:

http://www.scottaaronson.com/papers/noclone-ccc.pdf



edit Also note the search space is whatever you want.  For example the nonce is 32 bits.  You can search over all of it, some of it, or even include extranonce bits to search multiple nonce spaces.  Basically, if you can run Grover's algorithm for a k-bit input circuit, then you can search faster by a factor of 2^(k/2). 

Which is many thousand magnitudes slower than conventional mining.  2^(256/2) = 2^128

???

Still even if true.  You must perform the HASH which is the computaitonally intensive part.  You have nothing to index until the hash is performed.  There is nothing at the link that indicates that you could avoid performing 2^32 hashes to check one nonce range.

No, I think you do not understand Grover's algorithm or basic QC at all from your response.  This is elementary undergrad-level QC stuff so I'm not going to waste time arguing.  The lecture notes linked [1] will explain in more detail if you want.  I'll clarify once more in this thread though for anyone else who wants to understand.

Let us suppose we are given a black box that takes as input a number N and outputs either true or false; we want to know if the box ever outputs true.
Clearly, classically we must test the box on every input, so we need to evaluate the box N times.

Grover's algorithm says if we have such a box, and may make quantum queries to the box, then we can actually make only sqrt(N) queries.   Note that being able to query a box in superposition is very powerful.  For example, you can actually "evaluate the box on all inputs" in only a single query, by feeding as input a uniform superposition over all input states.   So that part is actually trivial.  The tricky part, and the cleverness of Grover's algorithm, is aggregating all those answers into a single answer.  See [1] for some lecture notes with the details.   Finally, while I said "being able to query a box in superposition is very powerful", it is implied by the existence of QC.  The axioms of QM mean that any quantum circuit that can be queried input-by-input, must also be able to be queried in superposition in the same amount of time (because QM is linear, and so a quantum circuit must transform any linear combination of input states to the same linear combination of the corresponding output states)

Now to relate this to the wiki page, where it says "let f be the function which maps database entries to 0 or 1".  That f is the black-box we are trying to test.   Thus, our testing procedure takes as input a function f, and answers if there is an x s.t. f(x) = 1.  

Now to get to the root of the confusion: how do we take as input a function "f"?  There are two ways: we could take it in as a list of input, output pairs.  Or we could take it in as a description of a circuit.  Note the latter may be exponentially smaller than the former, in that small circuits can compute functions with a massive input space.  Further, taking the input as a list of input-output pairs makes absolutely no sense, because then we need to spend N time to even READ the input (the "database"). So thinking about Grover's algorithm as a "database search" is actually pretty retarded, because if you used it that way, you would already need to spend N time just to build the database! Clearly, you can only improve over time N if the database actually has a description that is smaller than N bits.

Now, to apply this to bitcoin mining: Fix a block header, and let f(x) = 1 if using nonce x makes the block header hash below the target, 0 otherwise.  Mining is simply taking f() and searching for x s.t. f(x) = 1.  There are 2^32 possible xs, so classical mining requires testing 2^32 nonces.

A quantum miner would feed f into grover's algorithm, and query f in superposition on only 2^16 inputs before getting the answer.

For larger difficulties, a quantum miner can get a better improvement by making f() a bit more complicated, so that x includes the "extra nonce" in addition to the nonce.  That way f() has N = 2^32 * difficulty inputs instead of just N = 2^32.  The point is, something that would require a classical miner N tests, will require a quantum miner only sqrt(N) tests.  Each "test" requires evaluating f(), which computes the hashes and checks against the target.

[1] http://www.cs.washington.edu/education/courses/cse599d/06wi/lecturenotes12.pdf

On edit: Not worth but but I will leave these.

http://www.pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf

http://en.wikipedia.org/wiki/Post-quantum_cryptography

Reread the description.  The "test function" f(x) computes the hash.  Do you understand?  The INPUT to Grover's algorithm is a CIRCUIT describing the function f().  The function f, for mining, is the following.  Fix some block header B up to the nonce.  F(x) = compute hash(b,x), output 1 if it is below target, 0 otherwise.

That is, the circuit f includes, for example, a copy of the circuit for computing SHA2 (really that's all it is, plus an inequality tester).

Do you agree that, for that function f I described, bitcoin mining is just trying to find an x. s.t. f(x) = 1?  If you agree to that, then check those notes I linked, because they contain the details that once you accept that, you must accept a quantum procedure can find an x in sqrt(N) trials.

edit you edited out what I responded to.   Regarding your link, djb says so right there: grover's alg means key sizes need to be adjusted.  More precisely, key sizes need to be doubled.

Here's an analogy: You can essentially think of mining as inverting a deliberately-weakened hash.  E.g. imagine the targets are all powers of two -- then a block is valid if the first say, 50 bits of the SHA2 hash of the blockheader are zero.  Equivalently, we can think of it as defining a new hash function which is a deliberately weakened version of SHA2: H(x) = the first 50 bits of SHA2(x).  H() is a hash function with 50 effective security bits rather than the full 256 of SHA2. Now, finding a block means finding a nonce that when appended to the block header, hashes to 0 under H.

Now the same statements djb made apply to this H: while a classical adversary should need to test 2^50 inputs to find something that hashes to 0, a quantum
adversary can do it after testing 2^25.  

Saw second edit.  Not much more I can say, you are wrong.  Hopefully someone else who understands QC can provide a clearer explanation for you to see that.  The simplest way I can put it is "QC effectively halves keysizes for ANY cryptosystem; thus it halves the number of difficulty bits in bitcoin mining too".  Note the post-quantum crypto is relevant for PARTICULAR cryptosystems where QC does MUCH more than halve the keysize.  For example, for RSA the keysize is effectively LOGARITHMED rather than just HALVED.  But EVERY cryptosystem's keysize is AT LEAST halved by QC.

Section 3 of the lecture notes?  That part isn't really important.  It's just generalizing to the case where there's possibly more than one x s.t. f(x) = 1.  But that can be done without QC anyway, via a famous result:

http://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem

In general, you can assume there is either 0 or 1 solution and not worry about multiples.  E.g. you could apply the VV reduction to the function f and get a new function g that has at most 1 x s.t. g(x) = 1.

If your confusion is that there may not be an x s.t. f(x) = 1, then you're not understanding decision-versus-search.  Grovers algorithm promises this: if there is an x s.t. f(x) = 1, it will find it.  What will it do if you feed it an f s.t. f(x) = 0 for all x?  Well stop and think for a bit.  Who cares what it does?  At the end of the day, you expect to get back some x s.t. f(x) = 1.  If the algorithm doesn't give you such an x (maybe it gives you no x, or gives a bad x s.t. f(x) = 0), then the promise of the algorithm means no such x exists.

Thus, the entire 2^32 nonce space is tested in 2^16 queries.  Either the algorithm will find you the nonce, or it will do something else, in which case you know there's no nonce.

Once again 2^32 MEANS NOTHING.

A nonce range could have 0 hashes or it could have 4 billion solutions.  THERE IS NO FUNCTION which can resolve to 1 or 0 because a nonce isn't anything but any arbitrary distinction.  The target space is 2^256.  G's algorithm DOES reduce that to 2^128 cryptographic operations which is of academic value at best. 

SHA-256 isn't a 32 bit hash.  It is a 256 bit hash.  Using G's algorithm you could brute force it in 2^128 operations.  Wow.  Finding a 1.25 million diffiuclty hash can be done conventionally in 5.36871E+15 operations.

simple but wrong.

SHA-256 IS halved to 2^128 bit which is far beyond any computationally feasible attack.  Your belief that a nonce has some magic meaning is flawed.  2^128th still puts SHA-256 thousands of magnitudes beyond any possible brute force attack.

There is nothing you can do with quantum computing to speed up finding a block solution because finding a block solution is already much easier than 2^128th.

OK I think we're making some progress..

Exactly.  SHA256 isn't a 32-bit hash.  But mining isn't really using sha256.  Consider difficulty 2^20.  This would mean that, after hashing the blockheader, the nonce is valid if the first 20+32 = 52 bits are zero.  Thus, whether a block is valid or not depends ONLY ON THE FIRST 52 BITS, NOT all 256 bits.

In other words: Say we take all occurances of "SHA256" in bitcoin, and replace it with:
H(x) = the first 52 bits of SHA256(x)

Note H(x) is just a 52-bit hash function.  But as far as bitcoin MINING is concerned, SHA256 and H() are the same...



Quantum computing speeds up the time to get a FULL INVERSION for SHA256 from 2^256 to 2^128.   But mining isn't a full inversion -- it's a partial inversion (only need first k bits to match, where k depends on difficulty).  E.g. for k=52, finding a preimage matching a target on the first 52 bits takes time 2^52.  QC reduces this to 2^26, just as it did in the full inversion case.

Question: Say I replace SHA256 used in mining with a "broken" function that computes SHA256, and then only keeps the first 52 bits of the result, zeroing the remaining ones.  Will such a miner behave any differently from a normal one?  If not, aren't they effectively using only a 52 bit hash function?

It does not.  Your logic is flawed.  There is no guarantee of a solution in 2^52 operations or even 1 trillion * 2^52 operations.  QC doesn't allow for improved chances.  It always will find a solution or won't.  That isn't possible in your imaginary 2^52 scenario.

The keyspace is 256 bit.  There just happens to be (currently) 2.1568E+61 independent solutions.

Analogy:
You find a password file with 2.1568E+61 independently created (and unique) passwords.  All the passwords are hashed SHA-256.  You need to break into one account.  You don't care which.   How many quantum operation will it take to brute force the password file.  You won't find a single computer science professor, academic, or cryptographer anywhere who would say anything other than 2^128.




The miner would be flawed.
1) The zeroed hash wouldn't be valid.
2) A 52 bit hash WILL ALWAYS BE SOLVEABLE in 2^52 operations.  It is mathematically impossible to NOT FIND A SOLUTION in 2^52 operations.  Routinely the bitcoin network takes much longer than 2^52 operations to find a solution.  The reason is the KEYSPACE IS NOT 52 bit.  It is 256 bit AND there just happens to be multiple solutions.

Well, I am a CS academic and I say the answer is 2^195 classically and 2^(195/2) quantumly.  If you have 2^61 hashes, each 256 bits in length, then a random password matches one of your hashes with probability 2^(61)/2^(256) = 2^(-195).  So after 2^195 trials, you're probably good.  Applying Grover reduces the 195 by two.



You misunderstood because the point is it is the same.  As far as mining is concerned, bitcoin might as well be truncating the output of SHA256 beyond the first 64 bits or so, because that is all that is used to determine if a block is valid (you can tell from the first 64 high-order bits of the hash if it is below target or not).


It might be easier to, instead of thinking about numbers of solutions and some finite search space, think about the probability of solutions and then the size of the search space doesn't matter.  So I have a function f(x) where x is anything, and I have a distribution s.t. the probability f(x) = 1 is p.  Then classically, I can find such an x in time roughly 1/p by repeatedly guessing random x. (e.g. if you have a coin which comes up heads 1/10 of the time, you should see heads after 10 trials roughly).  A natural extension of Grover's algorithm says you can find such an x in time 1/sqrt(p).

EXCEPT IT DOES MATTER.  Quantum computers work on the set, not part of the set.  It is an inherent limitation of the technology.  It is why although quantum computing has been used to speed up factorization of tiny numbers RSA is still secure (but likely won't be someday when large enough quantum computers can be built).

You are just pretending away key element of the technology turning quantum computers into little more than magical fantasy computers.  They can't perform a linear search.  They can only work on the set.  The set is 2^256.  It isn't useful in Bitcoin because even reduced to 2^128 it is still slower than current difficulty requires.

There is no talking your way around that.

Once again I urge you to read Section III from your own link.

For Bitcoin (currently):
N is 2^256 =  1.15792E+77
M is 1.25 million * 2^32 = 5.36871E+15

k <= 3.64749E+30

Tada you put the upper bound on a quantum search at couple quadrillion times slower than a conventional one.

You can't just pretend away the limitation that Quantum computing works on SETS.  The set for Bitcoin is 256 bit which even reduces is quantum resistant.

Ah I see where the confusion is coming from.  You're uncomfortable me randomly downsizing the sample space by sampling.  I guess if you're not familiar with probability that might not be intuitive.  You can infact reasonably do that, but let's not assume that.

OK let's keep the search space at 2^256.  Now the question is, of those possibilities, how many of them are valid?  The answer is 1 in every (Difficulty * 2^32).   Say difficulty is 2^20, then 1 in 2^52 is good. This is why when you mine, even though the "space" is 2^256, if you pick a random x, you'll find a good one in roughly 2^52 steps.

Grover will find x in 2^26.

Check out the "Extensions" section of
http://en.wikipedia.org/wiki/Grover's_algorithm

It makes the same point you do:  What if there is actually much more than just 1 solution?  Then Grover seems useless, because just random guessing should yield a solution even faster.  Actually, there is a natural extension of Grover's algorithm that takes this into account in the obvious way: if K of the N values are good, then Grover finds a solution in sqrt(N/K) time (whereas randomly guessing takes N/K time).  I.e., if 1 in M points in the space is good, guessing takes time M, while extended-Grover takes time sqrt(M).

The details are in citation [2] on the wiki page.

Oh wow nice you read that section and understood it; all this confusion came because you mixed up M and N/M:

For bitcoin,
N = 2^256, as you said.
But what is M?  M is the NUMBER of good solutions.  How many is that?  Well, if one in every 2^32 * 1.25 million is good, then:
N/M = 2^32 * 1.25 million because M/N is the fraction of "good" x.

Thus K <= 2^16 * 1.25 million, as I said.


Intuitively, M/N is the fraction of points in our space that are good.  Say this is 1 in K.  Randomly guessing takes time K.  Grover does sqrt(K).  Is everything clear now?

why does quantum computing mean the end of all security? 

what about blind quantum computing (http://www.gizmag.com/quantum-cloud-computing-security/21260/)?

If you want to really get into it, the search space is actually much higher than 2^256.  It is either 2^640 or 2^768, depending on your point of view.  It is the output of the SHA256(SHA256(header)) operation that is 256 bits long.  Oh, and most of the search space is actually invalid.

I follow the argument about defining f(x) as the function that gives the answer you want, but in the real world that means that you need a quantum circuit that actually implements not only SHA256(SHA256(x)), but also evaluates it (against variable conditions, no less), and the circuit needs to do it in one clock, with no loops, no registers, etc.  Note that we can't even do this in classical circuits yet, even after like 60 to 80 years worth of progress.  Meanwhile, I think that quantum computers are now capable of double digit addition.  Granted, they can solve all double digit addition problems at once, which is pretty cool.  And for the record, yes, I do know that quantum logic is very different from classical logic.  That doesn't save you from having to build a reversible device that maps 640 inputs to 256 outputs.

You can argue that the search space is really only the nonce, the extraNonce and a few bits of the timestamp, which greatly reduces the search space.  But that has problems because it means that you need to build a bigger circuit for f(), and it also means that f() doesn't necessarily have any solutions that return success.  And extraNonce isn't a fixed size, but you can get around that by searching out a (nonce, Merkle root, timestamp) tuple that satisfies the hash criteria, and then turn around and solve that hash to find a valid coinbase that matches your generated Merkle hash (N=2^256, M=1), and then if you want the coins, you have to solve that hash (again N=2^256, M=1) to recover a public key, and then you have to invert the eliptic curve to find a private key that can generate that public key.

In the end, I'm pretty confident that we will shift from SHA256 to something else for aesthetic reasons long before (like decades before) an actual real live quantum computer gets turned into a miner.

The (cryptography) literature on this is a bit hard to follow because most attacks are developed under the assumption that the goal is to find a collision, which is not even remotely what we are concerned with.  For example, the SHA-3 contest explicitly included criteria for resistance to selected preimage attacks by adversaries with quantum computers with capabilities that don't even remotely come close to existing yet.  Such attacks like that might cause problems for other parts of bitcoin, but not for mining.

I guess I remain unconvinced that quantum computing means that we can't keep hashing like we have been.  And even if we do have to change, we will have plenty of warning.

Ugh, somehow I ended up unsubscribed from this thread, so I missed all this discussion.  I wanted to respond to the discussion about Grover's algorithm...

Any circuit that can be made on a classical computer (such as a circuit for evaluating sha256(sha256(X))), can be made equivalently on a quantum computer using quantum circuits.  As long as the quantum system includes entanglement (which a lot of QC research right now doesn't even include, because it's hard enough without it), then it can apply this concept of "quantum superposition" to execute Grover's algorithm.  It doesn't matter whether the black-box evaluates sha256 or sha256^2, it still takes N-byte input, and spits out an 32-byte output.  The difference is that the sha256^2 black-box will probably evaluate at about half the speed of the sha256 black-box.

Below is an illustration of how Grover's algorithm works.  It makes a lot more sense when you understand one key point about quantum computation:  Just like Schrodinger's cat, all possible outcomes are equally like, and it's the act of measuring the state (opening the box and checking on the cat) is what "collapses" the probability space into one state or another.  So the cat is both dead and alive, until you open the box and then it is dead or alive with 50% probability of each measurement.

With quantum circuits, we start by preparing the qubits to have a similar all-states-equally-likely situation.  If we were to measure the state at this point, we would get exactly one state, and the one we get is completely random (and then the system assumes that state).    If there are two correct answers and N possible states, the chance of getting the right answer is 2/N which is approximately 0 (the same as making one random guess).  However, each iteration of Grover's algorithm nudges the probabilities slightly in favor of the correct answer:

http://dl.dropbox.com/u/1139081/BitcoinImg/grover_illustr.png


At the end of ~O(sqrt(N)) iterations of Grover's algorithm, we then measure the state for the first (and only) time.  Now, the chance of measuring the wrong state is 2/N which is approximately 0.  The two correct states now contain all the "probability", and when we measure the qubits we will get one of the two answers (it's random which one we get).  Unfortunately, the act of measuring it destroys the quantum goodiness, so if we wanted to get the other answer, we'd have to repeat this process from the beginning (which would take as long a time as the first), measure again, and hope we get the other answer.  (this assumes we know how many correct answers there are, which wouldn't be the case with hashing:  all we know is that if there is an answer, Grover's algorithm will get us closer to it, a lot faster than random guessing).

This process can be applied to any "pure guessing" problem, as long as a quantum circuit can be constructed to evaluate it.  However, it's been proven that every classical circuit has a quantum counterpart, the issue is being able to string enough quantum gates together to build the complete circuit.  It also requires having enough qubits in your system to be able to represent all possible inputs.  If we are hashing a 256-bit number, we'll need 256 qubits to plug through this circuit.  Building a usable 256-qubit QC with entanglement might be a couple decades off...

but the banks will be hacked too... (not to say faster than bitcoin)

another question is, if the QC will be serialized /commercialized in the next 50-100 years

my head asplode

I would be digging this thread a lot more if I had paid attention in math. :-\

...and statistics, and algebra, and geometry, and physics, and quantum computing.. wait maybe not that last bunch.

i hear ya bro.

The rise of quantum computing would be so awesome that if it really must mean the end of bitcoin, it would be a totally acceptable collateral damage.

One thing we should keep in mind is that the public key is not visible unless you send bitcoins from it.  Those who send their bitcoins to a new address after a send, should be relatively safe from QC.  Obviously when the time comes and upgrade to a post-QC algorithm will be necessary, but QC won't be such a blow to Bitcoin as it will be to SSL, and PGP.

Unforgivable!   ;)


But you don't need to find someone's public key.  You only need to find a public key with the same 160 bit hash as theirs.  This will take a classical computer 2^160 guesses, but it will take the QC 2^80 guesses, for all the same reasons you used in the argument with Death & Taxes.


And so the "1 quadrillionth" should be reduced to "1 thousandth".

2.1568E+61 does not equal 2^61  

Why would they be doing this if D-Wave's quantum computers are no more powerful than a cellphone?

Saying they aren't real quantum computers is just disinformation.

Remember when binary computers took up entire rooms? We're at (or past) that state right now with quantum computers.

What about NTRU? Apparently no quantum based attack has been found and the keys don't have to be as long as other quantum-safe crytosystems.

It probably also means real arbitrary precision and never ending mining even without fees.

Two messages might produce the same 52 bit hash. There is no guarantee that whichever messages you put into the hash function will not produce the same 52 bit hash. Therefore there is no guarantee that you will find all possible message digests in 2^52 attempts. In fact, with a 52-bit hash function there is a 50% probability that two messages will hash to the same value if you try 2^26 different messages.

Or am I misunderstanding you here D&T?

http://www.technologyreview.com/news/429429/the-cia-and-jeff-bezos-bet-on-quantum-computing/

interesting.

Quantum computers are like space travels to nearby galaxies - it is fun talking about them and researching possibilities, but it will not happen tomorrow or next year. Worrying that Bitcoin or asymmetric cryptography will became useless because of Quantum computers is like being afraid of alien invasion.

No, because when the binary computer took up an entire room, it was in actuality a binary computer as represented.

Scientists in the field say that the D-wave machine is NOT a quantum computer at all. 

Quantum computing makes me believe that in some alternate universe, I'm filthy fucking rich smoking blunts and surrounded by bitches all day every day. It also makes me believe that in another alternate universe, I've committed suicide by slitting my throat with a dull edgeless spoon.

Oh right, Bitcoin.
Bitcoin exists, is the global reserve currency, and hasn't been invented yet.
Bitcoin doesn't exist, Satoshi was declared dead upon childbirth, and the Bildeburgs are a homeless poor family of Ethiopians.
Pick one.

Reminds me of a physicist joke about Everett's interpretation of QM:

«
- According to Everett, there is a universe in which Sarah Palin is president of the United-States?
- Well you know, it has to be compatible with the laws of physics.
»

It will mean you still can't buy anything with bitcoin.

I think this issue will bear down on us sooner than expected. I would be interested to hear thoughts on how the change to the algorithms could be implemented, as surely without an automated solution it would be a huge threat to ask users to manually migrate to a more secure wallet for example. A smooth and seamless update to the network is the answer, but can it be done?

Imagine if one day Satoshi's coins move and we do not have a solution in place.   

Depends if we see a slow integration where every system will be able to migrate and adapt to QC, then there wouldnt be such a problem to switch to QC mining. The real threat is if governments (or some rich corporations) are building it in secret and will have a huge advantage over majority of current systems.