科普 | 比特币系统的密码技术和量子计算的冲击

2008年，一个化名中本聪的人发表了一篇题为《比特币：一种点对点的电子现金系统》的旷世论文，创造出了比特币这种虚拟数字货币，其底层技术就是目前我们常说的区块链。

一、比特币系统的密码技术

1. 比特币系统 的形象表示

比特币系统的形象表示

如上图所示，比特币系统中每一个节点都是一台单独的计算机，每一个区块是对应计算机上的一个存储空间，每个区块上记录的是一段时间内的比特币交易记录。区块与区块之间通过时间戳和一个被称为“哈希函数”的单向函数保证相关节点上存储的记录数据不可被篡改。比特币系统将交易记录数据通过点到点网络，也就是P2P对等网分发存储在全网所有节点上，通过这种数据的高度冗余，从另一个层面保证了数据的全网一致性。

比特币系统是一种分布式系统，这种分布式系统可以解决传统中心化信息系统可能存在的中心节点失效、记录数据被篡改、其他节点对中心节点信任不足等问题。比特币系统可以看作是一个分布式的链接账本，每个区块就是一个账本。这个系统基于分布式的共识算法来决定由谁来记账。在比特币系统中的共识算法是POW，即工作量证明，获得记账权的节点将获得系统给予的一定数量的比特币。账本按共识算法确定的规则链接，当前账本含有上一个账本的哈希值。所有交易在这个账本中可以追溯。

2. 区块链与密码学

密码学是比特币系统的核心技术，也是区块链系统安全运行的基石。一旦相关的密码学算法被破解，区块链的系统安全将不复存在，其数据不可篡改性也将荡然无存。

比特币系统中多个环节使用到了密码学算法，包括各种常用的编码算法、哈希算法、签名算法等。这些算法在构建比特币系统以及确保比特币系统正常运行过程中发挥着重要的作用。构建比特币系统最重要的两类密码算法就包括了哈希（HASH）函数和非对称密码算法。

3. 比特币系统使用的密码技术

比特币系统或区块链技术并不是单一的技术，即使在密码学层面，也包含了非对称密码算法、哈希函数、安全多方计算等多种技术。

（1）非对称密码算法

非对称密码加密过程示意图

传统的对称密码算法在秘密信息传输时双方需要共享同一个会话密钥。秘密信息发送方使用这个会话密钥对信息进行加密之后传输，秘密信息接收方同样需要用这个会话密钥对接收到的秘密信息解密，还原出明文。这个会话密钥同样需要事先通过一个秘密信道进行保密传输，这在很多情况下是困难的甚至是不可能的。

非对称密码算法又被称为公钥密码算法，指的是存在一对数学相关的密钥，使用其中一个密钥对数据进行加密，只有使用另一个密钥才能对该数据进行解密。这对密钥中，对外公开的密钥叫做公钥，不公开的密钥叫做私钥。公钥就像银行的账户，私钥就像是该账户的密码或者账户所有者的签名。

A和B之间使用非对称密码算法进行信息传输，如果这个信息是秘密信息，A就可以用B的公开密钥对信息进行加密，然后发送出去。任何人都可以收到加过密的信息，但只有B可以用自己的私钥对这个信息进行解密，还原出明文。

如果A向B发送消息，发送之前，这个消息用A的私钥加密，任何人都可以用A的公钥解密。这个行为证明，这个消息就是由A发出的，而不是其他人发出的。这个动作在密码学上称为数字签名。

区块链上的有效交易数据包含了交易发起方的私钥签名，该交易的签名可以用交易发起方的公钥进行验证。公钥可以通过算法从私钥中计算得出，但私钥却不能从公钥中推出。

（2）哈希函数

哈希函数示意图

哈希函数是一类单向函数，这类函数可将任意长度的输入数据经由该算法转换为一组固定长度的输出数据。这种函数很容易被验证，但是却很难破解。在通常情况下，给定任何一个x作为输入，可以非常容易计算出输出的哈希值y，但却很难由y反向计算出x。此外，只要对x做一点小小的改动，y的变化就会极其明显。

比特币系统中每个区块上的数据除了原始数据或者交易记录，还包括上一个区块上所有数据的哈希函数值。比特币系统采用的是双SHA256哈希函数，也就是将上一个区块上所有数据用SHA256哈希函数进行两次运算，再将输出长度为256位的二进制数字存储在下一个区块链的区块头中。

（3）安全多方计算

安全多方计算用于解决一组互不信任的参与方在保护各自隐私情况下的协同问题。安全多方计算要确保各参与方输入的独立性、计算的正确性，同时不泄露各输入值给参与计算的其他成员。通俗地说，安全多方计算是指在一个分布式网络中，多个用户各自持有一些数据输入，他们希望共同完成对这些数据的计算，同时要求每个用户除计算结果外均不能获知其他用户的任何输入信息。

