區塊鏈新手科普｜雜湊函數 (Hash Function) 的過去、現在與未來

雜湊值和雜湊函數的概念是初次入門區塊鏈的人常聽到的兩個關鍵詞，而且似乎對安全性來說特別關鍵。（實際上也確實是。）對於像比特幣和以太坊這樣由成千上萬的節點通過 P2P 方法組成的去中心化網路來說，「免信任性」和驗證效率無疑是關鍵。本文源自於 Raul Jordan 的 Medium 文章《The State of Hashing Algorithms — The Why, The How, and The Future》，由專欄作者以太坊愛好者編譯、撰寫及整理。

比特幣和以太坊網路所處理的主要內容叫做「區塊」，指的是由交易、時間戳和其他重要元數據所組成的數據結構。比特幣和以太坊網路的安全性的關鍵一環是：

它能將表達網路全局狀態的大塊訊息壓縮成一個簡短的訊息。

在有需要之時，我們可以高效地驗證這個訊息的真實性。這個過程就是用雜湊函數來完成的，而得到的結果（消息）就是雜湊值。

密碼學雜湊廣泛應用於口令存儲和文件驗證系統。簡單來說，密碼學雜湊函數是一種確定性的算法，不論輸入什麼值，都能得到一個固定長度的字符串。也就是說，同一個輸入值始終對應同一個輸出值。

對雜湊函數來說，重要的不僅是確定性（還有結果的隨機性）：

即使只更改輸入中的一個比特位，也會導致最終得到的雜湊值截然不同。

雜湊算法有一個無可迴避的問題叫碰撞可能性。因為雜湊值是固定長度的字符串，同一個雜湊有可能對應多個輸入。碰撞會造成很嚴重的後果。如果有人能夠按需要發起碰撞攻擊，他就可以用恰當的雜湊值將惡意文件或數據偽裝成合法的、能夠通過驗證的文件。好的雜湊函數的設計目標是讓攻擊者極難找到方法來找出對應同一個雜湊的不同輸入。

雜湊計算的效率不應過高，以免讓攻擊者可以更簡單地人為計算出碰撞。雜湊算法必須能夠抵禦「原像攻擊（pre-image attack）」。也就是說，對於特定雜湊值，攻擊者很難通過確定性計算步驟倒推出輸入值（即，原像）。

假設 s = hash(x)，倒推 x 應該是近乎不可能的。

總的來說，「好的」雜湊算法需要具備以下 3 個特性：

更改輸入中的一個比特位會產生雪崩效應，導致最後得出的雜湊值截然不同
出現雜湊碰撞的概率非常低
在無需犧牲抗碰撞性的前提下計算效率過得去

破解雜湊算法

雜湊算法的初始標準之一是 MD5 雜湊。MD5 雜湊廣泛應用於文件完整性驗證（校驗和），以及在網路應用數據庫中存儲經過雜湊計算的帳號口令。MD5 的功能非常簡單，因為它會將每個輸入轉換成一個固定的 128 位字符串輸出，並通過多輪簡單的單向操作來計算確定性輸出。由於輸出值長度較短，操作又較為簡單，MD5 很容易被破解，一種常見的攻擊方法叫生日攻擊。

「生日攻擊」是啥玩意？

你有沒有聽說過這樣一個事實？如果你將 23 個人放到一個房間裡，其中兩個人生日相同的概率為 50% 。如果將 70 個人放到一個房間裡，其中兩個人生日相同的概率高達 99.9% 。這就是我們所說的鴿籠原理（pigeonhole principle），即，將 100 只鴿子裝進 99 個鴿籠，必然有兩隻鴿子分享同一個鴿籠。也就是說，固定長度的輸出意味著所有輸入輸出組合中一定存在碰撞。

事實上，MD5 的抗碰撞性太差，以至於一台家用 2.4 GHz 奔騰處理器都能在幾秒內計算出雜湊碰撞。此外，由於 MD5 在互聯網早期階段得到了廣泛應用，網路上有大量 MD5 原像遭到洩漏，通過Google 搜尋它們的雜湊值就能找到。

雜湊算法的多樣性發展

源起：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 的算法是否對 PoW 的安全性有利？ (工作量證明)

使用一類名為專用集成電路（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 倍。

延伸閱讀：巨大乾貨｜截至 2020 年 6 月，以太坊 2.0 發展狀況「全景式解讀」