量子计算对比特币的威胁

在介绍“共识机制”的文章之前，我们先来点甜点。

两周前在BBL上量子比特币，我给团队介绍了比特币，相关幻灯片见：

github.com/tyrchen/unchained

讨论量子计算对比特币的威胁花了一段时间。 上周，谷歌发布了72比特的通用量子计算机，引起了大家的热议——尤其是看似牢不可破的加密货币要被终结了吗？

下图是我当时讲的：

首先我们来看一下量子计算中的既定算法：Shor算法（以下简称Shor）和Grover算法（以下简称Grover）。

Shor 不是通用算法，它解决的是因式分解问题——给定一个整数 N，找出它的质因数。 下面是来自维基百科的介绍：

在量子计算机上，为了分解一个整数 N，Shor 的算法在多项式时间内运行（所用时间是多项式的 log N，它是输入的大小）。[1] 具体来说，它采用 O((log N)3) 阶的量子门，使用快速乘法，[2] 证明整数分解问题可以在量子计算机上有效地解决，因此属于复杂度类 BQP。 这比已知最有效的经典因式分解算法、一般数域筛法要快得多量子比特币，它在次指数时间内工作——大约 O(pow(e, 1.9(log N)1/3(log log N)2/3 )).[3] Shor 算法的效率归功于量子傅里叶变换的效率，以及通过重复平方的模幂运算。

简单的说，秀尔将指数时间复杂度降低为多项式时间，即多项式时间。 所谓多项式时间就是O(nk)，其中k是一个常数。 下图是时间复杂度的对比。 你可以看到指数（2n）和多项式（n2）之间的差异非常大：

虽然 Shor 只能加速因式分解，但如果你了解非对称加密的算法，你就会记得 RSA 的基石是两个大质数 p 和 q 的合数很难分解为 p 和 q。

大约五到十年前，人类通过通用计算机分解出的最大整数是 768 位，所以理论上低于这个数字的 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 * pow
252.389776867137634
> Math.pow(e, 52.389776867137634)
5.65706279069233e+22
> Math.pow(logn, 3)
150657362.61267015

前者为1022，后者为109，如果在1ns内完成一次运算（当然两种算法的运算时间不同，但常数），前者需要180万年，后者需要1s。

可以看出，Shor对RSA系统的破坏性是显而易见的，其变体也具有与基于椭圆双曲线的ECDSA相似的降维杀伤力。 从这个角度来看，量子计算机不断成熟，整个非对称加密体系下的算法都会受到很大的冲击——PKI会崩溃。 当你访问chase.com时，CA已经无法证明chase.com的证书属于Chase； 也不可能使用公钥来验证私钥的签名，因为私钥可以从公钥导出。 因此，受到威胁的不是比特币，而是整个互联网。 你不能信任你银行的网站，银行也不能信任你的 USB 令牌中的私钥提供的签名。 我们的数字生活正在走向黑暗时代。

但是，您仍然可以信任您的比特币钱包。 比特币钱包的私钥和钱包地址虽然是从ECDSA的私钥和公钥推导出来的，但是钱包地址并不是直接是公钥，而是公钥的hash。 因此，如果您向钱包汇款，则不需要钱包的公钥； 只有当钱包使用里面的钱（给别人转钱）的时候，你才需要把自己的公钥放在交易中。 如果一个钱包只收钱，那么它就是安全的——即使 Shor 的算法也需要公钥来反转私钥。 因为没有公开公钥，所以不能使用秀尔算法。 因此，即使量子计算破解了非对称加密算法，对于那些没有使用过的冷钱包（code wallet）也是无法破解的。 那些需要多重签名的钱包也是如此。

如果非要破解冷钱包，需要先逆向钱包地址得到它的公钥，而这个操作是Shor做不到的，只能用其他算法了。

这个算法就是Grover。 先看维基：

Grover 算法是一种量子算法，它仅使用函数的 O(sqrt N) 求值（其中 N 是函数域的大小），以高概率找到产生特定输出值的黑盒函数的唯一输入。 由 Lov Grover 于 1996 年设计。

基本上，Grover 对于函数 f(x) = y，只要给定 y 和一个 x 值的列表，它就能以 O(sqrt N) 的时间复杂度找到这个 x。 换句话说，对于任何算法，在正常情况下，暴力破解（在算法的域内一个一个地尝试）是O(N)，而Grover将其降低到O(sqrt N)。 对于时间复杂度，这个算法看起来不错，但大多数时候聊胜于无。 下图是与log N的对比：

我们来看一个256bit的公钥，它的O(sqrt N)有多大。 我们首先要找到256位数字的取值范围：

> n_max = 0b111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
5.78960446186581e+76

> Math.sqrt(n_max)
2.4061596916800453e+38

> Math.log(n_max)
176.75253104278605

可以看出，虽然sqrt之后的量级已经大大降低，但仍然在万亿万亿级别，在可预见的时间内无法破解。 因此，即使使用Grover算法，也无法通过钱包地址有效破译出公钥，然后再使用Shor算法从公钥中破译出私钥。

从这个意义上说，比特币仍然不受量子计算的影响。 当大家都在担心量子时代到来后比特币的前景（可能20年、30年，或者30年、50年），我们先担心现有的PKI体系。 毕竟，信用卡、网银、微信支付、支付宝等依赖非对称加密来保证安全的系统可能会变得不可信。 你以为你的叔叔是你的叔叔，但你的叔叔真的不再是你的叔叔了。

iOS用户鉴赏渠道：