量子计算对 bitcoin 的威胁
在奉上有关「共识机制」的文章前，我们先来点甜点。
在两周前的 BBL 上，我给团队介绍了 bitcoin，相关的 slides 见 github.com/tyrchen/unchained。其中花了点时间谈论了 quantum computing 对 bitcoin 的威胁。上周 google 发布了 72 量子比特通用量子计算机，引发了大家的热议 —— 尤其是，看上去牢不可破的 cryptocurrency，是不是到了快要被终结的时刻？
下图是当时我 talk 时讲的内容：
首先我们看量子计算中已经比较成型的算法：Shor’s algorithm（下文简称 Shor） 和 Grover’s algorithm（下文简称为 Grover）。
Shor 不是通用的算法，它解决因式分解的问题 —— 给定一个整数 N，找到其质因数。以下是 wikipedia 的介绍：
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.
简单说，Shor 就是把指数级的时间复杂度降维成了 polynomial time，也就是多项式时间。所谓多项式时间，就是 O(n^k^)，其中 k 是个常量。下图是时间复杂度的对比，大家可以看到，指数（2^n^）到多项式（n^2^）差异非常大：
虽然 Shor 只能加速因式分解，但如果你了解非对称加密的算法，你会记得 RSA 的基石就是两个大质数 p 和 q 的合数很难被因式分解出 p 和 q。
大概五到十年前，人类通过通用计算机分解出来的最大的整数是 768 bit，因而理论上 RSA 密钥低于这个数字就是不安全的。实际生活中，我们基本会用 4096 长度的密钥：
$ ssh-keygen -t rsa -b 4096 -C "tyr@awesome.com"对于一个 768bit（二进制）大小的整数，我们对比两个算法的复杂度：
> 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.61267015前者是 10^22^，后者 10^9^，如果 1ns 完成一个 operation（当然两个算法一次 operation 的时间是不等的，但是常量），前者需要 180 万年，后者需要 1s。
由此可见，Shor 对 RSA 体系的破坏性是显而易见的，而且，它的变种，对基于椭圆双曲线的 ECDSA 也有类似的降维杀伤力。从这个角度上讲，量子计算机不断走向成熟，整个非对称加密体系下的算法都会受到巨大的冲击 —— PKI 将坍塌，你访问 chase.com，CA 已经无法证明 chase.com 的 cert 属于 Chase；你也无法使用公钥去验证某个私钥的签名，因为私钥变得可以被公钥推导出来。所以，岌岌可危的并非 bitcoin，而是整个 internet。你无法信任你的银行的网站，银行无法信任你的 USB token 里的私钥提供出来的签名。我们的数字化生活会走向暗黑时代。
然而你还是能信任你的 bitcoin 钱包。虽然 bitcoin 钱包的私钥和钱包地址都来源于 ECDSA 的私钥和公钥，然而钱包地址并非直接是公钥，而是公钥的 hash。因而，你给一个钱包打钱，并不会需要钱包的公钥；只有这个钱包使用里面的钱（给别人打钱）时，才需要把自己的公钥放在 transaction 里。如果一个钱包只是收钱，那么它是安全的 —— 即便 Shor 算法也需要公钥去逆向私钥。因为公钥没有暴露出来，Shor 算法无法使用。因而即便量子计算破解了非对称加密算法，对于那些没有使用过的冷钱包（code wallet），也无法破解。对于那些需要 multisig 的钱包，也是类似。
如果非得破解冷钱包，那么需要先把钱包地址逆向出来其公钥，而这个操作 Shor 无法完成，只能借助其他算法。
这个算法是 Grover。先看 Wiki：
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.
基本上，Grover 对于函数 f(x) = y，只要给定 y，以及 x 取值的一个列表，它可以以 O(sqrt N) 的时间复杂度，找到这个 x。换句话说，随便一个算法，正常情况下暴力破解（在算法的定义域里一个个试），是 O(N)，Grover 将其降低成 O(sqrt N)，对于时间复杂度来说，这算法虽然看上去不错，但大多数情况下只是聊胜于无。下图是它和 log N 对比：
我们看一个 256bit 的公钥，其 O(sqrt N) 是多大。我们先得找 256bit 数字的取值范围：
> n_max = 0b111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
5.78960446186581e+76
> Math.sqrt(n_max)
2.4061596916800453e+38
> Math.log(n_max)
176.75253104278605可以看到，虽然 sqrt 后量级已经大大减少，但还是 trillion trillion trillion 级别，在一个可以预见的时间内无法破解。所以，即便使用了 Grover 算法，也无法有效地通过钱包地址破解出公钥，进而进一步使用 Shor 算法从公钥破解出私钥。
从这个意义上讲，bitcoin 对 quantum computing 还是有一定免疫力的。在大家担忧量子时代到来后（可能二三十年到来，也可能三五十年） bitcoin 的前景时，还是先担忧一下现有的 PKI 体系吧，毕竟，信用卡，网银，微信支付，支付宝等所有基于非对称加密来保证安全的系统，可能都会变得不再可信。你以为你大爷是你大爷，可是你大爷真的不再是你大爷了。
