風靡全球的量子計算，對區塊鏈的安全構成威脅嗎？現有的區塊鏈技術能抗擊量子計算的破解能力嗎？區塊鏈技術還可以做出哪些反擊？
帶著這些至關區塊鏈行業的核心痛點的問題，我們引領大家初步學習一下，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.
先把動作電影放一邊，能用於實際工作的大型量子計算機的開發日益加速，這也切實對區塊鏈技術和密碼學構成了威脅。量子計算挑戰了現代密碼學算法的核心數學基礎，使得這些算法不再有效。
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的數字簽名謎題雖然非常困難，但是並不是不可能的，比特幣的礦工們除了隨機嘗試一個一個可能的答案之外並沒有更好的特定算法能幫助求解。
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的傳統二進制編碼，量子計算機的量子位具有疊加屬性，通過利用最小的物理量呈幾何倍數地提高計算能力。一個計算週期就可以處理幾十億條信息。
I
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
14.“Why Bitcoin fears Quantum Computers— and IOTA doesn’t”, Hacker Noon 2018
15.“Quantum attacks on Bitcoin, and how to protect against them ”, Divesh Aggarwal, et.al. 2017
16.“Post-Quantum Cryptography”, Editors: Bernstein, Daniel J., Buchmann, Johannes, Dahmen, Erik (Eds.) 2009
17.“Post-Quantum Cryptography”, Bernstein, DJ and Lange T., Nature 2017
附錄：圖表1：
圖表2：上圖為未來25年比特幣網絡（每秒哈希值，用藍色曲線表示）和單臺量子計算機（用紅色曲線表示）的哈希率對比圖。我們所做估算或多或少會存在樂觀或者具有一定程度的不確定性。
閱讀更多 Penta公鏈中文社區 的文章
