1.1 密碼學哈希函數(shù)

我們需要理解的第一個密碼學的基礎知識是密碼學哈希函數(shù)，哈希函數(shù)是一個數(shù)學函數(shù)，具有以下三個特性：

● 其輸入可為任意大小的字符串。

● 它產(chǎn)生固定大小的輸出。為使本章討論更具體，我們假設輸出值大小為256位，但是，我們的討論適用于任意規(guī)模的輸出，只要其足夠大。

● 它能進行有效計算，簡單來說就是對于特定的輸入字符串，在合理時間內，我們可以算出哈希函數(shù)的輸出。更準確地說，對應n位的字符串，其哈希值計算的復雜度為O（n）。

這些特性定義了一般哈希函數(shù)，以這個函數(shù)為基礎，我們可以創(chuàng)建數(shù)據(jù)結構，例如哈希表。我們將只專注于加密的哈希函數(shù)，要使哈希函數(shù)達到密碼安全，我們要求其具有以下三個附加特性：（1）碰撞阻力（collision-resistance）；（2）隱秘性（hiding）；（3）謎題友好（puzzle-friendliness）。

我們會仔細研究這些特性，并會逐步闡釋我們?yōu)槭裁葱枰@樣的函數(shù)。學習過密碼學的讀者可能會注意到，我們這里對于哈希函數(shù)的論述與一般的密碼學課程會有所不同，特別是關于謎題友好。在一般密碼學中，謎題友好并非加密的哈希函數(shù)的一般要求，卻對加密數(shù)字貨幣這一特性非常有用。

特性1：碰撞阻力

加密的哈希函數(shù)的第一個特性是它要具有碰撞阻力。這里的碰撞指對于兩個不同的輸入，產(chǎn)生相同的輸出。如果對于哈希函數(shù)H(·)，沒有人能夠找到碰撞，我們則稱該函數(shù)具有碰撞阻力（見圖1.1）。即：

注意，我們說沒人能找到碰撞，并不表示不存在碰撞。事實上，通過簡單的計數(shù)論證（counting argument），我們可以證明碰撞的確存在。哈希函數(shù)的輸入空間包含所有長度的任意字符串，但輸出空間則只包含特定固定長度的字符串。因為輸入空間比輸出空間大（輸入空間是無限的，而輸出空間是有限的），一定會有輸入字符串映射到相同的輸出字符串。實際上，根據(jù)鴿巢原理（Pigeonhole Principle），我們可以得出，必然會有大量可能的輸入被映射到任意特定輸出（見圖1.2）。

而更糟糕的是，對于加密的哈希函數(shù)，我們雖然說應該找不到碰撞，但有些方法是能保證找到碰撞的。考慮以下對應于一個256位輸出大小的哈希函數(shù)，選擇2256+1個不同數(shù)值，計算每個數(shù)的哈希值，并檢查是否有兩個相等的輸出。因為我們這里選擇的輸入多于輸出，因此在應用哈希函數(shù)時，一些數(shù)對必將產(chǎn)生碰撞。

使用上述方法一定能找到碰撞。但如果我們隨機性地選擇輸入，并計算哈希值，我們在檢驗第2256+1個輸入之前便很可能找到碰撞。實際上，如果我們隨機選擇2130+1個輸入值，找到至少兩個等同哈希值的概率為99.8%。僅僅通過檢驗可能輸出數(shù)量的平方根次數(shù)，便大體能找到碰撞，這一事實在概率學中被稱為是生日悖論（birthday paradox）。

這個碰撞檢測算法對每個哈希函數(shù)都有效，但是它的問題是其計算需要花很長很長時間才能完成。對于一個256位輸出的哈希函數(shù)來說，最壞的情況是你需要進行2256+1次哈希函數(shù)計算，平均次數(shù)為2128次，這簡直是一個天文數(shù)字——如果一臺電腦每秒計算10 000個哈希值，計算2128個哈希值，需要花1027多年時間！換個角度，我們可以說，如果人類制造的每臺電腦在整個宇宙起源時便開始計算，到目前為止，它們找到碰撞的概率仍然無窮小，比下兩秒鐘地球將被大隕石摧毀的概率還要小得多。

因此，為了尋找一個任意的哈希函數(shù)的碰撞，我們只是有了一個一般，但并不實用的算法。一個更艱澀的問題是：有沒有其他的方法，可以用于對于某一特定哈希函數(shù)找到碰撞？也就是說，雖然一般的碰撞測試算法不適用，但仍可能有其他的算法，可以有效地找到某個哈希函數(shù)的碰撞。

