基于區(qū)塊鏈中的HASH算法解析

區(qū)塊鏈技術(shù)是一系列技術(shù)的結(jié)合，建立一種新的技術(shù)架構(gòu)，hash算法是其中尤為重要的一塊，這里簡(jiǎn)單對(duì)hash算法做一個(gè)說明。如果有理解不當(dāng)?shù)牡胤秸?qǐng)及時(shí)指正。

講hash算法之前先明確一個(gè)基礎(chǔ)的計(jì)算機(jī)知識(shí)，計(jì)算機(jī)在底層機(jī)器碼是采用二進(jìn)制的模式，所謂二進(jìn)制簡(jiǎn)單來說就是底層以0/1來標(biāo)識(shí)，所有數(shù)據(jù)傳輸記錄都以010101的模式來存儲(chǔ)記錄，兩種狀態(tài)也可認(rèn)為就是一個(gè)日常生活中的開關(guān)，1標(biāo)識(shí)開，0標(biāo)識(shí)關(guān)。那么計(jì)算機(jī)中最小的數(shù)據(jù)單位也就是這里說的0或者1，這里我們稱為bit（比特或者位），8個(gè)bit組成一個(gè)字節(jié)。當(dāng)然計(jì)算機(jī)中也有八進(jìn)制、十六進(jìn)制的表示，這里暫時(shí)不展開討論。只明確底層一個(gè)二進(jìn)制的概念。

Hash算法將任意長(zhǎng)度的二進(jìn)制值映射為較短的固定長(zhǎng)度的二進(jìn)制值，這個(gè)小的二進(jìn)制值稱為哈希值。哈希值是一段數(shù)據(jù)唯一且極其緊湊的數(shù)值表示形式。如果散列一段明文而且哪怕只更改該段落的一個(gè)字母，隨后的哈希都將產(chǎn)生不同的值。要找到散列為同一個(gè)值的兩個(gè)不同的輸入，在計(jì)算上是不可能的，所以數(shù)據(jù)的哈希值可以檢驗(yàn)數(shù)據(jù)的完整性。一般用于快速查找和加密算法。

再引入一個(gè)hash表概念，計(jì)算機(jī)數(shù)據(jù)結(jié)構(gòu)中，給定一個(gè)表M，關(guān)鍵字key，存在函數(shù)H（key），對(duì)任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為hash表。

簡(jiǎn)單理解hash算法就是這一種單向的加密，一個(gè)明文加密稱為密文，不可逆推，只有加密過程，沒有解密過程。說明了hash函數(shù)和hash表的概念，那么目前常用的hash算法有MD5（已被破解），SHA系列算法（比特幣中使用sha-256算法）。SHA這里稍微提下（secure hash algorithm）這不是一個(gè)算法，這是一個(gè)hash函數(shù)集，現(xiàn)在有sha-224、sha-256、sha-384、sha-512等算法。在09年中本聰設(shè)計(jì)比特幣的時(shí)候，當(dāng)時(shí)sha-256被認(rèn)為最安全的算法之一，故選擇了sha-256，到目前為止還沒有被破解。

解釋到這里，可能會(huì)聯(lián)想到，hash算法中key在計(jì)算后如果出現(xiàn)了同一位置，沖突的產(chǎn)生，這里簡(jiǎn)單說下幾種沖突處理，如有興趣可以查看hash算法論文。

1.拉鏈法：這種方法可以完全避免沖突，將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)鏈接在同一個(gè)單鏈表中。若選定的散列表長(zhǎng)度為m，則可將散列表定義為一個(gè)由m個(gè)頭指針組成的指針數(shù)組t［0..m-1］。凡是散列地址為i的結(jié)點(diǎn)，均插入到以t為頭指針的單鏈表中。t中各分量的初值均應(yīng)為空指針。在拉鏈法中，裝填因子α可以大于1，但一般均取α≤1。

