比特币的悬剑——来自量子计算机的威胁

这是加密货币三部曲的最后一章。 在本系列中，第一部分介绍了普通用户在私钥保护方面遇到的困难，第二部分阐述了基于区块链的加密货币在交易效率和安全性之间的无奈权衡。 如果普通企业家能够对这些问题采取行动，那么下一个严峻挑战的解决方案仍然是一个学术研究课题，即未来量子计算机将能够破解比特币区块链使用的椭圆曲线加密算法。 但是，抗量子计算机破解的加密算法还不成熟。 这是本次讨论的主题。

考虑到内容的难度和篇幅，现将结论解释如下：

未来，当通用量子计算机达到1800个量子比特时，区块链目前使用的椭圆曲线加密算法将面临破解；

比特币社区目前提出的“一密一用”方案是错误的，不足以应对量子计算机的威胁；

升级区块链算法是否可行仍有待商榷。

本文的组织结构如下：

区块链使用的算法介绍；

量子计算简介；

量子 Shor 算法的简要解决方案；

量子计算机破解区块链的前景；

为什么“一密一用”方案行不通；

升级区块链算法是否可行；

后记。

一、区块链使用的算法介绍

区块链主要使用两种密码算法：非对称算法使用椭圆曲线（ECC），哈希算法主要使用SHA256。 量子计算机理论上破解的是椭圆曲线算法，下面简单介绍一下。

椭圆曲线的一般方程为：

y^2 = x^3 + 轴 +b

其形状大致如下图所示：

可以看到两个明显的特征：曲线的 x 轴是对称的； 一条直线和一条椭圆曲线至多有三个交点。

上图还展示了椭圆曲线上的加点操作：曲线上加点P和Q是指连接P和Q的直线与椭圆曲线相交于第三点，各点沿x轴对称是添加的结果。

也可以定义一个点的倍数。 方法是通过点P取切线，与椭圆曲线相交于-R，沿x轴取对称点，即R=2P。

不管是加法还是乘法，对应的数学公式都比较简单，这里略过。 如果应用在密码学中，所有的操作都是对某个质数取模，这里也略过。

通过点的加倍 (x 2 ) 和加法运算，可以定义点的乘法。 一个自然数 k 乘以一个点 P 相当于将 P 与自身相加 k-1 次。 还有更快的算法。 这里不展开。

现在我们可以谈谈椭圆曲线密码学。 就经典计算机而言，给定椭圆曲线上的一个点G，很容易将任意整数k乘以G得到另一个点P=kG。 但是，给定G和P，如果要对k进行倒置计算，可是有相当大的计算量。 这构成了椭圆曲线密码学的基础。

在应用中指定曲线参数和生成点G的值，然后每个用户生成一个随机数k作为自己的私钥，私钥乘以生成点G得到的点就是公钥. 在区块链中，使用的椭圆曲线称为secp256k1，私钥长度为256位，可以提供相当于对称算法128位的加密强度（其实稍微弱一点，因为这条曲线有加速计算的某些特性。降低其强度，但这可以忽略不计）。

2. 量子计算简介

那么量子计算机是如何破解椭圆曲线密码的呢？ 是不是像有些文章说的那样，量子计算机可以进行超大规模的并行运算，解决所有的计算问题？ 甚至有人说，量子计算机可以颠倒因果，颠倒是非。

没那么神奇。

所谓的大规模并行计算确实存在，但是海量的计算结果都是量子态叠加的，你要哪个？ 不知道。 最终还是要观察结果，而这会导致量子态的崩溃，只会得到其中一个结果，也不知道是对是错。

让我们从头开始。 现炒卖。

