Can Scalable Quantum Computers Break Bitcoin?

There's been a lot of concerns about whether the advent of quantum computers (which specialize in solving extremely difficult mathematical problems) could break Bitcoin, a cryptocurrency in which computers mine coins by solving increasingly difficult blocks of data. In this article we address these concerns, determine the potential damage it would cause to the Bitcoin network, and address the feasibility of a computer capable of cornering the Bitcoin network.

So first of all, if scalable quantum computers were successfully created, what is the worst potential impact it could have on the Bitcoin network?


1. Bitcoin's ECDSA algorithm would be broken. Because quantum computers can easily decrypt the private key using the public key, anyone with a quantum computer can extract Bitcoins using the corresponding public key.

2. Bitcoin hashing would become exponentially difficult. There's already a predicted escalation in mining difficulty due to the advent of ASIC, and quantum computers would create a spike in mining difficulty to which ASIC mining effects pale in comparison. In the short run, this would lead to hyperinflation, but the long run effects aren't known at this point.

3. The hashing advantage of quantum computer will be curtailed by block mining limitations. To quote from the Bitcoin wiki:

"The difficulty is the measure of how difficult it is to find a new block compared to the easiest it can ever be. It is recalculated every 2016 blocks to a value such that the previous 2016 blocks would have been generated in exactly two weeks had everyone been mining at this difficulty. This will yield, on average, one block every ten minutes. As more miners join, the rate of block creation will go up. As the rate of block generation goes up, the difficulty rises to compensate which will push the rate of block creation back down."

This means that the rate of block creation will not be impacted by quantum computers (the increase in key generation is proportional to the increase in difficulty, resulting in an overall mining rate of 1 Bitcoin every 10 minutes), but it will drastically increase the mining difficulty, exponentially more than ASIC miner already have. This gives miners with quantum computers (presumably corporations, government agencies, or other power organizations) a major advantage, to the point of being considered a monopoly, on the bitcoin market.

Unless quantum computers either:

(a) become publicly available
(b) are given their own class for hashing purposes, so as to limit their mining advantage

Then miners with access to quantum computers have an unfair mining advantage, which can (and will be) used to manipulate the value and distribution of bitcoins. Furthermore,

4. Quantum computer's hashing power can be used as voting power. If a coalition of people with scalable quantum computers could generate enough hashes to comprise over 51% of the total Bitcoin hashes,they could use that power to greatly manipulate the bitcoin network.

As explained in the Bitcoin wiki ("Weaknesses")

"An attacker that controls more than 50% of the network's computing power can, for the time that he is in control, exclude and modify the ordering of transactions. This allows him to:

    Reverse transactions that he sends while he's in control. This has the potential to double-spend transactions that previously had already been seen in the block chain.
    Prevent some or all transactions from gaining any confirmations
    Prevent some or all other miners from mining any valid blocks

