Cryptocurrency And Quantum Computing
by John G. Cramer
In 2017 the cryptocurrency Bitcoin repeatedly made headlines by starting the year valued at about $1,000 per unit, climbing to over $19,000 in December, and then precipitously dropping below $8,000, where it has since remained. In the interest of full disclosure, I should say that last year I invested about $11,000 in three cryptocurrencies. At this writing in mid-March, my investment, which had been up in value by more than a factor of two, has declined and is now barely breaking even.
Also in 2017, IBM announced the initial operation of a 20-qubit quantum computer that they made available online, and Google did them 29 times better by announcing the development of a 49-qubit quantum computer to go into operation by the end of the year. Microsoft, which is developing a decoherence-resistant version of quantum computing based on the topology of two-dimensional systems, released a new coding language for quantum computing. Things moved fast in 2017.
Superficially, these two things are unrelated developments, but they were tied together by an October-2017 preprint by D. Aggarwal and coauthors based in Singapore and Australia. The group outlined in some detail the expected impact of quantum computing on cryptocurrencies like Bitcoin, and the impacts seem to be more negative than positive.
* * *
Let me begin this discussion by reviewing just what cryptocurrencies are and what quantum computing is. Normal currencies like the U.S. dollar, the U.K. pound, and the E.U. euro, either in the forms of printed bills or of bank balances, have a value (a) because they are issued and backed by trusted governments that exert some control over their value and stability, (b) because they can be stored in banks that keep reliable legers of financial transactions to prevent the spending of the same on-deposit currency twice, and (c) because regulated exchanges allow individuals to buy and sell currencies and to speculate on their increase or decline in value, contributing to their stability. The banks and exchanges normally extract a fee for each transaction that is sometimes small and sometimes substantial, introducing a kind of “friction” to the system. Further, there is normally a significant time delay, possibly of days, before a given transaction is completed. There are also the concerns in some quarters that governments can manipulate the value of their currencies for political reasons and can interfere with and snoop on transactions.
Cryptocurrencies serve essentially the same purpose, but without the involvement of governments and banks and with less friction. They are initially issued by their creators, and subsequently new cryptocurrency is created by “mining,” an operation that uses high-speed computers to competitively process transaction data in the form of blockchain blocks (see below). In the beginning, the mining computers were just ordinary laptops, desktops, and workstations, but the operation has evolved into “crypto-farms” with thousands of dedicated specialized processors located in cooled warehouses in locations where electrical energy is cheap. Many crypto-mining farms are located in China and South Korea, but old mining towns in Montana are also experiencing a new crypto-mining boom because of the cheap real estate and low power costs.
Cryptocurrencies are stored in individual digital “wallets” kept by the owners on their computers and devices and accessed by a unique digital key. (Don’t lose yours!) The transaction records reside in a publically available block of data shared over the internet by hundreds of thousands of the mining computers. Transaction fees are small, and transaction speeds are fast. All this is possible because of the digital encryption that verifies ownership while protecting peer-to-peer transactions from scrutiny and tampering.
To be more specific, each transaction is represented as an entry in a “block,” and each block is an element or link in the blockchain. Each transaction entry uniquely identifies the crypto-coin owner using a form of reverse cryptography and specifies the amounts to be withdrawn from one digital wallet and deposited into two other wallets. These transactions are entered until a block is full, at which point a cryptographic hash code is added that connects it to the previous block of the chain, and it is published on the Internet. Many mining computers then compete to process the new block’s transactions and to repetitively compute the smallest possible “nonce,” a fixed-length hash-code based on the digital structure of the block. For a nonce to win the mining competition, its value must be less than a previously established value. The mining processor that produces the smallest nonce the fastest is awarded a fee paid in the newly minted cybercurrency, and all the mining computers of the system then move on to competitively process the next block in the blockchain. In this way, the public digital ledger is updated, cryptocurrencies are transferred, newly minted cryptocurrency enters the system, and all is well.
* * *
A quantum computer is a device first suggested in 1978 by Richard Feynman that uses the manipulation of quantum states to process information and to solve problems. Feynman himself was particularly interested in applying such a device to problems involving quantum mechanics itself, but later enthusiasts seem to be more focused on database searches and cryptography. A quantum computer is a completely new kind of data-processing device that is today emerging from the academic and industrial laboratories of the planet, ready or not, and finding its initial applications in the real world.
A conventional computer has a memory in which bits of information are stored in definite binary states of 1 or 0 and has a processor that operates on this stored information. For example, the memory may contain two numbers stored in binary representation and a program specifying the locations of these numbers and calling for them to be multiplied together and the result stored in another location. With the execution of the program by the processor, the numbers are fetched, multiplied, and their product in binary representation stored in the memory.
A quantum computer differs from this computing scheme in one important way: the definite-state memory units, the 0-or-1 bits in the conventional computer, are replaced by indefinite-state qubits (short for quantum bits). The qubits are possible states in a quantum system and may be indefinite until they are “collapsed” to a 1 or 0.
Of course, a quantum computer needs more than just qubits for its operation. The qubits must be well enough insulated from the random scrambling effects of environmental noise (called decoherence) that the coherent state of the quantum system is preserved for at least long enough to set up a calculation, perform it, and read out the results. Because of this decoherence problem, a major part of quantum computer architecture involves correcting the errors that inevitably arise from decoherence.
A quantum computer must have the ability to initialize any qubit in a specified state and to measure the state of any specific qubit. It must have “universal quantum gates”—logical elements capable of arranging any desired logical relationship between the states of qubits. It must also have a processor capable of interlinking such quantum gates to establish rules and boundary conditions for their inter-relationships. In a quantum computation, the arrangement of quantum gates is set by the programmer to connect the qubits in a logical pattern, according to a program or algorithm. After an interval, the qubits assigned to the final result are read out. If this is done properly, the quantum computer can be made to perform calculations in a way that is qualitatively different from calculations performed on a conventional computer. In fact, computations easily performed with a quantum computer in some cases would require a computation time with a conventional computer greater than the age of the Universe.
It is relatively easy to visualize the operation of a quantum computer by using the transactional interpretation of quantum mechanics (see The Quantum Handshake below). The programming of the quantum computer that sets up the problem has created a set of conditions such that the quantum mechanical wave function can only form a final transaction and collapse to a definite state by solving the problem (for example, by finding the prime factors of an input number).
The advanced and retarded waves emanating from the initial qubits, describing all the possible qubit states of the system, propagate through the computer, seeking the ultimate multi-vertex quantum handshake that solves the problem and permits a transaction to form. This process converges very rapidly because the propagation duration of the advanced waves requires a negative time. The net result is that the solution transaction forms, the wave function collapses into the solution state, the problem is solved, and the results are read out. In particular, quantum computers can be used to rapidly determine the two numerical factors that, when multiplied together, form the large product that is the problem’s input. This capability can be used to break most codes in contemporary cryptography.
* * *
This brings us to the question of how the quantum computers now becoming available can be expected to impact cryptocurrencies. The impacts are expected to lie in two areas: (1) Cracking: i.e., breaking the cryptographic encoding within the blockchain to identify cryptocurrency owners and discover the keys to their digital wallets, and (2) Mining: i.e., out-competing existing cryptocurrency miners to win every race with the smallest nonce and to corrupt transactions by marshaling more computing power than all the rest of the blockchain system combined.
For the Cracking problem, Aggarwal, et al, estimate that by the year 2027 the current blockchain signature scheme can be broken by a quantum computer in less than ten minutes. This should be of great concern to the cryptocurrency community.
On the other hand, for the Mining problem they predict, projecting out as far as the year 2042, that quantum computing may perform very profitable blockchain mining operations using what is called the Grover algorithm but will not be able to overwhelm the standard hardware system and corrupt it. This is in part because the specialized ASIC systems developed specifically to mine quantum currency are extremely fast and cannot be easily overwhelmed in the near future.
There may be alternative signature algorithms on the horizon that will make it more difficult for quantum computers to impact the Cracking problem. However, Aggarwal, et al, analyze eleven of these schemes and conclude that they would not be of much help in protecting against a quantum attack.
Of course, it is very early in this hypothetical battle between quantum computers and cryptocurrencies. So far in this war not a single shot has been fired. Moreover, new developments not considered in the Aggarwal analysis are possible in both areas that could radically change everything. We live in interesting times.
* * *
John G. Cramer’s 2016 nonfiction book describing his transactional interpretation of quantum mechanics, The Quantum Handshake—Entanglement, Nonlocality, and Transactions, (Springer, January 2016) is available online as a hardcover or eBook at: http://www.springer.com/gp/book/9783319246406.
SF Novels by John Cramer: eBook editions of hard SF novels Twistor and Einstein’s Bridge are available from the Book View Café co-op at: http://bookviewcafe.com/bookstore/?s=Cramer.
Alternate View Columns Online: Electronic reprints of over 180 “The Alternate View” columns by John G. Cramer, previously published in Analog, are available online at: http://www.npl.washington.edu/av.
* * *
Quantum Computing and Bitcoin: “Quantum attacks on Bitcoin, and how to protect against them,” Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel, (October 2017); arXiv:1710.10377 [quant-ph].
Copyright © 2018 John G. Cramer