How many bitcoins are vulnerable to a hypothetical quantum attack?
What would an attacker with a powerful enough quantum computer do in order to steal someone’s bitcoins?
- First of all he would install Bitcoin full node and parse all unspent transaction outputs (UTXO) directly from the chainstate database using a tool like this https://github.com/mycroft/chainstate:
2. Next he would group UTXO by address to get balances on all addresses (script requires free 16 GB operating memory as of today):
And get an output with something like this:
3. Then attacker has to search through the addresses with balance and find addresses have been used for spending (i.e. addresses with revealed public keys). The easiest way to accomplish this is to install ElectrumX server (https://github.com/kyuupichan/electrumx) and let it build index, then check transaction history and sort vulnerable addresses by descending balance:
This will take quite a while (interaction with ElectrumX server should be faster if use batch requests and put database to a RAM drive). Output will look like:
As of 2018 June 4, 19% addresses (4,204,148 of 22,275,753) that hold 25% bitcoins (4,319,806 of 17,072,361) reveal their public keys. This is without taking into account a few Pay-to-publickey addresses, which unlike Pay-to-publickey-hash addresses contain public key directly in the locking scripts.
UPD: Also there are not so many unspent early P2PK transactions (e.g Satoshi coins) but they hold many bitcoins, all of them contain public keys in locking scripts: 38810 addresses with 1,760,284 BTC.
So together (as of 2018 June 4): 19% addresses (4,242,958 of 22,275,753) that hold 36% bitcoins (6,080,090 of 17,072,361) reveal their public keys.
4. Then the attacker has to extract public keys of the most valuable addresses. DER encoded public keys are 33-bytes or 65-bytes strings located right after signatures in scriptSig or corresponding witness items. For example let’s look at address 16ftSEQ4ctQFDtVZiUBusQUjRrGhM3JYwe that holds over 150,000 bitcoins:
https://blockchain.info/ru/tx/afb6523e4f5f060a076dcc2f8e5eb7a1aa58a3831456c62da946e2b5a41c24f0
Same way public keys can be extracted from Pay-to-script-hash addresses.
65-bytes public key consists of 1-byte prefix 04 and two 32-bytes integers which satisfy secp256k1 elliptic curve equation y² = x³ + 7 mod p. p is a constant prime number 2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1. To save space Bitcoin software usually use compressed public keys, which consist of 1-byte prefix (02 or 03) and 32-bytes integer x. In such case y is calculated by x from the above equation. As the equation has 2 roots, prefix 02 means y is even, 03 means y is odd.
All possible solutions of the equation are a commutative group, set of points (x,y) with addition operation defined for them. Let P₁ = (x₁,y₁) and P₂ = (x₂,y₂) — are some points from the set, then P₁+P₂ = Q, where Q is a point that also belongs to this set. We can define operation k*P = P + P + … + P (k times). k*P is also a point from the set.
In application to cryptography k*P = Q: k is a private key, Q is a public key, P is constant point named generator point. It is easy to add P k times to get Q (i.e. get public key from private key), but it is hard to find such k that k*P = Q (i.e. get private key from public key) — on a classical computer it will take as many as 2¹²⁸ operations.
5. An attacker with a powerful enough quantum computer will construct quantum circuit for Shor’s algorithm and restore k bit by bit from P and Q in a short polynomial time.
Details on how to do it can be found here: https://eprint.iacr.org/2017/598.pdf
Sources: https://github.com/quantumcthulhu/quantum-unsafe-bitcoins
