抗量子霸权？未来区块链新共识，有人提出了解决办法

一.新闻

近期 Google 在 Nature 上发表了一篇名叫“Quantum supremacy using a programmable superconducting processor”（用超导处理器实现量子霸权），宣布在量子计算机领域实现“量子霸权”。一个经典计算机需要计算 10000 年的难题，谷歌的 Sycamore 量子处理器用了 200 秒就解出来了。一石激起千层浪，随后各大媒体都开始报导量子计算机的话题，自然也会涉及到量子计算机对于现有密码体系安全性的影响。下面，我们需要先介绍一些背景知识，否则很难对这个话题深入讨论。

二.什么是“量子霸权”

结论：量子霸权的含义是，在一些计算任务上对经典计算机具有压倒性优势，行使“霸权”的对象是经典计算机。

说实话笔者对我国媒体将“quantum supremacy”译为“量子霸权”不是特别满意，这似乎象征着美国将倚赖量子技术来行使地缘政治意义上的“霸权”，这并不是英文中“quantum supremacy”的本意。它的确切意思是，在一些计算任务上，通过量子现象实现对经典计算机的压倒性优势，行使“霸权”的对象是经典计算机。根据计算任务的不同，有的就非常适合量子霸权，有的量子计算对它的帮助比较有限。

那谷歌这次实验的计算任务呢？按 IBM 科学家 Edwin Pednault 等人的观点，谷歌这次实验的计算任务完全是为量子计算机量身定做的，毫无任何实用价值。但也有人说，今天的量子计算机就像莱特兄弟试驾的飞机，以后在很短时间内就会普及。诸如 RSA，ECC 这些加密体系，很快也就不安全了。那么事实上真的是这样么？

三.RSA／ECC加密体系与 Shor 算法

结论：目前主流加密算法RSA／ECC在量子计算机面前，确实存在在多项式时间内被攻破的威胁。

想了解量子计算机对现有加密体系的具体威胁，我们首先要回顾一下现在它们为什么是安全的。在不介入过多数学细节的前提下，RSA 加密的安全性是由素数分解的难度来保障的，ECC 的安全性是由椭圆曲线上的离散对数问题的难度来保障的。我们以前者举例，已知素数 7 与 143，我们可以很容易算出它们的积：7 x 143 = 1001。但如果我们只知道 1001 的情况下，我们除了挨个试错，并没有特别好的方式来推出 1001 = 7 x 143。非对称加密体系的安全性，正是靠这个问题难度的不对称性来得以保障的。

量子架构异于经典计算机的最重要之处，就是它可以利用量子态的叠加，来同时对多个组合进行试错。Shor 算法正是有效地利用了这个架构，对素数分解问题与离散对数问题，都给出了多项式时间内计算方法。因此，我们认为 RSA 与 ECC 加密体系在量子计算机的时代是不安全的。

四.多项式时间那么重要么？

结论：由于计算速度是以指数速度倍增，对于复杂度是多项式时间的问题，解决它们只是时间问题。 

学术界普遍认为，如果一个问题有多项式时间内的计算方法，那么这个问题就不是问题了。这里首先要问，所谓的多项式是一个关于什么的多项式？一般来说，计算科学中所提到的“问题”，都有它本身的难度参数。例如素数分解，你分解越大的素数之积，难度就越大，需要的时间就越长。例如，如果难度是 O(2^n) 量级的话，我们并不需要 n 太大，就可以使问题难度迅速攀升到上亿年的计算量。

不过你也可能会问，如果问题难度是 O(n^100) 的话，虽然这已经属于多项式难度范畴了，但似乎难度也会攀升的很快，也很难被迅速解出？这就牵扯到了另一个知识点：摩尔定律。摩尔定律大致上告诉我们，由于计算机技术的革新，我们电脑的计算能力大约不到 2 年翻一倍。今天我们每个人手里的智能手机的计算能力，远高于当年将人类送上月球的阿波罗 11 任务中，所有计算设备的总和！

有了对摩尔定律的理解回过头来看，就发现“多项式难度”这个概念的重要性了。一个问题，只要在理论上有多项式难度的算法，由于计算设备的算力是指数级倍增的，解决它只是时间问题。那么实际上，从提出理论算法，到“等待”摩尔定律实现破解，需要花多长时间呢？我们以大家比较熟悉的 SHA－1 为例，我国密码学专家王小云院士，在 2005 年给出了对它产生撞击的高效算法（哈希函数一旦实现撞击，就算被“攻破”了）。但真正实现 SHA－1的撞击，则是在 2017 年由谷歌公司完成的。摩尔定律默默地发了 12 年的神功，才把理论变为实践。在此期间，全球相关行业早已完成了加密算法的升级。

五.量子计算机离破解 RSA／ECC 还有多远

结论：今天 RSA／ECC 的安全性，至少优于 2005 年 SHA－1 的安全性。因此，即便让摩尔定律再发 10 － 15 年的神功，RSA／ECC 依旧还是安全的。