以下面的哈希函數(shù)為例：

H(x)=x mod 2256

這個函數(shù)接受任何長度的輸入，產(chǎn)生一個固定大小輸出（256位），且能進行有效計算，因此符合我們對哈希函數(shù)的要求。但是對于這個函數(shù)，我們確實具備一個有效的能夠尋找碰撞的方法。注意，這個函數(shù)僅返回輸入的最后256位，因此，數(shù)值3和3+2256就構成了碰撞。這個簡單的例子表明，雖然我們的一般碰撞測試方法在實踐中不可行，但至少對于某些哈希函數(shù)，存在有效的測試碰撞的方法。

但對于某些哈希函數(shù)，我們無法確認識別碰撞的有效方法是否存在，我們只是懷疑這些函數(shù)具有防碰撞特性，但是我們已經(jīng)證明，世界上沒有哈希函數(shù)具有防碰撞特性。我們實踐中依賴的加密的哈希函數(shù)僅僅是人們經(jīng)過不懈努力之后暫未成功找到碰撞的函數(shù)。因此，我們選擇相信那些加密的哈希函數(shù)具有哈希阻力（在某些情況下，如之前的MD5哈希函數(shù)，在多年的努力之后最終找到了碰撞，導致該函數(shù)在實踐中被逐漸淘汰，最終被棄用）。

應用：信息摘要

現(xiàn)在我們知道什么是碰撞阻力了，我們自然會問：碰撞阻力有什么用途？以下就是一個應用：哈希函數(shù)H具有碰撞阻力，x和y是兩個不同的輸入，那么可以假設它們的哈希函數(shù)H(x)和H(y)也不同——如果已知x和y不同，但哈希值相同，那么H具有碰撞阻力的假設就不成立了。

這個論證使我們可以將哈希輸出作為信息摘要（message digest）。以SecureBox為例，SecureBox是一個允許用戶上傳文件，并保證文件被完整下載的線上文件存儲系統(tǒng)。假設愛麗絲上傳了很大的文件，并希望能夠在之后下載時確認她下載的文件與她上傳的文件相同。一種方法是將整個文件進行本地存儲，并直接將其與下載文件對比。如果這樣可行，那么將文件上傳便顯得毫無意義，倘若愛麗絲需要使用本地文件副本以保證其完整性，她可以直接使用本地副本。

無碰撞哈希函數(shù)為這個問題提供了簡單有效的解決方法，愛麗絲只需要記住原文件的哈希值，從SecureBox下載文件后，她可以計算下載文件的哈希值，并與原文件哈希值進行對比。如果哈希值相同，那么愛麗絲可以說該文件就是她上傳的那一個，但是如果不同，她則可以確定文件被破壞了。記錄哈希值可以幫助愛麗絲檢測文件在傳輸過程中，或在SecureBox服務器上是否產(chǎn)生了意外損壞，或者檢測文件是否受到服務器的蓄意修改。保證主體不受其他實體的惡意行為侵害，這正是密碼學的核心。

這里的哈希函數(shù)對于一個信息生成固定長度的摘要，或生成了簡明總結，這為我們提供了一種記住之前所見事物，并在今后認出這些事物的有效方法。雖然整個文件可能非常大，存儲規(guī)模達數(shù)G，但其哈希值的長度固定。例如，哈希函數(shù)為256位。這樣做，極大地降低了存儲要求。在本章后面及整本書中，我們都會看到哈希作為信息摘要的應用。

特性2：隱秘性

我們希望哈希函數(shù)擁有的第二個特性是其隱秘性。隱秘性保證，如果我們僅僅知道哈希函數(shù)的輸出y=H(x)，我們沒有可行的辦法算出輸入值x。問題是，上述的表示形式不一定是正確的?？紤]以下簡單的例子：我們做一個拋硬幣的實驗，如果拋硬幣結果為正面，我們會宣布字符串哈希為“正面”；如果結果為反面，我們會宣布字符串哈希為“反面”。

然后我們問我們的對手，在他沒有見到拋硬幣，而只見到哈希函數(shù)的輸出的前提下說出哈希函數(shù)的輸入字符串（很快我們就知道為什么要玩這個游戲了）。為了回答問題，對手會簡單計算“正面”字符串的哈希值及“反面”字符串的哈希值，然后對手便可以知道他得到的是哪一個。這樣，只需要幾步，對手就能反解出輸入值。

