etotheipi
Legendary
Offline
Activity: 1428
Core Armory Developer


October 10, 2011, 08:47:01 PM 

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 publicprivate 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 64byte 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 txwithpublickey immediately, and reduces the propagation speed of the original transaction.








Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.



punningclan


February 01, 2012, 04:44:35 AM 

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

It was a cunning plan to have the funny man be the money fan of the punning clan. 1J13NBTKiV8xrAo2dwaD4LhWs3zPobhh5S



DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 01, 2012, 04:54:19 AM 

So as Litecoin is Bitcoin's silver, QBit is Bitcoin's Platinum?
Bitcoin is Bitcoin silver and Bitcoin is already quantum resistant.




DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 01, 2012, 05:01:16 AM 

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


February 01, 2012, 10:09:54 PM 

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.

It was a cunning plan to have the funny man be the money fan of the punning clan. 1J13NBTKiV8xrAo2dwaD4LhWs3zPobhh5S



punningclan


February 01, 2012, 10:14:15 PM 

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.

It was a cunning plan to have the funny man be the money fan of the punning clan. 1J13NBTKiV8xrAo2dwaD4LhWs3zPobhh5S



DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 01, 2012, 10:15:28 PM 

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


February 01, 2012, 10:38:19 PM 

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.

It was a cunning plan to have the funny man be the money fan of the punning clan. 1J13NBTKiV8xrAo2dwaD4LhWs3zPobhh5S



DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 01, 2012, 10:54:17 PM 

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


February 02, 2012, 06:32:09 AM 

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

It was a cunning plan to have the funny man be the money fan of the punning clan. 1J13NBTKiV8xrAo2dwaD4LhWs3zPobhh5S



hashcoin


February 02, 2012, 08:35:00 AM 

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_algorithmEvery time the difficulty goes up by a factor of 4 for classical miners, it goes up only by 2 to quantum miners.




DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 02, 2012, 02:21:36 PM 

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_algorithmEvery 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
Member
Offline
Activity: 62
I was lucky enough to solve block 121306


February 02, 2012, 05:29:42 PM 

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

Haha! I'm the only one to control Bitcoin address 1HjtErSHNEHtY347LouvsFq5KesHkEZLAV



DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 02, 2012, 05:37:07 PM 

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_distributionGenerate a sequence of bits using secure pseudorandom 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


February 02, 2012, 10:29:16 PM 

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 ninput 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/electricalengineeringandcomputerscience/6845quantumcomplexitytheoryfall2010/lecturenotes/MIT6_845F10_lec09.pdfAlso 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/nocloneccc.pdfedit 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 kbit input circuit, then you can search faster by a factor of 2^(k/2).




DeathAndTaxes
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 02, 2012, 10:37:02 PM 

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


February 03, 2012, 03:28:50 AM 

No, I think you do not understand Grover's algorithm or basic QC at all from your response. This is elementary undergradlevel 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 inputbyinput, 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 blackbox 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 inputoutput 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
Donator
Legendary
Offline
Activity: 1218
Gerald Davis


February 03, 2012, 03:39:20 AM 





hashcoin


February 03, 2012, 03:51:26 AM 

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 deliberatelyweakened 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 postquantum 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


February 03, 2012, 04:08:36 AM 

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