以目前最新知识，欲对长度为 n 比特的 ECC 运用量子意义上的 Shor 算法，则至少需要 6n 以上的量子比特。这里需要强调一点，真正对计算有用的是经过降噪后（Quantum error correction）的逻辑量子比特。按 IBM 科学家 Sarah Sheldon于 2018 年的研究成果，物理量子比特与逻辑量子比特的最小比例是 1:17。在日后的实际应用中，恐怕这个比例远远不够。

我们暂且假设能做到 1:17，比特币等主流加密货币所用的椭圆加密算法 Secp256k1，它的私钥长度是 256 比特。欲对其运行 Shor 算法，需要至少 1536 个逻辑量子比特，也就是26112 个物理量子比特。实际上随着运算复杂性的提升，降噪比例将远不止 1:17。主流科学界的看法是，没有百万级物理量子比特，想攻破RSA／ECC 加密还是非常困难的。那么谷歌的 Sycamore 处理器到底有多少量子比特呢？54 个，实际运行时为 53 个，其中还有一个不争气的，坏了。

目前 RSA／ECC 的安全性，至少优于 2005 年 SHA－1 的安全性。因此，即便让摩尔定律再发 10 － 15 年的神功，RSA／ECC 暂时还是安全的。暂时的安全性绝不等于当下可以不作为，我们现在当然需要开始为后量子时代做准备了。

六.量子计算机对区块链网络的内在威胁

结论：今天所有的区块链项目，由于地址、数字签名用到了 ECC，因此都不抗量子。

现在我们讨论一下量子计算机对于区块链网络的威胁，这里只讨论内在威胁的意思是，不包括由于网络节点服务器密码被量子计算机攻破，而对区块链网络产生的衍生威胁。

首先，我们来分析一下比特币网络所受到的威胁。比特币网络用到了两种不同的密码学。它的 PoW，区块头，交易 ID，默克尔树用到的是哈希算法，具体来说是 SHA256。量子计算机对它的计算性能确实会有大幅度提升，利用 Grover 算法，计算复杂度会从2^256 降到 2^128。这也就意味着，以目前比特币网络的挖矿难度，比特币出块需要全网矿工遍历 nonce，找出一个前 75 位比特为 0 的哈希。如果用量子计算机运行 Grover 算法的话，可以轻松找到前 128 位比特为 0 的哈希出来。这意味着计算 Sha256d 的 ASIC 矿机全要废了。量子计算机之间虽然有足够空间来继续 PoW 竞争，但考虑到初期的量子矿工极其稀有，比特币能否能继续去中心化，或许会面临严峻的挑战。如果 PoW 的哈希算法属于 memory hard 或 bandwidth hard，那量子计算机比经典计算机，优势将显著变弱。

比特币网络在量子计算机面前，真正脆弱的是它的地址与数字签名体系，因为这里用到了椭圆加密算法。因此，坊间流传的 PoS 或 DPoS 抗量子攻击的说法，纯属无稽之谈。转账时用到的椭圆加密算法，是目前所有的区块链项目共同的问题。只要 ECC 被量子攻破，对方就可以获悉你的私钥，同时也可以伪造你的签名，将你的资产全网随便转移。

区块链在量子时代是否安全，主要取决于两个问题：

七. 后量子时代的加密体系

结论：ECC 有替换方案，但签名长度从原来的 256 比特显著增加，从而会大大降低区块链的性能。如果按比特币网络现有的同步规则，届时每秒钟只能处理不到一笔交易。

前面我们讨论了，量子计算机对区块链的最大冲击在椭圆加密上。那么椭圆加密有没有继承者？我们能否把它替换掉？这恐怕是现在所有人都关心的问题。答案是肯定的，而且不止一个方案。

美国国家标准技术研究所（NIST）于 2017 年就开始征收抗量子攻击的加密方案，作为下一代加密算法的行业标准。最初一共收到了 69 份申请，目前还在评估中的有 26 个。其中有一部分在评估阶段已经被攻破，还有一些安全性与性能达不到设计预期。在存活的 26 个方案中，依然存在哪天某个提案被攻破的可能。在 NIST 给出最终结论之前，笔者只能按照现在已经公开的知识，给大家做个简单的汇报。

这些抗量子加密方案的理论基础大致分为：哈希类（hash based），格类（lattice based），编码类（code based），多变量类（multivariate）以及超奇异椭圆曲线等值（supersingular elliptic curve isogeny）。

在大部分方案中，公钥长度与数字签名不可能同时很小。这将对区块链网络构成极大的挑战。在链上发出每发一笔交易，至少需要传输两个地址和一个数字签名。如果是 UTXO 的架构，则需要 m+n 个地址，和 m 个数字签名，这里 m 是 input 个数，n 是 output个数。假设一个地址的长度与签名长度均为 10k（地址长度不应该短于公钥长度），那么一笔交易至少需要占用 30k 的存储。按比特币 1mb 区块来算的话，每个区块最多能装 30 多笔交易。比特币 10 分钟出一个区块，也就是说 10 分钟才能处理 30 比交易，平均 5 秒才能处理 1 笔交易。这是区块链抗量子加密设计上最难办的一步。

