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.

Surveying NDAA Provisions And Domestic Terrorism In America

Obama had signed into law the NDAA, which is controversial for granting broad powers to the executive branch of the U.S. government to combat what it perceives to be terrorist activities, both foreign and domestic. The concerned section of the bill, entitled "Counterterrorism", is as follows:

Subtitle D—Counterterrorism

Sec. 1021. Affirmation of authority of the Armed Forces of the United States to de-

tain covered persons pursuant to the Authorization for Use of Military

Force.

Sec. 1022. Military custody for foreign al-Qaeda terrorists.

Sec. 1023. Procedures for periodic detention review of individuals detained at

United States Naval Station, Guantanamo Bay, Cuba.

Sec. 1024. Procedures for status determinations.

Sec. 1025. Requirement for national security protocols governing detainee commu-

nications.

Sec. 1026. Prohibition on use of funds to construct or modify facilities in the United

States to house detainees transferred from United States Naval Station,

Guantanamo Bay, Cuba.

Sec. 1027. Prohibition on the use of funds for the transfer or release of individuals

detained at United States Naval Station, Guantanamo Bay, Cuba.

Sec. 1028. Requirements for certifications relating to the transfer of detainees at

United States Naval Station, Guantanamo Bay, Cuba, to foreign coun-

tries and other foreign entities.

Sec. 1029. Requirement for consultation regarding prosecution of terrorists.

Sec. 1030. Clarification of right to plead guilty in trial of capital offense by military

commission.

Sec. 1031. Counterterrorism operational briefing requirement.

Sec. 1032. National security planning guidance to deny safe havens to al-Qaeda

and its violent extremist affiliates.

Sec. 1033. Extension of authority to make rewards for combating terrorism.

Sec. 1034. Amendments relating to the Military Commissions Act of 2009. 

While I'm personally a pacifist, and strongly disapprove of all military intervention, regardless of perceived merits, the majority of Americans are complacent with the military activities abroad these 

past 10 years, with the last two presidents (Bush and Obama) enjoying two terms in office despite the military campaigns conducted under their respective administrations.

However, domestic terrorism intervention (which treats all of the American people as potential 

terrorists) is a notion that directly impacts Americans' safety, civil rights, and well being, so it's no wonder that the NDAA has become under fire by the ACLU, and cities and states have been 

passing laws left and right banning its enforcement.

According to the Obama administration, the NDAA does not give Obama any greater powers to combat terrorism, foreign or domestic, than were already granted under the AUFF. However, the text provides no broad provisions for the combating of domestic terrorism, authorizing the use of military force only for those who conducted or who were involved with the 9/11 terrorist attacks.  

The NDAA provisions are far broader, extending the scope of executive powers to permit military intervention for any kind of terrorism, foreign or domestic, and includes special provisions concerning activities which are criminal but previously not considered terrorism:

Subtitle B—Counter-Drug Activities

Sec. 1004. Extension of authority for joint task forces to provide support to law en-

forcement agencies conducting counter-terrorism activities.

Sec. 1005. Three-year extension and modification of authority of Department of De-

fense to provide additional support for counterdrug activities of other

governmental agencies.

Sec. 1006. Two-year extension and expansion of authority to provide additional

support for counter-drug activities of certain foreign governments.

Sec. 1007. Extension of authority to support unified counter-drug and counterter-

rorism campaign in Colombia.

Sec. 1008. Reporting requirement on expenditures to support foreign counter-drug

activities.

As you can see, while Subtitle B Sections 1004-2008 don't explicitely define drug trafficking as "terrorism", the powers it grants are equivalent to, and implicitly justified in the name of counter-terrorism. These provisions also make it clear that even those not affiliated with terrorist organizations can be legally attacked by U.S. military forces, and / or detained without trial, if the President determines them to be terrorist. 

What is the definition of a "terrorist", according to the NDAA? Apparently there isn't an official one (scary, right?), but there is an official definition of "terrorist activity", "international/domestic terrorism", "terrorism", "terrorist group", and "terrorist sanctuary". I would paste the full definitions, but they're all far too long. But I can make the point needed with just the first definition:

*Note: "WCS" is an acronym for "Worst Cast Scenario" for this section

"Terrorist Activity":  "any activity which is unlawful under the laws of the place where it is committed...which involves any of the following: 

(I) The highjacking or sabotage of any conveyance (including an aircraft, vessel, or vehicle). 

WCS Stealing a car or boat is considered terrorism

 (II) The seizing or detaining, and threatening to kill, injure, or continue to detain, another individual in order to compel a third person (including a governmental organization) to do or abstain from doing any act as an explicit or implicit condition for the release of the individual seized or detained. 

WCS: Kidnapping, blackmailing, or hostage-holding are all terrorist activities

(III) A violent attack upon an internationally protected person (as defined in section 1116(b)(4) of title 18) or upon the liberty of such a person.

WCS: anyone who attacks an oppressive authority that is internationally protected (for whatever reason) is a terrorist. 

(IV) An assassination. 

WCS: all hitmen are terrorists.

(V) The use of any - (a) biological agent, chemical agent, or nuclear weapon or device, or (b) explosive, firearm, or other weapon or dangerous device (other than for mere personal monetary gain), with intent to endanger, directly or indirectly, the safety of one or more individuals or to cause substantial damage to property. 

WCS:  (a)  If you have the flu and knowingly associate with people, you're a terrorist

(b) if you user a tazer to defend against a mugger, you've committed a terrorist act

(VI) A threat, attempt, or conspiracy to do any of the foregoing."

 WCS: even if you had no intention of doing any of the above, if you so much as verbally or vocally entertained the possibility, you're considered a terrorist.

 ---

 Of course, these are all worst-case scenarios, and are only likely scenarios to the chronically paranoid, but it still is a major concern that the federal government, if it so willed, could use such open-ended interpretations to legally justify the military force provisions of the NDAA. Even if Obama pledged not to abuse those provisions, A politician's promise is of no comfort when he has the legal right to disregard it. Such concerns are why even the ACLU, a group unaffiliated with conspiracy theorism or tinfoil hats, is deeply concerned about the legality of the NDAA. Even if only in theory, the special provisions of HR.1540 and HR.4310 (which did nothing to change the provisions, merely reiterating the right to habeas corpus already part of Article 1, Section 9 of the Constitution) make every American citizen a potential target. 

Regarding the NDAA, we must conclude that although the claims regarding executive abuse of NDAA powers are greatly exaggerated, there is quite a bit of truth to them, and the threat of such abuse, while far from material at this point, is most  certainly present.