The attacker can't:

    Reverse other people's transactions
    Prevent transactions from being sent at all (they'll show as 0/unconfirmed)
    Change the number of coins generated per block
    Create coins out of thin air
    Send coins that never belonged to him

With less than 50%, the same kind of attacks are possible, but with less than 100% rate of success. For example, someone with only 40% of the network computing power can overcome a 6-deep confirmed transaction with a 50% success rate.

It's much more difficult to change historical blocks, and it becomes exponentially more difficult the further back you go. As above, changing historical blocks only allows you to exclude and change the ordering of transactions. It's impossible to change blocks created before the last checkpoint."
----

However:

"Since this attack doesn't permit all that much power over the network, it is expected that no one will attempt it. A profit-seeking person will always gain more by just following the rules, and even someone trying to destroy the system will probably find other attacks more attractive. However, if this attack is successfully executed, it will be difficult or impossible to "untangle" the mess created -- any changes the attacker makes might become permanent."

----

All this being said, is it possible for a scalable quantum computer (specially, one that is programmed (like ASIC) to hash blocks) to have an exponential advantage over traditional computers, FPGAs, ASICS, etc.?

That question is better addressed here. There's a lot of mathematics involved, which is a bit above my academic proficiency, but we can derive at least this much:

Most of the algorithms quantum computers are famous for efficiently utilizing (Shor's algorithm, Grover's search algorithm) probably can't be used for hashing Bitcoin blocks. One possible exception noted is the collision attack, which if done using Grover's algorithm, could *possibly* perform better attacks than conventional computers:

"Can quantum-computers perform better collision attacks? Actually I'm not sure about it. Grover's algorithm can be extended, such that if there are t items (that is, preimages), the time to find one is reduced to O(N/t−−−−√). But this gives no collision - running the algorithm again might return the same preimage. On the other hand, if we choose m1 at random, and then use Grover's Algorithm, it is probable that it will return a different message. I'm not sure if this gives better attacks."

In the event that scalable quantum computers manage to corner the Bitcoin network, new code will be released to patch this vulnerability, so while there would be a long-term breakage of the network in the short term, there's nothing to worry about for Bitcoin users in the long term.

Bitcoin: Investment or Liability?

Bitcoin has been hailed by conservatives and progressives alike as a wonderful alternative to fiat currency and the central banking system. Some media journalists have even gone so far as to call Bitcoin "Gold 2.0", the new gold standard made possible thanks to advances in computing and information technology. Indeed, the recent deflation of BTC (Bitcoin currency) has been something of a gold rush (metaphorically speaking), with the potential appreciation of this digital currency seeming to be limitless.

However, despite this, the financial elite aren't capitalizing on Bitcoin. One would think that, for the profit-driven banking elite, they'd be investing in Bitcoin more, if only to diversify their holdings. But they're not, and here are some reasons cited: 

1. Better virtual currencies will replace it: Ian Bremmer, the founder/CEO of the world's largest risk consulting firm (Eurasia Group), thinks Bitcoin is too flawed to be a strong contender, and its popularity will lead to its downfall, by providing the momentum for superior currencies to supersede it.

    2.  Bitcoin resembles a Ponzi Scheme: This argument is surprisingly pervasive, considering how rationally unsound it is: While it's true that Bitcoin mining becomes progressively harder with each new block, and the more Bitcoins are hoarded, the greater the value of each Bitcoin becomes, this argument is rather fallacious for several reasons:

     a. Bitcoin meets none of the the criteria of a Ponzi Scheme. Joshua Goldblum wrote an excellent piece on this.

     b. The price is Bitcoin is driven by the laws of supply and demand; mining Bitcoins increases amount of coins in circulation, resulting in a net inflationary cost. While early adopters do have an incentive to hoard to keep the price up, they do not have any greater ability to hoard than anyone else. This means that while initially they have an unfair mining advantage, this benefit is fair in that it is proportionate to the risk of investment in a developing currency. There's still a lot of debate regarding this, but suffice to say, The advantage of early adopters isn't unreasonable.

     c. Any "advantages" early adopters may have had have been counterbalanced by advances in technology and computing efficiency, particularly regarding Bitcoin-specific optimizations. In his article A Guide to Bitcoin Mining: Why Someone Bought a $1,500 Bitcoin Miner on eBay for $20,600, Alec Liu summarizes the history of Bitcoin mining as such:

"Back in 2009, when Satoshi Nakamoto first birthed bitcoin, mining difficulty was relatively low, which meant that anyone could download the software and more or less start mining with only their CPU.

The next logical step was the GPU, dedicated graphics chips usually reserved for gaming. A graphics card from the likes of Nvidia or ATI offered a significant boost over Intel and AMD CPUs. For about $150, you could buy an off-the-shelf graphics card and start a fairly profitable mining business.  

As more miners joined the party, difficulty increased, making the profit to power consumption ratio unpalatable for those used to a higher rate of return. Bitcoin's price collapse in July of 2011 only exacerbated the situation. Even if you believed in the future of bitcoin, if you spent more on your electric bill than you made from mining, you were better off just buying bitcoins. 

This initiated the advent of FPGA, or field-programmable gate array, use in mining. That's a mouthful for the technical layman, but all you really need to know is that these add-on cards, which cost in the hundreds of dollars, offered comparable mining performance to GPUs while using way less power. Better energy efficiency meant higher profit margins. Eventually, any self-respecting miner was FPGA-equipped. 

The endgame, however, was always going to be the ASIC, an application-specific integrated circuit–in other words, a chip designed from the ground up for the specific purpose of mining bitcoins. The result is a system that is not only incredibly powerful compared to anything else, it’s also exceedingly energy efficient."

As you can see, the progression of improvements to Bitcoin mining techniques has ensured that Bitcoin mining difficulty maintains remarkably fair, with subsequent improvements in mining efficiency eliminating virtually all of the original mining advantages enjoyed.

(d) The most compelling reason why Bitcoin mining is neither unfair nor a Ponzi scheme, is the advent of renewable energy sources. As technology for renewable energy continues to improve, the cost of mining Bitcoins (other than initial hardware) will become effectively nill, which in the long-run removes the vast majority of early adopter mining advantages from the system. Bitcoin's existence actually encourages investment in clean and renewable energy sources.

     3.  Tea Party founder and financial blogger Karl Denninger wrote a well-thought out piece on the legal problems and limitations of Bitcoin. Here are some particularly important points he made:

"Bitcoin and other digital currencies are different [from dollar bills, which are self-validated] -- they're just a string of bits. To validate a coin, therefore, I must know that the one you are presenting to me is unique, that it wasn't just made up by you at random but in fact is a valid coin (you were either transferred it and the chain is intact or you personally "mined" it, a computationally-expensive thing to do), and has not been spent by you somewhere else first.

In order to do this the system that implements the currency must maintain and expose a full and complete record of each and every transfer from the origin of that particular coin forward! This is the only way I can know that nobody else was presented the same token before I was, and that the last transfer made of that token was to you. I must know with certainty that both of these conditions are true, and then to be able to spend that coin I must make the fact that I hold it and you transferred it to me known to everyone as well.

Due to the indelible nature of the records you're exposed for much longer that with traditional currencies to the risk of a bust and in many cases you might be exposed for the rest of your life. In particular if there is a tax evasion issue that arises you're in big trouble because there is no statute of limitations on willful non-reporting of taxes in the United States, along with many other jurisdictions. Since the records never go away your exposure, once you engage in a transaction that leads to liability, is permanent.

Because Bitcoin is not state-linked and thus fluctuates in value there is an FX tax issue. Let's say you "buy" Bitcoins (whether for cash or in exchange for a good or service you provide) at a time when they have a "value" of $5 each against the US dollar. You spend them when they have a "value" of $20 each. You have a capital gain of $15. At the time of the sale you have a tax liability too, and I'm willing to bet you didn't keep track of it or report it. That liability never goes away as it was willfully evaded and yet the ability to track the transaction never goes away either!

Cryptocurrencies have a secondary problem in that because they are not self-validating there is a time delay between your proposed transaction using a given token and when you can know that the token is valid. Bitcoin typically takes a few minutes (about 10) to gain reasonable certainty that a given token is good, but quite a bit longer (an hour or so) to know with reasonable certainty that it is good. That is, it is computationally reasonable to believe after 10 minutes or so that the chain integrity you are relying on is good. It approaches computational impracticality after about an hour that the chain is invalid.

The other problem that a cryptocurrency has is that it possesses entropy. Entropy is simply the tendency toward disorder (that is, loss of value.) A car, left out in the open, exhibits this as it rusts away. Gold has very low entropy, in that it is almost-impossible to actually destroy it. It does not oxidize or react with most other elements and as such virtually all of the gold ever dug out of the ground still exists as actual gold. Fiat currencies, of course, have entropy in both directions because they can be emitted and withdrawn at will. We'll get to that in a minute, and it's quite important to understand.

Bitcoin exhibits irreversible entropy. A coin that is "lost", that is, which the current possessor loses control over either by physically losing their wallet or the key to it, can never be recovered. That cryptographic sequence is effectively and permanently abandoned since there is no way for the entity who currently has possession of it to pass it on to someone else. This is often touted as a feature in that it inevitably is deflationary, but whether that's good or bad remains to be seen. It certainly is something that those who tout the currency think is good for the value of what they hold, but the irreversible loss of value can also easily lead people to abandon the use of the currency in which case its utility value to express goods and service preference is damaged, quite-possibly to the point of revulsion.

Bitcoins are basically cryptographic 'solutions'. The design is such that when the system was initialized it was reasonably easy to compute a new solution, and thus "mine" a coin. As each coin is "mined" the next solution becomes more difficult. The scale of difficulty was set up in such a fashion that it is computationally unfeasible using known technology and that expected to be able to be developed in the foreseeable future to reach the maximum number of coins that can be in circulation."

There are also quite a few compelling reasons to invest in Bitcoin, which has gotten a few major investors interested. Paypal's president David Marcus believes that digital currencies, the most popular of which is Bitcoin, are the future of money, and it won't be long before "wallets are on their way out". Paypal founder and billionaire Peter Thiel believes Bitcoin will make Paypal's dream of becoming the universal standard for secured online transactions possible, To this end, he has invested (via the same Founders Fund that provided Facebook's initial outside investment) $2 million into Bitpay, an online payment system which promises to be the Paypal of Bitcoin.

