Penta首席科学家：区块链有办法对抗“量子计算”

风靡全球的量子计算，对区块链的安全构成威胁吗？现有的区块链技术能抗击量子计算的破解能力吗？区块链技术还可以做出哪些反击？

带着这些至关区块链行业的核心痛点的问题，我们引领大家初步学习一下，Penta的首席科学家、Penta区块链实验室奠基人Steve Melnikoff教授的新作。我们第一时间根据英文原文翻译出如下全文，以供大家探讨。

全文中文总共约3000字，大概需要阅读6分钟。

Picture this: somewhere high in the Hollywood Hills a group of screenwriters are meeting with an influential LA movie producer on an action film. Their pitch, hijacking of the first ‘quantum supreme’ computer en route from Australia’s University of New South Wales to Washington and the NSA.

试想以下场景：在好莱坞山某高处，一群编剧正和一位有影响力的电影制片人讨论一部动作电影的制作。编剧们提议的情节是，第一台“量子”计算机在从澳大利亚新南威尔士大学运送到华盛顿和美国国家安全局的路途中被劫持。

Our hero’s mission impossible, find and recover the stolen quantum computer before it is used to decode the world’s trove of encrypted blockchains, wreaking economic havoc.

我们的特工英雄找到并且取回了被窃的量子计算机，避免了全球大量使用加密算法的区块链系统遭到量子计算机攻击，引发经济混乱。

The producer says, ‘Quantum computers, quantum supreme evil geniuses, technology gone crazy and world domination. How much will it cost, and will it do CGI?’

制片人答复说“量子计算机，量子计算方面的邪恶天才，技术暴走和称霸世界。需要多少钱？需要CGI吗？”

Action movies aside, thechallengesto blockchain technology and cryptography posed by an accelerating development of large, working quantum computers are very real. Quantum computing calls into question the core mathematics foundational to modern crypto algorithms,attacking their viability.

先把动作电影放一边，能用于实际工作的大型量子计算机的开发日益加速，这也切实对区块链技术和密码学构成了威胁。量子计算挑战了现代密码学算法的核心数学基础，使得这些算法不再有效。

Penta首席科学家：区块链有办法对抗“量子计算”

D-Wave Quantum Annealing Computer CPU

D-Wave 公司量子退火计算机CPU

A quick review, NehaNarula of MIT’s Digital Currency Initiative says: “Cryptography isthe studyof how to secure communication, and it's about two really important things:masking information so it can be hidden in plain sight, and verifying a piece ofinformation's source.”

简单回顾一下，麻省理工数字货币项目团队的Neha Narula表示：“密码学研究的是怎样确保通讯安全，其中最重要有两点：第一、隐藏信息，让人们无法轻易地看出信息；第二、验证一条信息的来源”。

Digging deeper, three major cryptographic algorithms, RSA, DSA and ECDSA derive their ‘hardness’ or ‘hiding’ property from computationally infeasible problems. Extremely infeasible, like the factorisation of very large integers, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. Resistance to brute-force attacks against 256-bit hash signatures underpins the blockchain for the decentralised digital currency BitCoin which depends on the elliptic-curve discrete logarithm problem. Concurrently, as a cryptographic game the ‘puzzle friendly’ nature of the BitCoin hash signature function makes it impossible for any coin ‘mining’ strategy to be any better than trying possibilities at random. All these ‘trapdoor’ functions have a critical property in common. For ‘classical’ bit manipulating machines they are easy to compute in one direction, but next to impossible in the opposite one.

更深入地说，密码学主要有三种算法：RSA、DSA和ECDSA。这三种算法通过计算上的不可行来实现密码的“硬度”和“隐秘性”。计算上非常不可行的列子包括对非常大的整数进行因式分解、离散对数问题和椭圆曲线上的离散对数问题。比特币这一分布式数字货币的底层区块链采用的是椭圆曲线离散对数，其256位哈希函数电子签名足以抵抗暴力破解。同时，比特币的哈希函数电子签名具有“谜题友好”特性，因此，使用任何策略对数字货币进行“挖矿”效率都不会优于使用随机概率。所有此类“陷门”功能都具有关键的共同属性。“传统的”位操纵器容易从一个方向进行计算，但是无法反推。

