量子計(jì)算的時代的到來會影響比特幣的安全嗎

每次有量子計(jì)算的新聞出現(xiàn)時，人們都要擔(dān)心一次比特幣。原因很簡單，比特幣是基于密碼學(xué)的，而密碼學(xué)之所以能夠成立，是基于某種計(jì)算上的不可能性。如果量子計(jì)算把原本不可能或難以實(shí)現(xiàn)的計(jì)算變成可以計(jì)算，那么這種密碼學(xué)的方法就會失效。

但這種擔(dān)心是多余的。原因同樣簡單：我們只要有量子計(jì)算也無法完成的計(jì)算，不就可以嗎？以這種計(jì)算為基礎(chǔ)構(gòu)建的密碼學(xué)方法（量子安全密碼學(xué)），量子計(jì)算也就無法破解，然后把比特幣升級到該密碼學(xué)方法之下即可。

「格困難問題」就是典型的代表，即便對于量子計(jì)算，它也保持著計(jì)算上的不可能性?；谌祟惖摹笩o知」，我們很大程度上總可以找到方法生活在密碼學(xué)的保護(hù)之下。

比特幣中的密碼算法

我們知道比特幣錢包地址對應(yīng)一個公鑰和一個私鑰，只有擁有私鑰才能動用該錢包中的比特幣，但私鑰是安全的，它無法通過錢包地址或公鑰被計(jì)算出來。

這是如何實(shí)現(xiàn)的？讓我們從臺球廳開始。

你去臺球廳打臺球，把一個球放在臺球桌底邊的一個位置上，就叫它 A 點(diǎn)，然后你把這個球打出去，假設(shè)你擊球的力氣超級大，那么球從 A 點(diǎn)出發(fā)，總會撞到臺球桌某條邊上的一個點(diǎn)，然后又會從該點(diǎn)彈到臺球桌另一條邊上的另一個點(diǎn)……它可能這樣彈了 B 次（比如一萬次），最后停在了臺球桌某條邊的一個點(diǎn)上，就叫它 C 點(diǎn)。

這時候你的朋友來了，他能看見臺球在 C 點(diǎn)的位置，你告訴他這個球最初的位置 A 點(diǎn)和擊球的角度，問他這個球中間彈了多少次，也就是 B 是多少？你的朋友應(yīng)該一時回答不上來。

這就是一個簡單的公、私鑰生成算法，C（位置）是公鑰，B（次數(shù)）是私鑰。在我們知道 A 點(diǎn)和 B 次彈跳的情況下，是能得到 C 點(diǎn)的；但如果我們只知道 A 點(diǎn)和 C 點(diǎn)，是很難算出彈跳次數(shù) B 的。

在真正的密碼學(xué)中，臺球桌的邊被換成了橢圓曲線，A 是橢圓曲線（其實(shí)是橢圓群）上一個固定的點(diǎn)，它擊打自己（球從該點(diǎn)的切線位置被擊打出去），球在橢圓群里撞來撞去撞了 B 次，最后落在了橢圓群的一個點(diǎn)上，還要對該點(diǎn)再做一次映射，有了橢圓群上的一個點(diǎn) C。C 是公鑰，B 是私鑰。

這就是著名的橢圓曲線算法，被用于生成公鑰、私鑰，是比特幣系統(tǒng)中的第一個密碼學(xué)方法。

橢圓曲線算法難以被破解（基于「離散對數(shù)困難問題」），但并非不能被破解，足夠強(qiáng)大的量子計(jì)算可以找到多項(xiàng)式算法，通過 A 和 C 計(jì)算出 B，也就是可以通過公鑰算出私鑰。所以，如果真的進(jìn)入到量子計(jì)算時代，橢圓曲線算法是需要被新的抗量子計(jì)算的算法替換的。

量子計(jì)算與橢圓曲線算法

比特幣采用的橢圓曲線數(shù)字簽名算法的安全性是 2^128（secp256-k1 曲線群的階接近于 2^256，橢圓曲線攻擊算法的復(fù)雜度大約都是 O（sqrt（N）），對 2^256 開平方，得到2^128 ）。這是個天文數(shù)字。

