The Truth About Bitcoin And Quantum Computers

in #quantum-computer7 years ago

q1.jpg

Quantum computers are gradually becoming reality. The consequences for Bitcoin and other cryptocurrencies can be dramatic - but are far from uncontrollable. A team of scientists describes what quantum computers do for Bitcoin and how to make the transition to quantum-safe algorithms.

Quantum computers are still science fiction. Devices that bring little power with a tremendous effort. But the quantum engineers succeed in coupling more and more quantum bits - in short: qubits. So Google has recently introduced the quantum computer Bristlecone with 72 qubits. If the number of qubits continues to grow exponentially, the prediction is realistic that quantum computers will be wide enough from around 2031 to become a threat to many cryptographic techniques.

Click on the image to enlarge
q2.JPG

It does not burn yet, but it is no mistake to deal with the topic already. Finally, Bitcoins should have no expiration date. A research group, especially the Center for Cryptocurrency Research and Engineering at Imperial College London, describes in a paper how quantum computers can attack Bitcoin and how to protect against it.

The involved crypto algorithms

To assess the danger, one must know which cryptographic mechanisms use Bitcoin and other cryptocurrencies. These fall into two categories:

  • Signature Algorithms:
    These procedures consist of a public and a private key. With the private key one signs transactions, with the public one proves that the signature is correct. Cryptocurrencies usually use signature algorithms based on elliptic curves. For Bitcoin this is ECDSA, for some other currencies EdDSA or Schnorr signatures. Under normal conditions ECDSA is considered absolutely safe.

  • Hash Algorithms:
    Hash algorithms are one-way mathematical functions that transform a value deterministically into another fixed-length value. It's best to try it on Hashgenerator.de. Bitcoin uses hash functions in two ways. First, the miners must compute hashes with SHA256 to find blocks, and second, the public key of the signature algorithm is hashed with both SHA256 and RIPEMD-160 to form the address. This step is extremely important, as we will see later.

Quantum computers have an impact on the security of these cryptographic algorithms. Why exactly, is very difficult to explain. Let me just quote the researchers: "Just as a classical computer is built out of bits, quantum computers use qubits that have two fundamental states (0 and 1). However, while a calculation is running, the state is a linear combination of both states (a superposition). "One knows this from quantum physics, that a particle is somehow in both states. This super state collapses into one of the two fundamental states as soon as one observes the system.

"This means that a quantum computer with n qubits can internally present the entire span of n-bit numbers and perform all calculations simultaneously. But once you measure it, the state will collapse into one of the two basic states and only output one of the results of the calculations. Quantum algorithms attempt to use this structure to amplify certain base states and increase their likelihood, making the result repeatable and conclusive. For some problems, quantum algorithms can solve complex problems much faster than conventional algorithms. "

And these problems unfortunately include crypto-algorithms.

How quantum computers attack cryptography

You do not have to understand all that in detail. Importantly, there are several quantum algorithms that attack cryptographic techniques in new ways:

  • Shor's Algorithm:
    This quantum algorithm accelerates the factorization of integer exponentially. This drastically weakens the security of asymmetric cryptosystems such as RSA and ECDSA. Shor can be used to break the signature algorithms used by virtually all cryptocurrencies (except IOTA).

q3.JPG

  • Grover's Algorithm:
    This quantum algorithm can search unstructured data and find a hit with a relatively high probability. With Grover's algorithm, one can quadrally accelerate collisions of hash algorithms. This could theoretically be used to mine bitcoins, but it will probably take a long time for this to outperform Asics. If ever.

q4.JPG

Since especially signature algorithms like ECDSA are threatened by quantum computers, we will turn to them. With conventional computers, ECDSA is impossible to break. But what happens if quantum computers are able to crack them?

It will be possible to guess the private key using the public key. However, this does not mean that such an operation is trivial or fast. Thus, it is believed that quantum computers with 2,000 to 10,000 logical qubits will be able to break the widespread RSA encryption (so far they reach 72). How long the quantum computer will need, one second, two weeks, or a year, depends on its strength and the number of bits of encryption.

