What does Quantum Computing mean for Bitcoin?

[etotheipi]

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

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

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

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

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

[1713465605]

1713465605

[1713465605]

1713465605

[1713465605]

1713465605

[punningclan]

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

[DeathAndTaxes]

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

Bitcoin is Bitcoin silver and Bitcoin is already quantum resistant. 

[DeathAndTaxes]

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

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

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.

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.

[punningclan]

Could the sudden existence of quantum computing mean the sudden uselessness of Bitcoin as a currency?

I don't think practical quantum computing will "suddenly" exist.

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

[punningclan]

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

Bitcoin is Bitcoin silver and Bitcoin is already quantum resistant. 

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

[DeathAndTaxes]

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.

[punningclan]

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

Bitcoin is Bitcoin silver and Bitcoin is already quantum resistant. 

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.

[DeathAndTaxes]

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. 

[punningclan]

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.

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

[hashcoin]

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. 

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.

[DeathAndTaxes]

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. 

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.

[nayrB16]

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

[DeathAndTaxes]

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.

[hashcoin]

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.

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

[DeathAndTaxes]

To be precise, Grover's algorithm solves CIRCUITSAT with n inputs in time 2^(n/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.

[hashcoin]

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

[DeathAndTaxes]

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

[hashcoin]

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.

[hashcoin]

No.  Reread section III from your own link again.  

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.