The most interesting characteristic of Bitcoin, which is considered to be a feature by libertarians and gold standard advocates, but a bug for many economic theorists (particularly those of the Keynesian school), is its scarcity. Because there is a limited supply of Bitcoins (no more than 21 million), and a theoretically infinite potential demand for them, the potential deflation of Bitcoin is boundless.

As Felix Salmon notes, not only does Bitcoin's deflationary nature give people a strong incentive to hoard, but can be considered market hostile, as with deflationary currencies,  "people hoard their cash, and spend it only begrudgingly, on absolute necessities. And they certainly don’t spend it on hiring people — no matter how productive their employees might be, they’d still be better off just holding on to that money and not paying anybody anything.The result is an economy which would simply grind to a halt, with massive unemployment and almost no economic activity. In a word, it would be a Depression. In order to have economic growth, you need monetary growth as well — and that’s something which is impossible to achieve in a bitcoin-based system"

Felix's argument, while it perhaps holds strong if the people using it are ignorant of Bitcoin's flexibility of value, is mostly invalid, as product vendors can alter the value of products to match the value of the Bitcoin, and Bitcoins can be divided up to 8 decimal places to ensure all purchases are done with exactly the amount of currency agreed on by both vendors and consumers.

To give you an idea of how much 8 decimal places are, I will compare the "satoshi" (the smallest unit of Bitcoin currency) to the penny (the smallest unit of the USD currency): At current market rates, a Satoshi would be worth 0.00000001 BTC or 0.000129 pennies. This means that even if a single Bitcoin were worth $1,000,000, a satoshi would be worth the same value as a USD penny. Furthermore, the Bitcoin FAQ page notes that "If necessary, the protocol and related software can be modified to handle even smaller amounts."