The idea is that BitCoin holders, or participants in blockchain transactions use a crypto- hash function to create a pair of linked 256-bit numbers: a secret (SK or ‘private’) and public (PK) key. PKs are generated from SKs, and hash signatures along with their associated public keys are used to prove without revealing, ownership of the secret ones. Equipped with crypto-hash functions and public-private keys, the source of a piece of information, its ‘owner,’ like a blockchain transaction can be verified without debate.

比特币的持有者或者使用区块链进行交易的用户使用哈希函数加密，生成了一系列相互关联的256位数字：即私钥和公钥。公钥由私钥生成，并且相关公钥结合哈希函数电子签名使用，从而使得无需披露私钥的所有者即可以证明信息。因为有哈希函数加密、公钥和私钥，可以毫无争议地确定信息源，比如区块链交易的所有者。

To put into perspective how hard it is to solve BitCoin’s SHA-256 ‘proof of work puzzles’ (PoW), it is much, much easier to find a single grain of sand from all the sands on Earth then to examine PoW solutions until a correct ‘answer’ is found. For grains of sand the problem is on order around 2 to the power 60 compared to 2 to the power 256 for PoW, an insanely large number. Proof of Work is the backbone of BitCoin’s ‘consensus’ algorithm with which blockchain becomes a self-sustaining system of distributed ledger transactions.

求解比特币“工作证明”（PoW）共识机制采用的SHA-256有多难呢？从地球上所有沙子之中挑出特定的一粒都比求解PoW的正确答案远为容易。因为想从地球所有的沙里找到特定的一粒沙子，所需的试验次数大概是2的60次方，而求解PoW的复杂度则是2的256次方，数字大到难以想象。正是由于有PoW共识机制，比特币网络才能够成为可以处理交易并且独立运行的分布式账本。

This is key: solving a PoW signature puzzle is extremely hard, but not impossible and BitCoin miners are no better off using any particular algorithmic strategy for finding a solution than by trying each at random.

最为关键的是：求解PoW的数字签名谜题虽然非常困难，但是并不是不可能的，比特币的矿工们除了随机尝试一个一个可能的答案之外并没有更好的特定算法能帮助求解。

Penta首席科学家：区块链有办法对抗“量子计算”

Image courtesy BitCoin.org提供图片

That is what ‘mining pools’ do, figuratively they look at grains of sand for just the right one. Using specialised ASIC (Application Specific Integrated Circuit) hardware, racks of energy eating boxes churn upwards of 10 terra (trillion)-hashes per second to compete for the prize of ‘signing’ a ‘block’ on the ‘chain’. The winner rewarded with a number of bitcoin for their effort.

这也是“矿池”之所以会存在的原因，举个形象的例子，矿池就相当于在一大堆沙子里边找你想要的特定一粒。使用特制的ASIC（特殊应用集成电路）芯片就可以每秒尝试10兆哈希值，更好地争夺为区块链上一个区块签名的权利。最终获得签名权利的节点可以得到一定数额的比特币作为报酬。

Physically based mainly in China because of ultra-cheap energy costs, but with competing operations on-going around the world, the total market cap of the 2018 coin mining industry securing associated blockchains is in the hundreds of billions of dollars. Put another way, the electricity consumption is approximately equivalent to that of Ireland.

矿池主要设在中国，因为中国的电费特别便宜，但是在国外陆续也出现一些竞争对手，截至2018年各类区块链代币挖矿的市场总市值达到了数千亿美元。挖矿的耗电量相当于爱尔兰一个国家的耗电量。

Potentially, quantum computing renders all this processing power into nothing more than expensive, over-heating electronics.

量子计算机的出现可能导致我们不再需要以巨大的耗电量为代价处理计算，消耗大量电力进行计算不仅昂贵、还会导致气候变暖，也并无实际用处。

