摘 要：以比特幣為核心交易貨幣的區(qū)塊鏈技術(shù)分布在一個去中心化的P2P網(wǎng)絡(luò)中，近年來在如醫(yī)療、金融、智能制造等多個領(lǐng)域的市場中展現(xiàn)出了蓬勃的生機，極具發(fā)展前景。然而量子技術(shù)的不斷發(fā)展進步對區(qū)塊鏈的安全性能產(chǎn)生了極大的沖擊。首先闡述比特幣網(wǎng)絡(luò)中PoW共識算法對哈希函數(shù)的依賴性和交易事務(wù)中數(shù)字簽名ECDSA加密算法的工作原理，而后針對2類具有潛在威脅性的量子算法——Grover算法和Shor算法——對比特幣區(qū)塊鏈的攻擊機制展開分析。得出結(jié)論：Grover算法可對PoW中的SHA256哈希函數(shù)進行快速求解，有望在未來完成攻破；Shor算法可通過ECDSA加密算法中的公鑰信息推導(dǎo)出私鑰，從而竊取交易成果。最后列舉了幾種改進算法以應(yīng)對量子攻擊。

關(guān) 鍵 詞：關(guān) 鍵 詞：分子篩; 鈦硅沸石; 無溶劑法; 硅鈦摩爾比比特幣; 區(qū)塊鏈; 量子攻擊; 工作量證明機制; 數(shù)字簽名

中圖分類號：TP183;S-3 文獻標志碼：A

doi：10.3969/j.issn.1673-5862.2024.03.006

Research on bitcoin blockchain attacked by quantum algorithm

CUI Song^1，2， LYU Yan^1，2， CHEN Lanfeng^1，2YU Jian¹， YAN Fangxu¹， WANG Jianhui¹， YU Zexiang²

（1. College of Physical Science and Technology， Shenyang Normal University， Shenyang 110034， China）（1. College of Mathematics and Systems Science， Shenyang Normal University， Shenyang 110034， China; 2. Sydney Smart Technology College， Northeast University， Shenyang 110819， China）

Abstract：The blockchain technology based on bitcoin as the core trading currency is distributed in a decentralized P2P network. In recent years， it has shown vigorous vitality and great development prospects in markets such as medical， financial， and intelligent manufacturing. However， the continuous development and progress of quantum technology has had a great impact on the security performance of the blockchain. Firstly， this paper expounds the dependence of PoW （proof of work）consensus algorithm on hash function in bitcoin network and the working principle of digital signature ECDSA （elliptic curve digital signature algorithm） encryption algorithm in transaction. Then， we analyze the attack mechanism of two kinds of potentially threatening quantum algorithms-Grover’s algorithm and Shor algorithm on bitcoin blockchain， and conclude that Grover algorithm can quickly solve the SHA256 hash function in PoW， which is expected to be broken in the future. The Shor’s algorithm can derive the private key from the public key information in the ECDSA encryption algorithm， thereby stealing the transaction results. Finally， this paper lists several improved algorithms to deal with quantum attacks.

Key words：bitcoin; blockchain; quantum attacks; proof of work （PoW）; digital signature

區(qū)塊鏈作為一種去中心化的分布式賬本技術(shù)，融合了密碼學(xué)算法、共識機制、點對點分布式網(wǎng)絡(luò)等多項成熟技術(shù)?；谄湓诮灰字胁豢纱鄹?、不可偽造、可追溯、數(shù)據(jù)安全透明等優(yōu)越特性，區(qū)塊鏈的應(yīng)用由最開始的數(shù)字貨幣技術(shù)逐漸橫跨金融、醫(yī)療、物聯(lián)網(wǎng)、智能制造等多個行業(yè)領(lǐng)域，展現(xiàn)出了蓬勃的發(fā)展前景和經(jīng)濟價值。比特幣是區(qū)塊鏈的底層核心代表技術(shù)之一，自2008年10月由中本聰首次提出以來^［1］，激發(fā)了如Ethereum、Litecoin、Monero及ZCash等多種區(qū)塊鏈技術(shù)的研發(fā)，目前擁有超過1 000億美元的巨大市場價值。作為區(qū)塊鏈交易中的數(shù)字貨幣，比特幣的安全性依賴于工作量證明機制（proof of work，PoW）和數(shù)字簽名技術(shù)。前者通過各節(jié)點的挖礦競爭將工作量寫入數(shù)字賬本，保證數(shù)據(jù)和節(jié)點共識的一致性；后者基于橢圓曲線數(shù)字簽名算法（elliptic curve digital signature algorithm，ECDSA），通過對授權(quán)交易的加密簽名完成身份驗證，維護區(qū)塊鏈的魯棒性^［2］。