基于以太坊实现的智能合约已经能够实现链上计算。但是以太坊的链上数据都是公开透明的，任何人都可以获取这些数据，这也是以太坊迟迟无法跨入企业级和个人金融应用领域的原因。其实质就是以太坊缺乏对多方安全计算的支持，无法保护多方数据计算过程中的隐私。

4. 比特币 系统的 挖矿原理

比特币系统为了维持系统运行，会给予记账者一定数量的比特币作为奖励。为了获得比特币奖励，很多人会参与到记账争夺权的活动中来。因此，由谁来记账，就需要进行竞争。参与比特币记账竞争的人，被称为矿工。

比特币系统的挖矿，简单来说，就是由所有矿工对当前区块做同样的哈希运算，一旦运算出符合特定要求的哈希值，即可对全网广播。其他人经过验证，证明这个人的运算是正确的，就认定这个人获得了当前区块的记账权。

比特币系统中每个区块的区块头数据结构如下。

区块头的结构和大小

区块头中的信息，在挖矿前大部分已经是固定下来的，或者是可计算的。

• 版本号。跟随比特币客户端而定，一段时间内不会改变。

• 前一区块的哈希值。是对前一个区块计算的结果。

• Merkle_root 默克尔根。对当前区块中所有交易以二叉树方式进行的逐级哈希运算后得到的哈希值。

• time区块生成时间。也是当前打包时的时间，具体数字是指从格林威治时间1970年1月1日0时0分0秒至今的时间，不需要很精确。

• Target-bits 难度目标。参考上两周产生区块的平均生成时间而定，由系统进行调整，大体在10分钟左右。

• nonce随机数。由挖矿需要可以进行调整的数字，32位二进制数字。

• 附带消息。指在区块中每笔交易后的附言，该附言可以让merkle root也发生变化，从而有更多的可能去找到符合要求的结果。

比特币挖矿的算法可表示为：

比特币挖矿算法

在这个算法中，前面部分定义了区块链的数据结构，后面部分就是对随机数进行遍历，直到找到符合条件的哈希值为止。

区块链其实是通过区块头而链接在一起的。下面的比特币区块头示意图解释了区块链和区块的构成。

比特币区块链和区块头关系示意图

比特币的挖矿流程可概括为：

矿工首先对交易进行验证，剔除有问题的交易，然后通过一套自定义的标准来选择将哪些交易打包进区块。比如将交易的费用与交易占用的字节大小的比值超过某个门槛作为判断标准，符合条件的交易才被认为有利可图。当然，矿工也可以特意选择加入某条交易，或者故意忽略某些交易。

如果是通过矿池挖矿，矿池的服务器会去筛选交易，然后分配给每个参与的矿机一个独立的任务。这个任务的难度小于总的挖矿难度，完成了小难度的计算，即确认了自己参与的工作量。每台不同的矿机计算的问题不会重复，当其中一台矿机成功挖矿时，其他矿机依据工作量分配获得的总收益。

一旦筛选好交易数据，按照时间排序，两两哈希，层层约减，通过这些交易就可计算出一棵Merkle树，可以确定一个唯一的哈希值，这个就是Merkle树的根。Merkle树中任何节点的变化，都会导致Merkle root发生变化。通过这个值，可以用来验证区块中的交易数据是否被改动过。

Merkle树示意图

二、量子计算与量子算法

1. 量子计算与量子算法

量子计算是基于量子力学原理进行有效计算的新型计算模式，它能够利用量子的叠加性、纠缠性、相干性实现量子的并行计算。

1982年美国物理学家费曼提出量子计算概念。但由于量子态的测不准原则 以及量子系统容易受噪声干扰，量子运算很容易出错。1994年美国计算机专家Shor证明量子计算机可快速分解大因数，实现了第一套量子算法编码，量子计算以及量子计算机的研究才进入实验时代。美国国家标准技术研究院于2009年研制出世界上第一台通用编程量子计算机。

经典比特具有0和１这２种状态，量子比特与经典比特的不同之处在于1个量子比特除了可以像经典比特一样处于0和1这样的状态之外，还可以处于既非0又非１的状态，这个中间状态称为叠加态。量子叠加态是决定量子计算不同于经典计算的关键特性之一，也是量子并行计算的理论基础。相同位数的寄存器，量子计算机可记录的信息量是传统计算机的指数倍，在运算速度和信息处理能力方面，传统计算机无法比拟。量子并行计算体现了量子计算最重要的优越性。