The ECDSA encryption used by Bitcoin is believed to require about 1,800 qubits. However, for each effectively used qubit, a quantum computer must provide numerous physical qubits that correct errors. A cryptographer on Bitcointalk therefore estimates that a quantum computer will need more than 40,000 physical qubits to break ECDSA. And even if this is possible, it will not happen in a second, but will need a lot of arithmetic operations. How many exactly do I not know.

What happens when the time comes?

But suppose there are such powerful quantum computers that can break with Shor ECDSA in a reasonable amount of time. So what?

The good news is that the quantum computers will still not be able to steal Bitcoins that way. Because addresses are not a public key, but a hash of them, and these are far less prone to quantum cryptography. In other words, anyone who leaves his Bitcoin on an address does not run the risk of being stolen. The advice to use an address only once makes so much more sense.

The bad news is: There is another attack. The researchers call him the "kidnapping transactions" call. Once you sign a transaction, you reveal the public key. This makes the address useless for the future. Worse still, a quantum hacker can capture unconfirmed transactions. Because if the transaction is on the net, the public key is known. This can be exploited by a quantum computer: "Like a double spend, the attacker creates a transaction that transfers the same coins elsewhere, stealing the victim's funds."

Unlike a double spend, such abduction can be carried out not only by the one who is paying, but by any third party. Sending bitcoins becomes a difficult to control risk. The researchers acknowledge, however, that the effort is not trivial even for strong quantum computers: "Since the attacker not only has to create, sign and propagate the alternative transaction, but also first has to calculate the private key using the Shor algorithm, that's timining essential for this attack. "

Depending on the double-spending process, the hacker will have a few seconds to a few minutes to do it all. So even if quantum computers are theoretically capable of breaking ECDSA, that does not mean that they are fast enough to hijack transactions in practice. It is quite possible that such an attack will not only require 1,800 to 10,000 qubits, but much more. Cryptocurrencies with shorter block intervals, such as Ethereum with 13 seconds, should also be able to resist it much better.

Nevertheless, the attack remains problematic. It opens up a weak point in the system that can be exploited systematically, automatically and without risk. In addition, it is also possible to use the attack for DoS attacks or even make selfish mining attacks worse or more profitable for the miner. This would not only jeopardize individual credits, but the system Bitcoin in general.

How can you protect yourself?

Even if it does not burn for a long time, you can not think about it early enough on how to prepare for the day when quantum computers will break ECDSA. Fortunately, there are a lot of options.

On the one hand, you can gain time by increasing the bit number of ECDSA. Depending on the progress of quantum computers, this may or may not help. But it will only be a permanent solution if you switch to a quantum-proof algorithm. The authors of the paper point out which possibilities are already known for this:

  • The McElieve system "resists decoding of unknown codes for linear error correction" and is therefore quantum safe. The price is that individual signatures are considerably larger (up to one megabyte).

  • There are methods for hash-based signature, which can be attacked by quantum computers only to a very limited extent. The best-known of these concepts is the Lamport Diffie one time-signature, the Winternitz signatures used by IOTA also belong to this family.

  • There is also the possibility of forming signatures based on lattices (lattice-based cryptography). Examples are the more theoretical methods GGH and NTRUSign.

It's important, the authors explain, "that the Bitcoin community agrees to implement a good alternative (or maybe more) that replaces cryptography with elliptic curves as the basis of transactions' signatures."

However, this will not completely solve the problem: Because to enjoy the benefits of the quantum-proof algorithms, all users have to move their coins to new addresses. If this does not happen by day X - the day quantum computers can hijack unconfirmed transactions - the Bitcoins will be more or less frozen. At least it will be impossible for large sums to transfer them without a significant risk.

