Quantum Computers Are a Million Times Too Small To Hack Bitcoin (newscientist.com) 61
MattSparkes shares a report from New Scientist: Quantum computers would need to become around one million times larger than they are today in order to break the SHA-256 algorithm that secures bitcoin, which would put the cryptocurrency at risk from hackers. Breaking this impenetrable code is essentially impossible for ordinary computers, but quantum computers, which can exploit the properties of quantum physics to speed up some calculations, could theoretically crack it open.
[Mark Webber at the University of Sussex, UK, and his colleagues] calculated that breaking bitcoin's encryption in this 10 minute window would require a quantum computer with 1.9 billion qubits, while cracking it in an hour would require a machine with 317 million qubits. Even allowing for a whole day, this figure only drops to 13 million qubits. This is reassuring news for bitcoin owners because current machines have only a tiny fraction of this -- IBM's record-breaking superconducting quantum computer has only 127 qubits, so devices would need to become a million times larger to threaten the cryptocurrency, something Webber says is unlikely to happen for a decade. The study has been published in the journal AVS Quantum Science.
[Mark Webber at the University of Sussex, UK, and his colleagues] calculated that breaking bitcoin's encryption in this 10 minute window would require a quantum computer with 1.9 billion qubits, while cracking it in an hour would require a machine with 317 million qubits. Even allowing for a whole day, this figure only drops to 13 million qubits. This is reassuring news for bitcoin owners because current machines have only a tiny fraction of this -- IBM's record-breaking superconducting quantum computer has only 127 qubits, so devices would need to become a million times larger to threaten the cryptocurrency, something Webber says is unlikely to happen for a decade. The study has been published in the journal AVS Quantum Science.
MD5 required more than heatdeath of the universe (Score:3)
MD5 required more than heatdeath of the universe. Then it was cracked, and eventually easy.
This I don't believe.
Re: (Score:2)
MD5 required more than heatdeath of the universe.
Still does - if you're bruteforcing the full keyspace.
But you're right- that's always, and will always be the rub- cryptographic hashes (seem) to always be vulnerable to some kind of smaller-than-bruteforce keyspace search.
Re: (Score:2)
One of interests is to someday make an image that contains its own MD5 checksum. Should be doable by the average cryptographer eventually on modern hardware.
Re: (Score:2)
How in the world can you make a checksum of something that is immediately going to change the moment you insert the checksum? Is there something I'm missing here?
image = image+checksum(image+checksum(ad infinitum...)
Do you see the problem there? Every time you compute the checksum and then add it to the image, the checksum will change. You have to know the checksum before you can insert it into the image. Sure you can keep iterating until you eventually find something that works but with modern hardware it
Re: (Score:2)
Not as hard, but similar: XKCD: Self description [xkcd.com]
Re: (Score:2)
Yeah, but XKCD's example could be solved with a simple quadratic or similar equation being executed once, and you can even make intelligent guesses to get to the answer in just a few steps but computing md5=(image+md5) isn't since you must have the md5 BEFORE you can even begin to compute the md5. The only real solution is going to be similar to
for i =1 to infinity
if md5(image+i)=i then print "hurray"; exit
else next
Yes you could use random numbers or whatever type of search you like but since the md5 isn't
Re: MD5 required more than heatdeath of the univer (Score:1)
Re: (Score:2)
Now do secp256k1... (Score:3)
Hashes like SHA-256 and symmetric ciphers like AES are relatively robust to quantum computers. Traditional asymmetric cryptography is much easier for quantum computers to break, and would allow attackers to forge new transactions that move bitcoins between arbitrary wallets -- for example, the huge number of coins that Satoshi mined early on. The
Re:Now do secp256k1... (Score:4, Insightful)
Easier, yes. But still orders of magnitude beyond any existing quantum computer. And keep in mind, difficulty maintaining coherance scales exponentially with size.
Re: (Score:2)
Re: Now do secp256k1... (Score:2)
Re: Now do secp256k1... (Score:2)
Re: (Score:3)
Yes, the quantum attack on SHA-256 or AES (with 256-bit keys) uses Grover's algorithm. That reduces the cost from O(2^256) to O(2^128), which is still a pretty huge task.
The quantum attack on discrete log cryptosystems instead uses Shor's algorithm, which has a cost of O(log(n)*log(n)*some smaller factors that Slashdot doesn't like). That is much more practical to implement.
But it turns out (as FeelGood314 pointed out [slashdot.org]) that the actual paper was already talking about the public key part of Bitcoin, and the
Submitter didn't understand bitcoin or the paper (Score:5, Informative)
Re: (Score:2)
Thanks it was helpful.
Re: (Score:2)
That makes sense. 1,000,000X is a really small security margin (20 bits) for SHA-256 and Grover would only take you down to 128 from 256. So I could tell the summary was nonsense.
Re: (Score:2)
Next Week: (Score:1)
Hacker cracks bitcoin with HP 35C.
Interesting, but... (Score:1)
Interesting, but the question everyone is wondering is... can we do quantum mining! /s
No you can't do quantum mining (Score:2)
But lets look a bit closer at the mining hashing in Bitcoin. Bitcoin uses a
Correct me if I'm wrong (Score:5, Insightful)
Re: (Score:2)
Yes, but they've gotta have clickbait headlines to get those page views and drive up advertiser revenue.
Re: (Score:2)
Just wait until the Webb telescope finds... (Score:2)
An exoplanet made of qubits.
Break Bitcoin or Mine it? (Score:2)
If you had a computer that powerful that it approaches the power to break Bitcoin, it would definitely be more profitable to mine Bitcoin with it instead.
Even if.... (Score:2)
a quantum hacker you crack bitcoin, the majority of miners would probably agree to fix it?
Quantum Computers Are a Million Times Too Small.. (Score:1)
Bitcoin is completely secure, nothing to worry about.
something Webber says is unlikely to happen for a decade
oh. so all my bitcoins might become worthless in ten years?
Re: (Score:3, Funny)
or ten weeks.
Re: (Score:1)
Re: (Score:1)
Re: (Score:2)
Doublings (Score:2, Interesting)
If the size of quantum computers continues to double annually as it has been, that's log2(13 million / 127) = 17 years, or 2039.
If, on the other hand, the pace drops to doubling biennially, that'd be 34 years, or 2056.
This stuff is counted (Score:2)
you just need 51% of the mining to control bitcoin (Score:2)
you just need 51% of the mining to control bitcoin
moore's law (Score:2)
13 million qubits in about 32 years https://www.wolframalpha.com/i... [wolframalpha.com]
really pathetic article (Score:2)
So, about a decade then? (Score:2)
Good thing there's no precident (Score:3)
It's a matter of time (Score:1)
Given current understanding of quantum computing (Score:5, Insightful)
First of all, the point of a quantum computer is that algorithms run on a quantum computer should in theory decrease from exponential time to polynomial time.
The estimates made above are based on current qubit technology which in traditional computing terms is equivalent to transistors soldered together one by one in the 1950's compared to a modern computer with transistor to transistor interconnects measured in nanometers.
A current qubit propagation delay (there are better terms, but I'm trying to make analogies) is approximately 300 times slower than the qubits that are the "holy grail" of all quantum computer developers. This is the approximate speed they are focused on to make quantum a clearly usable technology. So, if the head of the CSC Finland quantum project is to be believed, this is a great focus.
At least for now, the goal of most public (not privately owned) quantum projects around the world is to create a quantum computing grid which would link all quantum computers together over the globe as basically a quantum super computer. In addition, each of these computers within a few years are scheduled to be connected directly to exascale HPC systems.
There are major points against cracking SHA-256 on quantum computers during the next 10 years.
1) No one in quantum gives a rats ass about bitcoin. These machines aren't being built for that. They're being built to estimate approximate shapes of proteins and to solve quantum chemistry problems such as understanding hydrogen cyanide (the smallest goal for quantum at this time... and it's already been done on quantum simulators... but it's a starting point)
2) Qubits are far from reliable. We currently depend on error correction algorithms to provide results. This is amazing for things which can be estimated by quantum and polished up by traditional computers. But it's not reliable or things like cracking precise bit chains. It's quite similar to the problems we faced with transistors before the first stable and reproduceable transistor was made.
3) The energy required to operate a quantum computer is expensive and there is little value in using them as an assault on the economy.
I can go on... but at least for 5-10 years, even if a hostile government were to invest in a goal of compromising bitcoin, it's not likely to happen.
Quantum is difficult for most people to understand and there are some excellent lectures from Microsoft Research presented by Krysta M. Svore who is one of the most talented people I've encountered in this field. I highly recommend watching her presentations if you want to understand more.
Before you watch her though, there are some key points which I'll explain here which makes quantum much much easier to understand.
1) Quantum is much more like an FPGA than a CPU. More accurately, it's reconfigurable computing. When you develop algorithms, you're pretty much defining the order in which qubits are wired. This allows the output of one qubit to be directly routed into the next.
2) Currently, quantum computers are programed in terms of satisfiability rather than an order of instructions. You wouldn't really compute loops. Rather you're attaching a series of what we might have called gates in the past and you're using the equivalent of comparative logic... in analog quantum computers, this would be like an opamp and in digital quantum computers, this would be like nand gates. So you would make use of superposition (find videos on this) and attach a series of quantum gates/logic/bits.... to describe what would be a solution to a problem. For the most part, this kind of thinking should be pretty clear to people who have developed in VHDL or even coded in functional languages.
3) We are working weirdly at this time. We've developed languages like Q# which are high level languages for quantum computers and make quantum practical. We sort of skipped the whole assembly language phase. This means th
Re: (Score:2)
I guess we'll need... (Score:2)
... a million quantum computers, then.
Thankfully there's No Such Agency in the US that could every amass that much computing power. Ever.
Re: (Score:2)
Re: (Score:2)
It doesn't.
A quantum computer's power is really given by how many bits each bit interacts with. A billion cubits isolated from each other isn't much use.
You cannot make a beowulf cluster of those.
What's the dollar per qbit value? (Score:1)
There is $1,030B in bitcoin.
If you stole ALL of it, you wouldn't really be able to spend it.
So say you're going to steal 1% of it. That's 10.3 billion dollars.
Fukagu is the world's fastest computer. You can buy one for $1B. That's 10% of the reward money.
It is an exascale computer, calculating 10**18 calculations per second.
A typical desktop computer does 150-200 million calculations per second, or: 2*10**8 calculations.
So Fukagu is about 10**10 times faster, which is... 10,000,000x faster.
1.9 billion q
A million times larger is probably reasonable. (Score:2)
Sounds familiar... (Score:2)
"640K ought to be enough for anyone."
We've heard it and seen it before. In a few decades time, quantum computers will be more than powerful enough to crack bitcoin, it's just a matter of "when", not "if"
Yeah, because that's what we're worried about (Score:2)
Right now a secret cabal of AIs is laughing their diodes off... "heh, they fell for it, they think *computers* are the security problem. WE WON!
Meanwhile, someone's getting sent an NFT that steals all their Ether while feeling perfectly secure because they read that computers won't decrypt the keychain.
error correct qubits (Score:1)
Don't need to hack Bitcoin itself (Score:2)
So, it's less than 10 years before bitcoin is gone (Score:2)
Right? A few years, and it'll be broken, as quantum computers grow, and crackers rent space on AmazOoogle QuantumCloud (tm).
Satoshi's 36 billion dollar wallet address (Score:2)
Scale up (Score:1)
Actually, it is only 100,000 times bigger (not 1M) (Score:1)
Decade (Score:2)
Only a decade away?
Sounds like Bitcoin should be pushing a protocol update to move to a quantum-safe algorithm already to be honest. They already exist and have for years.
Especially for something that purports to have billions in value, 10 years is not a lot of time to push such an update and you KNOW that you MUST do so eventually, so why are they waiting?