量子算法是量子计算科学的重要部分。1989年Deutsch首次提出Deutsch量子算法，首次展示了量子计算机的并行性特征；1994年Shor提出大数质因子分解量子算法，并将该算法的量子编码实现；之后，Grover数据库搜索算法、量子智能算法相继被提出。基于Grover的量子搜索算法和基于Shor的量子Fourier变换算法是目前比较成熟的量子算法。

2. 量子密码的安全性

量子密码的理论基础为量子力学，利用物理学原理对信息进行加密保护，创建安全的通信信道。

相比传统的基于数学的密码技术，量子密码技术拥有无条件安全性和对窃听者的可检测性，拥有巨大的发展前景。

量子密码的安全性基于以下三个量子力学基本定律。

一是海森堡测不准原理。由于量子具有波动性，在同一时刻微观粒子的位置与动量不能同时以相同的精度测定到确定值，只能精确测定两者之一。

二是量子不可克隆定理。量子系统的任一未知量子态，在不遭破坏的前提下，是不可能被克隆到另一量子体系上的。即测量必会改变量子状态，从而使通信双方察觉出通信是否被窃听。

三是测不准原理或测量即塌缩原理。如果粒子的量子态是一个叠加态，则对粒子的量子态的测量会影响到量子态本身，使其塌缩到它的一个本征态上，无法测出粒子的叠加态，这样测量就会留下痕迹。

量子保密通信的安全性不依靠数学计算的难度，而是依靠物理学定律，依靠量子力学的不确定、不可克隆的基本原理，因而理论上没法破解，更为可靠。

量子密码与传统密码具有很大的差异。首先传统密码算法是基于某个难解的数学问题，受限于当前的计算能力。量子密码基于量子力学，通过物理学原理而非数学问题，更加安全。随着量子计算的迅速发展，量子计算能力有了质的飞跃，传统密码被破解只是时间问题，其安全性将受到极大威胁。其次，传统密码体制很难证明密钥在传输、分发过程中未被窃听者窃取。量子密码在分发过程中，可有效识别攻击者的存在，从而保证通信过程的安全性。

3. 量子计算对当前通用加密 算法 的影响

尽管主流的密码系统目前依然能够安全运行，但是在量子计算技术的潜在冲击下，几乎所有的加密算法都需要进行改进甚至重构。2016年4月，美国国家标准与技术局对当前主要的密码技术将受量子计算能力影响的情况进行了预测，如下表所示。

主要密码技术将受量子计算能力影响的情况预测（2016年）

4. 量子计算的最新 发展

过去30年，物理学家在构建实用型量子计算机方面取得了巨大的进步。

2019年10月23日，谷歌在《自然》杂志发布了 “使用可编程超导处理器的量子至上性”实验结果。谷歌人工智能量子团队开发了一种名为“ Sycamore”的新型54比特处理器，该处理器能在200秒内完成目标计算。而要想完成相同的目标计算，世界上最快的超级计算机需要10000年。

竞争对手IBM第一时间对谷歌的这一“宣称”做出回应。IBM在一篇博客中表示，谷歌高估了计算项目的难度，谷歌所宣称的经典计算机需要10000年执行的任务，其实只要2.5天就能完成。但尽管如此，2.5天和200秒相比，毕竟还不是同一个数量级。

区块链的安全基于密码算法的安全，如 Hash 函数的安全和椭圆曲线密码算法的安全。量子计算机的出现将在底层密码算法层面对区块链的安全产生严重威胁，比特币、以太坊等许多区块链系统都会受到冲击。

三、 量子计算对区块链的冲击

以比特币为代表的区块链安全协议涉及２种类型密码技术。一个是比特币“挖矿”过程中使用的哈希函数，一个是区块链上提供数字签名的非对称密码。采用的算法分别是SHA-256 哈希算法，和椭圆曲线数字签名算法（ECDSA）。SHA-256 主要用于由公钥生成钱包地址，以及挖矿时的工作量证明（PoW），ECDSA 主要用于私钥、公钥的生成，签名和验签等。

1. 量子计算对挖矿的威胁

比特币系统中，新的比特币通过“挖矿”产生，挖矿的过程就是矿工利用计算机计算比特币网络中数学问题的过程。第一个解决问题的矿工公布其答案，并计入账本，同步计入比特币网络中的所有节点。挖矿成功，系统奖励矿工一定数量的比特币。

比特币挖矿中使用的哈希函数是SHA-256。使用 SHA-256为每个区块计算一个随机数，虽然结果很容易验证，但搜寻过程非常艰难。通常采取的方法是使用蛮力搜索，意味着要尝试不同的输入，直到找到满意的答案为止。