Because Bitcoin is software-based, it can be modified to account for any bugs or limitations. So most arguments regarding Bitcoin's "flaws" (perceived or legitimate) can be resolved through something as simple and straightforward as the modification of code. The versatility of Bitcoin's structure and implementation give it a major edge over other currencies. 

I would highly recommend that everyone wishing to understand Bitcoin (and to not be fooled by FUD-filled myths propagated by the media) check out the Bitcoin FAQ. It's almost certainly biased (as it's written by Bitcoin proponents), but it's also rich with the information you need to develop a more balanced opinion of Bitcoin, much of which is difficult to come by elsewhere. If you've gotten this far in the article, you should be able to tell the difference between hype and legitimate information. 

When all is said and done, There's still a lot of potential for Bitcoin, and it's far too early to tell whether the currency will stabilize as its supporters promise, or continue to destabilize as its critics contend. It may be the currency of the future, and at least for the time being, it's a lucrative and relatively accessible currency to mine, speculate on, and even trade for various goods, both legal and illicit. Furthermore (and on a more hopeful note)-- like all currencies, fiat or otherwise-- Bitcoin's worth and usefulness is ultimately dependent on trust and collective perceptions of value. So regardless of its intrinsic merits and shortcomings, The success or failure of Bitcoin, just like any other currency, is determined by our own faith in it, or the lack thereof.