Whenever I tell my friends about the potential of Quantum Computing, for example, how a Quantum Computer (QC) can do a large number of calculations in parallel worlds, they look at me like I’m kind of crazy.
So, rather than talk about it in the abstract, I decided to show them how radical QCs can be. I ordered one the other day and when I got it, I decided to look for an application that could demonstrate the power of this new form of computing.
Some of my friends know that I have been a bitcoin enthusiast for many years, even when it wasn’t popular, and it occurred to me that bitcoin mining might be the problem to solve to show the power of a quantum computer (and to make some money while I sleep!)
As you might expect, a quantum computer capable of solving the bitcoin mining algorithm was very expensive (this particular brand, the QIntellize Quantum Computer, costs at least $ 1million). Since the reward for mining a bitcoin block is now at 12.5 bitcoins, at $4000 per bitcoin I should be able to pay it off after mining a few blocks quickly!
So I ordered a QC and set it up. It wasn’t easy to get my one quantum computer to do the work that thousands of computers around the world are currently doing in mining bitcoin blocks; but I finally figured it out!
This article is meant as an introduction to both bitcoin mining and QC’s, to discuss some of the difficulties I had in cornering the bitcoin market in this way. While I won’t reveal all of my secrets (I’d rather keep my monopoly, mind you), there should be enough clues here to guide you in the right direction if you wanted to duplicate my experiment!
How Bitcoin Mining Works: A Brief Overview
I won’t go into all the details of bitcoin (you can do a simple search more about bitcoin since there are thousands of sites dedicated to it), or bitcoin mining (you can read more about it here: bitcoinmining.com), but this is a quick summary.
Bitcoin is a de-centralized currency and ledger where a very big file (called the blockchain), consisting of blocks, each of which has a list of transactions. The blockchain is the general ledger to say what happened to each bitcoin over time and where it went. Since multiple computers are managing the blockchain, there is no one computer in charge of what’s happening — the system is built on these distributed computers agreeing about what blocks should be on the blockchain.
New bitcoin are created by bitcoin miners, who are actually computers that are trying to add blocks to the blockchain. The mining itself is an algorithm that adjust in difficulty so that a new block can be added on average once every 10 minutes or so. Miners computers are trying a set of random numbers to see if they “match” the current criteria for a new block.
A small random number (4 bytes) is added as part of a blockheader (which is generated based on a proposed block of transactions), and the resulting number is hashed (twice using the SHA 256 algorithm) which produces a random number at the end. If the random number is less than a certain threshold, then you have successfully generated a new block in the blockchain, which is put forward and then validated by other computers. Figure 1 shows an overview of this process (source: bitcoinmining.com)
Figure 1: How Bitcoin Mining Works (source: bitcoinmining.com)
So why bother? Bitcoin mining is sometimes called a “lottery” because if you successfully generate the block, you are given some bitcoin in return. Since the price of bitcoin is several thousand dollars per bitcoin now, with a market capitalization in the many billions, this can be significant.
Why is this difficult? Because thus far hashing, which is the basis of current cryptography using secure keys, is a one way operation. At current, it’s impossible to know what a specific set of bits will hash to without actually doing the hashing algorithm, which has multiple cycles of moving bits around.
As a result, the best way to do mining currently is to keep trying random numbers to see which one hashes to a number that is less than the target difficulty. This is why bitcoin mining pools have cropped up where a large number of computers are working in parallel to find the solution to the problem — if one of them finds the solution then the pool gets the reward, sharing it with all the other miners.
How Quantum Computing Works: An even Briefer overview
This idea of pools working in parallel was what gave me the idea to use a Quantum Computer instead.
While it sounds like science fiction, quantum computers work, by taking into account the idea from quantum physics that there are parallel worlds out there. Every time we make a decision, we branch into multiple realities, or according to some physicists, there are multiple future probabilities that exist around us all the time.
This quantum foam, consisting of multiple probably realities, can be thought of as a quantum probability wave. Quantum physics tells us that an electron is really a set of probabilities of where that electron is likely to be, or that a photon is likely to be either a wave or a particle. When we observe the position or velocity of a particle, the quantum wave is said to collapse into a specific reality.
Sounding now more like Eastern Mysticism than even science fiction, it’s the conscious act of observing a particle that collapses the probability wave into a single, measurable reality.
Richard Feynman first proposed the idea of a quantum computer back in the 1980s, saying that if we could create device that could use this idea of parallel universes of probability waves to try out all possible values of a specific variable and then “collapse” it into the “right” answer. It’s taken a few decades, but we are finally at the point where quantum computers are becoming viable.
Quantum computers actually make difficult problems (those which require lots of computing power) significantly easier, because you are able to distribute the processing power across numerous probable realities.
To bring it in to the parlance of computer science, if x is a number, and f(x) is a function of x which produces an output y, then a quntum computer can try out all possible values of x, in parallel universes, and then if you make the right observation and add up all the results from different universes in a certain way, you can figure out which value of x produces y.
In regular computer science, the kind I learned at MIT, all data is represented as numbers which consist of a series of bits. Each bit is either a zero or a one — either on or off. By collecting bits we can represent any number in binary (b1011 for example is four bits and represents the number 11. If you have x bits, you can represent up to 2 raised the power of x. In most computers, 32 bits or 64 bits are the standard for how numbers are stored
The thing that makes QCs different form regular computers is that in addition to regular bits, they are able to use qubits. Qubits are quantum bits which like a quantum particle, can have two different states. This means that while a regular bit must be a zero or a one, a qubit can be either a zero or a one. You don’t know until the quantum wave collapses based on some observation taken by the conscious mind.
If you have a certain number of bits, you can try out all the possible combinations by running through all the values of 0 and 1. For example, to try out all the numbers between 0 and 512, you need 9 bits . If you write a computer program to try each of the possible values of the 9 bits (0 and 1 for each bit), ranging from 0=b000000000 to 1 = b000000001 to 511 = b111111111.
How To use a QC for Bitcoin Mining
So this brings us to how I used the quantum computer to solve the bitcoin mining problem.
If you have 9 qubits, you can try out all the values from 1 to 511 simultaneously. If you had 64 bits, you could try out the hash algorithm for all possible values of x to figure out which ones when input into function f(x) lead to a result of y, or in the case of bitcoin mining, less than some target value y.
The bitcoin algorithm, relies on an input shown in Figure 1 (source: bitcoinmining.com), if you think of a potential new block of transactions, you have to generate a header. The header of a block consists of several components, including a nonce which is a random 32 bit number. See Table 2 for a list of the possible values.
The exact algorithm is described here: https://en.bitcoin.it/wiki/Block_hashing_algorithm. The result of the hash is a 256 bit integer.
Figure 2: Table of Inputs for Bitcoin Hash
Closer inspection will reveal that of all the bytes that are used as input, only 4 bytes, the nonce, or 32 bits are actually random. The other bytes are actually coming from a block of transactions and timestamp, etc. The output is a 256 bit number which has to be less than a target.
This is complicated, however by the fact that there may not be a solution for a given block of transactions, so you may be trying to find a nonce for a block of transactions which doesn’t have a solution!
A qubyte is 8 qubits. So basically, what I needed was to program my QC to use 4 qubytes, or 32 qubits, which represented all of the possible values of the random number, nonce, and append this value to a set of 76 regular bytes, and then run them through the hashing algorithm. Then I could take the output, which is a 256 bits, and choose one of the output values which is less than the target.
Programming the Quantum Computer Circuit
It’s not quite that simple. Today, with my quantum computer, I had to come up with an actual circuit to accomplish this. In the future, there will be much simpler ways to program quantum computers — I envision a simple programming language, let’s QBASIC for Quantum BASIC which would be like the BASIC language that I learned computer programming on with my Apple II back in the day. Though first I suppose an assembly language would need to be made out of the basic circuits that perform logical operations like AND, NAND, OR, XOR, etc., and then someone can write, as Bill Gates and Paul Allen did for the ALTAIR computer in 1977, write a higher level language like BASIC.
The beginnings of languages like this are out there — QASM, QCL, but each of these have different models and results in quantum circuits, at least for the moment.
The Quantum Computer I used didn’t have a good language, so I had to build the circuit myself. Figure 3 shows the basic circuit architecture for how I programmed my quantum computer, but simplified to 6 bits. It’s much simpler to see how this would all work with a smaller number of bits.
The first four bits are the “conventional bits” and the second two bits are the qubits, which are in a super-positioned state of zero or 1. In this case the 2 qubits represent the nonce, and the 4 regular bits represent the rest of the header block.
The implementation of the actual Hash Algorithm used by bitcoin (SHA-256) is left as an exercise to the reader. The idea in the bitcoin mining that the output of the hash has to be less than M, the hashing difficulty, which is adjusted in the bitcoin network every so often.
From a binary perspective, what this means is that the first x bits out of n ( in our case, n = 6 bits, in the bitcoin case, n=256 bits in the output) have to be zero for the result to bed less than the difficulty M. For each level of difficulty, the number of 0’s at the front of the hash output will need to change.
Figure 3: A simplified version of the Hash circuit
The hard thing about quantum circuits isn’t just actually designing the circuit/program, but also to find a way to measure the output in a way that will give you the “right” (or in some cases, the optimal) answer!
In a quantum computer, although all possible values of qubits are processed in all possible worlds, it’s difficult to get the output of a single case when you don’t know exactly which input value caused the output value you want.
When you observe the output bits, the quantum probability wave collapses and you see only one set of possible values. While quantum computers are able to have all of the possible values of the qubits simultaneously, we are still at the point of needing to loop through all of the possible output values to find the one that we want at random.
The real problem is how do you measure all of the possible values to get the one you want? It might seem we are still back to step one, as we’d have to loop through all possible solutions one by one.
Finding the Optimal Solution From All Possible Worlds
The key is to find some function f2(x1,x2,x3..xn) which sums up the values in all possible worlds. Using f2 as simple addition, if the values of x1… xn were all 0 for example, then you would observe the result as 0. If the values were all 1, then you would observe a value of n (x1+x2+x3).
The key is what’s called quantum shaking. A quantum shake is a way to generate a wave such that the output is adjusted in the quantum universe/probably reality where the right answer is present differently from how it’s adjusted in other universes where the right answer is not present. It’s called a quantum shake because it adjusts the value in one universe.
By doing this shaking a certain number of times, the input values of the nonce which resulted in outputs of less than target t, are isolated. We just take those 4 bytes, append them to the other 76 regular bytes that we put as input, and then submit the transaction to the blockchain.
Another way to represent this is to use Grover’s algorithm, a well known quantum computing algorithm that cuts down the time needed to find one out of many possible solutions, as shown in Figure 4. In a simple example of Grover’s algorithm, you might have four qubits as an input, which would result in 2 to the 4th power, or 16 possible values.
Figure 4: Using Grover’s Algorithm to Find the Optimal Solution
Grover’s algorithm reduces this to the square root of N. So, for 16 possible values of the qubits you’d have to go through 2 to the power of 16, or 65,536 possible output values. The square root of this is 256, a significant difference.
Pulling it all together
The output of bitcoin mining hash algorithm produces 256 bit output (that’s why it’s called SHA-256) which is a very large number.
While I won’t go through the bitcoin mining in detail, the final solution involved a bit of regular computing (assembling transactions into a block, calculating the merkle root of the proposed block, getting the previous block), the quantum computer was useful for the “hard part”, which is to find the nonce, if one exists, that will produce an output less than the difficulty.
Using a combination of circuits for the hashing of the bits, followed by Grover’s algorithm or quantum shaking to reduce the search time of the solution, I was able to mine blocks by searching 256 values — easy!
As I said earlier, since each mined block has a reward 12.5 bitcoins per block, you can figure out that it’s going to make me pretty wealthy pretty quickly!
OK, Did I Really Do This?
Those readers who are familiar with both hashing algorithms and the state of Quantum Computers today will realize that I didn’t really do this today (I wrote the first part of this post in 2016, and now that bitcoin is back in the news, I finished it in 2017).
For one thing, you can just look at who’s mining the blocks and you’ll see that they are being mined by mining pools. For another thing, the bitcoin mining algorithm uses the SHA256 algorithm, which can take up to a very large number of input bits but always outputs 256 bits. For all quantum computers today, the number of bits input and the output need to be the same. Astute observers will notice that the bitcoin algorithm actually requires running SHA-256 twice, so you could theoretically do what I proposed for the second SHA-256 if you could design a quantum circuit to implement it.
Also, although there are now languages to help generate the underlying circuits, they have to be fed to the quantum computer. The languages are becoming better and though some are simulating the quantum computer on conventional hardware, the whole area of quantum computing is still very much in flux, moving quickly.
So, the truth is that the full extent of what I “did” is not possible. At least not yet.
Although there are algorithms that can be used by quantum computers to break public/private key cryptography (Shor’s algorithm for factoring for example), the computers themselves are not yet practical. However, if and when they do become practical, today’s standard cryptography needs to be updated and new algorithms need to be invented.
Another problem today with QC’s is that errors can creep up due o the physical processes which are used to superpose individual bits. While not many people know this, the reason there are two values of a bit on a computer today and not 3 is simply that a “zero” is represented by a certain range of volts and a “one” is represented by another range of volts. These ranges are far enough apart that there is very little error.
Qubits are much more complicated and the physical implementation varies with each type of QC. When dealing with Quantum Computers, the chances of a physical measurement error corrupting your results are much higher than in a normal computer. In fact, you need to run the algorithm many times to be sure that there wasn’t a physical error.
This article was meant to be a (theoretical) discussion that would introduce both concepts — bitcoin mining and quantum computers — for those who hadn’t been exposed to them at the level of a computer programmer. Experts in both areas will no doubt find some errors or omissions or additional reasons why this is not possible today (at least not yet!).
Feel free to leave comments on how/when/if you think this will ever be possible.