2.多哈希法：設(shè)計(jì)兩種以上的hash函數(shù)，避免沖突，這個(gè)感覺比較不靠譜，但是從概率上來說多種hash函數(shù)還是降低了沖突的出現(xiàn)。

3.開放地址法：開放地址法有一個(gè)公式：Hi=（H（key）+di） MOD m i=1，2，。..，k（k《=m-1），其中，m為哈希表的表長(zhǎng)。di 是產(chǎn)生沖突的時(shí)候的增量序列。如果di值可能為1，2，3，。..m-1，稱線性探測(cè)再散列。如果di取1，則每次沖突之后，向后移動(dòng)1個(gè)位置。如果di取值可能為1，-1，4，-4，9，-9，16，-16，。..k*k，-k*k（k《=m/2），稱二次探測(cè)再散列。如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測(cè)再散列。

Hash算法函數(shù)根據(jù)分類：加法hash、位運(yùn)算hash、乘法hash、除法hash、查表hash等。

參考百度百科說的比較抽象，有興趣可以深入了解下。

結(jié)合區(qū)塊鏈，在區(qū)塊鏈中很多地方都用到了hash函數(shù)：

1.區(qū)塊鏈中節(jié)點(diǎn)的地址、公鑰、私鑰的計(jì)算。以地址為例：公鑰經(jīng)過一次SHA256計(jì)算，再進(jìn)行一次RIPEMD160計(jì)算，得到一個(gè)公鑰哈希（20字節(jié)\160比特），添加版本信息，再來兩次SHA256運(yùn)算、取前4比特字節(jié)，放到哈希公鑰加版本信息后，再經(jīng)過base58編碼，最終得到地址。

2.merkle tree：是數(shù)據(jù)結(jié)構(gòu)中的一種樹結(jié)構(gòu)，可以是二叉樹，也可以是多叉樹，他和數(shù)據(jù)結(jié)構(gòu)中樹的特點(diǎn)幾乎一致，和普通樹不同的是：merkle tree上的葉節(jié)點(diǎn)存放hash計(jì)算后的hash值，非葉節(jié)點(diǎn)是其對(duì)應(yīng)的子節(jié)點(diǎn)串聯(lián)的字符串的hash值。用于區(qū)塊頭和SPV認(rèn)證中。

3.比特幣中的挖礦，工作量證明（pow），計(jì)算的其實(shí)就是一個(gè)nonce，當(dāng)這個(gè)隨機(jī)數(shù)和其他散列過的數(shù)據(jù)合并時(shí)，產(chǎn)生一個(gè)比規(guī)定目標(biāo)?。╰arget）值。挖礦也可以理解一種快速不可逆的計(jì)算。SHA256（SHA256（version + prev_hash + merkle_root + ntime + nbits + x ）） 《 TARGET。

4.比特幣中的bloom filter布隆過濾器，布隆過濾器基于hash函數(shù)的快速查找。解決了客戶端檢索的問題，原理是Bloom filter可以快速判斷出某檢索值一定不存在于某個(gè)指定的集合，從而可以過濾掉大量無關(guān)數(shù)據(jù)，減少客戶端不必要的下載量。

簡(jiǎn)單介紹了HASH算法，和區(qū)塊鏈中用到的HASH算法，區(qū)塊鏈?zhǔn)嵌鄠€(gè)技術(shù)的結(jié)合，結(jié)合各自特點(diǎn)出現(xiàn)的一種新的技術(shù)架構(gòu)，HASH算法和加密技術(shù)為區(qū)塊鏈的自證信任化及安全控制提供了基礎(chǔ)，算法的碰撞和現(xiàn)在量子計(jì)算的發(fā)展，之前在區(qū)塊鏈的安全性的文章中筆者有過說明，技術(shù)不斷發(fā)展，肯定會(huì)有更適合的技術(shù)保障應(yīng)用的實(shí)現(xiàn)。