Why? Because of the nature of quantum computing, in replacing bits with ‘quantum bits’ or ‘qubits’ rigs the game for blockchain. Cryptographic standards all made obsolete. Whether using entangled photons, iontraps or super conducting circuits, in reasonably finite ( polynomial ) time quantum computers make possible the calculation of private keys from public ones. The superposition property of qubits, in contrast to encoding either a 0 or 1 classical bit exploits the physics of the very small to perform calculations exponentially faster than ever before. Billions of pieces of information processed in a single compute cycle.

为什么呢？这是由于量子计算本身的性质决定的，用“量子比特”或者“量子位”取代位将会颠覆整个区块链行业的玩法。所有的加密体系都面临淘汰，不论是使用光子纠缠、离子探测，还是超导电路的加密体系均是如此。在合理的有限多项式时间内，量子计算机可以从公钥计算出私钥。相对于0或1的传统二进制编码，量子计算机的量子位具有叠加属性，通过利用最小的物理量呈几何倍数地提高计算能力。一个计算周期就可以处理几十亿条信息。

Penta首席科学家：区块链有办法对抗“量子计算”

nside a Chinese BitCoin mining farm

中国比特币矿池内部图

So, quantum computing destroys BitCoin, and blockchain applications are never to emerge from the Gartner ‘hype cycle trough of disillusionment’? All is lost?

因此，量子计算是否会毁掉比特币？Gartner“新兴科技技术成熟度曲线”预言的区块链应用是不是根本无法实现？区块链是否将会一败涂地呢？

Not necessarily, as an important caveat is revealed when the relative speeds of quantum computers expected to emerge near-term are compared to the existing capabilities of ASIC-based compute farms. That is where Divesh Aggarwal and colleagues from Singapore, France and Australia come in. For our action movie Aggarwal plays the pragmatic scientist who helps the hero save the day.

事实并不尽然如此。现在区块链技术受到量子计算机严重威胁这一结论是通过比较预计近期会出现的量子计算机的计算速度和基于现有ASIC芯片建立的矿池的能力得出的结论。这也是Divesh Aggarwal以及其新加坡、法国和澳大利亚同事得出结论的基础。在我们的动作电影之中，Aggarwal扮演的角色是务实的科学家，帮助我们的英雄拯救了世界。

Saving the day turns out to be a quantitative and comprehensive analysis of projected quantum computer clock speeds over the next two decades. What the Aggarwal team finds is that despite the expected exponential speed-up, BitCoin and associated cryptocurrencies are, relatively speaking, resistant to dominance by quantum computers because of the current and extremely fast performance of ASICs. But, that relief comes with a warning, as PoW elliptic curve hash signature schemes could be broken by single quantum computers as early as 2027. They may well succeed in attacking public, and returning private keys in less than 10 minutes.

最后，事实证明，在未来二十年中，起决定性作用的是对量子计算机预估时间表量化、全面的分析。Aggarwal团队认为虽然量子计算机会导致计算速度会呈几何倍数地提高，比特币和其他加密货币也会采取相应的措施应对量子计算机的威胁，ASIC芯片现在已经实现了极高的性能。但是，我们在松一口气的同时不能忘记仍然面临的威胁，因为PoW共识采用的椭圆曲线哈希电子签名算法最快在2027年就可以用单台量子计算机破解。届时，量子计算机可能用不了十分钟就可以从公钥推导出私钥。

What about ‘quantum resistant’ ledgers and post-quantum cryptography? Time to on- board and leave ‘classical’ methods behind? Maybe it is, and maybe not according to mathematician Daniel Bernstein. As he reports there are a number of existing cryptographic systems beyond RSA, DSA and ECDSA including: hash-based, code-based, lattice- based, and multivariate quadratic equations-based cryptography, each seen as resistant to attack from both classical and quantum-based computers.

是否存在“抗量子计算”的分布式账本和后量子密码学呢？是否是时候摒弃“传统”方法了呢？数学家Daniel Bernstein认为答案或许是“是”，但是也可以为“否”。Daniel Bernstein认为除了RSA、DSA和ECDSA之外，现在还有许多密码体系，包括：基于哈希函数的、基于编码的和基于格的密码体系，每一个密码体系似乎都能抵挡来自传统计算机和量子计算机的攻击。

