抗量子霸權？未來區塊鏈新共識，有人提出了解決辦法

一.新聞

近期 Google 在 Nature 上發表了一篇名叫「Quantum supremacy using a programmable superconducting processor」（用超導處理器實現量子霸權），宣布在量子計算機領域實現「量子霸權」。一個經典計算機需要計算 10000 年的難題，谷歌的 Sycamore 量子處理器用了 200 秒就解出來了。一石激起千層浪，隨後各大媒體都開始報導量子計算機的話題，自然也會涉及到量子計算機對於現有密碼體系安全性的影響。下面，我們需要先介紹一些背景知識，否則很難對這個話題深入討論。

二.什麼是「量子霸權」

結論：量子霸權的含義是，在一些計算任務上對經典計算機具有壓倒性優勢，行使「霸權」的對象是經典計算機。

說實話筆者對我國媒體將「quantum supremacy」譯為「量子霸權」不是特別滿意，這似乎象徵著美國將倚賴量子技術來行使地緣政治意義上的「霸權」，這並不是英文中「quantum supremacy」的本意。它的確切意思是，在一些計算任務上，通過量子現象實現對經典計算機的壓倒性優勢，行使「霸權」的對象是經典計算機。根據計算任務的不同，有的就非常適合量子霸權，有的量子計算對它的幫助比較有限。

那谷歌這次實驗的計算任務呢？按 IBM 科學家 Edwin Pednault 等人的觀點，谷歌這次實驗的計算任務完全是為量子計算機量身定做的，毫無任何實用價值。但也有人說，今天的量子計算機就像萊特兄弟試駕的飛機，以後在很短時間內就會普及。諸如 RSA，ECC 這些加密體系，很快也就不安全了。那麼事實上真的是這樣么？

三.RSA／ECC加密體系與 Shor 演算法

結論：目前主流加密演算法RSA／ECC在量子計算機面前，確實存在在多項式時間內被攻破的威脅。

想了解量子計算機對現有加密體系的具體威脅，我們首先要回顧一下現在它們為什麼是安全的。在不介入過多數學細節的前提下，RSA 加密的安全性是由素數分解的難度來保障的，ECC 的安全性是由橢圓曲線上的離散對數問題的難度來保障的。我們以前者舉例，已知素數 7 與 143，我們可以很容易算出它們的積：7 x 143 = 1001。但如果我們只知道 1001 的情況下，我們除了挨個試錯，並沒有特別好的方式來推出 1001 = 7 x 143。非對稱加密體系的安全性，正是靠這個問題難度的不對稱性來得以保障的。

量子架構異於經典計算機的最重要之處，就是它可以利用量子態的疊加，來同時對多個組合進行試錯。Shor 演算法正是有效地利用了這個架構，對素數分解問題與離散對數問題，都給出了多項式時間內計算方法。因此，我們認為 RSA 與 ECC 加密體系在量子計算機的時代是不安全的。

四.多項式時間那麼重要麼？

結論：由於計算速度是以指數速度倍增，對於複雜度是多項式時間的問題，解決它們只是時間問題。 

學術界普遍認為，如果一個問題有多項式時間內的計算方法，那麼這個問題就不是問題了。這裡首先要問，所謂的多項式是一個關於什麼的多項式？一般來說，計算科學中所提到的「問題」，都有它本身的難度參數。例如素數分解，你分解越大的素數之積，難度就越大，需要的時間就越長。例如，如果難度是 O(2^n) 量級的話，我們並不需要 n 太大，就可以使問題難度迅速攀升到上億年的計算量。

不過你也可能會問，如果問題難度是 O(n^100) 的話，雖然這已經屬於多項式難度範疇了，但似乎難度也會攀升的很快，也很難被迅速解出？這就牽扯到了另一個知識點：摩爾定律。摩爾定律大致上告訴我們，由於計算機技術的革新，我們電腦的計算能力大約不到 2 年翻一倍。今天我們每個人手裡的智能手機的計算能力，遠高於當年將人類送上月球的阿波羅 11 任務中，所有計算設備的總和！

