區(qū)塊鏈與量子計算

郭煒立 楊宇光

(北京工業(yè)大學信息學部 北京 100124) (yesguoweili@163.com)

區(qū)塊鏈是比特幣等新型數(shù)字加密貨幣體系的核心技術.其優(yōu)點是去中心化，而且能通過運用數(shù)字加密、時間戳、智能合約和經(jīng)濟激勵的手段，在每個節(jié)點之間都不需要相互信任的分布式系統(tǒng)中實現(xiàn)去中心化信用的點對點之間的交易，從而能夠解決很多中心化機構都普遍存在的低效率、高成本以及存儲不安全等問題.在2016年10月18日，由工業(yè)和信息化部信息化和軟件服務業(yè)司以及國標委指導下，中國區(qū)塊鏈技術和產(chǎn)業(yè)發(fā)展論壇編寫的《中國區(qū)塊鏈技術和應用發(fā)展白皮書(2016)》[1]指出，區(qū)塊鏈是分布式數(shù)據(jù)存儲、點對點傳輸、加密算法、共識機制等計算機技術在互聯(lián)網(wǎng)時代的創(chuàng)新應用模式.隨著近幾年比特幣的不斷普及與發(fā)展，區(qū)塊鏈技術也呈現(xiàn)出越來越火熱的態(tài)勢，被人們認為是在大型機、個人電腦、互聯(lián)網(wǎng)、移動社交網(wǎng)絡之后計算范式的第5次顛覆式創(chuàng)新，是人類信用進化史上繼血親信用、貴金屬信用、央行紙幣信用之后的第4個里程碑[2].

2008年由一名化名為“中本聰”的學者在密碼學郵件組發(fā)表的論文《比特幣:一種點對點電子現(xiàn)金系統(tǒng)》[3]，開啟了區(qū)塊鏈技術的新篇章.但目前在行業(yè)內還沒有形成公認的區(qū)塊鏈定義.從狹義上來講，區(qū)塊鏈技術是一種特定的數(shù)據(jù)結構，它按照時間順序將每個數(shù)據(jù)區(qū)塊以鏈的方式組合而成，并且是采用密碼學方式保證的不可偽造及不可篡改的去中心化共享總賬本(decentralized shared ledger)，能存儲在時間上有先后順序的、簡單的、可以在系統(tǒng)內驗證的數(shù)據(jù).區(qū)塊鏈技術的廣義定義則是利用密碼學方式加密鏈式區(qū)塊結構來驗證與存儲數(shù)據(jù)，利用共識算法來更新數(shù)據(jù)，用智能合約來編程和操作數(shù)據(jù)，是一種去中心化的基礎架構與分布式計算范式.區(qū)塊鏈技術具有去中心化、時序數(shù)據(jù)、共同維護、能編程、安全等特點.首先是去中心化.區(qū)塊鏈應用純數(shù)學方法建立分布式節(jié)點之間的信任，所以能形成去中心化的安全可信的分布式系統(tǒng).第二是時序數(shù)據(jù).區(qū)塊鏈的鏈式區(qū)塊結構帶有時間戳，所以在存儲數(shù)據(jù)時能為其增加時間維度，從而使數(shù)據(jù)具有極強的可追溯性和可驗證性.第三是共同維護.區(qū)塊鏈系統(tǒng)采用經(jīng)濟激勵機制使分布式系統(tǒng)中所有節(jié)點都可參與數(shù)據(jù)區(qū)塊的驗證過程(類似于比特幣的“挖礦”過程)，通過共識算法來選擇特定的節(jié)點，將新的區(qū)塊添加到區(qū)塊鏈上.第四是可編程.用戶可以使用區(qū)塊鏈技術提供的靈活的腳本代碼系統(tǒng)來創(chuàng)建高級智能合約或其他的去中心化應用.例如，以太坊(Ethereum)平臺為用戶提供了圖靈完備的腳本語言，以構建任何可以精確定義的智能合約或交易類型[4].最后是安全.區(qū)塊鏈技術采用的數(shù)據(jù)加密系統(tǒng)是基于非對稱密碼學原理，同時利用工作量證明等共識算法形成的強大算力抵御外部攻擊，能夠保證區(qū)塊鏈數(shù)據(jù)不可篡改和不可偽造，所以具有較高的安全性.

1 區(qū)塊鏈技術分析

區(qū)塊鏈是把數(shù)學、密碼學、演算法和經(jīng)濟模塊等技術整合在一起形成的一種新型的存儲、記錄和表達方式.其中區(qū)塊鏈的核心技術主要包括以下幾個方面.

1.1 區(qū)塊和鏈