然而，量子計算機的興起對區(qū)塊鏈的安全問題產(chǎn)生了巨大的威脅。量子計算機以量子比特為基本計算單元，以0和1的量子疊加態(tài)存在，通過操縱量子態(tài)確保其在短時間內(nèi)能夠有效解決多種復(fù)雜的數(shù)學(xué)問題，如分解主要因子、計算離散對數(shù)等。20世紀80年代初，首個量子計算系統(tǒng)的問世標志著量子計算技術(shù)逐漸成為數(shù)學(xué)的一種重要形式。1997年，Shor等^［3］提出了一種多項式時間內(nèi)分解主要因子的算法，可快速攻破傳統(tǒng)的公鑰密碼體制，嚴重威脅了ECDSA的安全性。2018年，谷歌推出Bristlecone芯片，實現(xiàn)了量子比特之間的耦合。2023年，谷歌研發(fā)的Sycamore量子處理器擁有70個量子比特，可在短短6秒完成世界最先進計算機47年的計算量。量子計算的飛速發(fā)展嚴重威脅傳統(tǒng)區(qū)塊鏈的安全機制，鑒于區(qū)塊數(shù)據(jù)和密碼算法間的強耦合性，量子計算的攻擊重點主要為數(shù)字簽名和PoW機制。這將造成欺詐交易和未授權(quán)的數(shù)據(jù)訪問，對區(qū)塊鏈的安全性和穩(wěn)定性造成致命打擊。2018年4月，美國國家標準與技術(shù)研究院（national institute of standards and technology，NIST）于后量子密碼算法會議中積極呼吁業(yè)界研究抗量子攻擊的加密算法。同時，俄羅斯量子中心也正在推進首個依賴量子加密技術(shù)的分布式量子區(qū)塊鏈設(shè)計^［4］。

研究表明，到2035年，量子技術(shù)可能已經(jīng)足夠成熟，能夠有效打破RSA2048密碼算法^［5］?；诖祟A(yù)測開展區(qū)塊鏈抗量子攻擊的性能研究，可對區(qū)塊鏈技術(shù)的可持續(xù)性和可靠性作出重要貢獻。本文以比特幣技術(shù)為例，分析其在區(qū)塊鏈中的運行機制，重點關(guān)注比特幣抗量子算法——Shor算法和Grover算法——攻擊的相對脆弱性，最后提出可行對策，為維護區(qū)塊鏈的安全性和穩(wěn)定性奠定理論基礎(chǔ)。

1 比特幣技術(shù)工作原理

比特幣是一種運行在P2P（peer-to-peer）網(wǎng)絡(luò)上的電子貨幣系統(tǒng)，在去中心化的分布式網(wǎng)絡(luò)環(huán)境中，節(jié)點可以通過自身的算力、網(wǎng)絡(luò)和存儲等資源，同時作為資源的提供者（服務(wù)器）和訪問者（客戶）^［6］，這意味著任意節(jié)點之間可以直接進行自由交易，無需第三方許可。比特幣通過PoW共識機制確保網(wǎng)絡(luò)中的所有節(jié)點共同維護一份分布式記賬本，并使用ECDSA數(shù)字簽名算法作為交易機制的框架，允許創(chuàng)建交易的節(jié)點以加密方式對事務(wù)進行簽名，以驗證與其相關(guān)的公鑰和私鑰，從而確保交易的安全性和完整性。

1.1 PoW共識機制

