在奉上有关「共鸣机制」的文章前,我们先来点甜点。

在两周前的 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(nk),其中 k 是个常量。下图是时光庞杂度的对照,大家可以看到,指数(2n)到多项式(n2)差别非常大:

虽然 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 * pow

252.389776867137634

Math.pow(e, 52.389776867137634)

5.65706279069233e+22

Math.pow(logn, 3)

150657362.61267015

前者是 1022,后者 109,如果 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 系统吧,究竟,信誉卡,网银,微信支付,支付宝等所有基于非对称加密来保证安全的体系,可能都会变得不再可信。你认为你大爷是你大爷,可是你大爷真的不再是你大爷了。

原文题目:《量子盘算对 bitcoin 的要挟》

网站模版


以太坊现如今存在一个难度炸弹(difficulty bomb)一种使加密货币挖矿变得更加艰苦的协定,这是自从Frontier阶段开端引入到以太坊区块链中的。