有了對摩爾定律的理解回過頭來看，就發現「多項式難度」這個概念的重要性了。一個問題，只要在理論上有多項式難度的演算法，由於計算設備的算力是指數級倍增的，解決它只是時間問題。那麼實際上，從提出理論演算法，到「等待」摩爾定律實現破解，需要花多長時間呢？我們以大家比較熟悉的 SHA－1 為例，我國密碼學專家王小雲院士，在 2005 年給出了對它產生撞擊的高效演算法（哈希函數一旦實現撞擊，就算被「攻破」了）。但真正實現 SHA－1的撞擊，則是在 2017 年由谷歌公司完成的。摩爾定律默默地發了 12 年的神功，才把理論變為實踐。在此期間，全球相關行業早已完成了加密演算法的升級。

五.量子計算機離破解 RSA／ECC 還有多遠

結論：今天 RSA／ECC 的安全性，至少優於 2005 年 SHA－1 的安全性。因此，即便讓摩爾定律再發 10 － 15 年的神功，RSA／ECC 依舊還是安全的。

以目前最新知識，欲對長度為 n 比特的 ECC 運用量子意義上的 Shor 演算法，則至少需要 6n 以上的量子比特。這裡需要強調一點，真正對計算有用的是經過降噪後（Quantum error correction）的邏輯量子比特。按 IBM 科學家 Sarah Sheldon於 2018 年的研究成果，物理量子比特與邏輯量子比特的最小比例是 1:17。在日後的實際應用中，恐怕這個比例遠遠不夠。

我們暫且假設能做到 1:17，比特幣等主流加密貨幣所用的橢圓加密演算法 Secp256k1，它的私鑰長度是 256 比特。欲對其運行 Shor 演算法，需要至少 1536 個邏輯量子比特，也就是26112 個物理量子比特。實際上隨著運算複雜性的提升，降噪比例將遠不止 1:17。主流科學界的看法是，沒有百萬級物理量子比特，想攻破RSA／ECC 加密還是非常困難的。那麼谷歌的 Sycamore 處理器到底有多少量子比特呢？54 個，實際運行時為 53 個，其中還有一個不爭氣的，壞了。

目前 RSA／ECC 的安全性，至少優於 2005 年 SHA－1 的安全性。因此，即便讓摩爾定律再發 10 － 15 年的神功，RSA／ECC 暫時還是安全的。暫時的安全性絕不等於當下可以不作為，我們現在當然需要開始為後量子時代做準備了。

六.量子計算機對區塊鏈網路的內在威脅

結論：今天所有的區塊鏈項目，由於地址、數字簽名用到了 ECC，因此都不抗量子。

現在我們討論一下量子計算機對於區塊鏈網路的威脅，這裡只討論內在威脅的意思是，不包括由於網路節點伺服器密碼被量子計算機攻破，而對區塊鏈網路產生的衍生威脅。

首先，我們來分析一下比特幣網路所受到的威脅。比特幣網路用到了兩種不同的密碼學。它的 PoW，區塊頭，交易 ID，默克爾樹用到的是哈希演算法，具體來說是 SHA256。量子計算機對它的計算性能確實會有大幅度提升，利用 Grover 演算法，計算複雜度會從2^256 降到 2^128。這也就意味著，以目前比特幣網路的挖礦難度，比特幣出塊需要全網礦工遍歷 nonce，找出一個前 75 位比特為 0 的哈希。如果用量子計算機運行 Grover 演算法的話，可以輕鬆找到前 128 位比特為 0 的哈希出來。這意味著計算 Sha256d 的 ASIC 礦機全要廢了。量子計算機之間雖然有足夠空間來繼續 PoW 競爭，但考慮到初期的量子礦工極其稀有，比特幣能否能繼續去中心化，或許會面臨嚴峻的挑戰。如果 PoW 的哈希演算法屬於 memory hard 或 bandwidth hard，那量子計算機比經典計算機，優勢將顯著變弱。