區(qū)塊鏈由一個個的數(shù)據(jù)區(qū)塊連接在一起而形成，數(shù)據(jù)區(qū)塊分為區(qū)塊頭(Header)和區(qū)塊體(Body)兩部分.其中區(qū)塊頭包括當前區(qū)塊版本號(Version)、前一個區(qū)塊的散列值(Perv-block)、當前區(qū)塊的目標散列值(Bits)、當前區(qū)塊PoW共識過程的解隨機數(shù)(Nonce)、Merkle根節(jié)點散列值(hashMerkleRoot)以及時間戳(Timestamp).區(qū)塊體中包括當前區(qū)塊的交易數(shù)目(TransactionCounter)和經(jīng)過驗證的、區(qū)塊創(chuàng)建過程中生成的所有的交易記錄(Transactions).這些記錄將通過Merkle樹的散列運算過程生成獨一無二的Merkle根并記入?yún)^(qū)塊頭.每一數(shù)據(jù)區(qū)塊都是通過“前一區(qū)塊的散列值”指向前一個區(qū)塊，從而形成一個巨大的鏈條，該鏈條可以一直追溯至源頭即創(chuàng)世區(qū)塊，創(chuàng)世區(qū)塊的“前一區(qū)塊的散列值”為0.Merkle根的生成過程是將區(qū)塊主體中所有交易的散列值逐級兩兩散列計算而形成，其主要作用是用于檢驗一筆交易是否存在于這個區(qū)塊中.比特幣網(wǎng)絡系統(tǒng)可以動態(tài)調整PoW共識過程的難易程度，第1個找到正確的解隨機數(shù)Nonce，且通過全體礦工驗證的礦工會獲得目前區(qū)塊的記賬權.值得一提的是，如果2個礦工在短時間內同時“挖出”2個新的區(qū)塊并且加以鏈接，區(qū)塊主鏈就可能會出現(xiàn)“分叉”現(xiàn)象，解決分叉問題的方法是約定礦工選擇延長累計工作量證明(PoW)最大的區(qū)塊鏈.簡單來說就是當主鏈產(chǎn)生分叉后，后續(xù)區(qū)塊的礦工通過計算和比較，把區(qū)塊鏈連接到當前累計工作量證明最大的備選鏈上，形成長度更長的新主鏈，進而解決了分叉問題.區(qū)塊鏈通過添加時間戳來記賬，使其形成了一個不可篡改且不能偽造的交易數(shù)據(jù)庫.

1.2 非對稱加密

非對稱加密是在加密和解密過程中分別使用公鑰和私鑰2個非對稱的密碼.非對稱密鑰對具有2個特點：1)用其中的一個密鑰(公鑰或私鑰) 加密信息，該加密信息只有用另一個對應的密鑰才能解開；2)公鑰可以公開、私鑰則需要保密，任何人無法通過公鑰推算出相應的私鑰.以比特幣系統(tǒng)為例，其通過調用操作系統(tǒng)的隨機數(shù)生成器生成一串256 b的隨機數(shù)來作為私鑰，這樣生成的比特幣私鑰總量可達，而且極難通過遍歷所有的私鑰空間來獲得存有比特幣的私鑰[5].為了方便識別，如圖1所示，通過Base58和SHA256散列算法轉換，將256 b二進制形式的比特幣私鑰轉換成50個字符長度的且易于識別和書寫的私鑰給用戶；而比特幣的公鑰是由私鑰先經(jīng)過Secp256k1橢圓曲線算法計算后生成長度為65 B的隨機數(shù).該公鑰可用于比特幣交易時使用的地址，成過程為先將公鑰進行RIPEMD160和SHA256散列運算并生成長度為20 B的hash160結果，再經(jīng)過SHA256散列算法和Base58轉換形成33個字符的比特幣地址[6].區(qū)塊鏈的所有權信任基礎是基于數(shù)學的，利用非對稱加密算法保障交易數(shù)據(jù)的安全可信，每一個節(jié)點都配備一個私鑰和公鑰，而且公鑰的生成過程不可逆.公鑰公開給區(qū)塊鏈網(wǎng)絡上的所有的節(jié)點，但私鑰僅本節(jié)點擁有.交易時用私鑰加密后發(fā)送，接收方可以用發(fā)送方的公鑰解密.

圖1 比特幣非對稱加密系統(tǒng)

1.3 分布式賬本

所謂分布式記賬本，即分布在不同地方的多個節(jié)點共同完成交易記賬，網(wǎng)絡中的每個節(jié)點都會有驗證區(qū)塊數(shù)據(jù)、網(wǎng)絡路由、傳播區(qū)塊數(shù)據(jù)、發(fā)現(xiàn)新節(jié)點等功能.因為網(wǎng)絡中所有的交易記錄也會記錄在每個節(jié)點中，所以它們都可以參與交易的合法性監(jiān)督，也可為某一交易作證.按照節(jié)點的存儲數(shù)量可以分為全節(jié)點和輕量節(jié)點.全節(jié)點保存有自創(chuàng)世區(qū)塊到目前最新區(qū)塊為止的所有區(qū)塊數(shù)據(jù)，而且會動態(tài)更新主鏈，實時參與區(qū)塊數(shù)據(jù)的校驗和記賬.其優(yōu)點在于不用依賴任何其他節(jié)點就能夠獨立完成任意區(qū)塊數(shù)據(jù)的更新、查詢和校驗.缺點則是全節(jié)點的空間維護成本較高.由于記賬節(jié)點有很多，理論上除非將所有節(jié)點都破壞，否則賬目就不會丟失，這樣就保證了賬目數(shù)據(jù)的安全性.區(qū)塊鏈采用分布式記賬、分布式存儲、分布式傳播，從而保證了系統(tǒng)內的數(shù)據(jù)存儲、交易驗證、信息傳輸都是去中心化的.

