區塊鏈入門 | 什麼是雜湊函式
今天我們來看看比特幣的一個重要概念:雜湊函式。本文首先介紹了什麼是雜湊函式以及雜湊函式的抗碰撞性、隱祕性和謎題友好三大特性。再結合區塊鏈的特性,分享了雜湊函式在區塊鏈挖礦工作量證明中的具體應用,並簡單講解了雜湊函式與防篡改性的關係。
全文約2600字,大概需要閱讀8分鐘。
01
什麼是雜湊函式
雜湊函式(Hash Function)是加密演算法雜湊演算法中廣泛應用的一種函式,也稱為雜湊函式或雜湊函式。雜湊函式作為公開函式,可以將任意長度的訊息M對映成為一個長度較短且長度固定的值H(M),稱H(M)為雜湊值或者訊息摘要(Message Digest)。雜湊運算是一種單向密碼體制,即一個從明文到密文的不可逆對映,只有加密過程,沒有解密過程。它的函式表示式為:
y = H(x)
安全雜湊演算法(Secure Hash Algorithm 256,SHA-256)是比特幣經常使用的一種雜湊函式,本文主要以 SHA-256演算法為例。無論輸入是什麼數字格式、檔案有多大,雜湊運算輸出的都是固定長度的位元串,比如在二進位制下有256bit,即256 個0或者1組成的串,用16進位制數字表示的話是64位,例如:
我們常用的16進位制:
0xd7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592
轉為2進位制:
1101011110101000111110111011001100000111110101111000000010010100011010011100101010011010101111001011000000001000001011100100111110001101010101100101000111100100011011010011110011011011011101100010110100000010110100001011111100110111110010011110010110010010
02
雜湊函式的三大特性
要使雜湊函式達到密碼安全,需要附加以下三個特性:碰撞阻力、隱祕性、謎題友好。
特性1:碰撞阻力
Hash 函式 H 將可變長度的資料塊 M 作為輸入,產生固定長度的 Hash 值 h = H(M)。稱 M 是 H 的原像。因為 H 是多對一的對映,所以對於任意給定的 Hash 值 H,對應有多個原像。如果滿足 x ≠ y 且 H(x) = H(y),即兩個不同的輸入 x 和 y 產生相同的輸出 H(x) = H(y),則稱為碰撞。如果對於雜湊函式 H(x),沒有人能夠找到碰撞,則稱該函式具有碰撞阻力。
對於給定的資料 X ,很容易算出雜湊值 H = H(M);但根據 H 很難反算出 X;很難找到 X 和 Y 使得 H(X) = H(Y)。事實上,把大空間的訊息壓縮到小空間上,碰撞肯定是存在的。
假設雜湊值長度固定為256位,如果順序取1,2,…2^256+1,這2^256+1個輸入值,逐一計算其雜湊值,肯定能找到兩個輸入值使得其雜湊值相同。但不要高興的太早,因為你得有時間把它算出來,才是你的。
對於雜湊值長度為256位的雜湊函式,平均需要完成2^128次雜湊計算,才能找到碰撞對。如果計算機每秒進行10000次雜湊計算,需要約10^27年才能完成2^128次雜湊計算。
特性2:隱祕性
隱祕性指的是當輸入 r 選自一個高階最小墒的概率分佈,在給定 H(r||x) 條件下確定 x 是不可能的。簡單的說,就是無法從輸出得到輸入。設 y=H(x) ,如果我們知道 y,很難迅速找到滿足符合條件的 x,則稱雜湊函式 H(x) 具有隱蔽性。隱蔽性意味著幾乎不可能找到其反函式 x'=H'(y),實際上滿足條件的 x 應該多個,這裡隱蔽性要求哪怕1個也找不出來。這是因為上面提到的雜湊函式單向性,對於給定的Hash值,在 2^128次雜湊計算量下是不可行的。
隱祕性的一個應用是“承諾”,將資訊(message)和一個隨機數(nounce)作為輸入,所得的輸出即為承諾。這裡的承諾包含兩方面的意思:通過承諾,其他人無法知道你的輸入;而你一旦公開了承諾,你無法欺騙別人該承諾是另外一個資訊。所以,這裡應用到了隱祕性。此外,每次的承諾都需要一個新的的隨機數,這對承諾的安全性很重要。
特性3:謎題友好
如果對於任意 n 位輸出值 y,假定 k 選自高階最小熵分佈,如果無法找到一個可行的方法,在比2的 n 次方小很多的時間內找到 x,保證 H(k||x) = y 成立,那麼我們稱雜湊函式 H 為謎題友好。在搜尋謎題這個應用中,我們將建立一個搜尋謎題,該謎題是一個需要對龐大空間進行搜尋,才能找到解決辦法的數學問題。簡單來說,就是要求具有隨機性,任意輸入可以得到固定位數的輸出,很難找到輸入和輸出之間的任何關聯性,哪怕是稍微調整輸入,得到的輸出都具有隨機性,除了通過調整輸入內容進行“暴力試算”,沒有其他更好的辦法。
碰撞阻力,隱祕性,謎題友好,各有側重,而又相互貫通。特別是隱祕性和謎題友好,十分相似,對於想深度理解的讀者,需要指明的是隱祕性說的是確定x,謎題友好說的是找到k。對於雜湊函式 H(x),我們做出如下總結:
- 對於 y = H(x),知道 x 計算其雜湊值 y 很簡單;
- 碰撞阻力:很難找出不同的x,y,使得 H(x) = H(y);
- 隱祕性/謎題友好(近似理解):對於 y = H(x),知道雜湊值 y ,很難反求出x。
03
雜湊函式的意義所在
雜湊函式與工作量證明
先回憶一下區塊結構。比特幣的區塊由區塊頭及該區塊所包含的交易列表組成,區塊頭的大小為80位元組,由4位元組的版本號、32位元組的上一個區塊的雜湊值、32位元組的 Merkle Root Hash、4位元組的時間綴(當前時間)、4位元組的當前難度值、4位元組的隨機陣列成。區塊包含的交易列表則附加在區塊頭後面,其中的第一筆交易是 coinbase 交易,這是一筆為了讓礦工獲得獎勵及手續費的特殊交易。
區塊的大致結構如圖所示:
其中:
- Version 是當前區塊的版本號
- 該區塊所包含的多個交易的 Hash 值構成區塊的 Merkel 資料結構
- nbits 是當前比特幣協議設定的計算複雜度
- ntime 是區塊的時間戳
- pre_hash 是前一個區塊的 Hash 值
Hash(L,x) = SHA256(SHA256(block_header))
block_header = version + Merkel + nbits + ntime + pre_hash
擁有80位元組固定長度的區塊頭,就是用於比特幣工作量證明的輸入字串。不停的變更區塊頭中的隨機數即 nonce 的數值,並對每次變更後的的區塊頭做雙重 SHA256運算(即 SHA256(SHA256(Block_Header))),將結果值與當前網路的目標值做對比,如果小於目標值,則解題成功,工作量證明完成。
小結:可以簡單理解成,比特幣工作量證明的過程,就是通過不停地變換區塊頭(即嘗試不同的隨機值)作為輸入進行 SHA256雜湊運算,找出一個特定格式雜湊值的過程,即要求有一定數量的前導0,而要求的前導0的個數越多,代表難度越大。
雜湊函式與防篡改性
當 x 只變化一個位元組,y 是不是也會只變化一個位元組,這種微小的差異是否能篡改事實?
不能!
如果輸入 x 有1bit 的變化,雜湊結果即雜湊值中將有一半以上的 bit 改變,這又叫做“雪崩效應(avalanche effect)”。
區塊鏈之所以稱為鏈,是因為每一個區塊都儲存了前一區塊的目標 Hash值(創世塊沒有前一 Hash 值)。某一個區塊的某一筆交易發生篡改,因為默克爾樹演算法的作用這個區塊的目標 Hash 值就會被改變,並導致連鎖反應。以這個區塊為基礎,後續所有區塊的 Hash 值都會發生變化,任一記賬節點都可以輕易的發現賬本被篡改,這樣就保證了區塊鏈上的所有區塊都具備了防篡改功能。
雜湊函式的抗碰撞性用來做區塊和交易的完整性驗證,一有篡改就能被識別出來。
最後我們對本文進行歸納總結:
1、雜湊函式輸入任意長度的資訊 x ,輸出的雜湊值 H(x)的 長度都是固定的 256bit;
2、雜湊函式具有碰撞阻力、隱祕性、謎題友好三重重要特性,具體來說:
- 對於 y=H(x),知道 x 計算其雜湊值 y 很簡單;
- 碰撞阻力:很難找出不同的 x,y,使得 H(x) = H(y);
- 隱祕性/謎題友好(近似理解):對於 y = H(x),知道雜湊值 y,很難反求出 x;
3、對每次變更後的的區塊頭做雙重 SHA256 運算(即SHA256(SHA256(Block_Header))),結果值小於目標值(有足夠多的前導0),工作量證明完成;
4、雜湊函式下的防篡改性意味著,輸入 x 哪怕 1bit 的變化都將改變一切,所以不可篡改。
今天的幣信小課堂就先到這裡,江湖路遠,下期再見。
- END-