比特幣網路在量子計算機面前，真正脆弱的是它的地址與數字簽名體系，因為這裡用到了橢圓加密演算法。因此，坊間流傳的 PoS 或 DPoS 抗量子攻擊的說法，純屬無稽之談。轉賬時用到的橢圓加密演算法，是目前所有的區塊鏈項目共同的問題。只要 ECC 被量子攻破，對方就可以獲悉你的私鑰，同時也可以偽造你的簽名，將你的資產全網隨便轉移。

區塊鏈在量子時代是否安全，主要取決於兩個問題：

七. 後量子時代的加密體系

結論：ECC 有替換方案，但簽名長度從原來的 256 比特顯著增加，從而會大大降低區塊鏈的性能。如果按比特幣網路現有的同步規則，屆時每秒鐘只能處理不到一筆交易。

前面我們討論了，量子計算機對區塊鏈的最大衝擊在橢圓加密上。那麼橢圓加密有沒有繼承者？我們能否把它替換掉？這恐怕是現在所有人都關心的問題。答案是肯定的，而且不止一個方案。

美國國家標準技術研究所（NIST）於 2017 年就開始徵收抗量子攻擊的加密方案，作為下一代加密演算法的行業標準。最初一共收到了 69 份申請，目前還在評估中的有 26 個。其中有一部分在評估階段已經被攻破，還有一些安全性與性能達不到設計預期。在存活的 26 個方案中，依然存在哪天某個提案被攻破的可能。在 NIST 給出最終結論之前，筆者只能按照現在已經公開的知識，給大家做個簡單的彙報。

這些抗量子加密方案的理論基礎大致分為：哈希類（hash based），格類（lattice based），編碼類（code based），多變數類（multivariate）以及超奇異橢圓曲線等值（supersingular elliptic curve isogeny）。

在大部分方案中，公鑰長度與數字簽名不可能同時很小。這將對區塊鏈網路構成極大的挑戰。在鏈上發出每發一筆交易，至少需要傳輸兩個地址和一個數字簽名。如果是 UTXO 的架構，則需要 m+n 個地址，和 m 個數字簽名，這裡 m 是 input 個數，n 是 output個數。假設一個地址的長度與簽名長度均為 10k（地址長度不應該短於公鑰長度），那麼一筆交易至少需要佔用 30k 的存儲。按比特幣 1mb 區塊來算的話，每個區塊最多能裝 30 多筆交易。比特幣 10 分鐘出一個區塊，也就是說 10 分鐘才能處理 30 比交易，平均 5 秒才能處理 1 筆交易。這是區塊鏈抗量子加密設計上最難辦的一步。

抗量子的公鑰與數字簽名之所以這麼大，主要的原因是量子計算機在矩陣運算上，對經典計算機的優勢較為遜色。因此，我們所見的公鑰，會從現在的

橢圓曲線：pk = 04fe43d0c2c3daab… (一串 16 進位的數字) 

變成未來的 6960 x 1547 的矩陣。這樣的矩陣會佔用非常大的帶寬與存儲。

最後給大家講個笑話，在遞交給 NIST 的 26 組仍然存活的提案中，有一個叫 pqRSA（post quantum RSA）的加密演算法，顧名思義是抗量子的 RSA 升級版。它的公鑰大小為 1 tb 以上，我真的沒敲錯，真的是 1,000,000,000,000 byte。

習題：自己回家計算，在 pqRSA 框架下，

提示：慘不忍睹

八.筆者心中的解決方案

結論：超奇異橢圓曲線等值（super-singular isogeny 或簡稱 SI）演算法是目前所有抗量子加密演算法提案中，公鑰佔用空間最小的。在 5G 網路的環境下，同時實現高吞吐、抗量子與去中心化是完全有可能的。SI 演算法的缺點是計算較慢，這方面在未來可以用硬體（例如，ASIC）的方式來進行彌補。