對手能夠猜出字符串，這是因為x只有兩個可能，他可以很輕易地將兩個可能對應的哈希值計算出來。為了能夠實現(xiàn)隱秘性，我們需要x的取值來自一個非常廣泛的集合，也就是說，僅僅通過嘗試幾個特定的x，就能找到輸出值的方式將不會發(fā)生了。

現(xiàn)在的問題是：在類似拋硬幣的“正面”、“反面”實驗中，如果我們想要的反解的輸入值并非來自分散的集合，我們是否還能得到隱秘性？幸運的是，對于這個問題答案是肯定的！我們甚至能夠通過與另一個較為分散的輸入進行結合，而將一個并不分散的輸入進行隱秘?，F(xiàn)在我們可以更精確地表示隱秘的含義了（雙豎線‖為連接符號，代表把一系列事件、事情等聯(lián)系起來）。

在信息論中，最小熵是用于測試結果可預測性的手段，而高階最小熵這個概念比較直觀描述了分布（如隨機變量）的分散程度。具體來說，在從這樣分布中取樣時，我們將無法判定取樣的傾向。舉個具體的例子，如果r是從長度為256位的字符串中隨意選出的，那么任意特定字符串被選中的概率為1/2256，這是一個小到幾乎可以忽略的取值。

應用：承諾

現(xiàn)在來看一下隱秘性的應用。具體來說，我們把想做的事情稱為承諾（commitment）。這里承諾是一個數(shù)字化過程，可以類比為以下動作：首先選定一個數(shù)字，將數(shù)字裝進信封，然后將該信封放到一個人人都看得到的桌子上。這樣做以后，可以說你就信封里的數(shù)字做出了承諾，在打開信封前，雖然你已經(jīng)做出了承諾，對其他人來說它還是秘密。在之后，你可以打開信封，來展示承諾的數(shù)值。

為了使用承諾方案，我們首先需要產(chǎn)生一個臨時隨機數(shù)。然后將這個臨時隨機數(shù)與承諾信息msg一起代入承諾函數(shù)，計算承諾函數(shù)輸出值com，然后公布該輸出。這個過程就如同將封好的信封放到一個人人能看到的桌上那樣。之后，如果我們希望展示之前的承諾值，我們首先公布用于產(chǎn)生承諾的臨時隨機數(shù)，并公布信息msg。此時任何人都可以驗證這時公布的msg是否為之前承諾，這個階段就如同打開信封。

以上兩個安全特性決定了這一算法就如同密封及打開信封。第一，如果僅僅知道com，即承諾函數(shù)的輸出，就如同只看信封并不能得到信息內容；第二就是約束性，這就保證了你一旦承諾信封內的內容，就不能再改變主意。也就是說，我們無法找到兩個不同的信息，當你在承諾一個信息后，而又聲稱你承諾了另一個信息。

我們如何在承諾協(xié)議中保證隱秘性和約束性這兩個性質成立呢？在討論這一點之前，我們需要討論如何執(zhí)行承諾方案。我們可以通過使用加密的哈希函數(shù)來達到目的，考慮如下承諾協(xié)議實施方案：

commit(msg, nonce):=H(nonce‖msg)

其中，nonce為長度為256位的臨時隨機數(shù)。

為承諾一段消息，我們首先生成一個256位的臨時隨機數(shù)，然后將這個臨時隨機數(shù)與信息鏈接，并返回這個鏈接值的哈希值，來作為承諾輸出。為了便于驗證，我們還要設定其他人來計算一下臨時隨機數(shù)與信息鏈接之后的哈希值，比對一下計算結果是否與承諾輸出相同。

再來看一下我們的承諾方案要求的兩個特性，如果我們將承諾和驗證換成H(nonce‖msg)，那么這些特性就變成：

● 隱秘性：已知H(nonce‖msg)，沒有可行方法找到msg。

● 約束性：沒有可行方法找到兩對(msg, nonce)和(msg’, nonce’)，msg≠msg’，而H(nonce‖msg)==H(nonce’‖msg’)。

承諾的隱秘特性正是我們要求哈希函數(shù)要具備的隱秘性，如果將一個解密鑰匙選定為256位的隨機值，那么由隱秘性得出，如果解密鑰匙與信息鏈接，那么僅僅從哈希函數(shù)的輸出中恢復信息就是不可行的。約束性隱含在哈希函數(shù)的碰撞阻力特性中，如果哈希函數(shù)具有碰撞阻力，那么我們將不能找到不同的msg及msg'值，而H(nonce‖msg)=H(nonce'‖msg')，如果這種情況發(fā)生，將構成碰撞。