1.4 共識機制

網(wǎng)絡中的各個節(jié)點之間如何有效的達成共識這就是共識機制，確認一個交易的有效性，既是認定的方法也是防止篡改的手段.區(qū)塊鏈技術的優(yōu)勢之一就是可以在決策權高度分散的去中心化系統(tǒng)中使各節(jié)點高效地針對區(qū)塊數(shù)據(jù)的有效性達成共識.區(qū)塊鏈有4 種共識機制，分別是工作量證明(PoW)、權益證明(PoS)、授權股份證明機制(DPoS)和驗證池(Pool).在不同的應用場景這4種共識機制各具優(yōu)勢，例如比特幣采用的就是工作量證明機制.工作量證明的強大計算能力為區(qū)塊鏈的安全性和不可篡改性提供了有力保證，假設有惡意攻擊者想要篡改或攻擊區(qū)塊數(shù)據(jù)，都必須重新計算這個區(qū)塊和它后面所有區(qū)塊的工作量，而且只有在控制了超過全網(wǎng)51%的節(jié)點計算力并且計算速度需要使偽造鏈長度超過主鏈的情況下，才可能偽造出一條不存在的記錄，然而這種攻擊的難度將會使其成本遠超其收益.

PoW共識機制對于比特幣是具有重要意義的創(chuàng)新，其近乎完美地整合了比特幣的貨幣發(fā)行、驗證和交易支付等功能，并通過算力競爭來保障系統(tǒng)的安全以及去中心性；但是PoW共識機制同樣存在著顯著的缺陷，其強大算力會造成資源浪費(如電力)而且交易確認時間長達10 min，使其不適合小額交易的商業(yè)應用.

1.5 智能合約

智能合約簡單來說就是一種協(xié)議，它采用編程語言(腳本)，是基于可信的、不可篡改的數(shù)據(jù)，會使系統(tǒng)能處理一些無法預知的交易模式，當約定的條件得到滿足時，系統(tǒng)就會自動地執(zhí)行一些預先定義的規(guī)則和條款.比特幣采用的是一種簡單的、基于堆棧、自左向右處理的腳本語言，腳本本質上是附著在比特幣交易上的一組指令的列表.比特幣交易依賴于鎖定腳本和解鎖腳本加以驗證，在比特幣交易中二者的不同組合可衍生出很多的控制條件.其中，鎖定腳本當作是附著在交易輸出值上的“障礙”，它規(guī)定了以后花費這筆交易輸出的條件；解鎖腳本則是當被鎖定的腳本在一個輸出上設定的花費條件被滿足時它將允許輸出被消費.

2 區(qū)塊鏈分類

2.1 公有區(qū)塊鏈

公有鏈是指任何人都能讀取都能發(fā)送交易而且交易都能獲得有效的確認、任何人都能參與其共識過程的區(qū)塊鏈.公有鏈通常被認為是“完全去中心化”無管理機構、無官方組織、無中心服務器.公有區(qū)塊鏈是世界上存在最早的區(qū)塊鏈，也是目前應用最廣泛的區(qū)塊鏈，公有區(qū)塊鏈具有保護用戶免受開發(fā)者影響，且訪問門檻低，所有數(shù)據(jù)都默認公開的特點.

2.2 私有區(qū)塊鏈

私有鏈指的是其寫入權限在企業(yè)或者個人手里的區(qū)塊鏈.但是讀取權限對外開放.其特點是交易速度非常快，交易成本很低甚至為0，能給隱私以更好的保障，且有助于保護基本的產(chǎn)品不會被破壞.

2.3 聯(lián)盟區(qū)塊鏈

聯(lián)盟區(qū)塊鏈介于公有區(qū)塊鏈和私有區(qū)塊鏈之間，對特定的組織團體開放.在某組織內部指定幾個預選的節(jié)點為記賬人.預選節(jié)點參與共識過程，而且每個塊的生成由這幾個選出的預選節(jié)點共同決定，其他的接入節(jié)點可以參與交易，但是不可以過問記賬過程.

3 區(qū)塊鏈技術的特點和優(yōu)勢

3.1 區(qū)塊鏈技術的特點

用去中心化結構提高運作效率降低運營成本.區(qū)塊鏈技術的信任機制是建立在數(shù)學原理基礎之上，這就可以使區(qū)塊鏈系統(tǒng)中的人們在無需了解對方基本信息的情況下進行可信任的價值交換，在信息安全的同時也保證了系統(tǒng)運營的高效率與低成本.

