On bitcoin and the quantum threat

Disclaimer: I'm a physicist, but by no means an expert. Just a strong interest in both quantum computing and cryptography. I've also simplified a lot of concepts, because they are complex and don't fundamentally bring anything more to the discussion

Introduction &

With IBM announcing their new quantum chip with 127 qubits, I thought i'd clear any misunderstandings concerning quantum computing as a threat to cryptocurrencies and cryptography as a whole. For this, we need to do a quick physics and cryptography recap.

The physics &

Qubits form the fundamental unit of quantum information, just like the bit is the fundamental unit of information in classical computing. Classicaly, the bit may take 2 values, either a 1 or a 0. In a quantum system, the qubit may be in a coherant superposition of both states. If this seems counterintuitive to you, I highly recommend the computerphile video on superposition, which will give you a much more intuitive notion of superposition. Quantum computing has an edge over classical computing via the implementation of quantum algorithms, which perform better than classical algorithms for a certain class of problems.

The cryptography &

Cryptographic functions are used in different ways in the bitcoin protocol. I won't get into too much detail as it is beyond the scope of this piece, but will go over two main functions.

1st - The public-private key pair. When you generate your seed phrase, you're creating a public-private key pair. These are interesting because both can be used to encrypt or decrypt a message, and consequently, to prove ownership of something. For example:

• Alice has both a public and private key
• Alice encrypts her message using the private key
• Alice shares her public key to the world
• Bob takes Alice's public key to decrypt Alice's message
• Bob therefore knows Alice is the one who wrote the message

We can see how this can be used in the bitcoin protocol. Simply put, each UTXO belongs to an address (which is derived from your public key, more on that later) and can only be spent by the holder of the corresponding private key (by signing the transaction).

2nd - The hash function. Hash functions are used for the proof of work part, where to mint a block, a hash of pending transactions and a nonce is generated (this is a gross simplification). The first person to generate a hash with a leading number of 0's may add his block to the blockchain and gather the rewards. Difficulty is adjusted by adding or removing the amount of leading 0's, and is a function of the total hash power of the network. Hash functions are also used to derive your wallet address by taking the SHA256 hash of the public key, and then taking the RIPEMD-160 hash of the previously SHA256 hashed output. A hash of a hash.

The Threat ? &

SHA256 is a time-tested hashing algorithm, which is widely thought to be secure and quantum resistant. Therefore, both mining and freshly generated wallets are immune to any attack, quantum or not. The issue comes when spending UTXO's. When you spend your bitcoin, you are broadcasting your public key to the network. In a classical world, this wouldn't be an issue, as computing the private key from a public key is an NP problem, i.e it is computationally too expensive to solve with a classical computer. This is where Shor's algorithm comes along. In 1994, Peter Shor showed that prime factorization can be performed in polynomial time using a quantum computer. In other words, with sufficient logical qubits, one could derive the private key from a public key. Even though ECDSA, the digital signature algorithm which is used in the bitcoin protocol, uses elliptical curves, both class of problems have similar properties which makes elliptical curve cryptography vulnerable to Shor's algorithm.

Now for the reality check &

IBM's computer is comprised of 127 PHYSICAL qubits, which are subject to decoherance. Simply put, these qubits don't behave like the idealised LOGICAL qubits. It is my understanding that a true implementation of Shor's algorithm was not able to factor out the number 35 see here and here. You can access the paper using scihub to find the quote in the article "Eventually, the algorithm fails to factor N = 35. This is due to the cumulative errors coming from the increasing number of two-qubit gates necessary to implement the more complex MEF needed for this case".

Furthermore, modern software wallets can generate a prohibitively large amount of private keys from a single seed phrase. This means that if Alice has 1 Bitcoin and sends Bob 0.1 Bitcoin, the remaining 0.9 are moved along as well to another address, in a manner which is completely transparent to Alice. With an average time of 10 minutes between minted blocks, this would leave very little time for an attacker to steal funderus (provided the transaction i included in the next block). It should be noted that in 2018, there were approximately 30 % of bitcoins with "public" public keys source.pdf)

Does this mean Bitcoin is safe for ever ?? &

Definitely not. Although according to most predictions we are still year if not decades away from breaking ECDSA, measures should be taken to implement quantum resistant digital signatures. One can hope that it will be implemented in the coming years through a BIP. I hope I've clear up any misunderstanding with bitcoin and quantum computing, and hopefully quantum resistant digital signatures will be implemented in the coming years