比特币的量子攻击及其防范

对于固定的门错误率，开销因子cτ的上限是反转256位哈希的成本（最大难度）。由于量子算法以叠加方式运行哈希，因此量子计算能力无法直接转换为哈希速率。然而，我们可以将有效的哈希率hQC定义为经典机器上的预期调用数除以50GHz（a）pgDnQ（b）下的pgdhqc（TH/s）图1。单个量子计算机的区块链攻击性能取决于物理门错误率pg（内部机器规范）和挖掘难度D（由区块链协议设置）。（a） 在50GHz时钟速度下运行的量子计算机的有效哈希率Hqc，该时钟速度处于可预见时钟速度的乐观极限。哈希率随着难度的平方根而增加（请注意对数比例）。对于并行运行的d量子计算机，有效哈希率增加了2.56倍√d、 （b）量子计算机发出的物理量子比特数。在量子计算机上找到解决方案的预期时间，即。寰球公司≡N/tτ=0.28×s√Dcτ（D，pg）。由于时间开销是有界的，因此有效的散列率随着难度的平方根逐渐提高，反映了quantumprocessors可获得的二次优势。Grover算法可以在d量子处理器上并行化。在optimalstrategy中，每个处理器都致力于搜索潜在解决方案的整个空间，找到解决方案所需的oracle调用的预期数量为#O=0.39×#O/√d【GWC00】。这意味着找到解决方案的预期时间为τk=0.39×τ/√d、 以及在并行ishQC中使用d量子处理器的有效哈希率，k=2.56×hQC√d、 Grover算法所需的逻辑量子位数量固定为2402，与难度无关。

所需的物理量子位数为2402×cnQ（D，pg），其中cnQ是由于量子纠错而产生的空间开销，即物理量子位，也是难度和门错误率的函数。在附录A中，我们展示了如何计算纠错所产生的时间和空间开销。结果显示了区块链2020 2025 2030 2035 204010141016101810201022量子计算机相对于单个量子计算机的性能图。该图显示了比特币网络（蓝色条纹曲线）与单个量子计算机（红色条纹曲线）的哈希能力（以每秒哈希数为单位）的两个估计值，作为未来25年时间的函数。我们给出了更多和更少的乐观估计和不确定性区域（蓝色和橙色区域）。该模型在附录B和附录C中有详细描述。在2028年之前（以更乐观的估计），将不会有任何具有足够多量子比特的量子计算机来实现Grover算法。为了进行比较，黑色虚线显示了当前单个ASIC设备的哈希率。攻击如图1所示。为了将这些结果与可实现的规格联系起来，我们将重点放在超导电路上，到目前为止，超导电路在候选量子技术中具有最快的量子门速度，并为实现可扩展性提供了一条有希望的途径。

假设在s=66.7MHz[KKL+17]的当前器件上可达到的最大门速度，并且假设物理门错误率为pg=5×10，在实验上具有挑战性，但并非不可信-4，接近当前困难度D=10，开销为cτ=538.6，cnQ=1810.7，这意味着使用nQ=4.4×10物理量子位时，hQC=13.8GH/s的有效哈希率。这比货架上的ASIC设备慢1000多倍，其灰分率达到14/s；原因是容错T门构造的量子门速度慢和延迟。量子技术将在未来几十年内显著扩展，量子时钟速度、门精细度和量子比特数可能会被量子摩尔定律的aquantum版本所取代。在超导量子电路技术当前改进的指导下，附录B和附录C给出了此类改进的预测。这使我们能够估计量子计算机的功率随时间的变化，如图2所示。显然，量子计算机要在这项任务上胜过经典机器还需要一段时间，而当它们做到这一点时，单个量子计算机将不会拥有大多数散列能力。然而，即使相对于竞争对手的classicalUsing（例如AntMiner S9）而言，功率略有提高，也可以在https://asicminermarket.commachines，某些攻击变得更加有利，例如对使用智能合约奖励池矿商扣留其区块的采矿池的攻击【VTL17】。例如，假设附录A中列出了乐观的假设，其中有效的哈希率比例如EHQC=0.04×s√D、 在D=10GHz和s=50GHz时，一组20个并行运行的量子机器的分数哈希功率相对于总哈希功率为0.1%。这将允许以最低的贿赂成本对池采矿进行量化攻击，从而将池收入减少10%。B

