Bitcoin and Quantum Computing

Even if a quantum computer existed — they do not — Bitcoin would be fine.

Quantum computers are hypothetical machines that are based on several postulates from quantum mechanics in physics. If such hypotheses from Deutsch (1985) and others prove to be true, then it is possible that quantum computers could outpace classical calculation on an electro-mechanical computer. Much of the existing hype stems from Shor’s finding (Shor, 1999) of a polynomial quantum algorithm that allows for the factorisation of selected classes of numbers and algorithms (especially those associated with cryptographic processes).

As with all undeveloped but potentially promising technologies, the scientists creating them oversell the near-term capability. And so is to be expected. Without funding, they would never come to exist. The result is that there are many purely theoretical attacks right now that are using quantum computation as an excuse to move people into new and untested areas. One such area of attack has been in cryptocurrency and Bitcoin where many false rumours have been spread [1]. Some of the reporting (intentionally) obscures the forms of calculation needed to break a system [2], confounding the reader into a false belief that the end is nigh.

The reality is that the arguments are spurious at best; at worst, they are intentionally designed to deceive. In a paper, we demonstrate the flaws in such arguments, and show that systems (such as Bitcoin) are safe for at least the next few decades and maybe all time from such an attack.

[1] https://www.cryptocoinsnews.com/quantum-computers-will-destroy-bitcoin-scientists-warn/
[2] https://www.cryptocoinsnews.com/nsa-working-encryption-cracking-quantum-computer/
Image result for quantum computing
Bitcoin is quantum resistant

Economically, it thus merely becomes viable to attack well-known and reused Bitcoin addresses that have exposed public keys and which hold large amounts of value for periods longer than 30 days. Even at the face value, we can demonstrate that it is not of concern. A large organisation that has a fixed address for receiving payments and ones that are derived from it is still not vulnerable. Any payments being received can first be moved between addresses from the receiving address to an alternate address owned by the corporation or another group within minutes of receipt. Further, an attack on a Bitcoin address requires an attack on all the keys associated with the address. Using multi-signature addresses, an organisation could create a 15-of-15 key. Even allowing for the hypothetical scenario where an exposed private key could be reverse-engineered in under 30 days, we come to the creation of a multiple-key address that would take 18 months to compromise.

privacy can still be maintained by breaking the flow of information in another place: by keeping public keys anonymous

The simple answer is to not reuse Bitcoin addresses.

If it was ever an issue, the simple addition of an indexed hash to a Bitcoin script completely mitigates all of the theoretical quantum attacks.

An example quantum-killer script.

In the script above, we have added a hash puzzle to a key we use merely once. I would like to see others think; so rather than detailing the possible scripts, I shall leave suggestions that others could create.

Additive hashes…

Option 1: We can modify the signature, the (R,S) value saved on the blockchain, using the hash and other values. The script allows you to add values.

The value <sig> that represents the signature can itself be modified in script. ECDSA plus a hash is immune even in theory to such so-called quantum-computer attacks (that do not exist). A developer can create a script template that takes the signature, duplicates it, and checks against a hashing OP_CODE.

E.g. [Hash256(<Sig> +<pubKey>+<Data_Hash(i)>)] Mod (N)
==< Redeem Value>

In doing so, the following are known:

  • <Sig>,
  • (N),
  • <Data_Hash(i)>, which must solve to the hash puzzle.
<Redeem Value> is thus only able to be computed by the holder of the <pubKey> value, and this only becomes known.

Next, we can create conditional branches that are based on such options. Now, if we look at how we can link ECDSA keys homomorphically and create additive structures from them, we start to see that we can create a 1-of-2 signature script where one key is used in the un-signing and the other in the hash puzzle.

Public-key variants

The hash puzzle can have a variant of the key in a hash puzzle. For example, we seek to use the value <pubKey>. Let us say that <pubKey(1)> is needed, and so is a solution to the problem:

<pubKey(1)> = <pubKey(0)> + Hash(Hash(S)).G + Hash(Hash(Y)).G

Now, we also add a hash puzzle to solve for Hash(S+Y) where Hash(Hash(S+Y)) is given…

Here, + represents point addition.

The truth is that Bitcoin was always quantum resistant. It stems from the scripting language, and the vary part of Bitcoin that allows it to be safe from any future attack is also one of the things that Core and BTC have done their utmost to subvert.