密碼學是衆多加密貨幣系統的根基，得益於數學上的獨特性質，hash 算法以及加密技術都在區塊鏈系統中都有着舉足輕重的作用，今天我們就詳細瞭解一下 hash 算法。
從數據結構和算法的角度看，所謂的 hash 函數就是將任意長度的數據映射到有限長度的域上，參考《算法導論》，我們很容易的給出一個這樣的函數：
h(k) = k mod m
同時，以 hash 函數爲基礎的數據結構 hash table 或 hash map 因爲有着優良的查找效率得到廣大程序員的厚愛，並且各個主流編程語言都會內置該數據結構或者以標準庫的形式予以支持。
回到密碼學領域，我們期望 Hash 算法擁有以下三個特性：
-
使用任意長度的字符串作爲輸入
-
輸出值是固定的（256 比特）
-
計算高效
常用的 Hash 算法有 MD5、SHA-1 SHA2 等。
與 hashmap 卓越的查找效率不同的是，hash 函數在區塊鏈中得到重用的原因基於以下三點：
-
碰撞阻力
-
隱祕性
-
謎題友好
碰撞阻力
碰撞阻力是指很難找到兩個不同的輸入值 x 和 y，使得它們的 hash 值相同，如果找到了這一對值，我們就稱發生了“碰撞”。
熟悉 hashmap 的同學一定對碰撞行爲不陌生，在設計 hash 函數的時候，有一個很重要的原則就是降低發生碰撞的概率，從而避免 hash 表的查找效率蛻變成數組。 我們用了“降低”這個詞，是因爲碰撞不可能完全避免，看下面這張圖：
因爲可能的輸入要遠遠大於可能的輸出，從數學上我們就能直觀的感受到，一定存在這樣一對數 x 和 y，擁有相同的 hash 值，實際上，如果將輸出固定爲 256bit，那麼不管選擇什麼 hash 函數，只要嘗試 Math.pow(2, 130) 個輸入， 發生碰撞的概率就是 99.8%。但是需要注意的是，雖然碰撞存在，但通常我們無法在普通的機器上，在有限的時間內找到碰撞。但是這也不意味着每個 hash 算法都是安全的，人們還是有辦法去構造碰撞，比如 md5 和 sha1 已經被證明不再安全。
基於 hash 算法碰撞阻力這一特性，我們可以得出以下一個重要的結論：如果我們知道 H(x) == H(y)，那麼我們可以安全的認爲 x == y，這就是 hash 算法的一個非常重要的應用：信息摘要，想象一下我們需要比較兩個非常大的文件內容是否相同，我們只需比較它們的 hash 值是否相同即可，大大的加快的了對比算法的速度。文件的 hash 值就被稱之爲“摘要信息”。
隱祕性
**
**
隱蔽性的意思是，給定 H(x) 的值，人們是沒有辦法找到初始值 x。 但是這樣的描述還不夠準確，因爲如果 x 的取值範圍非常有限，人們還是可以通過將每個可能的 x 進行 hash 並與 H(x) 進行對比，從而確定 x 。所以我們有一個更加準確的版本：
如果我們從一個滿足高階最小熵的概率分佈中選出一個祕密的值 r， 則在知道 H(r || x) 的情況下，人們無法推算出值 x。熵是信息論的範疇，熵越高，則能傳輸越多的信息，熵越低，則意味着傳輸的信息越少。這裏的高階最小熵基本上可以理解成可能性非常多，從而 r || x 的範圍變得特別大，使得上面窮舉然後對比的方法失去效果，和密碼學另一個概念“加鹽“有異曲同工之妙。
隱祕性的一個典型應用場景是實現承諾協議， 承諾可以理解成我放在信封裏的一封信，並在稍後合適的時間點將其公佈。對應到數字領域，我們可以給出如下定義：
msg 對應信的內容，commit(msg) 表示我們將信放進信封，隨後將 com 公佈；打開信的過程即是公佈 key 和 msg 的過程，人們可以使用 verify 函數來進行驗證。 使用 hash 算法實現承諾協議的方法如下：
commit 階段使用 H(key | msg) 求出 com 並將其公佈，verify 階段將 key 和 msg 公佈，並對比 H(key | msg) 和 com 的值是否相等。由於碰撞阻力的存在，人們沒有辦法在改變 msg 的情況下求出與之前公佈的 com 一樣的值，同時又因爲 key 的高階最小熵的概率分佈，人們也沒有辦法在沒有公佈 msg 之前，通過暴力算法將其推算出。承諾協議的應用範圍很廣，尤其是博彩領域，有興趣的可以搜索一下相關的材料。
謎題友好
**
**
謎題友好的意思是對於 H(k | x) = y，如果 k 遵循高階最小熵的概率分佈，那麼在知道 y 的情況下，人們並沒有有效的辦法去反推 x 的值，除了隨機的亂猜 …
最典型的應用場景就是 bitcoin 的 pow 共識機制，俗稱挖礦。
歡迎讀者加入哈希 1024 區塊鏈社區微信羣，進行更多的區塊鏈技術交流，可關注本公衆號，在後臺回覆“哈希”即可。
繁體中文
简体中文
English
日本語
Español