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

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

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

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.

why does quantum computing mean the end of all security? 

what about blind quantum computing?

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?

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.

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.

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

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.

OK I think we're making some progress..


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?

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.

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.

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.

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.

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

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

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

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.

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