區塊鏈知識分享——Hash

Hash 是什麼？

Hash 哈希演算法。密碼哈希函數是一類數學函數，可以在有限合理的時間內，將任意長度的消息壓縮為固定長度的二進位串，其輸出值稱為哈希值，也稱為散列值。以哈希函數為基礎構造的哈希演算法，在現代密碼學中扮演著重要的角色，常用於實現數據完整性和實體認證，同時也構成多種密碼體制和協議的安全保障。

碰撞是與哈希函數相關的重要概念，體現著哈希函數的安全性，所謂碰撞是指兩個不同的消息在同一個哈希函數作用下，具有相同的哈希值。哈希函數的安全性是指在現有的計算資源（包括時間、空間、資金等）下，找到一個碰撞是不可行的。

在比特幣系統中使用了兩個密碼學哈希函數，一個是 SHA256，另一個是 RIPEMD160。

RIPEMD160 主要用於生成比特幣地址，我們著重分析比特幣中用得最多的 SHA256 演算法。

SHA256 屬於著名的 SHA 家族一員。SHA（Secure Hash Algorithm，安全哈希演算法）是一類由美國國家標準與技術研究院（NIST）發布的密碼哈希函數。正式名稱為 SHA 的第一個成員發佈於 1993 年，兩年之後，著名的 SHA-1 發布，之後另外的 4 種變體相繼發布，包括SHA224、SHA256、SHA384 和 SHA512，這些演算法也被稱作 SHA2。SHA256 演算法是 SHA2 演算法簇中的一類。對於長度小於 2^{64}位的消息，SHA256 會產生一個 256 位的消息摘要。

SHA256 具有密碼哈希函數的一般特性。SHA256 是構造區塊鏈所用的主要密碼哈希函數。無論是區塊的頭部信息還是交易數據，都使用這個哈希函數去計算相關數據的哈希值，以保證數據的完整性。同時，在比特幣系統中，基於尋找給定前綴的 SHA256 哈希值，設計了工作量證明的共識機制；SHA256 也被用於構造比特幣地址，即用來識別不同的用戶。

SHA256 是一個 Merkle-Damgard 結構的迭代哈希函數，其計算過程分為兩個階段：消息的預處理和主循環。在消息的預處理階段，主要完成消息的填充和擴展填充，將所輸入的原始消息轉化為 n 個 512比特的消息塊，之後對每個消息塊利用 SHA256 壓縮函數進行處理，SHA256 的計算流程如圖

在比特幣系統中，SHA256 演算法的一個主要用途是完成 PoW（工作量證明）計算。按照比特幣的設計初衷，PoW 要求錢包（節點）數和算力值大致匹配，因為需要通過 CPU 的計算能力來進行投票。然而隨著人們對 SHA256 的計算由 CPU 逐漸升級到 GPU，到 FPGA，直至到 ASIC 礦機，這使得節點數和 PoW 算力也漸漸失配。解決這個問題的一個思路是引入另外的一些哈希函數來實現 PoW。

scrypt 演算法最早用於基於口令的密鑰生成，該演算法進行多次帶參數的 SHA256 計算，即基於 SHA256 的消息認證碼計算，這類計算需要大量的內存支持。

採用 scrypt 演算法進行 PoW 計算，將 PoW 計算由已有的拼算力在一定程度上轉化為拼內存，能夠使得節點數和 PoW 的計算力的失配現象得到緩解。

萊特幣就是採用 scrypt 演算法完成 PoW 計算的。SHA3 演算法是 2012 年 10 月由 NIST 所選定的下一代密碼哈希算法。在遴選 SHA3 演算法過程中人們提出了一系列的候選演算法，包括了BLAKE、Grostl、JH、Keccak、Skein、ECHO、Luffa、BMW、CubeHash、SHAvite、SMID 等，最後勝出的是 Keccak 演算法。達世幣（DASH，原名暗黑幣，DarkCoin）定義了順序調用上述 11 個哈希演算法的 X11 算法，並利用這個演算法完成 PoW 的計算力能夠保持一定程度上的匹配。