數(shù)據(jù)信息完整透明使得區(qū)塊鏈符合法律要求和便于追蹤.因為區(qū)塊鏈把從創(chuàng)世塊到現(xiàn)在的所有交易都明文記錄在區(qū)塊中，而且形成的數(shù)據(jù)記錄不可篡改，因此可以查詢或追蹤到任何交易雙方之間的價值交換活動.這種完全透明的數(shù)據(jù)管理體系可以為現(xiàn)有的審計查賬、物流追蹤、操作日志記錄等提供可信任的追蹤捷徑.

用分布式方法記賬與存儲可以提高容錯性.由于區(qū)塊鏈將記賬與存儲功能分配給每一個參與的節(jié)點，因此不會出現(xiàn)集中模式下的服務器崩潰的風險.分布模式的使用能讓區(qū)塊鏈在運轉的過程中有非常強大的容錯性功能，即便是數(shù)據(jù)庫中的一個或幾個節(jié)點出錯也不會影響到整個數(shù)據(jù)庫的數(shù)據(jù)運轉.

智能合約使區(qū)塊鏈有靈活的可編程性.區(qū)塊鏈技術基于可編程原理內嵌入了腳本的思想，這就為今后基于區(qū)塊鏈技術的價值交換活動增加了一種智能的可編程模式.

全球共用一個數(shù)據(jù)庫提高了業(yè)務包容性.基于區(qū)塊鏈技術建立的數(shù)據(jù)庫是一個可以在全球范圍內運行的超級大數(shù)據(jù)庫，區(qū)塊鏈所有的價值交換活動(例如開戶、登記、交易、支付、清算等)都可以在這個數(shù)據(jù)庫中完成，業(yè)務模式具有極高的包容性.

透明世界背后的匿名性——保護隱私.區(qū)塊鏈的信任基礎是通過純數(shù)學方式建立起來的，能讓人們在互聯(lián)網(wǎng)世界里實現(xiàn)信息共享的同時，不暴露在現(xiàn)實生活中的真實身份.區(qū)塊鏈上的數(shù)據(jù)都是公開透明的，但數(shù)據(jù)并沒有綁定到個人.透明世界的背后具有匿名性特點.

3.2 區(qū)塊鏈技術的核心應用優(yōu)勢

在了解區(qū)塊鏈的技術原理及特點之后，就能發(fā)現(xiàn)區(qū)塊鏈技術的核心價值所在.在無需系統(tǒng)內各節(jié)點互相信任的情況下，系統(tǒng)能保證一切數(shù)據(jù)的記錄都是真實有效的，從而形成了一個誠實有序的去中心化分布式的數(shù)據(jù)庫，而且用戶可以對系統(tǒng)內參與交換的價值進行靈活地編程.

去中心化的分布式結構：能夠節(jié)省大量的中介成本.由于區(qū)塊鏈技術能使人與人之間在不需要互信的情況下進行大規(guī)模的協(xié)作，所以其可以被應用于許多的傳統(tǒng)中心化領域，用來處理一些原本由中介機構處理的交易.

不可篡改的時間戳：能解決信息防偽和數(shù)據(jù)追蹤問題.在當今社會中，大量的假冒信息與數(shù)據(jù)困擾著我們的生活.而區(qū)塊鏈技術能夠很好地進行數(shù)據(jù)追蹤以及辨別信息真?zhèn)?因為區(qū)塊鏈中數(shù)據(jù)之間前后相連形成了一個不可篡改的時間鏈，就像為所有的物件貼上一套不可偽造的真實記錄，這對于現(xiàn)實生活中打擊假冒產(chǎn)品和整頓信息紀律等都有巨大的幫助.

安全的信任機制：可解決如今物聯(lián)網(wǎng)技術上的致命缺陷.傳統(tǒng)的物聯(lián)網(wǎng)是由一個數(shù)據(jù)中心來收集所有信息，這樣就會導致設備的生命周期等方面存在嚴重缺陷.區(qū)塊鏈技術能在無需信任單個節(jié)點的同時創(chuàng)建整個網(wǎng)絡的信任共識，從而能從根本上解決物聯(lián)網(wǎng)這一致命缺陷，使物與物之間不僅相連，而且能自發(fā)活動起來.

靈活的可編程特性：能夠使區(qū)塊鏈幫助規(guī)范現(xiàn)有市場秩序.由于當今的市場秩序不夠規(guī)范，在轉移自己資產(chǎn)時無法保證其能在未來發(fā)揮應有的價值.如果將區(qū)塊鏈技術的可編程性引入，在資產(chǎn)轉移的同時編輯一段程序寫入其中，能有效地規(guī)定資產(chǎn)今后的用途與方向.

4 量子計算的優(yōu)勢和算法

隨著信息化時代的飛速發(fā)展，人們對于信息處理速度方面的需求也越來越高，當今的計算機硬件水平已經(jīng)很難再出現(xiàn)突破性的發(fā)展，已不能滿足人們在信息處理速度方面的需求.然而在19世紀初期提出的量子力學理論給計算機帶來新的發(fā)展契機，量子具有獨有的相干性以及糾纏性等特性能夠為量子計算提供完全與經(jīng)典計算不同的獨特運算方式.在經(jīng)過了近一個世紀的發(fā)展后，美國國家標準技術研究院于2009年研制出了世界上第1臺通用編程量子計算機.量子計算是基于量子力學原理進行有效計算的新型計算模式，它能夠利用量子的疊加性、糾纏性以及量子的相干性來實現(xiàn)量子的并行計算，從而量子計算可以從根本上轉變傳統(tǒng)的計算理念.