使用基于secp256k1曲线的椭圆曲线数字签名算法对比特币中的签名进行攻击。该系统的安全性基于椭圆曲线离散对数问题（ECDLP）的复杂性。虽然这个问题仍然被认为是硬经典问题，但Shor【Sho99】给出了解决这个问题的有效量子算法。该算法意味着一台足够大的通用量子计算机可以有效地计算与给定公钥相关的私钥，从而使该方案完全安全。比特币的含义如下：1。（重复使用地址）要使用某个地址的比特币，必须显示与该地址关联的公钥。一旦公开密钥在aquantum计算机面前显示，地址就不再安全，因此不应再次使用。虽然在比特币中，总是使用新地址已经是建议的做法，但实际上并不总是这样。任何包含比特币且公开密钥的地址都是完全不安全的。2.（已处理的交易）如果交易是从之前未被发现的地址进行的，并且该交易被放置在区块链上，并有几个区块跟随它，那么该交易对于量子攻击是合理安全的。私钥可以从已发布的公钥中派生出来，但由于地址已被使用，因此必须结合对网络进行散列来执行双重开销攻击。正如我们在第III A节中所看到的，即使使用aquantum计算机，一旦事务后面有许多块，就不太可能发生双重开销攻击。3.（未处理的交易）在将交易广播到网络之后，但在将其置于区块链之前，它面临着量子攻击的风险。

如果在将交易放在区块链上之前可以从广播公钥中派生出密钥，那么攻击者可以使用该密钥将新交易从同一地址广播到自己的地址。如果攻击者随后确保该新交易首先放置在区块链上，那么他可以有效地窃取原始地址后面的比特币。我们认为第（3）项是最严重的攻击。要确定这种攻击的严重性，必须准确估计量子计算机计算ECDLP所需的时间，以及这是否可以在接近块间隔的时间内完成。对于一个具有n位素数场的实例，最近优化的分析表明，量子计算机可以使用9n+2dlog（n）e+10个逻辑量子位和（448 log（n）+4090）to off oli gates来解决这个问题【RNSL17】。比特币使用n=256位签名，因此To-fff-olipg10-65 x10-610-55x10-510-45x10-410-3020406801010010-65 x10-610-55x10-510-45x10-410-3 （分钟）（a）10-65 x10-610-55x10-510-45x10-410-301×1062×1063×1064×1065×10610-65 x10-610-55x10-510-45x10-410-3pgnQ（b）图3。以10GHz时钟速度运行的量子计算机对使用椭圆曲线数字签名算法的数字签名进行攻击的性能。（a） 根据物理门错误率pg.（b）量子计算机使用的物理量子位数，中断签名的时间（分钟）。闸门为1.28×10，可略微平行至深度1.16×10。每个To offoli都可以使用一个T门深度的小电路来实现，一个电路并行作用于7个量子位（包括4个辅助量子位）[Sel13]。根据Sec的分析。我们可以估计对数字签名进行量子攻击所需的资源。与块挖掘一样，主要时间是通过提取逻辑T门的神奇状态来消耗的。

在量子处理器上求解ECDLP的时间为τ=1.28×10×cτ（pg）/s，其中时间开销cτ现在仅取决于门错误率，s再次是时钟速度。所需物理量子位的数量为Nq=2334×cnQ（pg），其中第一个因素是逻辑量子位的数量，包括4个逻辑辅助量子位，CNQI是空间开销。图3给出了量子计算机攻击数字签名的性能。使用物理门错误率为pg=5×10的表面代码-4，开销因子为cτ=291.7，cnQ=735.3，在66.6 MHz时钟速度下，使用1.7×10物理量子位解决问题的时间为6.49天。期待性能改进，10GHz时钟速度和错误率为10-5，使用485550量子位在30分钟内破解签名。后者使得第（3）项中的攻击非常可能，并将使当前的比特币系统高度不安全。根据附录B和C中描述的模型，图4给出了quantumcomputer中断签名方案所需时间随时间变化的估计值。2020 2025 2030 2035 20400200400600800100012001400Time to break signature scheme for quantum computerFIG。该图显示了量子计算机破解签名方案所需的时间（秒）的两个估计值（红色曲线），作为未来25年时间的函数。我们给出了或多或少的乐观估计（红线）。这些模型在附录C中有详细描述。根据这一估计，签名方案最早可在2027年在不到10分钟（600秒，黑色虚线）内被破解。C、 量子攻击的未来增强我们描述了使用已知量子算法和错误纠正方案对比特币协议的攻击。

虽然对量子计算速度和可伸缩性的一些估计似乎是乐观的，但重要的是要记住，有几种途径可以改善量子计算机的性能，以解决上述问题。首先，这里假设的纠错码是表面码，它需要大量的经典计算开销来进行状态提取、错误综合征提取和校正。其他由横向通道和非通道通道组成的代码可以克服慢态蒸馏的需要【PR13】。事实上，通过使用无测量协议，可以完全消除症状提取和纠正的经典处理过程中的缓慢，例如[PSBT10]，在最近的分析中，该协议显示的错误阈值[CJS16]仅比测量重表面代码差约5倍。这可能会显著提高纠错的总体速度。其次，随着更先进的量子计算技术的发展，量子电路的逻辑门计数可能会减少。例如，使用先前工作[SVM+17]中分析的特定大型示例问题（包括oracle实现），在解决量子算法的旧[HHL09]和新[CKS15]线性系统之间实现了对具体门计数的直接比较，显示出几个数量级的改进。鉴于quantum Shor和Grover算法已经得到了很好的研究和高度优化，人们预计不会有如此显著的改进，尽管可能会有一些改进。第三，不同的量子算法可能会提供相对的加速。