假设一台量子计算机有四个量子比特。 所谓量子比特，我们不用去深究它的物理机制。 简而言之，它可以像经典计算机一样表达 0 或 1。 不同的是，量子比特可以同时表达0和1，以及两者的任意线性组合。 四个量子位可以同时表达0000到1111之间的16个数，操纵这四个量子位相当于同时对16个数进行运算，这就是量子计算机的并行计算能力。 这个能力还是很不错的。 如果有 32 个量子比特，它可以对超过 40 亿个数字进行并行运算。

四十亿！

要知道，去年世界超级计算机排名第一的太湖之光，也只有数千万个计算核心，可以同时计算数千万个数。 这是400倍的差距！

请不要那样看着我！ 是真的！ ！

但这岂不是意味着量子计算机可以轻松秒杀经典计算机？ 32 个量子比特将世界排名第一的超级（经典）计算机置于脚下，400 比 1，不是吗？ 传说中的量子霸权（Quantum Supermacy）。

没那么简单。 我们仍然生活在经典力学的世界里，量子计算机的计算结果必须时刻被观察，而且作为观察结果只会呈现一个结果。 至于会出什么结果，那是随机的。

随机的。 真的很随机​​。 如果我骗你，你就是！

是这样的，无论是初始数据、中间结果还是最终结果，每个量子态都有一定的概率。 如果不看，这些量子态都很好地共存，薛定谔的猫既是死的又是活的； 如果你坚持要看，好吧，那都是你的错，猫已经死了。

真怪你。 人家的正确答案本来是叠加了另外四十亿个错误答案的，你要看结果。 从这一点来看，四十亿个答案中的一个都会随机给你，而且答对的可能性很小，这比体彩中的大奖难多了。

该怎么办？

奇怪的是，在某些情况下，错误的结果可以相互抵消。 如何去做，简单来说，因为量子力学可以用波函数来描述系统的状态，所以这四十亿个答案中的每一个都有对应的波幅； 在量子力学中，振幅可以是正的也可以是负的（实际上是复数）。 那么只要我们尽量让那些错误答案的振幅大部分自己抵消，而正确答案可以相互加强，那么观察到最后会不会就是正确答案呢？

几乎。 量子态波函数的振幅与该量子态出现的概率有关。 如果错误的答案已经大部分相互抵消，出现的概率接近于零，那么剩下的高概率就是正确答案。

这很难，你想操纵上帝掷出的骰子？ 如果对问题本身（黑盒问题）没有结构性的理解，理论上最好的结果就是Grover算法，可以平方黑盒问题的计算量。 太神奇了，百万次计算变成千次，万亿次变成百万次。 但是对于破解密码来说，这还不够，因为你只需要将密钥长度加倍即可。

这样你就可以高枕无忧了吗？

不幸的是，椭圆曲线算法和 RSA 算法的数学原理已经被研究得相当透彻。 一位名叫Peter Shor的大神创造了以自己名字命名的Shor算法，将256位椭圆曲线的计算量从几十亿一下子减少到60亿，减少了几十个数量级。 这根本不是证券公司量子计算概念研究报告中提到的计算速度提升几百万倍，而是9999亿倍的提升好吗？ 而且，即使我们不知道未来的量子计算机每秒可以操纵多少个量子比特，60亿在今天也不再是遥不可及的数字。 毕竟手机处理器的主频已经达到了10亿。 赫兹级别。

那么，这么神奇的秀尔算法到底是怎么回事，我们也得花点时间看看了！

3. 量子秀尔算法简述

秀尔算法由运行在经典计算机上的主程序和运行在量子计算机上的“量子傅立叶变换”算法组成。 经典计算机的主程序可以将其他一些数学问题转化为乘法群的周期解问题，量子计算机利用量子傅里叶变换求解，经典计算机再求解剩下的部分（在大数分解问题，从数的周期非平凡因子求解大数）。 因此量子计算比特币，秀尔算法可用于大数分解、离散对数求解和椭圆曲线求解。 量子傅里叶变换负​​责9999亿倍的提速[1]，Shor算法可以破解RSA算法、DH密钥协商协议和椭圆曲线算法，可以说是非对称加密的主流算法。 这是一场杀戮。