4.1 量子計算的優(yōu)勢

1982年美國物理學家費曼(R.P.Feynman)提出量子計算概念，但由于量子態(tài)的測不準原則以及量子系統(tǒng)容易受噪聲干擾，量子運算很容易出錯.直到1994年美國計算機專家Shor證明了量子計算機能快速分解大因數(shù)，并實現(xiàn)了第1套量子算法編碼，量子計算以及量子計算機的研究才進入實驗時代.

經(jīng)典比特具有0和1這2種狀態(tài).量子比特與經(jīng)典比特的不同之處在于：一個量子比特除了可以像經(jīng)典比特一樣處于0和1這樣的狀態(tài)之外，還可以處于既非0又非1的狀態(tài)，這個中間狀態(tài)稱為疊加態(tài)(superposition).量子疊加態(tài)是決定量子計算不同于經(jīng)典計算的關鍵特性之一，也是量子并行計算的理論基礎.相同位數(shù)的寄存器，量子計算機可以記錄的信息量是傳統(tǒng)計算機的指數(shù)倍，其運算速度和信息處理能力是經(jīng)典計算機所無法比擬的.因此，量子的并行計算體現(xiàn)了量子計算最重要的優(yōu)越性.

4.2 量子算法

量子計算科學的重要部分即是量子算法，在過去的十幾年中，量子算法得到了廣泛的發(fā)展且取得了驚人的成就.基于Grover的量子搜索算法和基于Shor的量子Fourier變換算法是目前已知的最為成熟的2種量子算法.早在1989年Deutsch就首次提出了Deutsch量子算法.該算法首次很好地展示出了量子計算機的并行性.1994年，Shor提出了大數(shù)質因子分解量子算法并且將該算法的量子編碼進行了實現(xiàn)，在此之后，Grover數(shù)據(jù)庫搜索算法、量子智能算法等量子算法也相繼被提出[7]，各國也相繼展開對量子算法的研究工作.

4.2.1Shor大數(shù)質因子分解算法

1994年，Peter WillistonShor提出了基于離散對數(shù)問題和大整數(shù)質因子分解問題的量子算法，證明了這2個復雜的問題都屬于BQP類，這一發(fā)現(xiàn)不僅使人們第1次清楚地認識到量子計算獨特的優(yōu)勢和重要應用前景，而且極大地促進了量子計算的發(fā)展.此后，世界眾多研究小組紛紛加入了該項研究行列.得益于此，量子計算研究的許多領域取得了重大進步，Shor提出的量子糾錯也同樣重要，這項研究使容錯的量子計算變?yōu)榭赡?在密碼學領域量子計算也取得了迅速的發(fā)展，Shor算法的重要性不言而喻，因為它代表我們可以使用量子計算機來破解目前廣泛使用的公開密鑰機密算法，這將意味著政府、軍事及金融機構等重要單位的RSA公鑰密碼體系的安全性將會面臨致命的威脅，僅僅這一點就能引起人們對量子算法的足夠重視.

在目前提出的量子算法中，Shor算法已經(jīng)發(fā)展得相當成熟，其改進和優(yōu)化的空間不大.該算法不僅有著傳統(tǒng)算法無法比擬的優(yōu)勢，而且其表現(xiàn)出的實際應用價值以及巧妙的理論構思都十分寶貴.

4.2.2Grover數(shù)據(jù)庫搜索算法

Grover算法在解決從無序數(shù)據(jù)庫中搜索某個特定數(shù)據(jù)的問題上有獨特的優(yōu)勢.Grover算法利用量子的并行性，并不像Shor算法一樣實現(xiàn)解決問題的指數(shù)加速，然而搜索算法在廣泛應用性上卻很好地彌補了這一點.Grover算法可以作為通用算法解決現(xiàn)實中有許多問題，比如圖的著色問題、密碼的窮舉攻擊問題、排序問題及最短路徑問題等.事實上，Grover算法目前已經(jīng)在光學系統(tǒng)和核磁共振中得到實現(xiàn).

4.2.3量子智能算法

自從Shor算法和Grover算法相繼提出以后，量子計算方法以其獨特計算方式和在信息處理方面表現(xiàn)出的巨大潛力引起了研究者們的廣泛關注.雖然許多的研究者在量子算法領域投入了大量的研究，但迄今為止并沒有取得實質性的突破.而智能算法一直都是算法研究領域的一個熱點，將量子理論原理和智能計算相結合而產(chǎn)生的量子智能算法具有眾多優(yōu)點，比如在避免早熟現(xiàn)象和加快算法的收斂速度等.利用量子并行計算特性可以很好地彌補智能算法中的某些不足之處.