比特幣采用PoW共識算法保證分布式賬本的協(xié)同工作。PoW最初的設(shè)計目的是預(yù)防垃圾郵件的轟炸騷擾，發(fā)件人在發(fā)送郵件時需要歷經(jīng)一個階段運算，以此延緩郵件的發(fā)送速度，降低垃圾郵件的發(fā)送效率^［7］。PoW算法的核心是求解滿足條件的哈希函數(shù)原像，各節(jié)點通過競爭自身算力求解函數(shù)的過程即為挖礦，其中各節(jié)點又被稱為礦工，挖礦成功的礦工獲得優(yōu)先記賬權(quán)，即對區(qū)塊鏈執(zhí)行寫操作，將交易完成的區(qū)塊連接到鏈尾，并得到一定數(shù)額的比特幣，作為幣基（coinbase）保存在區(qū)塊鏈中。

PoW算法采用SHA256哈希函數(shù)，其目標公式為：

SHA256（SHA256（前驅(qū)區(qū)塊哈希值（32 byte）+Merkle樹根（32 byte）+Nonce值（4 byte）+

nBits（4 byte）+TimeStamp（4 byte）+版本號（4 byte）））＜Target（1）

如圖1所示，一個區(qū)塊分為區(qū)塊頭和區(qū)塊體，區(qū)塊體中的交易數(shù)據(jù)以Merkle樹結(jié)構(gòu)被存儲，樹根作為交易摘要分布在區(qū)塊頭中，便于追溯。區(qū)塊頭中的前驅(qū)區(qū)塊哈希值指向父區(qū)塊的哈希指針，實現(xiàn)各區(qū)塊之間按序連接。PoW算法參數(shù)包括Nonce值和nBits：Nonce值初始為0，隨挖礦的進度不斷增加，是節(jié)點工作量的關(guān)鍵證明，用于查驗礦工是否挖礦成功；nBits中壓縮存儲當(dāng)前區(qū)塊的難度值。UNIX時間戳中存儲創(chuàng)建此區(qū)塊時礦工的本地時間，單位精確到秒。版本號為區(qū)塊頭中的填充字段，表征當(dāng)前區(qū)塊的版本參數(shù)等信息^［8］。

比特幣采用的是基于交易的賬本模式（transaction-based ledger），節(jié)點可以通過挖礦或者接收其他節(jié)點匯入的方式獲得比特幣。交易信息通過泛洪機制全網(wǎng)廣播，礦工驗證交易信息有效后開始著手構(gòu)建Merkle樹，將當(dāng)前鏈尾區(qū)塊的Hash值、Merkle樹根、nBits值及自身條件參數(shù)作為公式（1）的輸入，檢驗結(jié)果是否小于目標閾值Target，并通過窮舉法解出Nonce值并填入?yún)^(qū)塊頭。而后礦工將新生成的區(qū)塊接入鏈尾，將此新生成的區(qū)塊鏈全網(wǎng)廣播，等待其他節(jié)點驗證新區(qū)塊鏈的各參數(shù)信息并達成共識，如果全網(wǎng)51%以上節(jié)點驗證通過，則該區(qū)塊將成功上鏈，最后礦工得到比特幣獎勵并作為自身的coinbase存儲在區(qū)塊體中。這種礦工因挖礦生成區(qū)塊而獲得獎勵的交易被稱為幣基交易（coinbase transaction）。此外，接收其他節(jié)點轉(zhuǎn)賬的交易被稱為鑄幣交易，鑄幣交易只承認coinbase為唯一輸入，輸出接收比特幣節(jié)點的地址。每一次交易的輸入值必須全部耗盡，并產(chǎn)生2筆未花費的交易輸出（unspent transaction outputs，UTXO）。一筆為支付給接收人的UTXO，另一筆作為支付找零匯入轉(zhuǎn)賬人的比特幣錢包。UTXO是鑄幣交易的基本單位，由于其不可分割的特性，大部分比特幣交易都會產(chǎn)生找零。

1.2 交易機制

區(qū)塊鏈交易機制中關(guān)鍵的加密工具是數(shù)字簽名（digital signature）。私鑰和公鑰是區(qū)塊鏈網(wǎng)絡(luò)中各成員節(jié)點都擁有的密鑰。公鑰用以驗證簽名的合法性，而私鑰則對除持有人外的其他節(jié)點保密并用于持有人自身創(chuàng)建數(shù)字簽名。數(shù)字簽名的創(chuàng)建表明一筆交易已獲得私鑰持有人的批準，從而證明了區(qū)塊鏈上交易的有效性。

