Topic: What does Quantum Computing mean for Bitcoin? (Read 23239 times)
Depends if we see a slow integration where every system will be able to migrate and adapt to QC, then there wouldnt be such a problem to switch to QC mining. The real threat is if governments (or some rich corporations) are building it in secret and will have a huge advantage over majority of current systems.
I think this issue will bear down on us sooner than expected. I would be interested to hear thoughts on how the change to the algorithms could be implemented, as surely without an automated solution it would be a huge threat to ask users to manually migrate to a more secure wallet for example. A smooth and seamless update to the network is the answer, but can it be done?
Imagine if one day Satoshi's coins move and we do not have a solution in place.
Imagine if one day Satoshi's coins move and we do not have a solution in place.
It will mean you still can't buy anything with bitcoin.
Quantum computing makes me believe that in some alternate universe, I'm filthy fucking rich smoking blunts and surrounded by bitches all day every day. It also makes me believe that in another alternate universe, I've committed suicide by slitting my throat with a dull edgeless spoon.
Reminds me of a physicist joke about Everett's interpretation of QM:
«
- According to Everett, there is a universe in which Sarah Palin is president of the United-States?
- Well you know, it has to be compatible with the laws of physics.
»
Quantum computing makes me believe that in some alternate universe, I'm filthy fucking rich smoking blunts and surrounded by bitches all day every day. It also makes me believe that in another alternate universe, I've committed suicide by slitting my throat with a dull edgeless spoon.
Oh right, Bitcoin.
Bitcoin exists, is the global reserve currency, and hasn't been invented yet.
Bitcoin doesn't exist, Satoshi was declared dead upon childbirth, and the Bildeburgs are a homeless poor family of Ethiopians.
Pick one.
Oh right, Bitcoin.
Bitcoin exists, is the global reserve currency, and hasn't been invented yet.
Bitcoin doesn't exist, Satoshi was declared dead upon childbirth, and the Bildeburgs are a homeless poor family of Ethiopians.
Pick one.
Quote
The National Security Center is building a highly fortified $2 Billion highly top secret complex simply named the “Utah Data Center” which will soon be home to the Hydrogen bomb of cybersecurity – A 512 Qubit Quantum Computer — which will revitalize the “total information awareness” program originally envisioned by George Bush in 2003.
Why would they be doing this if D-Wave's quantum computers are no more powerful than a cellphone?
Saying they aren't real quantum computers is just disinformation.
Remember when binary computers took up entire rooms? We're at (or past) that state right now with quantum computers.
No, because when the binary computer took up an entire room, it was in actuality a binary computer as represented.
Scientists in the field say that the D-wave machine is NOT a quantum computer at all.
Quantum computers are like space travels to nearby galaxies - it is fun talking about them and researching possibilities, but it will not happen tomorrow or next year. Worrying that Bitcoin or asymmetric cryptography will became useless because of Quantum computers is like being afraid of alien invasion.
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.
Two messages might produce the same 52 bit hash. There is no guarantee that whichever messages you put into the hash function will not produce the same 52 bit hash. Therefore there is no guarantee that you will find all possible message digests in 2^52 attempts. In fact, with a 52-bit hash function there is a 50% probability that two messages will hash to the same value if you try 2^26 different messages.Or am I misunderstanding you here D&T?
It probably also means real arbitrary precision and never ending mining even without fees.
What about NTRU? Apparently no quantum based attack has been found and the keys don't have to be as long as other quantum-safe crytosystems.
Quote
The National Security Center is building a highly fortified $2 Billion highly top secret complex simply named the “Utah Data Center” which will soon be home to the Hydrogen bomb of cybersecurity – A 512 Qubit Quantum Computer — which will revitalize the “total information awareness” program originally envisioned by George Bush in 2003.
Why would they be doing this if D-Wave's quantum computers are no more powerful than a cellphone?
Saying they aren't real quantum computers is just disinformation.
Remember when binary computers took up entire rooms? We're at (or past) that state right now with quantum computers.
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 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.
Quote
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.
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).
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".
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.
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.
I would be digging this thread a lot more if I had paid attention in math. 
...and statistics, and algebra, and geometry, and physics, and quantum computing.. wait maybe not that last bunch.
I would be digging this thread a lot more if I had paid attention in math.
my head asplode
Jump to: