量子计算机真的能摧毁区块链网络吗？

最近有很多朋友问我关于量子计算机的问题。 最大的担忧是量子计算会利用其超强的计算能力让加密货币不再加密，甚至破坏区块链网络。 让我从答案开始：不。 但是要理解这一点，有必要了解什么是量子计算和区块链密码算法。

本文特别感谢曾俊凯提供的技术支持。 他不仅是我的老同学，还是博士。 在弗吉尼亚理工大学获得物理学博士学位。 他的研究方向是量子计算。 目前就职于洛杉矶红杉资本投资的一家量子公司。

量子计算

要理解量子计算，我们需要理解什么是经典计算。 要知道经典计算机发展遇到的一个瓶颈叫做摩尔定律，即一块集成电路上所能容纳的晶体管数量每两年就会翻一番。

这导致晶体管的体积越来越小。 当小到2nm左右时，由于2nm级别的晶体管只能容纳10个原子，电子的行为将不再遵循传统的半导体理论，而是遵循量子力学。 随着晶体管集成度的提高，芯片产生的热量会越来越高。

这些负面影响严重阻碍了经典计算机的发展。 在这种关注下，人们想出了光子计算机、生物计算机、量子计算机等解决方案。

为什么人们如此关注量子计算机？

首先我们要知道，经典计算机的运算都是通过逻辑电路来完成的。 二进制 1 和 0 代表计算机中的逻辑运算，也称为布尔代数。

1 表示真（高电平），0 表示假（低电平）。

最常见的逻辑运算是 AND、OR 和 NOT。 例如，真与真结果为真，真与假结果为假； 要么真就是假，假就是真。 这些操作都是通过逻辑门完成的，其中一些是可逆的或不可逆的。 比如非门输入一个1（bit true），输出一个0（bit false），所以NOT门是一个可逆门，因为我们可以通过输出0（bit）来反转输入1（bit true）错误的）。 但是如果一个与门的输出是0（假位），那么输入位就有3种可能，分别是00、01、10。我们不能清楚地一对一映射回输入，所以与门是不可逆门。 本来是两位信息经过与门后变成一位信息，这里丢失了一位信息。

朗道尔原理

1961 年，IBM 工程师 Rolf Landauer 发现擦除一点信息需要热力学成本，即产生至少 kTln2 的热量，而写入信息则不需要热力学成本。 其中 k 是玻尔兹曼常数，T 是环境温度。 这就是著名的兰道尔原理，通过它我们知道信息也具有物理属性。 而经典计算机基本上都是不可逆的运算，所以经典计算机会产生越来越多的热量。

这是兰道尔在思考麦克斯韦妖时得出的结论：因为处理信息是需要代价的，而妖的记忆不可能是无限的，总会删除一些记忆导致熵增加，所以妖不可能存在。

于是人们认为，如果将经典计算机中的不可逆运算转化为可逆运算，那么问题就迎刃而解了。 理论上，一种称为酉变换的操作，一种对量子态的操纵，就足以解决经典计算机的散热问题。 然而，经典计算机擅长微分方程类型的问题，即模拟经典物理系统。 但是，如果仍然使用微分方程来描述量子物理系统，经典计算机就很难承担这一重任。 所以后来费曼等物理学家提出将经典比特直接转化为量子比特，直接用量子来模拟量子系统。 （理查德·费曼的声音就是我们在本文开头的视频中听到的声音）

量子的天然优势——并行计算

在经典计算机中，我们使用二进制来提高计算效率。 如果想让经典计算机计算100+100，首先要将十进制的100转为二进制的1100100。在经典计算机中，需要7个不同状态的晶体管才能用二进制表示1100100。 通俗地说，晶体管就是一个位，只能表示1或0（高电平或低电平）。 量子计算机不同。 一个量子二态系统就是一个比特，叫做量子比特qubit。