目前己存在的量子智能算法研究包括：量子進化算法、量子退火計算、量子神經(jīng)網(wǎng)絡、量子免疫計算和量子聚類算法等.其中，量子進化算法和量子神經(jīng)網(wǎng)絡已經(jīng)成為了目前學術研究的熱點并且取得了不錯的成績.

目前量子進化算法的應用研究領域還處于初級階段，未來量子進化算法的研究還有很長的路要走，很多的理論和應用研究還需要進一步深化和推廣，研究的空間還很大.

5 量子計算對于區(qū)塊鏈的威脅

區(qū)塊鏈技術作為比特幣的核心技術，想了解量子計算對于區(qū)塊鏈產(chǎn)生怎樣的威脅，首先要知道比特幣系統(tǒng)中采用什么樣的安全協(xié)議，比特幣的安全協(xié)議涉及2種類型密碼學，即在比特幣“挖礦”過程中使用的散列函數(shù)以及用于在區(qū)塊鏈上提供數(shù)字簽名的非對稱密碼術.

對于比特幣而言，新比特幣通過“挖礦”生成，進行“挖礦”工作的人被稱為“礦工”，挖礦的過程就是礦工利用計算機來計算比特幣網(wǎng)絡中數(shù)學問題的過程.第1個解決問題的礦工公布其答案，并計入賬本，同步計入比特幣網(wǎng)絡中的所有節(jié)點，這就表示挖礦成功，比特幣系統(tǒng)就會獎勵礦工一定數(shù)量的比特幣.不對稱密碼術則用于比特幣區(qū)塊鏈交易的授權，公鑰密碼系統(tǒng)(Public Key)會為整個鏈上的每個用戶分配1個公鑰和1個私鑰，公鑰密碼系統(tǒng)會使用1對公鑰和私鑰來加密信息：公鑰可以廣泛共享，私鑰只有密鑰所有者才知道.任何人都可以使用接收者的公鑰來加密消息，但解密消息只有通過接收者使用其私鑰才能進行.這樣的非對稱密碼算法使用過程就稱為橢圓曲線數(shù)字簽名算法(ECDSA)，通過一個給定的私鑰，很容易推算出相對應的公鑰，但是反過來推算很困難，這就體現(xiàn)出現(xiàn)在比特幣的安全性.

5.1 量子計算對挖礦的威脅

比特幣所使用的技術之一是SHA-256，它是一種加密散列函數(shù)，可以將任意輸入數(shù)據(jù)轉換成256 b串(“散列”).使用SHA-256散列函數(shù)為每一個區(qū)塊計算一個隨機數(shù).雖然得到的結果很容易被驗證，但是搜尋的過程卻很難.比特幣挖掘包括查找輸入(“隨機數(shù)”)的搜索問題，再加上最近的一個塊的信息，這些信息生成的散列值小于目標值T，可以被認為是有效的比特幣散列的最大數(shù)字.通過不斷調整目標值，使得塊之間的平均時間為10 min(在寫入目標時大約為T=8.9×1011，遠小于2256=1.2×1077).如果有可能找到一個量子算法來有效地轉化SHA-256，那么我們可以很容易地找到比特幣.然而，比特幣的價值就體現(xiàn)在找到這樣的解決方案的難易程度上.目前人們認為沒有有效的經(jīng)典的或量子的算法，可以轉化為SHA-256.因此，唯一的方法是使用蠻力搜索，這意味著需要嘗試不同的輸入，直到找到一個滿意的解決方案為止.

量子力學中的Grover搜索似乎可以完美地解決這類問題，并有一個二次量子加速.讓我們看看這個策略在與傳統(tǒng)計算機進行比較時的工作效果如何.從經(jīng)典的角度來看，使用猜測來挖掘一個塊的成功概率是Trt2256，其中r是散列率(每秒作出的猜測次數(shù))，t是以秒為單位的時間.對于運行Grover算法的量子礦工，成功概率是其中rq是每秒Grover迭代次數(shù)，我們稱之為“量子散列率”.

現(xiàn)在的古典和量子礦工之間存在著不同的心態(tài)，因為比特幣被設計為平均每10 min(600 s)尋找一個新的塊，因此搜索問題的性質就在這時發(fā)生了變化.為了使Grover程序能夠給出高的成功率，量子礦工應該在問題改變之前運行他們的算法一段時間，然后再進行測量.與此同時，古典礦工在這段時間嘗試了盡可能多的隨機數(shù).所以量子礦工希望古典礦工在Grover進化過程中找不到解決問題的辦法.由于區(qū)塊之間的區(qū)間遵循指數(shù)分布，區(qū)塊數(shù)量仍然可以由開采成功的概率給出.假設量子計算機在給定的時間內運行成本不變，那么量子比特幣挖掘的盈利就是這樣：

其中，R是獎勵，C是運行量子計算機的成本.

