经过了几十年的高速发展后，电子计算机芯片的运算速度已经迈入瓶颈期。平均每十八个月性能翻番的摩尔定律也已经失效。下一个里程碑式突破的很可能会由量子计算机实现。
在电子计算机中，信息以0和1的比特形式编码，n个比特的内存可以存储2^n种可能状态中的一种。而在量子计算机中，数据存储在量子比特（qubit）里，能同时表示0、1或它们的叠加态，所以n个量子比特可以在一个时刻同时表示最多2^n种状态。这使得在量子比特上的一些运算会比在传统电子计算机上快很多。
量子计算的研发在2018年的今天仍处于婴儿期，但学术界已经在研究它对加密学和加密货币未来的影响了。例如去年十月，新加坡国立大学的Divesh Aggarwal等学者发布了一篇论文《Quantum attacks on Bitcoin, and how to protect against them》（https://arxiv.org/pdf/1710.10377.pdf），探讨了针对比特币的量子计算攻击手段和防范措施。
他们认为量子计算在未来十年内几乎不可能影响到比特币的工作量证明（也就是挖矿）。在SHA256哈希函数的算力角逐中，量子计算机会长期败给专用的ASIC矿机。
为了稳妥起见，作者建议采用对量子计算难度更大的PoW算法。例如基于寻找哈希冲突的Momentum算法、Aeternity采用的Cuckoo Cycle图搜索算法、好几种币应用的Equihash泛化生日问题算法等等。
与工作量证明相比，更危险的是交易签名的安全性。比特币目前采用基于secp256k1的椭圆曲线数字签名算法（ECDSA）验证交易的有效性。它的安全性完全取决于ECDLP问题的难度。用传统方法解ECDLP需要指数级或接近指数级的时间复杂度（参阅http://www.icisc.org/icisc/asp/icisc2017_papers_camera_ready/sec6_2.pdf），难以暴力破解。但在量子计算机面前，它的时间复杂度却能降低到多项式级别（参阅Peter Shor的论文《Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer》）。
这意味着复用比特币地址会变得危险。因为当你从地址A转出币时，地址对应的公钥会被写入交易，用于解锁脚本的验证。根据公开的公钥，有可能用量子计算机成功算出对应的私钥。如果继续用地址A收款，其中的资金便随时可能被攻击方转走。
即使不重用地址，也存在潜在的风险：当你广播的交易A尚未得到区块确认时，理论上有可能率先被量子计算机破解出私钥。攻击方随后可以构造一个从源地址转给自己的新交易B，利用replace-by-fee功能或与矿池合作，抢先把B写入新区块。这样一来，你的交易A会被作废，同时损失其中包含的所有币。根据论文作者的估计，2027年的量子计算机有望在10分钟内破解ECDSA，对比特币的安全性构成巨大威胁。
防范这类攻击需要改用抗量子计算的数字签名，比如基于哈希的LMS、基于格结构（lattice）的BLISS、DILITHIUM等被称为后量子时代（post-quantum）的签名算法。
由于量子计算目前远不足以对椭圆曲线签名构成实质性威胁，所以比特币还没有采取防范措施。然而有些新兴加密货币已经在设计时就防患于未然了。比较典型的例子是Hcash（https://h.cash）。它支持基于SHA-3（Keccak）哈希算法的LMS/MSS和基于格结构的BLISS签名协议，提早为抗量子攻击做准备（参阅：https://github.com/HcashOrg/hcashd/blob/dev/docs/research/post-quantum-signature-schemes-in-hcash.pdf）。
LMS/MSS签名的安全性假定非常少，只要配套的哈希函数选择得当就能保障安全性。而BLISS除了性能高，生成的公钥和签名长度也是后量子签名算法中相对很小的。当然，比起ECDSA，BLISS签名仍旧显得非常臃肿。比如说，比特币的ECDSA签名平均才70多字节，而128位安全性的BLISS算法产生的签名高达5KB。这意味着交易吞吐量的减小或是带宽和存储需求的增大。为了缓解签名庞大带来的弊端，Hcash采用类似比特币隔离见证（SegWit）的方案，把部分验证信息移出交易，单独存放和同步。要根治这个问题还需研发出签名更短的高效抗量子攻击算法。
出于实际需求考虑，Hcash仍旧兼容久经考验且尺寸小巧的ECDSA签名。 这样的设计让用户不必为尚处于理论阶段的攻击手段过早地付出代价。在量子计算出现重大突破之前，我们仍旧可以信赖ECDSA的安全性。
原文发布时间为：2018-01-31
本文作者：水瓶座的老李头
本文来源：今日头条，如需转载请联系原作者。