對於區塊鏈應用來說，筆者最看好的方案是基於超奇異橢圓曲線等值的 sike 演算法。相較於其它原理的加密演算法，sike 最大的優勢是在於它佔用的帶寬與存儲相對可控，公鑰佔用空間為 2688 比特（不到 1 kb）。即便如此，這相較於傳統 ECC 公鑰的 256 比特也已經相當大了，大約是現在的十倍左右。如果立刻將比特幣網路升級為 SI 公鑰，那麼它每秒鐘也只能處理 1 筆交易。不過在可見的未來，5G 通訊系統將遍布全球，公鑰變大的問題可以靠提升網路速度來彌補。

SI 演算法的最大缺點，是計算速度特別慢。SI 演算法的根本是在多條橢圓曲線之間構造isogeny map。但由於這些運算特別複雜，往往導致普通電腦數秒時間才能完成一次驗證。設想一下，如果一個區塊中包了 100 筆交易，如果礦工驗證這些交易就需要 100 秒，那麼這樣的區塊鏈網路也不會有太大的發展前景。

值得慶幸的是，關於計算 isogeny map 的硬體方案已經有人開始研究了。考慮到量子計算機真正威脅到 ECC 至少還有 10 年時間，在此之前研製出一款能快速驗證的 ASIC，這個難度還不是很大。

九.CZZ 對未來的規劃

結論：如果 5G 網路普及，且針對 SI 演算法（super-singular isogeny）有成熟的硬體實現方案，CZZ 將在 2024 年左右啟動以 SI 為理論基礎的抗量子方案。啟動之後，CZZ 公鑰將從現有的 Secp256k1 擴容，擴容後的 CZZ 地址將以 pq 開頭加以區分。CZZ 網路將通過自身的糾纏體系，為 BTC，USDT，ETH，BCH，BSV，LTC 與 DOGE 的鏈上資產提供抗量子地址。

現在我們討論一下 CZZ 未來關於抗量子的路徑。由於 CZZ 的挖礦演算法 Bora Bora 本身自帶大量的矩陣運算以及較強的 bandwidth hard，PoW 的抗量子能力會遠好於比特幣的 SHA256d。因此，我們重點的討論方向還是 CZZ 的地址系統。

在未來兩三年內，5G 網路會變的普及。在未來三五年內，NIST 會確定最終的抗量子方案。如果其中有一個方案使用 SI 加密，高效驗證 SI 加密演算法的硬體設計（例如，ASIC）將會隨之而出。因此，CZZ 計劃在約五年後啟動抗量子地址體系的升級。

對於區塊鏈項目來說，SI 加密演算法的另一個優勢，就是公鑰體系可以兼容現有體系。因此，未來向 SI 體系切換的實現方式，其實就是一次地址的擴容。在原有地址的基礎上，會出現一批以 pq 開頭的新增地址（pq 的含義是 post quantum，譯為「後量子」）。這些地址的長度會是現有地址的 10 倍左右，我們稱它們為後量子地址。後量子地址需要 SI 演算法來驗證轉出的交易，經典地址仍然按 ECC 演算法來驗證交易。因此，後量子地址下的資產，在量子計算機面前是安全的；經典地址上的資產，在量子計算機面前是有風險的。或許 10 － 15 年後，當量子風險變的越來越現實，用戶自主會將資產從經典地址轉移到後量子地址。

由於 CZZ 公鑰所使用的橢圓曲線 Secp256k1與 BTC，USDT，ETH，BCH，BSV，LTC，DOGE相同，CZZ 地址的擴容也會自動對 BTC，USDT，ETH，BCH，BSV，LTC 與 DOGE 生效。假設某 BTC 用戶擔心自己資產有量子風險，他可以通過糾纏將資產轉移到以 pq 開頭的後量子地址上，這些地址可以幫助他們抵抗量子攻擊。具體實現方式與設計細節，以後會進一步詳細敘述。