比特幣和以太坊網路所處理的主要內容叫做 “區塊”,指的是由交易、時間戳和其他重要後設資料所組成的資料結構。比特幣和以太坊網路的安全性的關鍵一環是:它能將表達網路全域性狀態的大塊資訊壓縮成一個簡短的訊息。在有需要之時,我們可以高效地驗證這個訊息的真實性。這個過程就是用雜湊函式來完成的,而得到的結果(訊息)就是雜湊值。
事實上,MD5 的抗碰撞性太差,以至於一臺家用 2.4 GHz 奔騰處理器都能在幾秒內計算出雜湊碰撞。此外,由於 MD5 在網際網路早期階段得到了廣泛應用,網路上有大量 MD5 原像遭到洩漏,透過谷歌搜尋它們的雜湊值就能找到。
雜湊演算法的多樣性發展
源起:SHA1 和 SHA2
NSA (沒錯,就是美國國家安全保障局)是雜湊演算法標準的先驅。安全雜湊演算法(Secure Hashing Algorithm,SHA1)是最早提出的標準,將輸出值的長度固定在 160 位。遺憾的是,SHA1 只是在 MD5 的基礎上增加了輸出值長度、單向操作的次數和複雜度,但是並沒有作出能夠抵禦更強大機器攻擊的根本性改進。
我們如何才能做得更好?
SHA3 興起
在 2006 年,美國國家標準技術研究所(NIST)舉辦了一場競賽,旨在找到一個本質上不同於 SHA2 的替代標準。因此,SHA3 應運而生,它是 KECCAK 雜湊演算法的一種方案。
雖然 SHA 3 在名稱上與 SHA1 和 SHA2 一脈相承,但是在本質上差異很大,因為它採用了一種名為海綿結構(sponge construct)的機制。該機制使用隨機排列來吸收並輸出資料,同時為將來用於雜湊演算法的輸入值提供隨機性。
SHA3 的內部狀態相較於輸出值擁有更多資訊,突破了以往演算法的侷限性。NIST 於 2015 年正式認可了 SHA3 標準。
雜湊計算和工作量證明
就整合進區塊鏈協議的雜湊演算法而言,比較早的比特幣選擇了 SHA256 ,而以太坊採用了改進後的 SHA3 (KECCAK256)作為工作量證明演算法。對於採用工作量證明的區塊鏈來說,選擇雜湊函式的一大重要標準是雜湊運算效率。
使用一類名為專用積體電路(ASIC)的硬體,我們可以大幅提高比特幣 SHA256 演算法的雜湊運算的效率。有很多文章已經闡述了礦池是如何利用 ASIC 的,以及 ASIC 是如何讓協議趨向於計算中心化的。也就是說,工作量證明會激勵計算效率較高的機器聚整合礦池,從而形成較大的雜湊算力(算力大小的衡量標準就是礦機在每個時間間隔內可以完成多少次雜湊運算)。
以太坊選擇的是改進後的 SHA3 演算法(叫做 KECCAK256 )。此外,以太坊的工作量證明演算法 Dagger-Hashimoto 被設計成了記憶體密集型模式,計算硬體需要加大記憶體才能提高計算效率。
為什麼比特幣採用雙重 SHA256 ?
有趣的是,比特幣協議(的工作量證明)需要重複執行兩遍 SHA256 演算法。請注意,這不是為了抵禦生日攻擊,畢竟在 hash(x) = hash(y) 的情況下,hash(hash(x)) = hash(hash(y)) 。雙重 SHA256 旨在抵禦長度擴充套件攻擊。
從本質上來說,所謂的長度擴充套件攻擊,指的是如果惡意攻擊者知道了某個雜湊輸入的長度,就可以在雜湊值上新增一個秘密的字串、欺騙雜湊函式從其內部狀態的一個特定部分開始計算。作為 SHA2 演算法家族的一員,SHA256 也存在這一缺陷。因此,比特幣採取執行兩遍雜湊計算的方式來解決這一缺陷。
Ethereum 2.0 和 BLAKE
SHA3 並非雜湊演算法競賽取得的唯一突破。雖然最終勝出的是 SHA3 ,但是 BLAKE 演算法緊隨其後,位居第二。對於以太坊 2.0 的分片實現來說,更高效的雜湊演算法可以說是一項功能性要求,研究團隊對此非常重視。BLAKE2b 雜湊演算法是 BLAKE 演算法的高度升級版本。與 KECCAK256 相比,BLAKE2b 雜湊演算法在保持高度安全性的同時,在提升效率方面也進行了深入探索。
使用一臺現代 CPU 計算 BLAKE2b 的速度比計算 KECCAK 快了 3 倍。
雜湊演算法的前景展望
這麼看來,無論我們做了什麼,無非就是(1)增加內部雜湊操作的複雜度,或者(2)增加雜湊輸出值的長度,讓攻擊者的計算機無法足夠快地有效計算出碰撞。
我們依靠單向操作的原像模糊性來保護網路的安全性。也就是說,雜湊演算法的安全性目標是在有無限多可能的衝突的情況下,讓找出雜湊碰撞的難度儘可能高。
如果量子計算時代到來,雜湊演算法依然安全嗎?
就目前來看,答案是肯定的,雜湊演算法將經受時間的考驗,抵禦量子計算。量子計算能夠解決的是那些嚴格按照某些小技巧或 RSA 加密理論打造底層結構的數學問題。另一方面,雜湊演算法的內部構造沒那麼形式化。
量子計算機確實能夠提高雜湊等非結構化問題的計算速度,但它們最終還是會像如今的計算機一樣採取暴力破解手段。
無論我們為協議選擇了哪種演算法,我們顯然都在邁向計算高效化的未來。為此,我們必須慎重選擇最合適的工具,使之經受住時間的檢驗。
參考文獻
[1]: https://bitcoin.stackexchange.com/questions/6037/why-are-hashes-in-the-bitcoin-protocol-typically-computed-twice-double-computed
[2]: https://en.wikibooks.org/wiki/Cryptography/Breaking_Hash_Algorithms
[3]: https://learncryptography.com/hash-functions/hash-collision-attack
[4]: https://github.com/zcash/zcash/issues/2233
[5]: https://crypto.stackexchange.com/questions/18612/how-is-sha1-different-from-md5
[6]: https://en.wikipedia.org/wiki/Birthday_attack
[7]: https://keccak.team/
[8]: https://en.wikipedia.org/wiki/Cryptographic_hash_function
[9]: https://crypto.stackexchange.com/questions/44386/are-cryptographic-hash-functions-quantum-secure