Imperial College researchers are now proposing a solution to this problem: a concept that allows Bitcoins to be securely moved to quantum-safe addresses even after that time. The concept is relatively complex. It forms, as it were, a smart contract that composes a transaction to be valid only after a relatively long time has elapsed, and when evidence of ownership of both a conventional and a quantum secure private key is obtained. With this method you could probably also credit balances of non-quantum-safe addresses safely against all attacks on a quantum secure address.

If you want to know more about the method, you should read the last third of the paper. Time enough you will have for sure.



Image Sources:

end.png
Have a nice day!

LOVE&LIGHT
mylo.PNG

Sort:  

Soon we have Quantum BTC

We shall call it; Bitcoin Intelligence...

lol :)))

Each year the technology that we become accustomed to increases in speed and decreases in size....geometrically. The computer power in our phones right now is faster and obviously microsized compared the room full of computers that would do the same thing decades ago. I used to build computers that had megabytes of processing speed and now I build with gigabytes upon gigabytes with terabytes of storage...and just your random average dude. Can you imagine those that design and program the computers, that in turn design and program computers? Y'all seen 'Terminator'? We are getting closer and closer to SKYNET! Good post. -Respect

Thank you!
SKYNET lol nice one but yes it's going in this direction.
Damn my first PC was a Commodore 64 with 20 KB memory lol crazy how fast technology is developing I am wondering if there is help involved from some ETs ;)

I remember when i was younger, I heard that the government is always more than a handful of years ahead of the general public. As technology makes these leaps and bounds forwards...I'm wondering what BIG BROTHER has got cookin'. -Respect

But SKYNET will have a vulnerability somewhere too!... Our random, human/animal, instinctive, unpredictable chaos?!

Everybody and everything has a vulnerability....including the Death Star...and Superman! A little humor mixed in with some information sharing is always a good thing. Keep up the good work and fun. -Respect

I think the threat to bitcoin and other cryptocurrencies will be something that is not even in our reality yet. It can't be as predictable as quantum computers if you see it coming from a mile away you can take steps to stop it.

The threat to the multi million dollar company Kodak was not a better camera, it was a phone - who saw that coming? No one, not even the phone companies.

Nice point of view thanks for that :)

I have faith in the Bitcoin community as a whole to ensure that any risks to the network are mitigated.

Throughout its' history Bitcoin has showed tremendous resiliency, quantum may be the network's biggest challenge yet but I'm confident Bitcoin will continue on its' trajection (to the moon?!)

can quantum computers be a threat for cryptocurrency if it comes in hands of a hacker?

.

okay alles klar :)

Tulisan keren ini.. telah kami follow.. ;]

.

Okay cool danke hoffentlich geht es jetzt wieder Berg auf mit Steem :)

Sieht aus als wird das ein neuer Aufwärtstrend. Hoffen wir es mal. Will nicht das es noch länger dauert... Denke das will keiner.

thanks for share it
nice topic

Interesting information. Computer technology is developing rapidly. We need to follow the development.

I really need the Bitquin to have a very high safety ratio because it is a Belmune coin piece
Choosing the algorithm is very impressive

I could not understand everything, but the danger to the private key worried me :(

You got a 14.90% upvote from @postpromoter courtesy of @danyelk!

Want to promote your posts too? Check out the Steem Bot Tracker website for more info. If you would like to support the development of @postpromoter and the bot tracker please vote for @yabapmatt for witness!

Thank you very much for your post. you have informed us in this regard. I am waiting for your support in the last posting. good luck

This is great news of bitcoin.I appreciate your post.actually you are
great one in this steemit..I am always follow your post..Cause I like your post always..And your every post is mind blowing ..Thanks for sharing you valuable post..My support will for your every .I wish you overcome in this steemit by your post.

Very informative and useful! Thanks

Bitcoin may not even exist. There may NANO still, or NEXUS, or Hashgraph. But Blockchains will serve a purpose for now!

Well i think i understood most of that. :D

Great article , keep the good work

Learned a lot from this post....Thanks =D