比特幣的開采是否有利可圖呢，假設一臺量子計算機每小時的使用成本與經(jīng)典計算機相同，并使用今天的比特幣價格、區(qū)塊獎勵和挖掘難度.我們估計，量子比特幣的開采將以48khashs的量子散列速率實現(xiàn)盈利.相對于目前最好的經(jīng)典比特幣挖掘硬件，其散列速率為125khashs，這些數(shù)字可能看起來很有希望，但我們需認識到傳統(tǒng)的比特幣礦商可以實現(xiàn)巨大的散列速率，因為隨機猜測的挖掘算法可以很容易地實現(xiàn)并行化.問題是不管有多少的量子位，量子優(yōu)勢不會超過因子的因此，雖然有量子優(yōu)勢，但它并不是不可克服的，并不是古典的并行無法擊敗它的.對于一個散列速率比最低的48khashs低的量子計算機，人們只需要借助于經(jīng)典的量子計算機并行化.例如，如果量子散列速率是3khashs，那么需要1 300個量子計算機才能比得上最佳的經(jīng)典采礦硬件，而且這些硬件可以在今天隨時購買.因此，要使量子采礦獲利，就需要相當快的量子散列速率和更強的量子加速.這種情況在未來可能還會發(fā)生，但對于目前的情況來說，古典采礦似乎很難被擊敗.

在比特幣系統(tǒng)中，雖然經(jīng)典計算機的算力和挖礦的成功率有一定關系，但是算力大也并不是意味著一定能挖到礦(在你的總算力沒超過全網(wǎng)絡算力50%的情況下)，挖礦的成功率和運氣也有一定程度的關系，就像走迷宮一樣，即便是一個人走得快，如果他每條路都試一下，他肯定可以到達迷宮終點，如果一個人雖然走得慢，但只用一次嘗試就能走到了迷宮的終點.所以，走得慢的人也有贏走得快的人的可能性，同理，算力強大的礦工也并不一定能比算力小的礦工先挖到礦.在區(qū)塊鏈系統(tǒng)中，如果一個礦工組掌握著整個網(wǎng)絡中51%的算力，那么他就能壟斷整個區(qū)塊鏈，因為他永遠會比剩余的49%算力的礦工組更快地處理區(qū)塊，也就是說他將會得到之后產(chǎn)生的所有比特幣.

戴夫士·阿加沃爾(Divesh Aggarwal)和新加坡國立大學(NUS)的研究人員對量子計算機將會威脅到挖礦的問題進行了深入研究，并且在2017年10月就此發(fā)表了論文，首先他們認為在未來至少10年內，使用ASIC挖礦的速度會比量子計算機快，但是過了10年后，量子計算機的挖礦速度將會飛速增長.

5.2 量子計算對加密算法的威脅

為了保證比特幣只能被合法擁有者使用，其使用了橢圓曲線數(shù)字簽名算法(ECDSA).簡而言之，它基于公鑰密碼術，比特幣的所有者可以使用他們的私鑰對交易進行唯一的簽名，而其他人可以通過他們的公鑰來驗證它是否真實.橢圓曲線密碼在量子計算中很容易受到攻擊，因為Shor的算法可以很容易將其修改，以解密帶有橢圓曲線的消息，也就是說，可以用量子計算機從公鑰中找到私鑰，我們可以把這個解密過程同樣地比作走迷宮，經(jīng)典的計算機只能很傻地每個方向走，直至走到死胡同才會返回來重新選擇別的方向，然而量子計算機會給你一個上帝視角，通過俯視整個迷宮就會一目了然地得到該走的路.這似乎暴露了比特幣的一個弱點，但事實上量子計算機需要一定數(shù)量的量子比特才能達到這種效果，有外媒稱一個4 000個量子比特的量子計算機可以瓦解區(qū)塊鏈，如果哪個組織或個人先做出并能夠應用這樣的量子計算機，他就能解出并且驗證每一筆交易，以后將會產(chǎn)生但還未流通的加密貨幣都會被其壟斷.但是以目前的量子計算機水平還不能達到這種效果.況且比特幣有幾個安全保障措施可以防止這種情況發(fā)生.首先，你的地址不公開密鑰.比特幣協(xié)議首先將公鑰通過SHA-256函數(shù)進行散列，然后通過RIPEMD-160函數(shù)來生成地址.由于公鑰只有在比特幣被使用時才顯示出來，因此只有在交易中公開密鑰后才會受到量子計算機的攻擊.在每次事務之后生成一個新的地址，這種情況很容易得到補救.當量子計算機普及大眾，大多數(shù)比特幣客戶可能會在每次交易后轉向自動密鑰生成，這可能會減少某些應用程序的方便性.例如，您將無法打印出一個地址二維碼并永久地用作收銀機.

另一種可能性是，一旦在待交易中公開密鑰被泄露，一個惡意的參與者Eve使用量子計算機可以在交易完成之前偷走比特幣.在交易完成之前，Eve只有10 min的時間才能找到私鑰.在實際操作中，比特幣交易通常會在一個非官方的待決池(“存儲池”)中停留1 h或更長時間.對256位ECDSA大約需要1 500量子位和6×109，還需要添加一個量子位[10].每一個量子位需要9個量子門.因此，要在1 h內執(zhí)行這類攻擊，量子計算機需要執(zhí)行大約660 MHz的門運算速度.對量子比特數(shù)和速度的要求可能使得這一點具有挑戰(zhàn)性，至少在近期是如此.