“We find that the proof of- work used by Bitcoin is relatively resistant to substantial speedup by quantum computers in the next 10 years …”Aggarwal.et.al.

“我们发现在未来十年，比特币所使用的工作证明共识机制将更好地抵抗量子计算机带来的计算速度大幅提升……”，Aggarwal团队说道。

So why not switch now and not worry when quantum supreme computers actually arrive? Again, Bernstein provides some thoughts, around how cryptographic systems are a collaborative science, played out between cryptographers who design systems to scramble and unscramble data, and cryptanalysts busy developing the best, most effective attacks to break these very same systems.

那我们为什么不从现在开始使用不同的密码体系，这样即使量子计算机真的出现，我们也不用担心了？Bernstein还分享了更多的看法，进一步说明了密码体系是一个多方合作的科学。密码体系中既有密码专家负责进行数据加扰和去扰，也有密码破译专家负责设计最为有效的最佳攻击方法，破解密码专家设计的体系。

To be prepared for a post-quantum future he gives three answers for why it is not too early to start today, rather than waiting until the announcement of a large quantum computer. Starting with identifying the interesting ideas:

为迎接后量子未来，Bernstein还从三方面回答了为什么应该从现在开始转变，而不是等到大型量子计算机出现之后再进行改变。主要原因有三：

1. We need time to improve the efficiency of post-quantum cryptographic algorithms.

我们需要时间提升后量子密码算法的效率；

2. We need time to build confidence in the robustness of these systems.

我们需要时间建立对此类密码体系的信心；

3. We need time to build up their usability.

我们需要时间增强此类密码体系的可用性。

Any forward thinking blockchain company will be doing just that, building the right kind of flexibility into their platform and infrastructure to deliver systems that can migrate from a classical to post-quantum future with a minimum of upset.

任何高瞻远瞩的区块链公司都会提前布局，在一定程度上对平台和基础设施进行灵活设计，从而确保其系统能够尽可能方便地从传统架构转移到后量子架构。

The prospects of incredibly powerful quantum computers dominating our digital lives makes for good action movies. So now fast forward to 2027, and our hero once again has to save the world from technology gone off the rails. This time, from a sentient quantum computer bent on replacing the human race with its own simulation.

未来有可能出现极为强大的量子计算机统治我们的数据生活这一情节非常适合用于拍摄动作电影。因此，从现在快进到2027年，我们的英雄再一次控制了暴走的技术，拯救了世界。但是这一次是制止了一台有感情的量子计算机尝试用自己的克隆体取代人类。

Call it, ‘Buckaroo Blockchain’. Wait, maybe the human race in a computer simulation idea has been done before. Watch this space.

名字就叫“区块链牛仔”。等等，或许我们已经拍过电脑试图用克隆体取代人类的电影了。让我们拭目以待。

参考文献（References）：

1.“ASCR Report on a Quantum Computing Testbed for Science”, Sponsored by U.S. Department of Energy, Office of Science, Advanced Scientific Computing Research Program, 2017

2.“Bitcoin Mining the Hard Way: the Algorithms, Protocols, and Bytes”, Ken Shirrif’s Blog, 2018

3.“A Quantum Boost for a Different Kind of Computer”, MIT Technology Review 2017

4.“Could Quantum Computing Kill Blockchain?”, Invest in Blockchain 2018

5.“Bitcoin and Cryptocurrency Technologies”, Arvind Narayanan et.al. Princeton Univ. 2016

6.“Introduction to the SHA-256 hash function”, steemit blog 2017

7.“What is an ASIC miner?”, digitaltrends.com 2018

8.“How Quantum Computing Threatens Blockchain”, National Review 2018

9.“Quantum Computers Pose Imminent Threat to BitCoin Security”, MIT Technology Review 2018

10.“How Blockchain is an Execution Layer in the Cloud”, Hacker Noon 2017

11.“Consensus in Blockchain Systems. In Short.”, Chris Hammerschmidt 2017

12.“An introduction to understanding attacks and dishonesty on proof-of-work blockchains”, Chris Hammerschmidt 2017

13.“Introduction to Proof of Work or Stake in the Blockchain”, Tibert van der Loop 2016