比特幣在交易中使用ECDSA加密算法，該算法使用secp256-k1素階橢圓曲線來生成數(shù)字簽名。表1為該簽名算法的偽代碼^［9］，簽名由2個變量r和s組成，其中r是P點橫坐標，P點即為一個臨時公私鑰對中的公鑰，由用戶在簽署交易的過程中創(chuàng)建；對于步驟8中s的參數(shù)，e為交易的哈希值，d為節(jié)點簽名時所用的私鑰，k為臨時私鑰。給定簽名參數(shù)中的s、r值可產(chǎn)生一個臨時公鑰，區(qū)塊鏈中其他節(jié)點通過該公鑰驗證數(shù)字簽名的合法性。例如，Vivian將挖礦得到的比特幣匯給Henry，Henry首先要創(chuàng)建一個公私鑰對，公鑰的哈希值作為Henry接收比特幣的地址（在后文將深入討論，比特幣將公鑰哈希值作為地址的這一特性確實為量子攻擊提供了可能性）。作為匯款方，Vivian在區(qū)塊鏈中廣播此交易的轉(zhuǎn)賬地址，提供相應(yīng)的公鑰等待其他節(jié)點驗證，并使用此地址對應(yīng)的私鑰完成簽名授權(quán)。

2 針對比特幣的量子攻擊

量子計算中有2種算法可對比特幣網(wǎng)絡(luò)造成威脅：Grover算法和Shor算法。前者通過子群發(fā)現(xiàn)法進行二次量子加速，實現(xiàn)對任意NP-完全問題（non-deterministic polynomial-complete）的求解，且速度遠超現(xiàn)存的經(jīng)典算法。Grover主攻區(qū)塊鏈的共識機制，因為PoW算法依賴于求解NP-完全問題。Shor算法既能分解大整數(shù)，又能在多項式時間內(nèi)求解離散對數(shù)，而在比特幣區(qū)塊鏈中，公鑰密碼的算法難度正取決于上述2類計算問題，因此Shor算法會針對比特幣交易機制中數(shù)字簽名的漏洞進行攻擊。

2.1 Grover算法對共識機制的攻擊

根據(jù)公式（1）可知，區(qū)塊頭的哈希函數(shù)值需滿足不等式h（head） ≤ t，其中t為target，h（·）=SHA256（SHA256（·））。在Oracle數(shù)據(jù)庫中，設(shè)h（head） ≤ t的概率為t/2²⁵⁶，記作Pr［h（head） ≤ t］=t/2²⁵⁶，此概率均勻分布在任意給定時刻內(nèi)，可被打包至交易池中的表現(xiàn)良好的區(qū)塊頭上?？梢酝ㄟ^改變Nonce值、交易信息、時間戳中的最低有效位等方式來找出這些良好區(qū)塊頭。在一臺經(jīng)典計算機上，滿h（head） ≤ t的區(qū)塊頭預(yù)期值為D×2³²，其中D為依賴D=2²²⁴/t的哈希難度。

在一臺量子計算機中，結(jié)合一般量子技術(shù)的Grover算法對于規(guī)模為N的數(shù)據(jù)庫可通過O（N）次查詢操作完成對數(shù)據(jù)庫中某標記項目的檢索。而在經(jīng)典計算機中，完成相同的任務(wù)需要進行Ω（N）次查詢操作?，F(xiàn)令h的取值范圍為N=2²⁵⁶，根據(jù)假設(shè)可知，當(dāng)Pr≥0.99時，一個由10·N/t個區(qū)塊頭組成的隨機集合至少包含一個元素，其哈希值不超過t。為發(fā)現(xiàn)良好區(qū)塊頭，現(xiàn)令函數(shù)f映射S={0，1{0，1}^{「log（10·N/t）}}，函數(shù)g為良好區(qū)塊頭判定函數(shù)，具體公式為：

量子計算機可以通過疊加輸入來計算g（x），即完成如下映射^［11］：

