如果量子计算时代到来，我们的比特币会安全吗？

量子计算对挖矿的影响更多是芯片升级的经济问题，而不是安全问题。

作者：李华和安比实验室创始人郭宇

更正：郭宇

每次有关于量子计算的新闻，人们都会担心比特币。原因很简单，比特币是基于密码学的，而密码学之所以能够成立，是基于某种计算上的不可能性。如果量子计算使原本不可能或难以实现的计算变得可计算，那么这种密码学方法将失败。但这种担心是多余的。原因同样简单：我们只是有量子计算无法完成的计算，不是吗？建立在这种计算基础上的密码学方法（quantum-safe cryptography），量子计算无法破解，然后比特币可以升级为这种密码学方法。 “晶格难题”是一个典型的代表，即使对于量子计算，它在计算上仍然是不可能的。基于人类的“无知”，我们基本上总能在密码学的保护下找到生存之道。

比特币中的密码算法我们知道，比特币钱包地址对应一个公钥和一个私钥。只有私钥才能使用钱包里的比特币，但是​​私钥是安全的，不能通过钱包地址或公钥计算。

这是如何实现的？让我们从台球厅开始。你去台球厅打台球，你把一个球放在台球桌底部边缘的一个点，我们称之为A点，然后你击球，假设你击球非常用力，那么球从点 A ，总是击中台球桌一侧的一个点，然后从该点反弹到台球桌另一侧的另一个点......它可能会这样做 B 次（比如 10,000 次），最后停止在台球桌一侧的一个点，称为C点。此时你的朋友来了，他可以看到台球在C点的位置，你告诉他球在A点的初始位置和击球的角度，问他球在中间弹了多少次，也就是B是多少？你的朋友应该暂时无法回答。这是一个简单的公钥和私钥生成算法，C（位置）是公钥，B（计数）是私钥。如果我们知道A点和B点反弹，我们可以得到C点；但是如果我们只知道A点和C点，就很难计算出B点的反弹次数。在真正的密码学中，台球桌的边被一条椭圆曲线代替，A是椭圆曲线上的一个不动点(实际上是击中自身的椭圆组（球从该点的切线击中）。 )，小球在椭圆组内碰撞了B次，最后落在了椭圆组的一个点上，该点再次被映射，椭圆组上有一个点C。 C是公钥，B是私钥。这就是著名的椭圆曲线算法，用于生成公钥和私钥，是比特币系统中的第一个密码学方法。椭圆曲线算法很难破解（基于“离散对数难题”），但也不是不可能破解的。足够强大的量子计算可以找到一个多项式算法，通过A和C计算出B，也就是可以通过公钥计算出私钥。 因此，如果真的进入量子计算时代，椭圆曲线算法就需要被新的抵抗量子计算的算法所取代。

量子计算和椭圆曲线算法

比特币使用的椭圆曲线数字签名算法的安全性为2^128（secp256-k1曲线组的阶数接近2^256，椭圆曲线攻击算法的复杂度约为O(sqrt (N)) ，取 2^256 的平方根得到 2^128)。这是一个天文数字。在量子计算的情况下，使用 Peter Shor 提出的 Shor 算法，攻击椭圆曲线的复杂度约为 O(log(N)^3) 。对于比特币，理论计算阶数为 128^3 次。相关论文研究表明，构建攻击 secp256-k1 曲线的量子计算机，假设计算机可以将误码率降低到 10^-4，希望在使用 170 万量子比特的情况下，完成计算7 天。

在比特币系统中，还有另一种加密方式，哈希函数SHA-256，用于生成公钥对应的钱包地址。算法很好理解，就是将输入以不可逆的方式转换为输出。它具有很强的单向性，不可能通过输出来计算输入。因此，哈希函数只能通过蛮力破解，即改变输入值，反复尝试，直到可以用一定的输入值计算出目标输出值。

与经典计算机相比，量子计算机在蛮力搜索方面具有相当大的优势，但它仍然是多项式级别的性能优化，我们可以通过将安全比特数增加一倍来保持安全性，例如使用 SHA-512。比特币钱包地址是通过两次散列公钥得到的，一个是SHA-256，另一个是RIPEMD-160（另一个散列函数）。量子计算很难突破这两个哈希阈值。 “碰撞”公钥。

量子计算和 SHA-256

目前可以加速计算SHA-256的量子算法是Lov Grover在1996年提出的Grover算法，可以将蛮力搜索的性能提升到一个平方倍。假设我们在一个巨大的 N×N 方格中寻找一根针，经典计算机需要逐个搜索每个方格，最坏的情况是 N×N 次；但是Grover的算法即使在最坏的情况下也只需要搜索N次。

总结一下：比特币有两种基本的密码算法，一种是椭圆曲线算法，一种是哈希函数SHA-256。目前可以找到并破解前者的高效量子计算方法；但是，尚未找到针对后者的有效量子计算方法。当然，破解的前提是量子计算真的够发达。要知道，谷歌最新的量子芯片只有 54 个量子比特。

