量子計算與加密貨幣
經過了幾十年的高速發展後，電子計算機晶元的運算速度已經邁入瓶頸期。平均每十八個月性能翻番的摩爾定律也已經失效。下一個里程碑式突破的很可能會由量子計算機實現。
在電子計算機中，信息以0和1的比特形式編碼，n個比特的內存可以存儲2^n種可能狀態中的一種。而在量子計算機中，數據存儲在量子比特（qubit）里，能同時表示0、1或它們的疊加態，所以n個量子比特可以在一個時刻同時表示最多2^n種狀態。這使得在量子比特上的一些運算會比在傳統電子計算機上快很多。
量子計算的研發在2018年的今天仍處於嬰兒期，但學術界已經在研究它對加密學和加密貨幣未來的影響了。例如去年十月，新加坡國立大學的Divesh Aggarwal等學者發布了一篇論文《Quantum attacks on Bitcoin, and how to protect against them》（https://arxiv.org/pdf/1710.10377.pdf），探討了針對比特幣的量子計算攻擊手段和防範措施。
他們認為量子計算在未來十年內幾乎不可能影響到比特幣的工作量證明（也就是挖礦）。在SHA256哈希函數的算力角逐中，量子計算機會長期敗給專用的ASIC礦機（參閱《[block #11] 亦敵亦友的ASIC》）。
為了穩妥起見，作者建議採用對量子計算難度更大的PoW演算法。例如基於尋找哈希衝突的Momentum演算法、Aeternity採用的Cuckoo Cycle圖搜索演算法、好幾種幣應用的Equihash泛化生日問題演算法等等。
與工作量證明相比，更危險的是交易簽名的安全性。比特幣目前採用基於secp256k1的橢圓曲線數字簽名演算法（ECDSA）驗證交易的有效性。它的安全性完全取決於ECDLP問題的難度。用傳統方法解ECDLP需要指數級或接近指數級的時間複雜度（參閱http://www.icisc.org/icisc/asp/icisc2017_papers_camera_ready/sec6_2.pdf），難以暴力破解。但在量子計算機面前，它的時間複雜度卻能降低到多項式級別（參閱Peter Shor的論文《Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer》）。
這意味著復用比特幣地址會變得危險。因為當你從地址A轉出幣時，地址對應的公鑰會被寫入交易，用於解鎖腳本的驗證（參閱《[block #20] 詳解比特幣地址 #1：P2SH地址與multisig》）。根據公開的公鑰，有可能用量子計算機成功算出對應的私鑰。如果繼續用地址A收款，其中的資金便隨時可能被攻擊方轉走。
即使不重用地址，也存在潛在的風險：當你廣播的交易A尚未得到區塊確認時，理論上有可能率先被量子計算機破解出私鑰。攻擊方隨後可以構造一個從源地址轉給自己的新交易B，利用replace-by-fee功能或與礦池合作，搶先把B寫入新區塊。這樣一來，你的交易A會被作廢，同時損失其中包含的所有幣。根據論文作者的估計，2027年的量子計算機有望在10分鐘內破解ECDSA，對比特幣的安全性構成巨大威脅。
防範這類攻擊需要改用抗量子計算的數字簽名，比如基於哈希的LMS、基於格結構（lattice）的BLISS、DILITHIUM等被稱為後量子時代（post-quantum）的簽名演算法。
由於量子計算目前遠不足以對橢圓曲線簽名構成實質性威脅，所以比特幣還沒有採取防範措施。然而有些新興加密貨幣已經在設計時就防患於未然了。比較典型的例子是Hcash（https://h.cash）。它支持基於SHA-3（Keccak）哈希演算法的LMS/MSS和基於格結構的BLISS簽名協議，提早為抗量子攻擊做準備（參閱：https://github.com/HcashOrg/hcashd/blob/dev/docs/research/post-quantum-signature-schemes-in-hcash.pdf）。
LMS/MSS簽名的安全性假定非常少，只要配套的哈希函數選擇得當就能保障安全性。而BLISS除了性能高，生成的公鑰和簽名長度也是後量子簽名演算法中相對很小的。當然，比起ECDSA，BLISS簽名仍舊顯得非常臃腫。比如說，比特幣的ECDSA簽名平均才70多位元組，而128位安全性的BLISS演算法產生的簽名高達5KB。這意味著交易吞吐量的減小或是帶寬和存儲需求的增大。為了緩解簽名龐大帶來的弊端，Hcash採用類似比特幣隔離見證（SegWit）的方案，把部分驗證信息移出交易，單獨存放和同步。要根治這個問題還需研發出簽名更短的高效抗量子攻擊演算法。
出於實際需求考慮，Hcash仍舊兼容久經考驗且尺寸小巧的ECDSA簽名。 這樣的設計讓用戶不必為尚處於理論階段的攻擊手段過早地付出代價。在量子計算出現重大突破之前，我們仍舊可以信賴ECDSA的安全性。
TAG:貓本聰 |