利用Grover算法，量子計算機可在Oracle中通過 π410·N/t=π2¹⁴10·D次調(diào)用，在S中找到良好區(qū)塊頭來實現(xiàn)攻擊，即使S未知或不存在，Grover也可以按此規(guī)模照常運行。

從圖2中不難看出，現(xiàn)階段的ASIC（application-specific integrated circuit）硬件對于求解PoW算法的哈希算力遠優(yōu)于量子計算機。所以得出結(jié)論：未來10年之內(nèi)量子計算無法對比特幣造成實質(zhì)性威脅。但當(dāng)量子技術(shù)的計算速度達到100GHz時，量子計算機求解PoW的速度將達到當(dāng)前技術(shù)的100倍，如此強大的算力將與ASIC礦工展開激烈競爭，從而攻擊共識機制。

2.2 Shor算法對交易機制的攻擊

比特幣中的數(shù)字簽名算法ESDCA的難度主要依賴于橢圓曲線的離散對數(shù)問題（elliptic curve discrete log problem ，ECDLP）。對于此問題，普通計算機可在多項式時間O（2ⁿ）內(nèi)求解，而量子計算機可在多項式時間O（2³）內(nèi)快速求解。不難證明量子計算機已有足夠的能力針對數(shù)字簽名技術(shù)展開攻擊。分以下3種交易情況討論Shor算法的攻擊效果：

1）重復(fù)使用地址：如需使用某一地址支付比特幣，必須向網(wǎng)絡(luò)中的各節(jié)點公布該地址的公鑰以供驗證。一旦在交易中重復(fù)使用某一地址，那么公鑰就會被泄露。任何儲有比特幣且公鑰被泄露的地址都是不安全的。

2）交易已完成：一個交易完成的標志是該交易所在的區(qū)塊成功上鏈，并將新形成的區(qū)塊鏈廣播至全網(wǎng)。這種情況是相當(dāng)安全的，Shor算法基本已經(jīng)沒有能力與網(wǎng)絡(luò)外部攻擊相結(jié)合，對已完成的交易展開雙重攻擊。

3）交易未完成：比特幣交易是以UTXO為單位進行的，只要攻擊者能夠確保自己篡改的交易在真實交易之前被放在區(qū)塊鏈上，就可以竊取交易，并將新創(chuàng)建的UTXO輸出至他們選擇的賬戶。這種情況是最容易遭受量子攻擊的，下面展開具體分析：

量子進程求解ECDLP的時間 τ 計算公式為^［12］：

τ=1.28×10¹¹×c_τ（p_g）/s（4）

量子數(shù)n_Q的計算公式為：

n_Q=2 334×c_nQ×（p_g）（5）

其中取開銷參數(shù)c_τ=292.2、c_nQ=735.6；門容錯率p_g=5×10^－4；時鐘速度s=10 GHz。如圖3、圖4所示，量子計算可在30分鐘內(nèi)使用485550個量子攻破比特幣的數(shù)字簽名系統(tǒng)。

3 結(jié) 語

隨著量子計算的日益興起，量子算力的不斷增強，區(qū)塊鏈的安全面臨著巨大挑戰(zhàn)。本文主要對比特幣區(qū)塊鏈中共識機制與交易機制的工作原理進行分析，結(jié)合具有潛在威脅性的2類量子算法——Grover和Shor算法，得出以下結(jié)論：Grover算法可求解PoW算法中SHA256函數(shù)的哈希值以達到對算法的快速破解，雖然目前Grover的算力不敵傳統(tǒng)ASIC硬件，但有望在未來實現(xiàn)對PoW的攻破；Shor算法針對UTXO中已泄露的公鑰信息推導(dǎo)私鑰，以此偽裝交易原主獲得簽名權(quán)，通過改寫交易提前入鏈，竊取成果。