什么是傅里叶变换这里就不说了。 读者只需要知道音频的有损压缩需要使用一种称为“快速傅里叶变换”的算法 [2]。 至于量子傅立叶变换在秀尔算法中的作用，举个简单的例子可能更容易理解。

比如分解一个数15，首先经典计算机将其转化为7的模15乘法群的周期性问题（随机抽取，如果恰好是3或5则结束，否则继续），即就是，找到最小的整数 r，使得 7^r= 1 (mod 15)，其中 ^ 表示幂。 7的平方是49，对15取模后是4； 7 模 15 的立方等于 7 乘以 4 除以 15 的余数，即 13； 7的四次方模15恰好是1，所以这里的r应该是4。检查r满足一定条件后，可以求出15的分解（7^(r/2)+1的最大公约数和15，是因子5之一；而分解7^(r/2)-1和15的最大公约数，是另一个因子3)，否则随机选一个数继续试。

现在因为这个例子中使用的数字非常小，所以它会做数学运算。 实际应用中的数量特别多。 例如，目前主流的RSA应用使用的整数长度为2048位二进制数，而十进制数则有700多位长度。 在合理的时间内完成，这就是非对称加密算法能够流行的原因。

那么，量子计算机如何解决这个循环呢？ 它需要8个量子位，可以表示0到255共256个数的叠加态。初始化，使每个数的概率相等。 然后，将这8个量子位表示的数作为指数，进行7的次方（模15）运算。 然后对结果进行量子傅立叶变换。 计算结果是多个数的叠加状态。 但由于周期的存在，只有特定方向的结果才会相互加强，在观察结果时出现的概率更大。 周期可以通过观察结果进一步处理得到（本来想把具体的计算写出来，但是在微信里写复杂的数学公式并不容易[3]）。

所以你看，观察结果是必须的一步，哪有什么因果颠倒，宇宙颠倒。 只有通过观察，我们才能使用周期性来呈现所需的结果。

4. 量子计算机破解区块链的前景

因此，非对称算法在理论上已经被破解，问题只是这一天何时到来。

什么时候破解？ 要破解一个 256 位的椭圆曲线密钥，大约需要 1800 个量子比特。 在撰写本文前四个月，即 2017 年 5 月，IBM 宣布已构建了一台 16 量子位通用量子计算机。 谷歌实验室声称在年底前制造出具有 50 个量子比特的通用量子计算机，以实现量子霸权。 那么，什么时候才能建造出具有 1,800 个量子比特的通用量子计算机呢？ 没人知道。 现在还有一些身体障碍。 但没有人敢说突破不会立即发生。 因此，很难说现有的非对称加密算法还能使用多久。 不过不用太担心，因为如果量子计算机取得进展，肯定会广为人知，让社会有所准备。

在几秒钟内破解一个？ 或者多少天？ 这涉及到量子计算机的“处理器频率”能达到什么水平。 可以使用激光束来操纵处于量子态的粒子的量子计算机，原则上应该不比硅晶体电路慢。 理论计算表明，破解256位椭圆曲线算法只需要60亿次计算，所以时间最多为秒级。

我的比特币什么时候会被黑？ 正如本系列上一篇文章所述，加密货币存在私钥保管难题。 肯定会有很多比特币因为私钥丢失而变得“无主”。 1800量子比特的通用计算机制造出来后，拥有者可以保密，悄悄用它来破解那些“无主”的比特币（只要知道公钥，比如用过比特币的地址；是否最近两年一直在用），赚了很多钱，变现了。 然后上市并观看加密货币崩溃。 就怕根本没人攻击你的比特币，一下子就自己崩了。