假設你能同時破解SHA-256和RIPEMD-160，那么在現(xiàn)有的地址下你很容易從別人手中拿走錢.但是這個問題基本上與為區(qū)塊鏈添加塊(即挖掘)而發(fā)現(xiàn)散列沖突的問題相同.該理論認為，只要偷比特幣所需的計算能力遠遠高于比特幣的計算能力，任何能竊取比特幣的人都將取代挖掘比特幣.量子計算并不能很好地改變這一邏輯.在經(jīng)典計算機上進行散列碰撞攻擊，需要盡可能地生成錢包，而在后量子世界中，可以先檢查散列函數(shù)的原始輸入，私鑰可以在事后識別.因此，在碰撞攻擊中得到一個常數(shù)因子加速.除此之外，比特幣對散列碰撞攻擊的現(xiàn)有安全性依然存在.雖然沒有證據(jù)證明其他的漏洞是不存在的，但目前沒有理由相信存在這樣的漏洞.我們唯一的保證是，比特幣已經(jīng)存在了很多年，盡管有巨大的財務激勵，但沒有人對它進行黑客攻擊.雖然我們不排除這種新型量子算法的可能性是為了黑客或采礦的目的而發(fā)明的，但也是不容小覷的.

6 結束語

量子計算機是注定要發(fā)展下去的，而且終將有一天會威脅到區(qū)塊鏈，但是似乎很多的區(qū)塊鏈專家們還沒有提高警惕.

在2017年11月召開的Crypto 2017會議(頂尖區(qū)塊鏈密碼技術人員會議)上，有一位專家表示，這將是一個“十分昂貴的操作”，可能需要“政府級”的支出，而另一位專家完全不擔心這個問題，他表示，等到實用量子計算機研究出來時，公鑰密碼系統(tǒng)早就已經(jīng)發(fā)展到不用擔心量子計算機威脅的程度了，所以這個問題不必放在心上.

但是有一個觀點是這些專家們都認同的，那就是量子計算機的出現(xiàn)將危及所有的現(xiàn)有加密方法(其中包括RSA令牌)的安全性.量子計算機將威脅整個金融和銀行業(yè)的安全，不僅僅是區(qū)塊鏈.

與此同時，也有相關機構對此表示極為重視，早在2015年，美國國家安全局(National Security Agency, NSA)就宣布正在研究量子密碼系統(tǒng)，即可以抵抗量子計算的加密系統(tǒng).在當今學術界，也有許多密碼學專家致力于研究量子密碼學，并且已經(jīng)有了實施量子密碼學的區(qū)塊鏈項目，例如，俄羅斯量子中心的Evgeny Kiktenko團隊和Quantum Resistant Ledger團隊正在積極研究構建能夠抵御量子計算機攻擊的量子區(qū)塊鏈，而且已經(jīng)有標準的量子密碼系統(tǒng)可以實現(xiàn)商用.

目前，任何人都無法準確預測實用量子計算機何時誕生，但是用積極的眼光看，因為如今的科技發(fā)展是加速的，所以商用量子計算機的誕生速度可能超乎我們的想象.區(qū)塊鏈和加密貨幣等新興技術或許處于萌芽時期，達到技術成熟還有很長一段路要走，開發(fā)人員需要注意在這個過程中會出現(xiàn)的一系列潛在威脅，這其中就包括量子計算.

[1]周平. 中國區(qū)塊鏈技術和應用發(fā)展白皮書[M]. 北京: 工業(yè)和信息化部, 2016

[2]Swan M. BlockChain:Blueprint for a New Economy[M]. Sebastopol, USA: O’Reilly Media Inc, 2015

[3]Nakamoto S. Bitcoin: A peer-to-peer electronic cash system[OL]. 2009 [2018-03-15]. https:bitcoin.orgbitcoin.pdf

[4]Buterin V. A next-generation smart con-tract and decen-tralized application platform[OL]. [2018-03-15]. https:github.comethereumwikiwikiWhite-Paper

[5]袁勇, 王飛躍. 區(qū)塊鏈技術發(fā)展現(xiàn)狀與展望[J]. 自動化學報, 2016, 42(4): 481-494

[6]Antonopoulos A M. Mastering Bitcoin: Unlocking Digital Crypto-Currencies[M]. Sebastopol, USA: O’Reilly Media, Inc, 2014

[7]Grover L K. A fast quantum mechanical algorithm for datbase search[C]Proc of the 28th ACM Symp on Theory of Computating. New York: ACM, 1996: 212-219

[8]Grover L K. Quantum mechanics helps in searching for a needle in a haystack[C]Proc of Quantum Entanglement and Quantum Information. 1999: 325-328

[9]Boyer M, Brassard G, H?yer P, et al. Tight bounds on quantum searching[J]. Fortschritte Der Physik, 2015, 46(45): 493-505

[10]Proos J, Zalka C. Shor’s discrete logarithm quantum algorithm for elliptic curves[J]. Quantum Information & Computation, 2003, 3(4): 317-344