我们的比特币安全吗？如果我们进入量子计算时代，我们只需要用抗量子计算的密码算法生成公钥、私钥和钱包地址。但是如果用户没有升级公钥和私钥，钱包里的比特币会被盗吗？答案是否定的。

大致有以下几种情况：1.如果钱包地址中的比特币从未被使用过，那么该地址的公钥是未知的，只有钱包地址（公钥才需要）给定当我们在一个地址上花费比特币时，但即使只花费一次，公钥也会广播到整个网络）。如前所述，SHA-256 很难被量子计算破解，这意味着其他人无法从钱包地址计算出公钥。因此，即使可以从公钥中计算出私钥，那些没有暴露公钥的钱包地址也是安全的。 2.如果你有良好的比特币使用习惯，一个钱包地址只使用一次，那么同样，新地址的公钥也是未知的，新地址中的比特币是安全的。 3. 如果用户重复使用某个钱包地址，则该地址对应的公钥被暴露；如果量子计算破解了椭圆曲线算法，地址中的比特币就有被盗的风险。据统计，截至目前，有近500万比特币存储在公钥暴露的地址中，近177万比特币使用P2PK地址，这是最早的比特币账户格式。密钥是公开的，包括被认为是中本聪的账户。如果这些比特币不改变地址，它们就属于量子计算攻击的范围。 （数据来源：Ambi Labs） 除了钱包地址，SHA-256 还用在了比特币系统的一个重要地方，那就是挖矿。挖矿是对哈希函数进行暴力破解的过程。通过调整输入值，使落在目标范围内的输出值“碰撞”。如前所述，理论上量子计算机芯片可以在暴力搜索中“翻车”经典计算机芯片，但我们也需要考虑到它的技术发展水平和芯片制造工艺。另外，随着技术的发展，芯片也在不断升级，量子计算对挖矿的影响更多的是芯片升级的经济问题，而不是安全问题。

量子计算下的安全性：随着量子计算的发展，量子安全密码学也在快速发展。其中最具代表性的是“lattice cipher”，它是一种基于格的密码系统（lattice-based cryptography）。 “格”是一个整数系数的向量空间，可以理解为一个高维空间。它有两个基本的“格困难”，一个是最短向量问题，另一个是最近向量问题。求解此类问题需要指数时间复杂度，那么如果因子是多项式，则此类问题没有多项式时间算法，对于量子计算来说也是计算上的不可能。这听起来有点抽象，或许可以这样理解：用钢笔在一张A4纸上画很多黑点，然后换一支笔在纸上画一个红点，我们需要做的就是找到距离红点最近的黑点，这个很容易；现在从A4纸的二维空间到三维空间，想象空间中有很多黑点漂浮，然后放一个红点进去，也找到离红点最近的一个。黑点难度不是很高，但和二次元空间相比，它的难度却不是一个档次的。现在，我们把三维空间变成了一个三百维空间，给定一个红点找到离它最近的黑点，这个黑点肯定是存在的，但是想想，是不是几乎不可能找到呢？这就是网格难度的问题。格空间类似于椭圆曲线。在椭圆曲线上，可以有一个数学公式（椭圆曲线算法）将公钥和私钥放在一个方程的两端。把东西放在一个等式的两端，然后我们可以使用这些公式来生成公钥和私钥。在椭圆曲线算法中，由于“离散对数问题”，传统计算机无法通过私钥计算出公钥；在格密码算法中，由于“格难度问题”，量子计算机无法通过私钥计算出公钥。 格密码学发展迅速。基于格，我们不仅有抗量子计算的公钥和私钥，还有一系列抗量子计算的、对应经典密码学概念的密码算法或协议。它们可用于数字签名、加密等。密钥交换、零知识证明等。“宇宙相信加密。加密容易，解密难。”在可预见的未来，情况仍将如此。所以，别担心，比特币如此，区块链也是如此。

参考文献

[1] Arute、Frank、Kunal Arya、Ryan Babbush、Dave Bacon、Joseph C. Bardin、Rami Barends、Rupak Biswas 等人。 “使用可编程超导处理器的量子霸权。”自然 574，没有。 7779 (2019): 505-510.[2] Andreas M. Antonopoulos 回答有关量子计算的问题：

;[3] 绅士，克雷格。 “使用理想格的完全同态加密。”在股票，第一卷。 9，没有。 2009 年，第 169-17 页8. 2009.[4] Aggarwal、Divesh、Gavin K. Brennen、Troy Lee、Miklos Santha 和 Marco Tomamichel。 “对比特币的量子攻击比特币的算法，以及如何防范它们。” arXivpreprint arXiv:1710.10377 (2017). [5] Stewart, I., D. Ilie, Alexei Zamyatin, Sam Werner, M. F. Torshizi 和 William J. Knottenbelt。“致力于量子抵抗：比特币对快速量子计算攻击的缓慢防御。” Royal Society openscience 5, no . 6 (2018): 180410.[6] Regev, Oded。“基于格的密码学。”在年度国际密码学会议上，第 131-14 页1. Springer，柏林，海德堡比特币的算法，2006.