前言：哈希算法對於保證區塊鏈網絡安全很重要。為了減少哈希衝突可能性，要麼提高哈希內部操作的複雜性，要麼提高哈希輸出的長度，寄希望於攻擊者計算速度不夠快。本文分析了哈希算法的歷史，原理和未來，對於我們理解區塊鏈的安全問題很有幫助。本文作者是Raul Jordan，文章來源於medium.com,由藍狐筆記社群「李熙和」翻譯。
新手在了解區塊鏈的時候經常會接觸到哈希（hash）和哈希算法（hashing algorithm）這樣的概念，它們在安全方面可以說是無處不在。通過P2P運行像比特幣，以太坊之類有眾多節點的去中心化網絡需要去信任機制和驗證的高效性。
這就是說，這些系統需要想辦法將信息以一種高效而簡潔的方式編碼，並允許其參與者能夠安全而快速的進行驗證。
比特幣和以太坊所涉及的主要概念是「區塊」，這是一種包含交易記錄，時間戳以及其他元數據的數據結構。這種數據結構安全性的關鍵在於：它能夠將大量關於全球網絡狀態的信息壓縮成一小段信息標準，並使這一小段信息能被高效的驗證，這一小段信息被稱為哈希。
即使僅僅改變輸入信息的一個字符也會產生一個完全不同的哈希值！
加密學上的哈希被用於各行各業，從密碼儲存到文件驗證系統。基本思想是使用一種確定性的算法(deterministicalgorithm)，這種算法能夠接受一個輸入並每次都產生一個長度固定的字符串。也就是說，一個相同的輸入得到的永遠都是相同的輸出。
除了這種確定性，哈希算法還有一個特性：輸入中的任何一點點的改變都會導致輸出變得完全不同。
哈希算法有一個問題，就是衝突必然性（inevitability of collisions）。它的意思是：由於哈希函數輸出的字符串長度一定，不同的輸入有可能會產生相同的哈希值。衝突是不好的，如果一個攻擊者能夠故意產生衝突，他便能夠把惡意的文件或者數據偽裝成正確的哈希值並將其傳遞下去。一個好的哈希函數的目標是讓衝突的發生變得幾乎不可能。
計算一個哈希值不應該太過高效，因為這會讓衝突的實現變得太過容易。哈希算法應該能夠抵禦「原像攻擊（pre-image attack）」。也就是說，根據已知的哈希值找到輸入值應該是極其困難的（輸入值被稱作原像，比如s = hash(x)，根據s找到x應該是幾乎不可能的）。
總結起來，一個好的哈希算法應該具備以下特徵：
· 改變輸入的任意一點都會產生一個完全不同的輸出
· 發生衝突的可能性非常低
· 在不犧牲抵禦衝突的情況下有一定的效率
攻擊哈希
最初的哈希算法標準之一是MD5哈希，它被廣泛的應用於文件完整性驗證（校驗和），同時在網絡應用的資料庫中用於儲存哈希密碼。那時它的功能還十分簡單，因為不論輸入如何，輸出是一個固定的128位的字符串，並且它使用並不有效的多輪單向操作（one-wayoperations across several rounds）來計算確定性輸出。
由於輸出字符串長度較短以及操作較為簡單，MD5很容易被破解並易受生日攻擊（Birthday Attack）的侵擾。
什麼是「生日攻擊」？
你可能聽說過：如果一個房間裡有23個人，那麼兩兩生日重疊的可能性就有50%，而在一個房間內如果提高到70人，那麼這個概率就變成了99.9%。這就是鴿子洞原則（pigeonhole principle），如果有100隻鴿子只有99個洞，那麼必然有一個洞中有兩隻鴿子。
放在哈希算法的案例中就變成了，一個固定長度的字符串意味著一個固定的排列組合數量，因此當輸入值達到一定的數量時，衝突必然會發生。
太多鴿子了！至少有一隻鴿子會與另一隻共用一個洞
MD5抵禦衝突的能力如此之弱，以至於一個2.4GHz的奔騰處理器都能在數秒之內製造一次哈希衝突。事實上，由於MD5在較早年代的廣泛應用，已經有大量的原像在線上洩漏，你甚至可以用簡單的谷歌搜索來找到它們。
多樣性和哈希算法的進化
開端：SHA1 & SHA2
美國國家安全局（NSA）一直都是哈希算法標準方面的先驅，他們最早提出安全哈希算法，也就是SHA1，這個算法輸出的是160位固定長度的字符串。
然而，SHA1僅僅在MD5的基礎上提高了輸出的長度，單向操作的數量以及單向操作的複雜性，但未做任何根本改進來使其能夠抵禦更強大的機器，這些機器嘗試不同的攻擊向量。
那麼我們該如何提高呢？
SHA3
在2006年，美國國家標準與技術研究所（NIST）發起了一場尋找一個與SHA2從根本上不同的替代品，讓它成為新的算法標準。因此，SHA3的誕生是哈希算法偉大機制的一部分，它被稱為KECCAK。
雖然名字看上去差不多，SHA3內部與之前的算法完全不同，因為它擁有海綿結構（Sponge Construct）機制。這種結構使用隨機的排列組合來吸收和輸出數據，同時還能為未來輸入值提供隨機源。
KECCAK256海綿結構作用於輸入值
SHA3維持一個內部狀態，使得輸出信息比字符串長度長（依然能夠做到對於信息的壓縮），這使它克服了先前算法的局限性。它也在2015年成為了NIST的標準算法。
哈希和PoW
當哈希算法被集成到區塊鏈協議中的時候，更老一些的比特幣選擇了SHA256算法，而以太坊選擇了改良版的SHA3（KECCAK256）作為PoW的算法。一個在區塊鏈PoW協議中選擇哈希函數的重要標準是計算哈希值的效率。
對比特幣SHA256算法的執行效率可以通過製造諸如ASICs礦機之類的專門硬體來進一步提高。這表現在礦池中ASICs的使用，並使協議趨向於計算中心化。
也就是說，PoW鼓勵高效的計算群體聚合成更大的群體（礦池）從而提高我們所說的哈希算力（也就是一個機器在固定的時間間隔能夠計算的哈希數量）。
以太坊，選擇了改良後的SHA3，也被稱作KECCAK256。此外，以太坊的PoW算法（Dagger-Hashimoto）設計成硬體內存難以計算，這從一定程度上避免了ASICs礦機的使用。
為什麼比特幣要使用雙重SHA256？
比特幣使用SHA256來轉換數據的方式很有趣，它將算法在協議中連續執行了兩次。注意，這並不是為了抵禦生日攻擊，顯然如果hash(x) = hash(y) 那麼也有hash(hash(x)) = hash(hash(y))，而是為了緩解長度擴展（length-extension）攻擊。
從本質上說，這種攻擊需要惡意攻擊者知道哈希輸入值的長度，在這個已知的長度上再加上一個秘密的字符串，就可以發動哈希函數內部的一部分，從而擾亂哈希函數。由於SHA256是SHA2算法家族的成員，它有這一類的短板，而比特幣通過將哈希函數連續運行兩次來緩解這個缺陷。
以太坊2.0和BLAKE
SHA3並不是NIST在2006年發起的那場競賽中唯一的突破。雖然SHA3最終獲勝，一個叫做BLAKE的算法緊隨其後位居第二。對於以太坊2.0分片的執行，更高效的哈希算法可以說是必不可少的。
BLAKE2b哈希算法是一個在競賽之後被高度升級優化過的版本，由於在保持高度安全性的同時擁有極高的效率（跟KECCAK256相比），這個算法也經歷了較為徹底的測試。
在一個現代CPU上計算BLAKE2b實際上比KECCAK要快3倍。
哈希算法的未來
看起來無論我們做什麼，要麼是在（1）提高哈希函數內部操作的複雜性，要麼是在（2）提高哈希輸出的長度，寄希望於攻擊者的計算機由於速度不夠快而無法有效產生計算衝突。
我們網絡的安全性目前依賴著單向操作原像的模糊性。也就是說一個哈希算法的安全目標是讓任何人找到具有兩個相同輸出的值變得越難越好，從而使得哈希衝突的可能性儘可能的小，雖然依舊存在無限數量的可能的衝突。
那麼量子計算呢？在量子計算面前哈希算法足夠安全嗎？
根據目前的理解，簡單的回答是：安全。哈希算法將能夠經受量子計算的挑戰。量子計算能夠破解那些諸如RSA加密問題，這些問題具有嚴格的底層數學結構，它們由巧妙的技巧和理論構建。而哈希算法內部構造中並沒有那么正式的結構。
量子計算機確實可以加快計算非結構化問題（如哈希）的速度，但是到最後，量子計算機發起攻擊的方式依然是暴力破解，和傳統的計算機並沒有什麼不同。
不論我們選擇什麼算法，顯然我們都在駛向一個計算更高效的未來，我們必須盡全力挑選最好的工具並經得起時間的考驗。
-
風險警示：藍狐筆記所有文章都不構成投資推薦，投資有風險，投資應該考慮個人風險承受能力，建議對項目進行深入考察，慎重做好自己的投資決策。
本文已加入「POB.Network腦力挖礦」內容天使合伙人計劃。
通往區塊鏈的新世界：關注「藍狐筆記」區塊鏈公眾號：lanhubiji
或加入藍狐筆記的知識星球：https://t.zsxq.com/iaQNnIq