因此，如果哈希函數(shù)H具有碰撞阻力及隱秘性，從安全特性上來講，這個承諾方案將有效。

特性3：謎題友好

哈希函數(shù)需要的第三個安全特性為謎題友好特性。這一特性較為復雜，我們首先解釋該特性的技術要求，然后通過舉例來闡釋該特性的意義。

直覺上，謎題友好可以這樣解釋，如果有一個人想找到y(tǒng)值所對應的輸入，假定在輸入集合中，有一部分是非常隨機的，那么他將非常難以求得y值對應的輸入。

應用：搜索謎題

現(xiàn)在，讓我們試想一個應用以闡釋謎題友好特性的意義。在這個應用中，我們將建立一個搜索謎題，該謎題是一個需要對龐大空間進行搜索，才能找到解決辦法的數(shù)學問題。該搜索謎題沒有捷徑，也就是說除了搜索龐大的空間來進行求解，別無他法。

H(id‖x)∈Y

這個直覺是：如果H有一個n位輸出，那么它的可能取值有2n個。解決這個謎題要求找到一個位于集合Y（通常比所有輸出值集合小很多）內的輸出值，Y的大小決定了謎題的難度。如果Y是所有n位字符串的集合，這個謎題就毫無意義。然而，如果Y只有一個元素，那么這個謎題難度最大，謎題ID取自高階最小熵分布，這個事實保證了求解無捷徑。反過來，如果該ID的確定性很高，那么有人可能會作弊，比如通過使用該ID，事先對謎題進行求解。

如果一個哈希函數(shù)具備謎題友好特性，這就意味著對于這個謎題沒有一個解決策略，比只是隨機地嘗試x取值會更好。因此，如果我們要把謎題做成很難解決是可以的，只要我們能用適合的隨機方式生成謎題ID。當我們討論比特幣采礦（是一種搜索謎題）時會采用這一思路。

安全哈希算法

我們討論了哈希函數(shù)的三個特性及其相應的應用?，F(xiàn)在，讓我們討論本書中將會大量用到的一個哈希函數(shù)，安全哈希算法（Secure Hash Algorithm 256，簡稱SHA-256）。哈希函數(shù)有很多，但SHA-256是一個主要被比特幣世界采用，并且效果還很不錯的哈希函數(shù)。

回想一下，我們要求哈希函數(shù)可以用于任意長度輸入。幸運的是，只要我們能建立一個用于固定長度輸入的哈希函數(shù)，然后通過一般方法，就可以將接受固定長度的哈希函數(shù)轉化為可接受任意長度輸入的哈希函數(shù)，我們稱這個轉換過程為MD（Merkle-Damgard）變換，SHA-256是采用這種變換方法的常用哈希函數(shù)之一。在通用術語中，這種基礎型，可用于固定長度，具備碰撞阻力的哈希函數(shù)被稱為是壓縮函數(shù)（compression function）。經(jīng)過驗證，如果基本壓縮函數(shù)具有碰撞阻力的特性，那么經(jīng)過轉換而生成的哈希函數(shù)也具有碰撞阻力。

MD變換很簡單。比如壓縮函數(shù)代入長度為m的輸入值，并產(chǎn)生長度短一些為n的輸出值。哈希函數(shù)的輸入（可為任意大小）被分為長度為m-n的區(qū)塊。MD變換運作過程如下：將每個區(qū)塊與之前區(qū)塊的輸出一起代入壓縮函數(shù)，注意，輸入長度則變?yōu)?m-n)+n=m，也剛好就是壓縮函數(shù)的輸入長度。對于第一個區(qū)塊而言，之前沒有的區(qū)塊，我們需要選取一個初始向量（見圖1.3）。每次調用哈希函數(shù)，這個數(shù)字都會被再一次使用，而在實踐中，你可以直接在標準文檔中找到它。最后一個區(qū)塊的輸出也就是你返回的結果。

SHA-256函數(shù)利用了這樣的一個壓縮函數(shù)，這個壓縮函數(shù)把一個768位的輸入壓縮成一個256位的輸出，每一個區(qū)塊的大小是512位。我們可以通過圖1.3來理解SHA-256的工作過程。

截至目前，我們已經(jīng)討論了哈希函數(shù)、密碼學上使用具備特性的哈希函數(shù)、這些特性的應用，以及在比特幣世界中使用的一類特殊的哈希函數(shù)。在下面的章節(jié)中，我們將討論通過哈希函數(shù)來構建比特幣網(wǎng)絡中的更為復雜的數(shù)據(jù)結構。