How does Quantum affect Blockchain?
There has been plenty of talk about Quantum Computing lately and its implication on cryptography which is one of the massive building blocks of Blockchain.
I’m trying to make a trend in the articles I write (junior writer here) to make the article self-contained, that is, try to make the reader understand everything in the article without having to research 100 hours to comprehend what is written here.
So let’s start!
I’ve heard of Blockchain, what is it?
In a very general sense, Blockchain is a distributed (everyone participating has the same information) and decentralized (no one participant has more power than another) transaction ledger that is immutable — extremely difficult to tamper with — this is where Quantum Computing rears its ugly fangs and puts “extremely difficult to tamper with” to the test — or that’s what been said (cue the intense music).
How does Blockchain work?
This video does an excellent job at explaining how Blockchain works!
tl;dw: Blockchain lets you keep an immutable record of the transactions that you and your peers make. Every group of transactions is stored into blocks and they are chained together through a cryptographic function called a hash function. Voilà! Now you know where the word Blockchain comes from!
Previously I said cryptography (the art of sending messages in a secure fashion) is one of the principal building blocks of Blockchain (mind you, cryptography has existed long before Blockchain — you use it everyday without knowing). So where does Blockchain use cryptography?
It uses cryptography in essentially two different parts:
- To identify each user and help them encrypt/decrypt and sign their transactions: Every user has a private key (used to sign and decrypt) that is their identity on the blockchain network, and public key that is used to encrypt/verify signatures messages for them. This private and public key mechanism is called asymmetric encryption (remember this).
2. Figuring out the hash that is going to be used to chain together the blocks on the Blockchain: What do you mean Enrique? First off, a hash is a “pseudo random” output fixed-length string that represents a variable-length input string.
For example:
hash("enrique") => 7ce571623580d69bbcd06f73c2fae388 and
hash("Enrique") => 24423c14d6fbaaddf95f36021d6c1014
As you can see, changing just the e in Enrique from lowercase to uppercase produces a hash that is completely different. Any time you pass the same hash function over the string “Enrique” it will output the same hash, so it is deterministic (same input always produces the same output).
However, from 7ce571623580d69bbcd06f73c2fae388 it’s extremely hard to go back to the original string "enrique" , this is known as a trapdoor function — easy to go from "enrique" to 7ce571623580d69bbcd06f73c2fae388 but very difficult to go back.
Another example to get the point across, if I told you that 1931 x 3571 equals 6895601, you can verify that easily, but if I told you, what are the prime factors of 6895601, it would take you some time (without a computer) to arrive at 1931 and 3571.
As I said, a variable-length input produces a fixed-length output:
hash("I really like learning about Blockchain and Quantum!") => aeb1e2d0a3264705d68206e322e79d13I
The output hash of “I really like learning about Blockchain and Quantum” is the same length as the output hash of “Enrique”!!
Now that we’re on the same page on what a hash is, let’s explore its importance in Blockchain. This is a very simple representation of the Blockchain:
As you can see, the hash of the previous (block 64) block, is part of the next (block 65) block, this hash is what links blocks. So I’m going to oversimplify the hash generation process for each block: You have to come up with a special string to concatenate with the transactions in the block (which are also strings), apply a hash function to that and that output must meet with certain characteristics (for example, the output hash must start with 5 zeros). This process of finding the special string is called mining (also remember this). So in essence:
hash(special string + transactions) = hash with some characteristicsSince the output hash has no correlation to the input string (as you saw previously), finding that special string that complies with the characteristics is quite troublesome, even with powerful computers.
How does this tie in with Quantum?
For that discussion, we first have to establish just enough of What is Quantum to be able to answer that!
So…What is Quantum?!
I’m going to try to keep this explanation short and sweet, because there is A LOT of terminology and math involved!
Up until a few years ago, all we had at our disposal were good ol’ classical computers with good ol’ classical bits (can be 0 —low voltage, OR 1 — high voltage). These bits allow the computer to be in different states, that is (for example 3 bits) 000, 001, 010, 011, 100, 101, 110, 111 => 2^3bits = 8 states , however, the computer can only be in each separate state at a time! It can be 000 at some point, 001 at another moment, 100 at another time, etc. So while it can fully be in all 8 states, it can’t be all 8 states at the same time!
I can hear the screams of “What are you talking about Enrique?!” — yeah I’ve been there, it’s hard to wrap your head around it but we’ll see how we fare at the end of the article.
This is where Quantum Computing enters the spotlight, it uses qubits (quantum bits —creative huh) which have the divine property of being 0 OR 1 OR both at the same time! So the short explanation of how this can happen is: CUZ QUANTUM MECHANICS. So I’ll leave it at that.
Nonetheless, this property is specially important in how quantum computing works, because it lets (in the same example with 3 qubits) the computer be in the same 8 states simultaneously!!
Ok ok, I’ll explain a little about how this happens.
Qubits can be both 0 AND 1 because of something called superposition, so hmm…what is that? It’s a quantum mechanics principle that means (basically) that the qubit is in a combined weighted state of both 0 and 1. This is where it gets tricky, the qubit could be in a superposition state (both 0 and 1 at the same time) until you literally measure the qubit, and in that moment, it will undoubtedly be 0 OR 1 with the weighted probability that I mentioned earlier.
For example, you have 1 qubit in superposition with the weighted probability of 0.25 it being a 0, and 0.75 it being a 1 (probabilities have to sum up to 1), and you ask (measure in technical terms) it “Hey, I see that you are in superposition, but what are you really at this moment?” and it will reply, “I’m 0”. You say “Ok cool!”. Let’s say you repeat this experiment 100 times — asking the qubit what it is, it will reply “I’m 0” or “I’m 1” more or less 25 and 75 times, respectively (it could be 20 and 80, just like when you flip a coin 100 times you don’t get exactly 50 heads and 50 tails, but the probabilities are there).
So if you have 2 qubits with each of them being in a weighted probability of 0.50 being a 0 and 0.50 being a 1, when you measure both of them, you will have 25% of the time a “00”, 25% a “01”, 25% a “10” and 25% a “11”. Why is that? That’s homework (evil laugh).
It’s completely OK if you don’t understand it yet, it goes against what we’ve learned our whole lives, but hey — its quantum mechanics.
The second point I want to very quickly go over is another important principle of qubits and that is entanglement, and that is a principle that states that you can “connect” qubits so that one qubit’s state (measured 0 or 1) is directly correlated to another qubit that it’s entangled to. Let me explain this a little further with another example.
You have 2 qubits, and you entangle them (magic quantum mechanics here), you take 1 qubit go to one edge of the universe, you tell your friend to grab the second qubit and go to the opposite edge of the universe. You measure each qubit independently and you will find that there is an undeniable correlation between the 2 states measured! You measure 0, and your friend measures 0, you measure 1, and your friend measures 1, you measure 0 and your friend measures 1 or you measure 1 and your friend measures 0, it’s not random, their states depend on each other: 0–0, 0–1, 1–0, 1–1, those are the possible outcomes for the qubits, depending on how you entangled them.
So the first thing that popped into my mind when I read this (they actually have taken an entangled qubit into space and another one on earth, measured both at pretty much exactly the same time and they have held their end of the bargain of having correlated output states, so it’s correlation that is done “faster” than light) is that it could be used to transmit data at faster than light speeds, but alas (for the moment) it cannot since it is only correlation between individually random qubits, you can’t transmit data.
Entanglement is a property of most quantum superpositions and does not occur in classical superpositions. In an entangled state, the whole system is in a definite state, even though the parts are not. Observing one of two entangled particles causes it to behave randomly, but tells the observer how the other particle would act if a similar observation were made on it. Because entanglement involves a correlation between individually random behaviors of the two particles, it cannot be used to send a message. Therefore, the term “instantaneous action at a distance,” sometimes used to describe entanglement, is a misnomer. There is no action (in the sense of something that can be used to exert a controllable influence or send a message) — only correlation, which, though uncannily perfect, can only be detected afterward when the two observers compare notes. The ability of quantum computers to exist in entangled states is responsible for much of their extra computing power, as well as many other feats of quantum information processing that cannot be performed, or even described, classically. — IBM Q
So the good news is that you don’t need to understand any of that to understand its implications on the Blockchain! But it’s always good to learn a bit about everything.
Basically, quantum computing accelerates exponentially some algorithms, but it’s not going to replace classical computers! You will still browse the internet on your laptop, play games (although they have made games on quantum computers), chat, etc.
So where is the risk with quantum computing and the blockchain? Well it’s in how it can use Shor’s algorithm to possibly take down many of the widely used encryption algorithms (RSA, Elliptic Curves, etc). So what is Shor’s algorithm, it just computes and finds, in a very efficient manner, the prime factors of a number N (or a modification of Shor’s algorithm allows you to solve the discrete logarithm problem). You don’t need Shor’s algorithm to find the prime factors of 21, you can use a classical computer to do that, but when the going gets tough (a number N of hundreds of digits), and those are numbers that the encryption algorithms use, a classical computer will take billions of years to factor the number into its prime components, while a quantum computer will take seconds to do the same feat (mind blown right?).
Most of the widely used current encryption algorithms base their security on just that, that it is extremely difficult to factor large numbers into their prime components! So when someone shouted that Quantum Computers could easily do just that, it was worrisome to say the least. But for every obstacle, we always find a way through, encryption algorithms have been developed and are being developed that are called quantum safe, meaning that they are not susceptible to quantum computer’s wrath, they won’t be cracked by the speedup in processing.
They will replace the encryption algorithms that are weak to quantum, if the time comes.
We’re almost done guys! This one is a short one I promise.
The second point where Quantum Computing could possibly threaten the blockchain ecosystem is in its mining process (iterating millions of times to find the special string to join blocks — point 2). This has happened with classical computers, they have upgraded, processes and calculations have been streamlined, making everything more efficient and the miners (the people who mine — yeah) have all upgraded to the best classical computers, and the mining process has evolved to take into consideration the advances in mining speed. This will also happen if and when quantum computers are commercially available, and the keywords here are if and when. All the miners will upgrade to quantum computers and the mining algorithm will be modified to render quantum computer’s speedup useless.
The last point I want to touch on in this article is how real this quantum computing demise is. There are plenty of engineering problems associated to developing quantum computers: Decoherence — the loss of information due to environmental disturbances, keeping the quantum computer’s temperature as close to absolute zero as possible (they have managed to get to around 10 millikelvin — amazing), etc. The amount of qubits necessary to actually be a threat to cryptography is in the thousands, and so far the biggest general quantum computer released has 72 (Google’s Bristlecone).
There are other quantum computers that do have thousands of qubits, but they are quantum annealing, they are not able to run Shor’s or Grover’s (speed up an unstructured search problem quadratically) algorithm, so we don’t have to worry about that!
So for the moment, according to experts, quantum computing’s threat to mankind as we know is still about 15–20 years away, and when the time does come that it poses a real threat, we will replace the encryption algorithms and modify the mining process!
I hope you guys enjoyed reading the article, and please feel free to leave a comment. I had a blast writing it and learned a lot myself in the process!
I leave you all with an inspiring quote from Richard Feynman.
Until next time guys! Take care!
