What does Quantum Computing mean for Bitcoin?

[DeathAndTaxes]

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.

[DeathAndTaxes]

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.

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.

[hashcoin]

OK I think we're making some progress..

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.

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

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.

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?

[DeathAndTaxes]

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.

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.

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?

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.

[hashcoin]

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.

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.

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.

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

[DeathAndTaxes]

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.  

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.

So far I have worked with a function which maps {0, 1}
n → {0, 1} and has only one marked item. But more
generally we can design our Grovers algorithm to work with a function {0, 1, . . . , N −1} → {0, 1} which is 0 on N −M
on this domain and is 1 on the rest of the M points of this domain. The goal then will be to find a single one of the
inputs x such that f(x) = 1. For now we will assume that we know M. Let S be the set of x such that f(x) = 1.

....

Putting this together we find that the number of iterations is bounded by
k ≤ (Pi)/4 * SQRT(N/M)

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.

[hashcoin]

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. 

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.

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.

[hashcoin]

There is no talking your way around that.

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

So far I have worked with a function which maps {0, 1}
n → {0, 1} and has only one marked item. But more
generally we can design our Grovers algorithm to work with a function {0, 1, . . . , N −1} → {0, 1} which is 0 on N −M
on this domain and is 1 on the rest of the M points of this domain. The goal then will be to find a single one of the
inputs x such that f(x) = 1. For now we will assume that we know M. Let S be the set of x such that f(x) = 1.

....

Putting this together we find that the number of iterations is bounded by
k ≤ (Pi)/4 * SQRT(N/M)

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.

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?

[chsados]

why does quantum computing mean the end of all security? 

what about blind quantum computing?

[kjj]

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.

[etotheipi]

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:




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

[cloon]

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

[Hexadecibel]

my head asplode

[RodeoX]

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

[rjk]

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.

[cypherdoc]

my head asplode

i hear ya bro.

[grondilu]

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.

[Stardust]

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.

[dooglus]

Sorry to revive an old thread

Unforgivable!   

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.

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.

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

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

[kentrolla]

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.

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.

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.

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

2.1568E+61 does not equal 2^61