双态系统就像电子的自旋和光子的极化。 最流行的解释是薛定谔的猫。 当薛定谔的猫不被观察时，从量子力学的角度来看，它既是死的又是活的，处于生与死的叠加状态。 该状态遵循量子态叠加原理。 如果我们将经典计算机中的晶体管换成薛定谔的猫，那么薛定谔的猫就可以同时代表1和0，而不是经典计算机中的1或0。 两只薛定谔的猫可以代表 00、01、10、11 四种状态，而经典计算机中的两位只能取这四种状态中的一种。

那么对于n位，经典位只能表示1个数，而量子位理论上可以同时表示2^n次幂数。 这是经典计算机和量子计算机最大的区别。 2^n 的指数增长的巨大诱惑力激发了人们对量子计算机的极大兴趣——自然并行计算的好处。

如何实现量子计算机 难点一：用什么做量子比特？

从物理学家的角度来看，理论上，两能级量子系统都可以作为量子比特。 例如，电子的自旋在不被测量时处于既上又下的叠加态，而一旦被测量，它就会出现不是上就是下的本征态。

难点二：量子计算机的算法？

由于算法是计算机的灵魂，而经典算法只适用于经典比特，即使量子芯片做得再好，经典算法也无法用在量子芯片上。 1994 年，贝尔实验室的 Peter Shor 发表了 Shor 算法，可以对大数进行质因数分解。

质因数分解问题是一个NP问题，即其复杂度在经典算法中无法在多项式时间内完成。 质因数分解的一般算法复杂度为O，即e^n，n是指这个数在二进制中表示的位数。 目前，使用最快的经典超级计算机分解一个 300 位（十进制）素因数分解大约需要 15 万年。 这也是为什么大数的质因数分解可以用来加密的原因，因为经典的计算机暴力几乎不可能计算出哪两个质数相乘来解密。

但是秀尔算法可以把复杂度降低到(logN)^3，也就是说秀尔算法把一个NP问题变成了P型问题。 用秀尔算法分解300位的质因数分解，理论上也只需要不到1分钟。

此外，秀尔还解决了一个困扰物理学家十多年的难题。 如果用秀尔算法用量子位来计算，结果还是一堆量子位，我们需要对结果进行测量。 但是薛定谔的猫告诉我们，测量猫生死的概率是50%，所以理论上测量出来的结果还是随机的。

Shor 告诉我们，通过使用 Shor 的算法，所需的数据将是连贯的和建设性的，而不需要的数据将是连贯的和取消的。 最终测量正确的概率为1。由于现在银行乃至政府的机密信息都是基于素数的RSA算法进行加密，因此自从秀尔算法问世以来，量子计算就引起了世界各国政府的浓厚兴趣1994年，就连美国国防高级研究计划局DARPA（DARPA提出并投资了Internet、Unix系统、全球定位系统GPS等）也加入了竞争。

2001年，IBM的中国研究员Isaac Zhuang和他的研究团队通过核磁共振演示了Shor的算法，即一个由5个氟原子和2个碳原子组成的分子，利用每个原子的核自旋来作为一个量子比特，7个量子比特是相当于2^7，也就是128个经典位。 利用这台微型量子计算机，用秀尔算法对15的质因数进行分解，得到的结果是3和5，成功证明了秀尔算法的可行性。 后来证明，秀尔算法也可以用来求解离散对数问题。 量子计算机的算法除了秀尔算法外，还有Grover、QAOA、VQE等。 我们稍后会再次提到 Grover 算法。

难点三：如何保持量子相干性？

量子的相干性很难维持。 处于叠加态的量子即使不被测量，也会与周围环境发生量子纠缠而成为确定态，即成为经典态，即俗称的波函数坍缩。 这个过程称为量子退相干。 为了抵抗量子退相干的影响，我们主要有两种方法：

量子纠缠