怕什么，到时候网上银行、电子商务、网络服务等都会​​遇到更大的问题。 呵呵。 银行业和互联网服务业是否也会受到量子计算机的冲击是肯定的。 但大不了的是，银行将关闭面向公众的网络服务。 让我们回到过去线下做生意的模式。 银行仍然可以使用网络通过专线和预共享对称密钥加密（量子计算机无法破解对称密码）来清除交易数据； 即使银行向每位用户发送了一个带有预设共享对称密钥的U盾进行加密通信，用户仍然可以继续使用部分网上银行服务。 银行也可以使用量子计算机并运行量子加密软件。 至于电子商务和互联网服务，会出现一些问题，但这是扎克伯格、皮查伊和马云需要担心的问题。 普通互联网用户顶多是不方便。 然而，量子计算机给加密货币带来的却是一场灾难。 是加密货币资产的流失，是整个系统的崩溃。

宝宝被吓死了，赶紧给作者打赏

5. 为什么“一密一用”方案行不通

比特币一旦被使用，持有者必须对比特币进行签名，签名必须释放公钥。 那么，如果公钥被能够破解椭圆曲线算法的人看到，私钥就可以被破解，也就意味着比特币可以被窃取。

为了缓解焦虑，在中国比特币圈流传着一种所谓的“一密一用”方案：每使用一枚比特币后，将地址上剩余未使用的比特币转移到新地址。 由于地址是双重哈希的，而且哈希算法是抗量子计算机的，所以不存在问题[4]。

说这话的安德烈亚斯·安东诺普洛斯，在比特币圈内颇有名气。 他还在希腊一所大学教授加密货币硕士课程。

但他的说法是错误的。

正如本系列文章《区块链不可能三角》一文所述，区块链上的交易需要时间，不会瞬间完成； 更糟糕的是，可能存在故意干扰导致交易失败。 然而，量子计算机很可能能够在几秒钟内破解它。 一旦您花费比特币，或者甚至只是尝试将比特币转移到一个新地址，您的公钥就会被发布并迅速被破解。 在交易所将您的交易请求添加到新区块之前，您的比特币已被收割。

另外，哥们说椭圆曲线算法的安全性依赖于大数分解问题也是错误的。

6、区块链算法升级是否可行

那么，区块链算法能否升级为能够抵抗量子计算机破解的新算法呢？

我不敢说不可能。 然而，所谓的后量子计算机加密算法主要是非对称算法。 尽管有很多替代方案量子计算比特币，但它们还不成熟。 而且，因为这样的算法比较复杂，所以在实现的时候会出现各种各样的问题（有一个算法叫SIDH，我还没有弄明白，主要是不明白什么是Isogeny）。 不过话虽如此，到底哪种算法实现起来一定没有问题呢？ 即使是二进制搜索也会导致问题。 至于区块链使用的椭圆曲线算法，索尼当年闹了个大丑闻。 索尼的PS3在实现椭圆曲线签名时，在应该使用随机数的地方使用了固定值，被黑客曝光。 索尼威胁要起诉这些黑客，黑客们说，“你活该一辈子呆在地下室写Excel宏”。 离这很远...

至于即使找到了算法，区块链能否顺利迁移，也是一个问题。 因为在区块链世界里，连设置交易限额都不能约定，增加区块大小需要硬分叉。

7.结语

一不小心闯入了区块链的浑水，硬着头皮写完了这篇文章，作为加密货币底层缺陷分析的收官之作。 稍后我会再写一篇区块链应用评论。

[1] 这只是对 256 位椭圆曲线算法的改进。 量子算法的强大之处不在于它改进了多少倍，而在于它可以把一些指数时间复杂度的特定算法变成多项式时间，可谓质的飞跃。

[2] MP3有损压缩算法的主要原理是将音频信号通过傅里叶变换变换到频域，然后通过心理模型滤除人耳不敏感的频率成分，从而降低数据量。

[3] 好吧，我承认，其实我还没有完全理解。

[4] Andreas Antonopoulos：比特币的设计可以抵御量子计算机攻击