量子力学中的Grover搜索从理论上可以解决这个问题。Grover算法在解决从无序数据库中搜索某个特定的数据问题方面有独特的优势，Grover算法使找到 Hash 函数的碰撞变得相对容易，也就意味着将会降低破解密码学哈希函数的安全级别。

那么反过来，能否用量子算法进行挖矿呢？如果用量子算法探矿，则需要相当快的量子哈希运算速度和更强的量子加速，但目前的技术水平还难以达到。关于量子计算机对挖矿的威胁，戴夫士•阿加沃尔（Divesh Aggarwal）和新加坡国立大学（NUS）的研究人员进行了深入研究，并在2017年10月就此发表了论文。他们认为，至少在未来10年内，使用ASIC挖矿的速度会比量子计算机快，不过10年后，量子计算机的挖矿速度会飞速增长。

2. 量子计算对 非对称密码 算法的威胁

非对称密码用于比特币系统中对交易的授权。非对称密码为系统中的所有用户分别分配1个公钥和1个私钥，公钥可广泛共享，私钥只有密钥所有者本人才知道。通过给定的私钥，可以很容易推算出对应的公钥，但反过来由公钥推算私钥，则非常困难。

比特币使用的非对称密码算法是椭圆曲线数字签名算法（ECDSA），利用 secp256k1 生成密钥。该算法保证比特币只能被合法拥有者使用。

椭圆曲线密码在量子计算中很容易受到攻击。Shor算法在理论上可以很容易将其修改，以解密带有椭圆曲线的消息。目前世界上已经有几例分别从理论上和实践上利用Shor算法攻击 ECC 的研究案例。有专家预计在 2027 年，量子计算机就可以实现对密钥的破解，量子计算机破解加密签名所需的时间预估为10分钟。但目前来看，要实现量子计算对ECDSA的攻击，需要一定数量的量子比特，有外媒报道称是4000个，目前的量子计算机远达不到这样的水平。

3. 谷歌量子计算机对密码算法的影响

谷歌量子计算机目前的水平基本可以从以下几个方面进行评判。

（1）谷歌的量子计算机还不是真正的量子计算机，不能实现所有的量子变换。只有实现破解密码算法中的那些变换，才可能对密码算法有影响。

（2）谷歌量子计算机能够实现的量子比特位数还很少。它完成的任务在大型传统计算机上也能完成。

（3）量子计算机实用化后，才有可能对基于离散对数和大合数分解设计的公钥算法有威胁。

（4）量子计算机对对称密码算法没有致命的威胁。从时间复杂性上看，只要密钥长度加倍，对称密码算法抗量子计算机的时间复杂性与电子计算机相同。

长远来看，运行Shor算法的实用量子计算机能够破解RSA、ECC等非对称密码算法。谷歌53个量子比特的量子计算机，针对一个没有应用价值的问题，验证了量子计算机比现有经典计算机强大。但目前谷歌量子计算机并不能对经典密码（包括非对称密码）的安全造成威胁。要想破译现用的RSA算法，目前估计需要能够稳定操纵几千个逻辑量子比特，相应的大概操纵百万量级的物理量子比特，要达到这一目标，还有很长的一段路。

4. 后量子密码技术在区块链系统中的应用

尽管目前区块链应用所使用的本地加密算法是安全的，这并不代表区块链从业者们可以高枕无忧。研究在量子计算机出现后对区块链系统仍然安全的密码算法十分重要。后量子密码技术，作为未来 5-10 年逐渐代替 RSA、Diffie-Hellman、椭圆曲线等现行公钥密码算法的密码技术，正被越来越多的人所重视。

后量子密码，又被称为抗量子密码，是被认为能够抵抗量子计算机攻击的密码算法。此类加密技术的开发采取传统方式，即基于特定数学领域的困难问题，通过研究开发算法使其在网络通信中得到应用，从而实现保护数据安全的目的。

后量子密码的应用不依赖于任何量子理论现象，但其计算安全性据信可以抵御当前已知任何形式的量子攻击。在区块链系统中应用后量子密码技术，以保证区块链在量子计算机出现后仍然安全。

非对称密码是后量子密码技术发展的重点领域。如随着Shor算法的提出，包括RSA、ECC以及DH密钥交换技术等非对称密码算法已经从理论上被证明彻底丧失了安全性。相对于对称密码系统还可以采取升级措施应对量子威胁，非对称密码必须采取全新方法重建，因而也就成为了后量子密码技术发展的重点。

当前国际后量子密码研究主要集中于基于格的密码（Lattice-based cryptography）、基于编码（Code-based cryptosystems）的密码系统、多元密码（Multivariate cryptography）和基于哈希算法签名（Hash-based signatures）等密码算法。在所有被认为具有抵御量子威胁潜力的计算问题中，基于格的密码系统在过去十年中得到了最为广泛的关注。