Kaliski最近的工作【Kal17】提出了一种离散对数问题的量子算法：使用对所谓的“魔盒”子例程的查询，计算m的最重要位。通过使用目标值的明智选择的幂重复查询，找到mgiven b=am，其中b是一个已知的目标值，a是一个已知的基，m的所有位都可以计算出来，问题就解决了。因为不同的位是一个接一个地解决的，所以这个问题可以分配到多个量子处理器。每个处理器都需要一些与解决整个问题相当的逻辑量子位，但通过并行化可以减少总时间。此外，量子错误校正的开销可能会减少，因为电路的量子傅立叶变换部分的相位不需要像原始Shor算法那样精确。四、 对策a。工作的替代证明正如我们在上一节中所看到的，量子计算机可以使用Grover搜索来执行比特币工作证明，使用的哈希数比经典方法所需的哈希数少。在本节中，我们将研究可能不太具有quantumadvantage的其他工作证明。我们希望从工作证明中获得的基本属性是：1。（困难）问题的困难程度可以根据网络中可用的计算能力进行调整。2.（不对称性）验证工作证明是否成功完成要比执行工作证明容易得多。3.

（没有量子优势）量子计算机无法比经典计算机更快地完成工作证明。比特币工作证明完成了第（1）、（2）项，但我们希望找到一个在第（3）项上做得更好的替代工作证明。作者也进行了类似的研究，试图找到工作证明，而不是（3）寻找ASIC无法加速的工作证明。实现这一点的一种方法是查看内存密集型工作证明。针对这一点，已经提出了几种有趣的候选方法，例如动量[Lar14]，基于在哈希函数中查找碰撞，布谷鸟循环[Tro15]，基于在随机图中查找常量大小的子图，以及基于广义生日问题的Equihash[BK17]。这些也是更具量子抗性的工作证明的很好的候选者。这些方案都基于hashcash风格的工作证明，并使用以下模板。设h：{0，1}*→ {0，1}nbe是一个加密安全的哈希函数，H=H（header）是块头的哈希。然后，目标是找到一个nonce x，使得H（H k x）≤ t和P（H，x），A.Scherer，某些谓词P的个人交流。标头和nonce必须满足谓词pm这一事实意味着，最佳算法将不再简单地连续迭代nonce x。具有这种形式的功证明也可以确保参数t仍然可以选择以改变难度。在接下来的内容中，我们将分析此模板以证明动量做功，因为这可能与已知的量子下界有关。对于功的动量证明，leth：{0，1}*→ {0，1}`是另一个具有n的哈希函数≤ `. 在最初的Momentumproposal中，HCL可以被视为SHA-256，并具有内存密集型哈希函数，但这对于我们的讨论并不重要。

工作证明是找到H、a、b，使H（H k a k b）≤ t和h（h k a）=h（h k b）和a，b≤ 2`. （1） 首先，假设哈希函数h，hc可以在单位时间内计算，让我们研究运行时间以解决此工作证明。取子集S {0，1}`并计算所有a的h（h k a）∈ S、 我们预计会发现约| S |/2 `多次碰撞。请注意，通过使用适当的数据结构，可以在大约| S |的时间内找到这些冲突。一种算法如下所示。对于每个H，我们评估一个子集S和| S |/2 `多对a，b，使得H（H k a）=H（H k b）。对于每次碰撞，我们测试h（h k a k b）≤ t、 预计，我们将不得不多次执行第二次测试2n/t。因此，我们必须尝试的H的数量约为m=max{1，n+\'t | s |}，因为我们必须尝试至少一个H。对于每个H，我们花费时间| s |，总运行时间为m | s |。我们看到，当| S |=qn+`t时，它是最小的，也就是当m=1时，我们只需尝试一个H。这个最佳运行时间是t=qn+`t，为了实现它，我们必须使用与运行时间大小相等的内存，这可能是禁止的。对于一些较小的内存| S |<qn+`t，运行时间将为+`+1t | S |。现在让我们看看量子计算机上的运行时间。在量子计算机上，我们可以做到以下几点。如果存在a、b，则称H为良好∈ S使得h（h k a k b）≤t和h（h k a）=h（h k b）。测试H是否良好需要找到碰撞，因此需要Aaronsonand Shi【AS04】的量子查询下限至少为2/3次。请注意，这个下限很紧，因为使用Ambainis的元素区分算法[Amb07]也可以在大约2/3的时间内发现这种碰撞。我们在上文中提出，需要一组大小m=max{1，n+`t | S |}才能找到至少一个goodH。