在量子計(jì)算的情況下，使用 Peter Shor 提出的 Shor 算法，它攻擊橢圓曲線的復(fù)雜度大概是 O（log（N）^3） ，對于比特幣而言，理論上的計(jì)算量級是 128^3 次。

相關(guān)論文研究顯示，構(gòu)造一個攻擊 secp256-k1 曲線的量子計(jì)算機(jī)，假設(shè)該計(jì)算機(jī)能把比特錯誤率降低到 10^-4，那么有希望在使用 170 萬個量子比特的情況下，在 7 天之內(nèi)完成計(jì)算。

在比特幣系統(tǒng)中，還有另一個密碼學(xué)方法，哈希函數(shù) SHA-256，它被用于生成與公鑰對應(yīng)的錢包地址。該算法很好理解，就是把一個輸入以一種不可逆的方式轉(zhuǎn)換成一個輸出，它有非常強(qiáng)的單向性，想通過輸出來計(jì)算輸入是不可能的。

因此，哈希函數(shù)只能通過暴力的方式破解，也就是變換輸入值一次次去試，直到可以用某個輸入值算出目標(biāo)輸出值。

相較于經(jīng)典計(jì)算機(jī)，量子計(jì)算機(jī)在暴力搜索上具有可觀的優(yōu)勢，不過仍然是一種多項(xiàng)式級別的性能優(yōu)化，我們可以通過加倍安全位數(shù)，比如采用 SHA-512 來維持安全性。

比特幣錢包地址是公鑰經(jīng)過兩次哈希計(jì)算得到的，一次是 SHA-256，一次是RIPEMD-160（另一種哈希函數(shù)），量子計(jì)算很難攻破兩道哈希關(guān)口，通過錢包地址「撞」出公鑰。

量子計(jì)算與 SHA-256

目前在量子算法里可以加速計(jì)算SHA-256 的是Lov Grover 在1996年提出來的 Grover 算法，它可以將暴力搜索的性能提高到平方倍。假設(shè)我們要在一個 N× N 的巨大方格里尋找一根針，經(jīng)典計(jì)算機(jī)需要逐一搜索每一個方格，最壞情況下需要搜索N×N 次；但Grover 算法即使是在最壞的情況下也只需要搜索 N 次。

總結(jié)一下：比特幣中有兩種基礎(chǔ)密碼算法，一是橢圓曲線算法，一是哈希函數(shù) SHA-256。目前能夠找到前者的高效量子計(jì)算方法，實(shí)現(xiàn)破解；但并沒有找到后者的高效量子計(jì)算方法。當(dāng)然，破解的前提是量子計(jì)算真的發(fā)展到足夠強(qiáng)大，要知道，谷歌最新的量子芯片只有 54 個量子比特。

我們的比特幣安全嗎？

如果進(jìn)入到量子計(jì)算時代，我們只需要用抗量子計(jì)算的密碼學(xué)算法生成公鑰、私鑰、錢包地址即可。但假如用戶未能升級公鑰私鑰，他們錢包中的比特幣是否就一定會被竊?。看鸢甘欠穸ǖ?。

大致有如下幾種情況：

1. 如果錢包地址中的比特幣從未被使用過，那么該地址的公鑰是不被人知曉的，其他人所知道的只有錢包地址（只有當(dāng)我們花費(fèi)某地址上的比特幣時才需要給出公鑰，不過哪怕只花費(fèi)過一次，公鑰就會被廣播到全網(wǎng)）。

如前文所述，SHA-256 是難以被量子計(jì)算破解的，這意味著其他人是無法通過錢包地址算出公鑰的。所以，即使可以通過公鑰算出私鑰，那些沒有暴露過公鑰的錢包地址也是安全的。

2. 如果有好的比特幣使用習(xí)慣，一個錢包地址只使用一次，那么同理，新地址的公鑰也是不被人知曉的，新地址中的比特幣是安全的。

3. 如果用戶重復(fù)使用一個錢包地址，那么該地址對應(yīng)的公鑰就處于暴露狀態(tài)；如果量子計(jì)算破解了橢圓曲線算法，那么該地址中的比特幣就面臨被竊取的危險(xiǎn)。

