第2章 區塊鏈技術基礎

2.1 哈希

哈希（Hash）是一種數學運算轉換，即把任意長度的輸入值通過哈希算法轉換為固定長度的輸出值。哈希的目標是把任意長度的輸入值壓縮到固定長度，并使輸出值作為輸入值的數字指紋。哈希函數（Hash Function）是給定的輸入值x對應的輸出值f （x）中的數學函數f。哈希函數的典型特征是，若給定的f （x₁）≠ f （x₂），則不存在x₁=x₂，即不允許輸出值不同時輸入值相同。對于表T和任意輸入值x，若我們可通過將f （x）作為索引來計算出x在表T中存儲的位置，則表T可稱為哈希表（Hash Table）。碰撞（Collision）是指當輸入值x₁≠x₂時，存在f （x₁）= f （x₂）的情況。好的哈希函數要盡量避免碰撞。

哈希函數具有壓縮、易計算、抗碰撞等特性，而加密領域的哈希函數需具備以下3個典型特性。

1）抗-原像攻擊（Pre-image Resistance）

抗-原像攻擊，即給定一個哈希值y= f （x），人們幾乎不可能在有限時間內算出x。在加密應用中，抗-原像攻擊是非常重要的特性，它可以防止攻擊者獲取原始的加密內容。舉個例子，用戶登錄網站的密碼一般在數據庫中存儲為哈希值，不會直接存儲為密碼明文，假定攻擊者從數據庫中獲取到哈希值，他們很難根據哈希值獲得密碼明文，這意味著攻擊者無法登錄網站。

2）抗-次原像攻擊（Second Pre-image Resistance）

抗-次原像攻擊，即給定一個輸入值x₁，人們幾乎不可能在有限時間內找到一個與x₁相同的值x₂來使 f （x₁）= f （x₂）。這意味著攻擊者無法使用一個相近或相似的原像來替換原像。

3）抗碰撞

抗碰撞即很難找到任意的兩個相同的輸入值 x₁和 x₂，從而使f （x₁）= f （x₂）。它與抗-次原像攻擊的不同之處在于， x₁不是指定的，這意味著窮舉范圍是無窮大的。

常見的加密哈希算法包括MD5、SHA-1、SHA-2，主要應用于文件和信息校驗、數字簽名驗證、密碼校驗、工作量證明等場景，下面我們對這幾種算法進行簡單的介紹。

MD5全稱為Message-Digest Algorithm 5（信息-摘要算法5），是1991年Ronald Rivest設計的替代MD4的算法，可以參考RFC1321中對其進行的詳細描述，是在SHA-2沒出現之前廣泛應用于安全領域的哈希算法。其特點是對于輸入值，會固定輸出128bit（128/8=16Byte）的哈希值。但是MD5被發現可以人為構造碰撞，以文件哈希為例，相同的MD5可以通過構造不同的文件讓兩者的哈希值相等。目前，MD5在來源不可信的情況下不推薦使用，在區塊鏈領域更加不可采用。

SHA-1全稱為Secure Hash Algorithm 1（安全哈希算法-1），1995年由美國國家安全局（NSA）設計，并由美國國家標準技術研究所（NIST）發布為聯邦數據處理標準（FIPS）。SHA-1會根據輸入值生成160bit（160/8=20Byte）的哈希值，哈希值通常的呈現形式為40個十六進制數，又稱消息摘要。SHA-1在許多安全協議中得到廣泛使用，如TLS（Transport Layer Security）和SSL（Secure Sockets Layer）、PGP（Pretty Good Privacy）、SSH（Secure Shell）、S/MIME （Secure Multipurpose Internet Mail Extensions）和 IPSec （Internet Protocol Security）。SHA-1在2005年已經被發現存在有效攻擊方式；2017年2月23日，Google經過兩年的研究，聲稱已經成功破解SHA-1的加密，目前各大機構均推薦使用SHA-2和SHA-3來替換SHA-1。

SHA-2的全稱為Secure Hash Algorithm 2（安全哈希算法-2），2001年由NSA設計，由NIST發布為FIPS，是SHA-1的繼任者，包括SHA-224、SHA-256、SHA-384、SHA-512，SHA 后面的數字指的是哈希后的位數。下面我們重點描述SHA-256，目前它被重點應用于區塊鏈技術中，因為SHA-256有256bit（256/8=32Byte）的哈希值，每一位可能為0或1，即有2²⁵⁶種組合，對于數量如此龐大的可能性，人們用當下的計算機暴力破解需要漫長的時間，這意味著SHA-256的碰撞概率是極小的。因此，區塊鏈技術大量使用了SHA-256等安全哈希算法。SHA-256通常用64bit的十六進制字符串表示，譬如輸入：

測試SHA-256長度字符串。

輸出：

90edfab86aace2d98a417426f6f32c3fb13695a2a2e674631b1fdd3c79321343

哈希主要作用于區塊鏈的幾個重要場景，包括默克爾樹（Merkle Tree）、錢包地址等，比特幣等常用的是SHA-256，下面我們詳細介紹默克爾樹。