量子计算时代会影响比特币的安全性吗？

每次有量子计算的消息，人们都会担心比特币。 原因很简单，比特币是建立在密码学基础上的，而密码学之所以能够成立，是基于某种计算上的不可能性。 如果量子计算使原本不可能或难以实现的计算在计算上可行，那么这种密码学方法就会失败。

但这种担心是不必要的。 道理同样简单：只要我们有量子计算无法完成的计算，我们就不行吗？ 建立在这种计算基础上的密码学方法（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 Second-rate。

相关论文研究表明，构建攻击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 Lab）

除了钱包地址，比特币系统还有一个重要的地方用到了SHA-256，那就是挖矿。 挖矿是暴力破解哈希函数的过程，通过调整输入值来“敲出”落在目标范围内的输出值。

如上所述，从理论上讲，量子计算机芯片可以在暴力搜索中“碾压”经典计算机芯片，但我们还需要考虑其技术发展水平和芯片制造工艺。 此外量子计算对比特币的影响，芯片随着技术的发展不断升级，量子计算对挖矿的影响与其说是安全问题，不如说是芯片升级的经济问题。

量子计算下的安全：格密码学

在量子计算发展的同时，量子安全密码学也在快速发展，其中最具代表性的就是“格密码学”，它是一种基于格的密码系统（latTIce-based cryptography）。

“格”是一个向量空间，其系数是整数。 可以理解为高维空间。 它有两个基本的“格难度问题”，一个是最短向量问题，一个是最近向量问题。 解决此类问题需要指数时间复杂度，所以如果因子是多项式，则这类问题没有多项式时间算法，对于量子计算来说也是一个计算上的不可能。

这听起来有点抽象，或许可以这样理解：用一支笔在一张A4纸上画很多黑点，然后换一支笔在纸上画一个红点，我们需要做的就是要做的就是找到距离红点最近的黑点很容易； 现在从A4纸的二维空间到三维空间，想象一下空间里漂浮着很多黑点，然后在里面放一个红点，同样求离红点最近的距离，这不难度很大，但是和二次元空间相比，它的难度已经不是一个档次了。

现在，我们把三维空间变成三百维空间，给定一个红点去寻找最近的黑点，这个黑点肯定是存在的，但是想想，是不是几乎不可能找到呢？ 这就是网格难度的问题。

格空间类似于椭圆曲线。 在椭圆曲线上，可以有一个数学公式（椭圆曲线算法），把公钥和私钥放在等式的两端。 在格空间中，也有数学公式（比如LLL算法）可以把Put things放在一个等式的两边，那么我们就可以用这个公式来生成公钥和私钥。

在椭圆曲线算法中，由于“离散对数问题”，传统计算机无法通过私钥计算出公钥； 在格密码算法中，由于“格难度问题”，量子计算机无法通过私钥计算出公钥。

格密码学发展迅速。 基于Lattice，我们不仅有抗量子计算的公钥和私钥，还有一系列抗量子计算的经典密码概念对应的密码算法或协议。 它们可用于数字签名、加密密钥交换、零知识证明等应用领域。

“宇宙相信加密，加密容易，解密难。” 在可预见的未来，它仍将如此。 所以，别担心，比特币如此，区块链也是如此。