據(jù)統(tǒng)計(jì)截止到當(dāng)前，有將近 500 萬個比特幣是存放于公鑰暴露的地址中的，此外還有將近 177 萬個比特幣使用的是 P2PK 地址，這是最早期的比特幣賬戶格式，公鑰是公開的，其中就包括被認(rèn)為是中本聰?shù)馁~戶。如果這些比特幣不更換地址，它們是在量子計(jì)算攻擊范圍內(nèi)的。（數(shù)據(jù)來源：安比實(shí)驗(yàn)室）

除了錢包地址，在比特幣系統(tǒng)中還有一個重要的地方使用到了 SHA-256，那就是挖礦。挖礦就是暴力破解哈希函數(shù)的過程，通過調(diào)整輸入值「撞」出落在目標(biāo)區(qū)間的輸出值。

如前文所述，從理論上講，量子計(jì)算機(jī)芯片在暴力搜索時是可以「碾壓」經(jīng)典計(jì)算機(jī)芯片的，但我們同樣需要考慮到它的技術(shù)發(fā)展水平和芯片制作工藝。此外，芯片本就是隨著技術(shù)的發(fā)展不斷升級的，量子計(jì)算對挖礦的影響更多的是芯片升級的經(jīng)濟(jì)問題，而不是安全問題。

量子計(jì)算下的安全：格密碼

在量子計(jì)算發(fā)展的同時，量子安全密碼學(xué)也在飛速發(fā)展，這其中最具代表性的是「格密碼」，它是基于格的密碼體制（lattice-based cryptography）。

「格」是一個系數(shù)為整數(shù)的向量空間，可以把它理解成一個高維度空間，它有兩個基本的「格困難問題」，一是最短向量問題，一是最近向量問題，求解這類問題需要指數(shù)時間的復(fù)雜度，那么如果因子為多項(xiàng)式，這類問題就不存在多項(xiàng)式時間算法，對于量子計(jì)算也是一種計(jì)算上的不可能性。

這聽起來有些抽象，也許可以這么去理解：用筆在一張 A4 紙上畫出很多黑色的點(diǎn)，然后換支筆在紙上畫下一個紅色的點(diǎn)，我們需要做的是找到距離紅點(diǎn)最近的黑點(diǎn)，這很容易；現(xiàn)在從 A4 紙這個二維空間到一個三維空間，想象一下空間里漂浮著很多黑色的點(diǎn)，這時放一個紅色的點(diǎn)進(jìn)去，同樣是去找距離紅點(diǎn)最近的黑點(diǎn)，這并不算很難，但相對于二維空間，其困難度已經(jīng)不在一個級別了。

現(xiàn)在，我們把三維空間變成一個三百維的空間，給定一個紅點(diǎn)去找距離它最近的黑點(diǎn)，這個黑點(diǎn)一定存在，但想想看，找出它是不是幾乎不可能？這就是格困難問題。

格空間與橢圓曲線是相似的。在橢圓曲線上，可以有數(shù)學(xué)公式（橢圓曲線算法）把公鑰和私鑰放在一個等式的兩頭，在格空間里，也有數(shù)學(xué)公式（比如LLL算法）可以把類似黑點(diǎn)和紅點(diǎn)的東西放在一個等式的兩頭，那么我們就可以利用這類公式來生成公鑰和私鑰。

在橢圓曲線算法中，因?yàn)椤鸽x散對數(shù)困難問題」，傳統(tǒng)計(jì)算機(jī)無法通過私鑰計(jì)算出公鑰；在格密碼的算法中，因?yàn)椤父窭щy問題」，量子計(jì)算機(jī)也無法通過私鑰算出公鑰。

格密碼發(fā)展很快，基于格我們不僅有抗量子計(jì)算的公鑰和私鑰，還有抗量子計(jì)算的對應(yīng)于經(jīng)典密碼概念的一系列密碼學(xué)算法或協(xié)議，它們可以被用于數(shù)字簽名、密鑰交換、零知識證明等等應(yīng)用領(lǐng)域。

「宇宙相信加密。加密容易，解密難?！乖诳梢灶A(yù)見的未來，依然如此。所以，不用擔(dān)心，對于比特幣是這樣，對于區(qū)塊鏈也是。

來源： 鏈聞ChainNews