The Quantum Computing Threat to Bitcoin
Before serving the article on “consensus mechanisms,” let’s start with dessert.
At a BBL two weeks ago, I introduced Bitcoin to the team; the slides are at github.com/tyrchen/unchained. I spent some time discussing the threat of quantum computing to Bitcoin. Last week Google announced a 72-qubit universal quantum computer, sparking heated discussion—especially about whether cryptocurrency, which looks unbreakable, is nearing its end.
Here is what I covered in that talk:
First, let’s look at two relatively mature quantum algorithms: Shor’s algorithm (Shor for short) and Grover’s algorithm (Grover for short).
Shor is not a general-purpose algorithm; it solves the factorization problem—given an integer N, find its prime factors. Here is Wikipedia’s introduction:
On a quantum computer, to factor an integer N, Shor’s algorithm runs in polynomial time (the time taken is polynomial in log N, which is the size of the input).[1] Specifically it takes quantum gates of order O((log N)^3^) using fast multiplication,[2] demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is thus in the complexity class BQP. This is substantially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time – about O(pow(e, 1.9(log N)^1/3^(log log N)^2/3^)).[3] The efficiency of Shor’s algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings.
Simply put, Shor collapses exponential time complexity into polynomial time. Polynomial time means O(n^k^), where k is a constant. The chart below compares time complexities; you can see the enormous gap between exponential (2^n^) and polynomial (n^2^):
Although Shor can only accelerate factorization, if you know anything about asymmetric cryptography, you’ll remember that RSA rests on the fact that the product of two large primes p and q is hard to factor back into p and q.
About five to ten years ago, the largest integer factored by general-purpose computers was 768 bits, so in theory RSA keys below that size are insecure. In practice we mostly use 4096-bit keys:
$ ssh-keygen -t rsa -b 4096 -C "tyr@awesome.com"For an integer of 768 bits (binary), let’s compare the complexity of the two algorithms:
> n = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
1.2301866845301178e+231
> logn = Math.log(n)
532.1043224155328
> loglogn = Math.log(logn)
6.276839564883618
> pow1 = Math.pow(logn, 1/3)
8.103368625868256
> pow2 = Math.pow(loglogn, 2/3)
3.402728919940164
> 1.9 * pow1 * pow2
52.389776867137634
> Math.pow(e, 52.389776867137634)
5.65706279069233e+22
> Math.pow(logn, 3)
150657362.61267015The former is 10^22^, the latter 10^9^. If one operation takes 1ns (the two algorithms do not take the same time per operation, of course, but this is a constant), the former needs 1.8 million years, while the latter needs 1s.
From this we can see that Shor’s destructive power against RSA is obvious. Moreover, its variants have a similar dimension-reducing effect on ECDSA, which is based on elliptic curves. In this sense, as quantum computers mature, the entire asymmetric cryptography system will be hit hard—PKI will collapse. When you visit chase.com, a CA can no longer prove that the cert for chase.com belongs to Chase; nor can you use a public key to verify a signature from some private key, because the private key can be derived from the public key. So what is at risk is not Bitcoin but the entire internet. You cannot trust your bank’s website, and the bank cannot trust the signature produced by the private key in your USB token. Our digital lives would enter a dark age.
However, you can still trust your Bitcoin wallet. Although a Bitcoin wallet’s private key and wallet address both derive from an ECDSA private key and public key, the wallet address is not the public key directly; it is a hash of the public key. Therefore, sending money to a wallet does not require the wallet’s public key; only when the wallet spends its funds (sends money to someone else) does it need to put its public key into a transaction. If a wallet only receives money, it is safe—even Shor’s algorithm needs a public key to reverse the private key. Since the public key is not exposed, Shor cannot be used. Thus, even if quantum computing breaks asymmetric encryption, unused cold wallets (code wallets) cannot be broken. The same applies to wallets that require multisig.
If one absolutely must break a cold wallet, one first has to reverse the wallet address into its public key, and Shor cannot do that; only other algorithms can.
This algorithm is Grover. First, Wikipedia:
Grover’s algorithm is a quantum algorithm that finds with high probability the unique input to a black box function that produces a particular output value, using just O(sqrt N) evaluations of the function, where N is the size of the function’s domain. It was devised by Lov Grover in 1996.
Basically, for a function f(x) = y, given y and a list of possible x values, Grover can find x in O(sqrt N) time. In other words, for any algorithm, brute force (trying values one by one across the domain) is normally O(N); Grover reduces it to O(sqrt N). In terms of time complexity, although this looks good, in most cases it is merely better than nothing. The chart below compares it with log N:
Let’s look at a 256-bit public key and how large its O(sqrt N) is. First we need the range of a 256-bit number:
> n_max = 0b111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
5.78960446186581e+76
> Math.sqrt(n_max)
2.4061596916800453e+38
> Math.log(n_max)
176.75253104278605As you can see, although the magnitude after sqrt is greatly reduced, it is still on the order of trillion trillion trillion, impossible to break in any foreseeable timeframe. So even with Grover, one cannot efficiently derive the public key from a wallet address and then use Shor to derive the private key from the public key.
In this sense, Bitcoin has some immunity to quantum computing. While everyone worries about Bitcoin’s prospects once the quantum era arrives (maybe in twenty or thirty years, maybe thirty or fifty), they should first worry about the existing PKI system. After all, credit cards, online banking, WeChat Pay, Alipay, and every system that relies on asymmetric encryption for security may become untrustworthy. You may think your grandpa is still your grandpa, but your grandpa really is no longer your grandpa.