抗量子的公钥与数字签名之所以这么大，主要的原因是量子计算机在矩阵运算上，对经典计算机的优势较为逊色。因此，我们所见的公钥，会从现在的

椭圆曲线：pk = 04fe43d0c2c3daab… (一串 16 进制的数字) 

变成未来的 6960 x 1547 的矩阵。这样的矩阵会占用非常大的带宽与存储。

最后给大家讲个笑话，在递交给 NIST 的 26 组仍然存活的提案中，有一个叫 pqRSA（post quantum RSA）的加密算法，顾名思义是抗量子的 RSA 升级版。它的公钥大小为 1 tb 以上，我真的没敲错，真的是 1,000,000,000,000 byte。

习题：自己回家计算，在 pqRSA 框架下，

提示：惨不忍睹

八.笔者心中的解决方案

结论：超奇异椭圆曲线等值（super-singular isogeny 或简称 SI）算法是目前所有抗量子加密算法提案中，公钥占用空间最小的。在 5G 网络的环境下，同时实现高吞吐、抗量子与去中心化是完全有可能的。SI 算法的缺点是计算较慢，这方面在未来可以用硬件（例如，ASIC）的方式来进行弥补。

对于区块链应用来说，笔者最看好的方案是基于超奇异椭圆曲线等值的 sike 算法。相较于其它原理的加密算法，sike 最大的优势是在于它占用的带宽与存储相对可控，公钥占用空间为 2688 比特（不到 1 kb）。即便如此，这相较于传统 ECC 公钥的 256 比特也已经相当大了，大约是现在的十倍左右。如果立刻将比特币网络升级为 SI 公钥，那么它每秒钟也只能处理 1 笔交易。不过在可见的未来，5G 通讯系统将遍布全球，公钥变大的问题可以靠提升网络速度来弥补。

SI 算法的最大缺点，是计算速度特别慢。SI 算法的根本是在多条椭圆曲线之间构造isogeny map。但由于这些运算特别复杂，往往导致普通电脑数秒时间才能完成一次验证。设想一下，如果一个区块中包了 100 笔交易，如果矿工验证这些交易就需要 100 秒，那么这样的区块链网络也不会有太大的发展前景。

值得庆幸的是，关于计算 isogeny map 的硬件方案已经有人开始研究了。考虑到量子计算机真正威胁到 ECC 至少还有 10 年时间，在此之前研制出一款能快速验证的 ASIC，这个难度还不是很大。

九.CZZ 对未来的规划

结论：如果 5G 网络普及，且针对 SI 算法（super-singular isogeny）有成熟的硬件实现方案，CZZ 将在 2024 年左右启动以 SI 为理论基础的抗量子方案。启动之后，CZZ 公钥将从现有的 Secp256k1 扩容，扩容后的 CZZ 地址将以 pq 开头加以区分。CZZ 网络将通过自身的纠缠体系，为 BTC，USDT，ETH，BCH，BSV，LTC 与 DOGE 的链上资产提供抗量子地址。

现在我们讨论一下 CZZ 未来关于抗量子的路径。由于 CZZ 的挖矿算法 Bora Bora 本身自带大量的矩阵运算以及较强的 bandwidth hard，PoW 的抗量子能力会远好于比特币的 SHA256d。因此，我们重点的讨论方向还是 CZZ 的地址系统。

在未来两三年内，5G 网络会变的普及。在未来三五年内，NIST 会确定最终的抗量子方案。如果其中有一个方案使用 SI 加密，高效验证 SI 加密算法的硬件设计（例如，ASIC）将会随之而出。因此，CZZ 计划在约五年后启动抗量子地址体系的升级。

对于区块链项目来说，SI 加密算法的另一个优势，就是公钥体系可以兼容现有体系。因此，未来向 SI 体系切换的实现方式，其实就是一次地址的扩容。在原有地址的基础上，会出现一批以 pq 开头的新增地址（pq 的含义是 post quantum，译为“后量子”）。这些地址的长度会是现有地址的 10 倍左右，我们称它们为后量子地址。后量子地址需要 SI 算法来验证转出的交易，经典地址仍然按 ECC 算法来验证交易。因此，后量子地址下的资产，在量子计算机面前是安全的；经典地址上的资产，在量子计算机面前是有风险的。或许 10 － 15 年后，当量子风险变的越来越现实，用户自主会将资产从经典地址转移到后量子地址。

由于 CZZ 公钥所使用的椭圆曲线 Secp256k1与 BTC，USDT，ETH，BCH，BSV，LTC，DOGE相同，CZZ 地址的扩容也会自动对 BTC，USDT，ETH，BCH，BSV，LTC 与 DOGE 生效。假设某 BTC 用户担心自己资产有量子风险，他可以通过纠缠将资产转移到以 pq 开头的后量子地址上，这些地址可以帮助他们抵抗量子攻击。具体实现方式与设计细节，以后会进一步详细叙述。