量子纠错； 类似于经典计算机，以牺牲资源为代价，比如把8个量子比特作为一个，不管有一个还是两个退相干，少部分退相干的量子被修正。 使用纠错码存在两个问题：一是量子计算每一步的操作必须低于一定的比例，这样才能纠正错误，比如错误率低于1% ; 另一个是纠错码需要大量的物理层。 逻辑层面的量子比特被用来对逻辑层面的量子比特进行编码，这给量子计算在硬件层面的实现带来了很大的障碍。

操纵量子系统的更好技术：

因为量子力学的一些特性，即使实现了同样的操作，在物理层面以不同的方式控制量子比特，也会带来完全不同的保真度。 通过使用更好的方式优化这些操作，可以将错误率控制在量子纠错的阈值以下，为更通用的量子纠错铺平道路。

到目前为止量子计算能破解比特币吗，量子计算机在理论上没有任何问题。 至于物理层面，量子芯片是怎么工作的量子计算能破解比特币吗，有什么用。 这是目前各大机构的主要研究方向，需要在保持相干性的同时保证量子位的集成。 实现量子比特的典型硬件实现方案主要包括光学系统、半导体量子点、超导电路、冷原子、离子阱等。 谷歌、IBM、阿里达摩院等行业研究机构致力于通过超导电路实现量子芯片。

今年9月，谷歌宣布使用包含53个有效量子比特的处理器成功实现“量子至上”（Quantum Supremacy）。 需要指出的是，“量子至上”是指实现量子计算在某些问题上可以做到经典计算机做不到的事情，实现“量子”对“经典”的霸权，是一种新技术。 对旧技术的霸权，不是某个公司或研究机构在国际上处于领先地位，而是产生了对其他公司和研究机构的霸权。

区块链加密算法

这里，我们以比特币为例，介绍区块链的加密算法。 比特币加密算法有两类和三种，分别是椭圆曲线算法、SHA256哈希算法和RIPEMD160哈希算法。 大致流程如下：

私钥 -> 椭圆曲线算法 -> 公钥 -> SHA256 -> RIPEMD -> SHA256 -> SHA256 -> 地址

单向箭头表示经典计算中的算法是不可逆的，公钥不能从地址逆向，私钥不能从公钥逆向。 由于量子计算是将经典计算中的不可逆转化为可逆，为了说明方便，我们从地址开始倒推。

哈希算法

在比特币使用的两种哈希算法中，SHA256是在SHA-2之下细分的一种算法。 是美国国家安全局制定的密码哈希函数算法标准； RIPEMD（RIPE Message Digest）也是一种哈希函数。 对于对称加密和散列函数，存在量子攻击，但危险性较小。 Grover算法只能将经典计算下的2^256难度降低到2^128，这还是天文数字，而且从公钥到地址需要1次RIPEMD和3次SHA256哈希运算，对对称加密是颠覆性的. 在量子算法诞生之前，我们不必太过担心。

由于比特币挖矿使用的是SHA256算法，如果未来诞生远优于Grover算法的量子算法，并且随着时间的推移，量子计算机的速度越来越快，价格越来越低，那么量子计算机就会在比特币挖掘中确实优于经典计算机。 但是这个过程就像是从CPU挖矿到GPU挖矿再到ASIC挖矿，我们完全不用担心。

椭圆曲线算法

从公钥反推到私钥只有一个障碍---椭圆曲线密码学（Elliptic curve cryptography），简称ECC，是一种建立公钥加密的算法，即非对称加密。 在数学上，椭圆曲线可以表示如下：

比特币基于secp256k1曲线的椭圆曲线数字签名算法（ECDSA）就是椭圆曲线的一种。 由于椭圆曲线算法依赖于离散对数问题，而前面提到的秀尔算法可以用来求解离散对数，理论上，具有一定有效量子比特的量子计算机将对解决比特币的椭圆曲线算法构成威胁。