為提高共識機制的安全性，目前主要采用工作量證明和權(quán)益證明（proof-of-stake，PoS）相結(jié)合的二跳共識算法^［13］，將PoW算力和PoS權(quán)益有機融合為聯(lián)合資源，從而保證誠實節(jié)點占有大多數(shù)聯(lián)合資源。二跳算法有效解決了PoW存在的51%攻擊問題（拜占庭節(jié)點必須同時掌握51%以上的權(quán)益和51%以上的算力，才能實施51%攻擊）大大提高了區(qū)塊鏈的可靠性和安全性。休眠共識算法^［14］針對多數(shù)節(jié)點處于離線狀態(tài)、只有少數(shù)節(jié)點在線參與共識的情況提出了一種新的解決思路，即使得在線誠實節(jié)點數(shù)大于問題節(jié)點數(shù)，以此保障區(qū)塊鏈的魯棒性和安全性。

本文針對改進數(shù)字簽名算法提出了一系列基于格的簽名方案，如基于格的盲簽名方案，基于格的環(huán)簽名方案、以及基于格的盲環(huán)簽名方案等^［15］，利用格密碼抗量子攻擊的突出性，結(jié)合環(huán)簽名的匿名性、盲簽名的盲性，以及二者兼?zhèn)涞牟豢蓚卧煨?，重新生成公私鑰簽名，在抗量子攻擊的性能方面有顯著提高。

參考文獻：

［1］KRAJCINOVIC D，F(xiàn)ONSEKA G U.The continuous damage theory of brittle materials［J］.J Appl Mech，1981，48（4）：809-824.

NAKAMOTO S.Bitcoin：A peer-to-peer electronic cash system［EB/OL］．（2008-10-31）［2023-10-29］.http：//bitcoin.org/bitcoin.pdf．

［2］THANALAKSHMI P，RISHIKHESH A，MARCELINE J M，et al.A quantum-resistant blockchain system：A comparative analysis［J］.Mathematics，2023，11（18）：3947.

［3］SHOR P W.Algorithms for quantum computation：Discrete logarithms and factoring［C］// Proceedings 35th Annual Symposium on Foundations of Computer Science.Washington DC：IEEE Computer Society，1994：124-134.

［4］韓璇，袁勇，王飛躍.區(qū)塊鏈安全問題：研究現(xiàn)狀與展望［J］.自動化學(xué)報，2019，45（1）：206-225.

［5］MOSCA M.Cybersecurity in an era with quantum computers：Will we be ready？［J］.IEEE Secur Priv，2018，16（5）：38-41.

［6］倪雪莉，馬卓，王群.區(qū)塊鏈P2P網(wǎng)絡(luò)及安全研究［J/OL］.［2023-10-20］.http：//kns.cnki.net/kcms/detail/11.2127.TP.20231020.1100.004.html.

［7］DWORK C，NAOR M.Pricing via processing or combatting junk mail［C］//Annual international cryptology conference.Heidelberg：Springer，1992：139-147.

［8］ZHENG W L，ZHENG Z B，CHEN X P，et al.Nutbaas：A blockchain-as-a-service platform［J］.IEEE Access，2019，7：134422-134433.

［9］JOHNSON D，MENEZES A，VANSTONE S.The elliptic curve digital signature algorithm（ECDSA）［J］.Int J Inf Security，2001，1（1）：36-63.

［10］CHEN L，JORDAN S，LIU Y K，et al.Report on post-quantum cryptography［EB/OL］.（2016-04-28）［2023-10-29］.http：//dx.doi.org/10.6028/NIST.IR.8105.

［11］AGGARWAL D，BRENNEN G K，LEE T，et al.Quantum attacks on bitcoin，and how to protect against them［J］.Ledger，2018，3：68-90.

［12］SELINGER P.Quantum circuits of T-depth one［J］.Phys Rev A，2013，87（4）：042302.

［13］DUONG T，F(xiàn)AN L，KATZ J，et al.2-hop blockchain：Combining proof-of-work and proof-of-stake securely［EB/OL］.（2017-04-16）［2023-10-29］.https：//eprint.iacr.org/2016/716.

［14］PASS R，SHI E.The sleepy model of consensus［EB/OL］.（2017-11-18）［2023-10-20］.https：//eprint.iacr.org/2016/918.pdf.

［15］REN Y，GUAN H P，ZHAO Q X.An efficient lattice-based linkable ring signature scheme with scalabilityto multiple layer［J］.J Amb Intel Hum Com，2022，13：1547-1556.

【責(zé)任編輯：孫 可】