【猫本聪】量子计算与加密货币

【猫本聪】量子计算与加密货币

圆方圆书院 2018-10-24

作者简介： 茂本聪，区块链布道者，前谷歌高级工程师。 茂本中本聪的区块链专栏，视角独特，技术专业，逻辑严密，文笔清晰，是很好的学习和启迪材料。

经过几十年的高速发展量子计算机会影响比特币吗，电子计算机芯片的运算速度已经进入瓶颈期。 性能每 18 个月翻一番的摩尔定律也已经失效。 下一个突破里程碑很可能由量子计算机实现。

在电子计算机中，信息以 0 和 1 的位编码，n 位内存可以存储 2^n 种可能状态之一。 在量子计算机中，数据以量子位（qubits）的形式存储，可以同时表示0、1或它们的叠加态，因此n个量子位一次最多可以同时表示2^n种状态。 这使得量子比特上的某些操作比传统电子计算机上的操作快得多。

量子计算的发展在 2018 年仍处于起步阶段，但学术界已经在研究它对密码学和加密货币未来的影响。 例如，去年10月，新加坡国立大学的Divesh Aggarwal等学者发表了论文《比特币的量子攻击，以及如何防范》（），讨论了针对比特币的量子计算攻击方法和防范措施。

他们认为，量子计算几乎不可能在未来十年内影响比特币的工作量证明（又称挖矿）。 在 SHA256 哈希函数的计算能力竞争中，量子计算机将长期输给专用 ASIC 矿机（参见“[block #11] ASICs of friends and foes”）。

为了保险起见，作者推荐使用量子计算难度更大的PoW算法。 比如基于寻找哈希碰撞的Momentum算法，Aeternity采用的Cuckoo Cycle图搜索算法，几个币种采用的Equihash广义生日问题算法等等。

比工作证明更危险的是交易签名的安全性。 比特币目前使用基于 secp256k1 的椭圆曲线数字签名算法（ECDSA）来验证交易的有效性。 它的安全性完全取决于 ECDLP 问题的难度。 使用传统方法求解 ECDLP 需要指数级或接近指数级的时间复杂度（参见 参考资料），这很难通过暴力破解。 但在量子计算机面前，它的时间复杂度可以降低到多项式级别（参见 Peter Shor 的论文“Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”）。

这意味着重复使用比特币地址会变得很危险。 因为当你从地址A转币时，该地址对应的公钥会被写入交易中，用于解锁脚本的验证（参见《【区块#20】比特币地址#1详解：P2SH地址和多重签名》） . 根据公钥，可以用量子计算机成功计算出对应的私钥。 如果继续使用地址A收款，其中的资金随时可能被攻击者转移。

即使不复用地址，也存在潜在风险：当你广播的交易A还没有被区块确认时，理论上有可能量子计算机最先破解私钥。 然后攻击者可以构造一个新的从源地址转给自己的交易B，并使用replace-by-fee功能或者配合矿池先将B写入新的区块。 这样，你的交易A将作废，其中包含的所有币都将丢失。 据笔者估计，2027年的量子计算机有望在10分钟内破解ECDSA，对比特币的安全构成巨大威胁。

为了防止此类攻击，需要使用抗量子计算的数字签名，例如基于散列的LMS、基于格的BLISS和DILITHIUM，这些被称为后量子签名算法。

由于目前量子计算还远不足以对椭圆曲线签名构成实质性威胁，比特币并未对其采取防范措施。 但是，一些新兴的加密货币旨在防患于未然。 一个典型的例子是 Hcash()。 支持基于SHA-3（Keccak）哈希算法的LMS/MSS和基于点阵结构的BLISS签名协议，提前做好抗量子攻击准备（参见：）。

LMS/MSS签名的安全假设很少，只要选择合适的匹配哈希函数就可以保证安全。 除了BLISS的高性能之外，生成的公钥和签名长度在后量子签名算法中也比较小。 当然，相比于ECDSA，BLISS签名还是很臃肿的。 例如，比特币的平均ECDSA签名只有70多字节，而128位安全BLISS算法生成的签名却高达5KB。 这意味着交易吞吐量减少或带宽和存储要求增加。 为了缓解大签名带来的弊端，Hcash采用了类似比特币隔离见证（SegWit）的方案，从交易中去掉部分验证信息，单独存储和同步。 为了解决这个问题量子计算机会影响比特币吗，有必要开发一种高效的短签名抗量子攻击算法。

考虑到实际需要，Hcash 仍然兼容久经考验的紧凑型 ECDSA 签名。 这种设计避免了用户过早地为一种还处于理论阶段的攻击方式买单。 在量子计算没有重大突破之前，我们仍然可以依赖 ECDSA 的安全性。

更多技术文章请关注

圆圈链环