但是secp256k1曲线的安全性是2^128，所以即使Shor算法将其复杂度降低到128^3，理论上攻击secp256k1曲线的量子计算机也至少要有1500个逻辑量子比特。 考虑到要使用量子纠错，实际需要的物理量子比特数会远高于这个数字。

谷歌今年 9 月公布的最大通用量子计算机只有 53 个物理量子比特，错误率极高，只能在接近绝对零的实验室条件下运行。 同时，谷歌使用的超导芯片在可扩展性方面自然存在诸多问题，因此如何在保持可控性的同时增加更多的量子比特，在可预见的未来将是一个非常大的挑战。 虽然无法准确预测量子计算的发展速度，但比特币的 256 位 ECDSA 密钥预计至少在 2040 年之前都是安全的。

比特币本身已经具有一些内置的抗量子特性。 如果你有使用比特币的好习惯，即一个钱包地址只使用一次，那么你的公钥只会在你花费比特币时向全网广播。 . 此时，量子计算机将只有很短的时间来破解你的私钥，也就是从交易发出到交易信息被加入区块的时间。

假设你没有使用比特币的好习惯，量子计算机的发展突飞猛进，所有常见的公钥算法都被破解了。 比特币还有一个杀手锏，就是升级了加密算法。 众所周知，如果一种技术手段能够破解一种密码，那么它一定能够创造出另一种无法破解的密码。 目前，在用于量子安全的公钥加密算法中，比特币专家倾向于支持基于 Lamport 签名的加密系统。 虽然 Lamport 签名的计算速度非常快，但主要有两个缺点：

签名会非常大，至少有几kB（比现在大40-170倍），这对比特币的整体可扩展性非常不利。

创建每个密钥对时，您需要设置可以使用该密钥签名的有效最大签名数。 如果签名超过这个数量，它将变得不安全。 但是如果每个地址只使用一次，这不是一个大问题。

此外，在密码学家对后量子密码学的研究中，超奇异椭圆曲线同源密钥交换（SIDH）也有望取代目前传统的椭圆曲线密钥交换（ECDH）。 基于高维向量空间的密码学，即格密码学，也会增加另一个宇宙层次的破译难度，足以抵抗量子计算。 新的公钥算法将作为软分叉添加到比特币中，比特币用户只需将比特币发送到新创建的地址即可实现量子安全。

密码学与计算机科学

当我们研究量子计算机对区块链的挑战时，很难不反复思考密码学与计算机科学的关系。 历史事实总是惊人地纠缠和相似。 破译密码是计算机诞生的源泉。

二战期间，计算机科学与人工智能之父艾伦·图灵受雇于英国皇家海军破译德国军事密码。 当时，纳粹军方拥有一套复杂精密的通信安全系统——恩尼格玛密码机。 它由一系列不断变化的转子组成，其复杂度高达1大本或10亿亿，以当时的破译手段极难攻克。 图灵用他设计的破译机bombe首先破译了Enigma，然后破译了当时纳粹军方使用的几乎所有级别的通信加密系统，包括Tunny密码。 这让盟军很好地掌握了德国的军事指挥和计划，硬生生的帮助盟军至少提前两年打败了纳粹德军，结束了二战。

图灵提出了一种抽象人类计算行为的数理逻辑机，即图灵机。 后来，现代计算机之父冯诺依曼利用冯诺依曼结构完成了图灵机的实现。 以他的名字命名的图灵测试被广泛用作判断机器是否智能的测试方法。 图灵在数学和逻辑方面的辉煌成就，也为计算机的发展乃至整个数字时代树立了宏伟的蓝图。 为表彰他的开创性贡献，以他的名字命名的计算机界诺贝尔奖——图灵奖于1966年正式设立，成为该领域的最高奖项。

对于即将到来的量子时代，作为区块链从业者，我们更应该怀着敬畏和期待迎接它的到来。 量子计算机的价值在于解决典型的NPC等问题，如三体、七桥、蛋白质折叠、地震预报、天气预报等。量子计算机不是万能的，不能替代经典计算机。