## Introduction

In this blog post, we are going to address one of the biggest security problems of cryptocurrencies: quantum computers. The value of the bitcoin is sustained by the fact that people trust the transaction process between two entities and secured in the blockchain. Basically, they trust the fact that their bitcoins couldn't be stolen easily. That isn't true anymore if a person/entity has access to a big quantum computer. In order to understand why, we need to present some fundamentals of cryptography.

## Asymmetric Cryptography

Asymmetric Cryptogrophy (AC) is the domain that allows a secure transmission of information through the distinction between public and private data.

Its usage goes as follows: the cryptographic system uses pairs of keys: a public one that can be shared with anyone without compromising security, and a private one that is only known by its owner. The way such key pairs are generated is through the usage of a mathematical concept called one-way functions. Such functions are defined such that $f:\{0,1\}\rightarrow \{0,1\}$ and can be calculated with a polynomial time algorithm. However, if one tries to compute the inverse of such a function the probability that an algorithm finds a solution is negligible.

One simple example of such one-way function is the multiplication of two large prime numbers. Multiplying them is rather easy. However, if one tries to get a prime factorization of the product is pretty much impossible in a reasonable time with a standard computer. But what about a quantum computer?

It turns out that the mathematician Peter Shor proved that asymmetric cryptography is not secure anymore in the context of quantum computing. In classical computing the AC allows to derive the public key from the private key. However, the reverse is not possible: one cannot derive the private key from the public key with a classical computer. Such assumption is not true anymore with a quantum computer.

## How do bitcoin transactions work ?

Bitcoin is a decentralized way to have value transferred from one person to another. The classical way to transfer value is through banks, where two persons (or institutions) have each a bank account. The banks are needed to transfer the value agreed between the two entities. With bitcoin, you do not need any middleman: if you want to transfer value to a friend, you need to have a bitcoin wallet that once is in your device will create an address related to your public key and a private key. The private key is used to sign the transactions, and therefore to prove that you are the owner of the bitcoin wallet.

That's exactly the weakness: if someone has a quantum computer capable of deciphering your private key based on your public key, they would theoretically be able to falsify your signature and therefore steal your bitcoins from someone else.

## How bad is it ?

So, is bitcoin valueless ? Not so fast. There is two types of payments that might potentially compromise the value of bitcoin. The first type is when the public key serves as the address of the recipient of the bitcoin. In that case the transaction is called “pay to public key” (p2pk). Such kind of transaction was the first type of transaction created by Satoshi Nakamoto (the creator of bitcoin) himself. In that particular case, the public key is open to anyone in the blockchain, and in fact lots of bitcoins from Satoshi Nakamoto are still in such addresses (and therefore in danger to be stolen).

The second type of transactions that might be dangerous are the so-called “pay to public key hash” (p2pkh). In that case, the public key is hashed to serve as the address and therefore not directly visible in the address. However, the public key is revealed in the blockchain, if funds are transferred from a p2pkh address. In that case, a quantum computer could be used in conjonction with Shor's algorithm to get the private key of that address and therefore potentially be able to steal the bitcoins of such wallet.

## Is there any hope ?

Quantum computers are coming, rather soon that later. Therefore, the community should be ready for such challenges. Two things that should be done:

1. do not use p2pk addresses;
2. do not reuse the same p2pkh addresses;

Can your bitcoin still be stolen if you follow these two rules ? Normally not, because the time needed for a transaction to be verified in the blockchain is of the order of 10 minutes, while theoretical estimates tell us that a quantum computer would need at least 8 hours to decipher a private key from its public key. However, quantum computing is a very new field and it might actually happen that a much faster algorithm than Shor's algorithm might be found.

Actually, even if you follow the two rules cited above, bitcoin might still lose lots of its value, simply because other people will not necessarily follow them and will be hacked. If lots of bitcoins are stolen, its value will likely crash and the confidence in the technology would be lost.

So, when are those quantum computers coming? Well, they are already around! Did you know that google reached the so-called “quantum supremacy” ?

Right now, there is no real universal solution to the problem that quantum computers might bring to the cryptocurrency world. Some people might say that such a problem will only arise far in the future… but clearly, this is of fundamental importance to understand what will be the fair price of bitcoin in the future.

If you would like to cite the present content, please use:


@article{fabio2021bitcoinquantum,
title   = "Is Bitcoin Worthless?",
author  = "Capela, Fabio",
journal = "capfab.io/blog",
year    = "2021",
url     = "https://capfab.io/blog/biggest-risk-to-bitcoin"
}