所有貨幣都需要一些方法來控制供應(yīng)，并強(qiáng)制執(zhí)行各種安全屬性以防止作弊。在法定貨幣方面，像中央銀行這樣的組織控制貨幣供應(yīng)量，并對實(shí)體貨幣增加防偽功能。這些安全功能提高了對攻擊者的防范能力，但是他們不可能不賺錢地進(jìn)行偽造。最終，執(zhí)法對于阻止人們違反制度規(guī)則是必要的。

加密數(shù)字貨幣也必須采取安全措施，防止人們篡改系統(tǒng)狀態(tài)，并避免對不同的人造成不一致的陳述。如果Alice說服Bob，她給他一個數(shù)字貨幣，例如，她不應(yīng)該說服卡羅爾，向卡羅爾支付同一個數(shù)字貨幣。與法定貨幣不同的是，加密貨幣的安全規(guī)則需要純粹在技術(shù)上執(zhí)行，而不依賴于中央機(jī)構(gòu)。

顧名思義，加密貨幣大量使用加密技術(shù)。在加密數(shù)字貨幣系統(tǒng)本身的機(jī)制上，密碼學(xué)提供了一個安全的編碼規(guī)則體系。我們可以用它來防止篡改和避免模棱兩可的陳述，以及將數(shù)字協(xié)議用于創(chuàng)建編碼新貨幣單位的規(guī)則。在我們可以正確理解加密貨幣之前，我們需要深入研究密碼學(xué)賴以依賴的基礎(chǔ)。

密碼學(xué)是一個深入的學(xué)術(shù)研究領(lǐng)域，它利用許多先進(jìn)的數(shù)學(xué)技術(shù)，以巧妙而微妙的方式理解。幸運(yùn)的是，比特幣只依賴于一些相對簡單和知名的加密結(jié)構(gòu)。在本章中，我們將專門研究加密散列和數(shù)字簽名，證明對構(gòu)建加密貨幣非常有用的兩個原語。未來章節(jié)將介紹更復(fù)雜的加密方案，例如零知識證明，用于比特幣擴(kuò)展和修改的提議。

一旦我們學(xué)習(xí)了必要的加密原語，我們將討論一些用來構(gòu)建加密貨幣的方式。我們將在本章中介紹一些簡單的加密貨幣示例，演示我們需要處理的一些設(shè)計挑戰(zhàn)。

1.1加密Hash函數(shù)

我們需要理解的第一個加密原語是加密散列函數(shù)（Hash function）。一個加密散列函數(shù)（Hash function）具有以下三個屬性：

·它的輸入可以是任意大小的字符串。

·它產(chǎn)生一個固定大小的輸出。為了使本章中的討論具體化，我們將假設(shè)它是一個256位大小的輸出。然而，我們的討論適用于任何輸出大小，只要它足夠大。

·這意味著對于給定的輸入字符串，可以在合理的時間內(nèi)計算哈希函數(shù)的輸出。從技術(shù)上講，計算一個n位字符串的散列應(yīng)該有一個O（n）的運(yùn)行時間。

這些屬性定義了一個通用哈希函數(shù)，一個可用于構(gòu)建數(shù)據(jù)結(jié)構(gòu)（如哈希表）的函數(shù)。我們將專注于加密散列函數(shù)（Hash functions）。對于密碼安全的哈希函數(shù)，我們將要求它具有以下三個附加屬性：（1）防撞；（2）隱匿；（3）友好的謎題。

我們將更仔細(xì)地研究每一個屬性，以了解為什么有這樣一個函數(shù)的行為是有用的。研究密碼學(xué)的讀者應(yīng)該意識到，本書中哈希函數(shù)的處理與標(biāo)準(zhǔn)加密教科書有點(diǎn)不同。特別是謎題友好的屬性不是對加密哈希函數(shù)的一般要求，而是對特定加密貨幣的有用屬性。

防碰撞性：如果不可能找到兩個值x和y，使得x ≠ y，而H（x）= H（y），哈希函數(shù)H被認(rèn)為是防碰撞的。

屬性1：防碰撞性。我們從加密哈希函數(shù)中需要的第一個屬性就是它的防碰撞。當(dāng)兩個不同的輸入產(chǎn)生相同的輸出時，會發(fā)生碰撞。如果沒有人可以發(fā)現(xiàn)碰撞，哈希函數(shù)H（.）則具有防碰撞性。正式地：

圖1.1哈希碰撞。x和y是不同的值，但是當(dāng)輸入到哈希函數(shù)H中時，它們產(chǎn)生相同的輸出。

請注意，我們說沒有人可以找到碰撞，但是我們沒有說沒有碰撞存在。實(shí)際上，我們確實(shí)知道碰撞存在的事實(shí)，我們可以通過一個簡單的計數(shù)參數(shù)來證明這一點(diǎn)。哈希函數(shù)的輸入空間包含所有長度的所有字符串，但輸出空間只包含特定且固定長度的字符串。因?yàn)檩斎肟臻g大于輸出空間（實(shí)際上，輸入空間是無窮大的，而輸出空間是有限的），所以必須有輸入字符串映射到相同的輸出字符串。事實(shí)上，根據(jù)“鴿子原則”，映射到任何特定輸出的可能輸入必然將是非常大的。

圖1.2由于輸入數(shù)量超過輸出數(shù)量，我們保證必須至少有一個輸出，能讓哈希函數(shù)映射到多個輸入。

現(xiàn)在，為了使事情變得更糟，我們說它不可能發(fā)現(xiàn)碰撞。然而，有些方法可以保證發(fā)現(xiàn)碰撞。考慮以下簡單的方法來查找具有256位輸出大小的哈希函數(shù)的碰撞：挑選2的256次方加1個不同的值，計算它們中每一個的hash值，并檢查是否有兩個一樣的輸出。由于我們選擇了比可能輸出更多的輸入，所以當(dāng)應(yīng)用哈希函數(shù)時，它們中的一些必須發(fā)生碰撞。

上面的方法保證會找到碰撞。但是，如果我們選擇隨機(jī)輸入并計算哈希值，那么在檢查2的256次方加1個輸入之前，我們會高概率的發(fā)現(xiàn)碰撞。事實(shí)上，如果我們隨機(jī)選擇2的130次方加1個輸入，結(jié)果會有99.8％的概率至少有兩個會碰撞。事實(shí)上，我們可以通過只是粗略地檢查可能的輸出數(shù)量的平方根來找到?jīng)_突，這現(xiàn)象在概率上被稱為第二天悖論。在本章末尾家庭作業(yè)的問題中，我們將對此進(jìn)行更詳細(xì)的研究。

這種碰撞檢測算法適用于每個哈希函數(shù)。但是，問題在于這需要很長很長的時間。對于具有256位輸出的哈希函數(shù)，在最壞的情況下，您必須計算哈希函數(shù)2的256次方加1次，平均大約2的128次方次。這當(dāng)然是一個天文數(shù)字 ——如果一臺計算機(jī)每秒計算10,000次hash值，那么需要超過一千萬（10的27次方）年的時間來計算2的128次方個hash值！以另一方式來思考這個問題，我們可以這樣說，如果人類制造的每一臺計算機(jī)從宇宙誕生以來都開始計算，到目前為止，他們發(fā)現(xiàn)沖突的幾率仍然是非常渺小的。如此之小，比地球在接下來的兩秒鐘內(nèi)被一顆巨大的流星摧毀的幾率都要小得多。

因此，我們看到了一種通用但不切實(shí)際的算法來找尋任意哈希函數(shù)的碰撞。一個更難的問題是：是否有其他方法可以在特定的哈希函數(shù)上使用，以便找到碰撞？換句話說，雖然通用碰撞檢測算法是不可行的，但仍然可能有其他一些可以有效地找到特定哈希函數(shù)碰撞的算法。

例如，考慮以下哈希函數(shù)：

該函數(shù)滿足我們對散列函數(shù)的要求，因?yàn)樗邮苋魏伍L度的輸入，返回一個固定大小的輸出（256位），并且是有效可計算的。這個函數(shù)還有一個找到碰撞的有效方法。請注意，此函數(shù)只返回輸入的最后256位。一個碰撞的值會是3和3加2的256次方。這個簡單的例子說明，盡管我們的通用碰撞檢測方法在實(shí)踐中是不可用的，但至少存在一些確實(shí)有效的碰撞檢測方法的哈希函數(shù)。

然而對于其他哈希函數(shù)，我們不知道是否存在這樣的方法。我們懷疑他們是抗碰撞的。但是，沒有任何哈希函數(shù)被證明是抗碰撞的。我們在實(shí)踐中依賴的加密哈希函數(shù)只是人們嘗試的功能，真的很難找到碰撞，且從未成功過。在某些情況下，如舊的MD5哈希函數(shù)，最終在多年的工作中發(fā)現(xiàn)了沖突，導(dǎo)致功能過時，被實(shí)用界逐步拋棄。所以我們選擇相信那些是抗碰撞的。

應(yīng)用：消息摘要現(xiàn)在我們知道抗碰撞是什么，合乎邏輯的問題是：抗碰撞有什么用？這里有一個應(yīng)用：這里有一個應(yīng)用：如果我們知道抗碰撞哈希函數(shù)H的兩個輸入x和y是不同的，那么可以安全地假定它們的hash值H（x）和H（y）是不同的，如果有人知道一個x和y是不同的，但是具有相同的hash值，這將違反我們的假設(shè)，這樣的H是抗碰撞的。

這個論據(jù)允許我們使用hash輸出作為消息摘要?？紤]SecureBox，一個經(jīng)過身份驗(yàn)證的在線文件存儲系統(tǒng)，允許用戶在下載文件時上傳文件并確保其完整性。假設(shè)Alice上傳的文件很大，想要稍后能驗(yàn)證她下載的文件與上傳的文件是一樣的。一種方法是在將整個大文件保存在本地，并直接將其與下載的文件進(jìn)行比較。雖然這樣做有效，但它在很大程度上違背了上傳它的目的；如果Alice需要訪問文件的本地副本以確保其完整性，則可以直接使用本地副本。

無碰撞的哈希為這個問題提供了一個優(yōu)雅而高效的解決方案。Alice只需要記住原始文件的hash值。當(dāng)她以后從SecureBox下載文件時，她會計算下載的文件的hash值并將其與存儲的文件進(jìn)行比較。如果哈希值是相同的，那么她可以得出結(jié)論，文件確實(shí)是她上傳的，如果它們不同，那么Alice可以斷定該文件已被篡改。因此，記住哈?？梢宰屗趥鬏斶^程中或在SecureBox的服務(wù)器上檢測文件的意外損壞，而且還可以由服務(wù)器義務(wù)修改文件。面對其他實(shí)體潛在的惡意行為，這是加密技術(shù)為我們提供保證的核心。

Hash用作消息的固定長度摘要或明確的摘要。這給了我們以一個非常有效的方式來記住我們以前看到的事情，并再次認(rèn)出它們。而整個文件可能已經(jīng)是千兆字節(jié)長，hash卻是固定的長度，在我們的例子中hash函數(shù)有256位字節(jié)。這大大降低了我們的存儲需求。在本章后面和整本書中，我們將看到使用哈希作為消息摘要的有用應(yīng)用程序。

屬性2：隱匿性從哈希函數(shù)中得到想要的第二個屬性是隱匿。隱匿屬性聲明如果我們給出hash函數(shù)y= H（x）的輸出，則沒有可行的方法來確定輸入x是什么。問題是，該屬性不能以聲明的形式存在?？紤]以下簡單的例子：我們要做一個擲硬幣的實(shí)驗(yàn)。如果硬幣翻轉(zhuǎn)的結(jié)果是頭，我們要宣布字符串的哈希值是“頭”。如果結(jié)果是尾，那么我們要宣布字符串的哈希值是“尾”。

然后我們問一個沒有看到硬幣翻轉(zhuǎn)，只看到哈希輸出值的對手，讓他弄清楚字符串是散列的（我們很快就會知道為什么我們可能想玩這樣的游戲）。作為回應(yīng)，他們將簡單地計算字符串“頭”和字符串“尾”的哈希值，并且他們可以看到他們被給予了哪一個。所以，在短短幾步之后，他們可以弄清楚輸入的是什么。

對手能夠猜出這個字符串是因?yàn)閤只有兩個可能的值，對手很容易嘗試這兩個值。為了能夠?qū)崿F(xiàn)隱匿屬性，需要注意的是沒有特別可能的x值，也就是說x必須在某種意義上從分散的集合中選擇。如果從這樣一個集合中選擇x，那么嘗試x值可能有幾個值的方法將不起作用。

最大的問題是：當(dāng)我們想要的值不像我們的“頭”和“尾”的實(shí)驗(yàn)?zāi)菢?，我們可以?shí)現(xiàn)隱匿的屬性嗎？幸運(yùn)的是，答案是肯定的！所以我們或許可以隱藏，甚至一個輸入可以不通過將其連接到另一個相關(guān)聯(lián)的輸入來傳播。我們現(xiàn)在可以稍微更精確地說明我們隱匿的意思（雙垂直條‖表示連接）。

隱匿?hash函數(shù)H是隱匿的，如果：從具有高的最小熵的概率分布中選擇秘密值r，當(dāng)給定H（r||x）時，找到x是不可行的。

在信息理論中，最小熵是衡量結(jié)果可預(yù)測性的一個指標(biāo)，高最小熵捕捉到分布（即隨機(jī)變量）是非常分散的直觀思想。這具體意味著，當(dāng)我們從分布中抽樣時，沒有特定的值可能發(fā)生。所以，對于一個具體的例子，如果從256位長的所有字符串中均勻地選擇了r，然后選擇任何特定的字符串的概率為1／2的256次方，這是一個無窮小的值。

應(yīng)用：托管現(xiàn)在讓我們來看一下隱匿屬性的應(yīng)用。特別是我們想要做的就是所謂的托管。托管的是帶有值的數(shù)字模擬，把它密封在一個信封里，然后把信封放在桌子上，每個人都可以看到它。當(dāng)你這樣做時，你已經(jīng)托管了信封里面的內(nèi)容。但是你沒有打開它，所以即使你托管了一個值，這個值對于其他人仍然是秘密。稍后，你可以打開信封并顯示你先前提交的值。

托管方案托管方案由兩種算法組成：

com:=托管（msg，nonce）托管函數(shù)輸入消息和秘密的隨機(jī)值nonce，返回一個托管值

校驗(yàn)（com，msg，nonce）驗(yàn)證函數(shù)將托管值、隨機(jī)數(shù)nonce和消息作為輸入。如果com==commit（msg，nonce）則返回True，否則返回False。

我們要求以下兩個安全屬性保持不變：

隱匿：給定com，找到msg是不可能的。

綁定：不可能找到兩對（msg，nonce）和（msg’，nonce’），這樣msg≠msg’但commit（msg,nonce）==commit（msg’,nonce’）

要使用托管方案，我們首先需要生成隨機(jī)數(shù)n。然后，我們將commit函數(shù)與msg一起應(yīng)用到該隨機(jī)數(shù)n，該值被托管，并發(fā)布托管值com。這個階段類似于將密封的信封放在桌子上。稍后，如果我們想要揭示他們之前提交的值，我們會發(fā)布我們用來創(chuàng)建這個托管的隨機(jī)數(shù)n，以及消息msg?，F(xiàn)在，任何人都可以驗(yàn)證msg確實(shí)是早期托管的消息。這個階段類似于打開信封。

每次你托管一個值，重要的是您選擇一個新的隨機(jī)數(shù)n。 在密碼學(xué)中，術(shù)語“隨機(jī)數(shù)”用于指代只能使用一次的值。

這兩個安全屬性規(guī)定，算法實(shí)際上表現(xiàn)為密封和打開信封。首先，給定com和托管，只看信封的人無法弄清楚里面的信息是什么。第二個屬性是它的綁定。這樣可以確保當(dāng)你托管信封中的內(nèi)容時，你將不能再改變主意。也就是說，找到兩條不同的消息是不可行的，你不可以提交一個消息，然后再聲明你已經(jīng)提交另一個消息。

那么，我們怎么知道這兩個屬性呢？在我們回答之前，我們需要討論如何實(shí)際實(shí)施一個托管方案。我們可以使用加密哈希函數(shù)來做到這一點(diǎn)?？紤]以下托管方案：

commit(msg, nonce) := H(nonce ‖msg) n是一個256字節(jié)的隨機(jī)數(shù)

為了提交一個消息，我們生成一個256位的隨機(jī)數(shù)n。然后我們連接隨機(jī)數(shù)n和消息，并返回這個連接值的哈希作為托管。要驗(yàn)證，有人要去計算與消息連接的隨機(jī)數(shù)的相同哈希值。他們會檢查這是否等于他們看到的托管。

再看一下我們承諾計劃中需要的兩個屬性。如果我們替換實(shí)例化的托管，然后驗(yàn)證H（nonce||msg）是com，那么這些屬性將變?yōu)椋?/p>

隱匿：給定H（nonce||msg），不可能找到msg

綁定：不可能找到兩對（msg，nonce）和（msg’，nonce’），這樣msg≠msg’但H（msg,nonce）==H（msg’,nonce’）

托管的隱匿屬性正是我們對哈希函數(shù)所需的隱匿屬性。如果密鑰被選擇為256位的隨機(jī)值，則隱匿屬性表示，如果我們對密鑰和消息一起進(jìn)行哈希，那么從哈希的結(jié)果去恢復(fù)消息是不可能的。事實(shí)證明，綁定屬性隱含了底層哈希函數(shù)的抗碰撞特性。如果哈希函數(shù)是抗碰撞的，那么是不可能找到不同的msg和msg'的，使得H（nonce‖msg）= H（nonce’||“msg”），因?yàn)檫@些值確實(shí)是一個碰撞。

因此，如果H是具有防碰撞和隱匿的哈希函數(shù)，則該托管方案將在其具有必要的安全屬性的意義上起作用。

屬性3：謎題友好性我們從哈希函數(shù)中需要的第三個安全屬性是謎題友好。這個屬性有點(diǎn)復(fù)雜。首先，我們將解釋這個屬性的技術(shù)要求，然后給出一個應(yīng)用程序，說明為什么這個屬性是有用的。

謎題友好?一個哈希函數(shù)H被稱為謎題友好——對于每個可能的n位輸出值y，如果從具有高最小熵的分布中選擇k，則不可能找到x使得H（k||x）=y最后明顯小于2的n次方。

直觀地說，這意味著如果有人想要將哈希函數(shù)定位到一些特定的輸出值y，那么如果有一部分輸入以適當(dāng)?shù)碾S機(jī)方式選擇，則很難找到另一個值恰好命中該值。

應(yīng)用：搜索謎題現(xiàn)在，我們通過一個應(yīng)用來說明這個屬性的有用性。在這個應(yīng)用中，我們將構(gòu)建一個搜索謎題，一個需要搜索非常大空間才能找到解決方案的數(shù)學(xué)問題。特別的是，這個搜索謎題沒有捷徑。也就是說，除了窮盡整個空間之外，沒有辦法找到有效的解決方案。

搜索謎題?搜索謎題包括

·一個哈希函數(shù)，H

·一個值，id（我們稱之為謎題ID），從高最小熵分布中選擇的

·目標(biāo)集合Y

這個謎題的解決方案是一個值x，使得

H(id‖x)∈Y.

直覺是這樣的：如果H具有n位輸出，則可能是2的n次方個值中的任何一個。如果要解決謎題，需要找到一個輸入，使得輸出落在遠(yuǎn)小于所有輸出集合的集合Y內(nèi)。Y的大小決定了謎題的難度。如果Y是所有n位串的集合，這個謎題是微不足道的，而如果Y只有1個元素，那么這個難題就是最難的。謎題ID具有高的最小熵的事實(shí)，確保這沒有捷徑。相反，如果ID的特定值很適合，那么有人就可能會欺騙，比如通過使用該ID預(yù)先計算一個謎題的解決方案。

如果一個搜索謎題是謎題友好的，這意味著這個謎題沒有解決策略，這比只是嘗試x的隨機(jī)值更好。因此，如果我們想要構(gòu)建一個難以解決的謎題，只要我們能以適當(dāng)?shù)碾S機(jī)方式生成謎題ID就可以了。稍后當(dāng)我們談?wù)摫忍貛砰_采時，我們將使用這個想法，這是一種計算謎題。

SHA‐256。我們已經(jīng)討論了哈希函數(shù)的三個屬性，并且每個屬性都有一個應(yīng)用實(shí)例?，F(xiàn)在，讓我們來討論一個將在本書中使用很多次的特定哈希函數(shù)。哈希函數(shù)有很多，但是這個是Bitcoin主要使用的，一個相當(dāng)不錯的使用。這就是所謂的SHA-256。

回想一下，我們要求哈希函數(shù)適用于任意輸入長度。幸運(yùn)的是，只要我們可以建立一個適用于固定輸入長度的哈希函數(shù)，用一個通用的方法將其轉(zhuǎn)換成適用于任意輸入長度的哈希函數(shù)即可。這就是所謂的Merkle‐Damgard轉(zhuǎn)換。SHA‐256是使用這種方法的常用哈希函數(shù)之一。在通用術(shù)語中，底層為固定長度抗碰撞哈希函數(shù)被稱作壓縮函數(shù)。已經(jīng)證明，如果底層壓縮函數(shù)是抗沖擊的，那么整個哈希函數(shù)也具有抗沖擊性。

Merkle‐Damgard轉(zhuǎn)換非常簡單。說的是壓縮函數(shù)取長度為m的輸入，并產(chǎn)生一個較小長度為n的輸出。對哈希函數(shù)的輸入，可以是任何規(guī)模，被分成長度為m-n的塊。結(jié)構(gòu)工作如下：將每個塊與前一塊的輸出一起傳遞到壓縮函數(shù)。注意，輸入長度將變?yōu)椋╩-n）+n=m，這也是壓縮函數(shù)的輸入長度。對于沒有先前塊輸出的第一個塊，我改為使用初始化向量（IV）。這個數(shù)字被重復(fù)使用到哈希函數(shù)的每一個調(diào)用中，實(shí)際上你可以在標(biāo)準(zhǔn)文檔中查找到。最后一個塊的輸出就是你想要返回的結(jié)果。

SHA-256采用一個壓縮函數(shù)，它需要768位輸入并產(chǎn)生256位的輸出，塊的大小為512位。有關(guān)SHA-256工作的圖形說明，請參見圖1.3。

圖1.3：SHA-256哈希函數(shù)（簡圖）SHA‐256使用Merkle-Damgard變換將固定長度的抗碰撞壓縮函數(shù)轉(zhuǎn)換為接受任意長度輸入的哈希函數(shù)。它的輸入是“填充”，故其長度為512位的倍數(shù)。

我們討論了哈希函數(shù)，具有特殊屬性的加密哈希函數(shù)，這些屬性的應(yīng)用以及我們在比特幣中使用的特定哈希函數(shù)。在下一屆中，我們將討論如何使用哈希函數(shù)來構(gòu)建更多復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)用于像Bitcoin這樣的分布式系統(tǒng)。

補(bǔ)充部分：哈希函數(shù)建模哈希函數(shù)是加密領(lǐng)域的瑞士軍刀：他們在各種各樣的應(yīng)用中找到了一個地方。這種多功能性的另一面是，不同的應(yīng)用需要稍微不同的哈希函數(shù)屬性來確保安全性。眾所周知，很難確定一個哈希函數(shù)屬性的列表，這將導(dǎo)致整個系統(tǒng)的安全性證明。

在本文中，我們選擇了三中屬性，這些屬性對于比特幣和其他加密貨幣使用哈希函數(shù)的方式至關(guān)重要。即使在這個空間中，并不是所有這些屬性都是每次使用哈希函數(shù)所必需的。例如，我們將看到謎題友好只在比特幣挖礦中是重要的。

安全系統(tǒng)的設(shè)計者通常會拋出一個模型，將哈希函數(shù)建模為為每一個可能的輸入輸出獨(dú)立隨機(jī)值的函數(shù)。在密碼學(xué)中，使用這種“隨機(jī)語言模型”來證明安全性仍然存在爭議。不管人們對這個辯論的立場如何，論證如何將我們的應(yīng)用中所需的安全屬性降低到底層基元的基本屬性上，對于構(gòu)建安全系統(tǒng)是一個很有價值的智力練習(xí)。我們在本章中的陳述旨在幫助你學(xué)習(xí)這項(xiàng)技能。

1.2哈希指針和數(shù)據(jù)結(jié)構(gòu)

我在本節(jié)中，我們將討論哈希指針以及它的應(yīng)用。哈希指針是一種數(shù)據(jù)結(jié)構(gòu)，它在我們將討論的許多系統(tǒng)中非常有用。哈希指針只是一個指向一些信息與利用加密哈希的信息存儲在一起的指針。一個常規(guī)指針給你一種檢索信息的方法，而一個哈希指針也提供了一種驗(yàn)證信息沒有改變的方法。

圖1.4：哈希指針S哈希指針是一個指向數(shù)據(jù)在某個固定時間點(diǎn)與該數(shù)據(jù)的加密哈希值一起存儲的位置指針。

我們可以使用哈希指針來構(gòu)建各種數(shù)據(jù)結(jié)構(gòu)。直觀地，我們可以采用一種熟悉的數(shù)據(jù)結(jié)構(gòu)，它使用諸如鏈接列表或二叉搜索樹之類的指針，并用哈希指針來實(shí)現(xiàn)，而不是像通常那樣使用指針。

區(qū)塊鏈在圖1.5中，我們使用哈希指針構(gòu)建了一個鏈表。我們將把這個數(shù)據(jù)結(jié)構(gòu)稱為區(qū)塊鏈。而在具有一系列塊的常規(guī)鏈表中，每個塊都有數(shù)據(jù)，以及指向列表中先前一個塊的指針，在塊鏈中，前一個塊指針將被替換為哈希指針。因此，每個塊不僅告訴我們上一塊的值在哪里，而且還包含該值的摘要，允許我們驗(yàn)證值沒有改變。我們存儲列表的頭，它只是一個指向最新數(shù)據(jù)塊的常規(guī)哈希指針。

圖1.5區(qū)塊鏈 區(qū)塊鏈?zhǔn)且粋€使用哈希指針而不是指針構(gòu)建的鏈表。

區(qū)塊鏈的一個用例就是一個防篡改的日志。也就是說，我們要構(gòu)建一個存儲一堆數(shù)據(jù)的日志數(shù)據(jù)結(jié)構(gòu)，并允許我們將數(shù)據(jù)附加到日志的末尾。但是，如果有人改變了日志中較早的數(shù)據(jù)，我們將會檢測到它。

要了解為什么一個區(qū)塊鏈可以實(shí)現(xiàn)這個篡改的屬性，讓我們來看一看，如果對手想篡改鏈中間的數(shù)據(jù)會發(fā)生什么。具體來說，對手的目標(biāo)是以這樣的方式進(jìn)行的，只記住區(qū)塊鏈頭部的哈希指針的人將無法檢測到篡改。為了實(shí)現(xiàn)這個目標(biāo)，對手改變了一些區(qū)塊k的數(shù)據(jù)。由于數(shù)據(jù)已經(jīng)被改變，區(qū)塊k+1中的哈希值是整個區(qū)塊k的哈希值，因此不會匹配。請記住，我們在統(tǒng)計上保證，由于哈希函數(shù)具有抗碰撞性，故新哈希將不會與更改后的內(nèi)容相匹配。因此，我們將檢測區(qū)塊k中的新數(shù)據(jù)與區(qū)塊k+1中的哈希指針之間的不一致。當(dāng)然，對手可以繼續(xù)嘗試通過改變下一個區(qū)塊的哈希來掩蓋這個變化。對手可以繼續(xù)這樣做，但是當(dāng)他到達(dá)名單的頭部時，這個策略就會失敗。具體來說，只要我們將哈希指針列表的頭部存儲在對手不能改變的地方，對手將不能在不被檢測的情況下改變?nèi)魏螀^(qū)塊。

這樣做的結(jié)果是，如果對手想要在整個鏈中的任何地方篡改數(shù)據(jù)，為了保持故事的一致性，他將不得不篡改哈希指針直到它開始的地方。而且他最終會遇到障礙，因?yàn)樗麩o法篡改列表的頭部。因此出現(xiàn)的是，通過記住這個單獨(dú)的哈希指針，我們基本上記住了一個防篡改哈希的整個列表。因此，我們可以構(gòu)建一個像這樣的區(qū)塊鏈，它包含了我們想要的區(qū)塊，在列表的開始追溯到的一些特殊的區(qū)塊，我們將其稱之為起源區(qū)塊。

您可能已經(jīng)注意到，這個區(qū)塊鏈結(jié)構(gòu)類似于上一節(jié)中我們看到的Merkle-Damgard結(jié)構(gòu)。實(shí)際上，它們是非常相似的，同樣的安全論據(jù)也適用于他們。

圖1.6防篡改日志?如果對手在區(qū)塊鏈中的任何位置修改數(shù)據(jù)，則會導(dǎo)致以下區(qū)塊中的哈希指針不正確。如果我們存儲列表的頭部，那么即使對手將所有指針修改為與修改后的數(shù)據(jù)一致，頭指針也將不正確，我們會檢測到篡改。

Merkle樹。我們可以使用哈希指針構(gòu)建的另一個有用的數(shù)據(jù)結(jié)構(gòu)是二叉樹。具有哈希指針的二進(jìn)制樹被稱為Merkle樹，其發(fā)明人是Ralph Merkle。假設(shè)我們有一些包含數(shù)據(jù)的區(qū)塊，這些區(qū)塊包括我們樹的葉子。我們將這些數(shù)據(jù)塊分成兩組，然后對于每一對，我們構(gòu)建一個具有兩個哈希指針的數(shù)據(jù)結(jié)構(gòu)，每個指向其中之一的區(qū)塊。這些數(shù)據(jù)結(jié)構(gòu)成為樹的下一個級別。我們反過來將它們分成兩組，每對都創(chuàng)建一個包含每個哈希的新數(shù)據(jù)結(jié)構(gòu)。我們繼續(xù)這樣做，直到我們到達(dá)一個單一的區(qū)塊，樹的根。

圖1.7 Merkle樹?在Merkle樹中，數(shù)據(jù)塊成對分組，并且這些塊中的每一個的哈希存儲在父節(jié)點(diǎn)中。父節(jié)點(diǎn)依次成對分組，并將其哈希存儲在樹的上一級。這一直延續(xù)到樹上，直到我們到達(dá)根節(jié)點(diǎn)。

像以前一樣，我們只記得樹的頭部的哈希指針。我們現(xiàn)在有能力向下遍歷哈希指針到列表中的任何一點(diǎn)。這樣我們就可以確保數(shù)據(jù)沒有被篡改，因?yàn)檎缥覀冇脜^(qū)塊鏈所看到的那樣，如果一個對手在樹底部篡改一些數(shù)據(jù)塊，這將導(dǎo)致一個級別的哈希指針不匹配，即使他繼續(xù)篡改該區(qū)塊，更改將最終傳播到樹的頂部，在那里他將無法篡改我們存儲的哈希指針。再來一次，任何篡改任何數(shù)據(jù)的嘗試都將通過記住頂部的哈希指針來被檢測。

會籍證明Merkle樹的另一個很好的特征是，與之前建立的區(qū)塊鏈不同，它允許一個簡明的會籍證明。有人想證明某個數(shù)據(jù)塊是Merkle Tree的成員。像往常一樣，我們只記得根源。然后他們需要向我們顯示這個數(shù)據(jù)區(qū)塊，以及從數(shù)據(jù)區(qū)塊到根的路徑上的區(qū)塊。我們可以忽略樹的其余部分，因?yàn)樵撀窂缴系膲K足以允許我們一直驗(yàn)證散列到樹的根部。有關(guān)如何工作的圖形描述，請參見圖1.8。

如果樹中有n個節(jié)點(diǎn)，則只需要顯示大約log（n）個項(xiàng)目。并且由于每個步驟只需要計算子塊的哈希值，所以需要大約log（n）時間來驗(yàn)證它。所以即使Merkle樹包含了大量的塊，我們?nèi)匀豢梢栽谙鄬^短的時間內(nèi)證明成員資格。驗(yàn)證因此在時間和空間上運(yùn)行，數(shù)目是樹中節(jié)點(diǎn)數(shù)的對數(shù)。

圖1.8會籍證明?為了證明樹中包含一個數(shù)據(jù)塊，只需要顯示從該數(shù)據(jù)區(qū)塊到根的路徑中的區(qū)塊。

一個分類的Merkle樹只是一個我們在底部采集區(qū)塊，使用一些排序函數(shù)進(jìn)行排序的Merkle樹。這可以是字母順序，字典順序，數(shù)字順序或其他一些約定的順序。

非會籍證明Merkle樹的另一個很好的特征是，與之前建立的區(qū)塊鏈不同，它允許一個簡明的會籍證明。

使用排序的Merkle樹，我們可以在時間和空間的對數(shù)上驗(yàn)證非會員資格。也就是說，我們可以證明一個特定的區(qū)塊不在Merkle樹中 。而我們這樣做的方式只是簡單通過顯示一個項(xiàng)目的路徑，這個項(xiàng)目恰好在所討論項(xiàng)目之前，并顯示該項(xiàng)目的路徑。如果這兩個項(xiàng)目在樹中是連續(xù)的，那么這可以作為證明該項(xiàng)目不包括在內(nèi)的證據(jù)。因?yàn)槿绻话?，它將需要在顯示的兩個項(xiàng)目之間，但因?yàn)樗鼈兪沁B續(xù)的，故它們之間沒有空格。

我們已經(jīng)討論過在鏈表和二叉樹中使用哈希指針，但更普遍的是，只要數(shù)據(jù)結(jié)構(gòu)沒有循環(huán)，我們就可以在任何基于指針的數(shù)據(jù)結(jié)構(gòu)中使用哈希指針。如果數(shù)據(jù)結(jié)構(gòu)中有循環(huán)，那么我們將無法使所有的哈希值相匹配。如果你考慮一下，在一個非循環(huán)的數(shù)據(jù)結(jié)構(gòu)中，我們可以在葉子附近開始，或者靠近沒有任何指針出來的東西，計算它們的哈希值，然后回到起始點(diǎn)。但是在一個有循環(huán)的結(jié)構(gòu)中，沒有一個地方是頭，也沒有一個地方是尾，我們無法從頭開始并從中計算出來。

所以，考慮到另一個例子，我們可以從哈希指針中構(gòu)建一個有向無環(huán)圖。我們將能夠非常有效地驗(yàn)證該圖表中的成員資格，而且它很容易計算。以這種方式使用哈希指針是一般的技巧，您將在分布式數(shù)據(jù)結(jié)構(gòu)和本章后面的整個本書中討論的算法中一次又一次地看到。

1.3數(shù)字簽名

在本節(jié)中，我們將看看數(shù)字簽名。這是第二個加密原語，和哈希函數(shù)一樣，我們后續(xù)會把它作為加密的構(gòu)建區(qū)塊來討論。數(shù)字簽名應(yīng)該是手寫在紙上簽名的模擬數(shù)字。我們希望數(shù)字簽名中的兩個屬性與手寫簽名類比很好。首先，只有你可以簽名，但任何看到它的人都可以驗(yàn)證它是否有效。其次，我們希望將簽名與特定文件相關(guān)聯(lián)，以便簽名不能用于表示你的協(xié)議或認(rèn)可其他文檔。對于手寫簽名，后一個屬性類似于確保有人不能將您的簽名從一個文檔中刪除，并將其粘貼到另一個文檔的底部。

數(shù)字簽名方案數(shù)字簽名方案由以下三種算法組成：

·（sk，pk）:=generateKeys（keysize）The generateeys的方法獲取一個密鑰的大小，并生成一個密鑰與之配對。秘密密鑰sk被保密起來，用于簽署消息。Pk是你向每個人提供的公開驗(yàn)證密鑰，任何擁有此密鑰的人都可以驗(yàn)證你的簽名。

·sig:=sign（sk，message）符號方法將消一個消息和一個秘密密鑰sk作為輸入，并在sk下輸出簽名消息

·isValid:=verify（pk，message，sig）驗(yàn)證方法將消息、簽名和公鑰作為輸入。它返回一個布爾值isValid，如果sig是公鑰pk下的有效簽名消息則為true，否則為false。

我們要求以下兩個屬性：

·必須驗(yàn)證有效的簽名

verify（pk，message，sign（sk，message））==ture

·簽名存在且不可偽造

我們?nèi)绾问褂脭?shù)字加密技術(shù)來搭建它？首先，讓我們將以前直觀的討論稍微具體一些。這將使我們更好地理解數(shù)字簽名方案，并討論其安全屬性。

我們注意到，generateKeys和sign可以是隨機(jī)算法。事實(shí)上，generateeys最好被隨機(jī)分配，因?yàn)樗鼞?yīng)該為不同的人生成不同的鑰匙。另一方面，驗(yàn)證將永遠(yuǎn)是確定性的。

現(xiàn)在讓我們更詳細(xì)地研究我們要求的數(shù)字簽名方案的兩個屬性。第一個屬性是直接的——有效的簽名必須驗(yàn)證。如果我使用密鑰sk簽名一個消息，某人稍后嘗試使用我的公鑰pk驗(yàn)證該簽名，該簽名必須正確驗(yàn)證。這個屬性是簽名有用的基本要求。

不可偽造性。第二個要求是偽造的簽名在計算上是不可行的。也就是說，一個知道你的公鑰并在其他信息上看到你簽名的對手不能在沒有看到你簽名的消息上偽造你的簽名。這種不可偽造性的屬性通常是以我們與對手一起玩游戲的形式來展現(xiàn)的。在加密安全性證明中，使用游戲是很常見的。

在不可偽造的游戲中，有一個對手聲稱他可以偽造簽名，還有一個挑戰(zhàn)者會測試這個聲明。我們首先做的是使用generateKeys來生成一個秘密簽名密鑰和一個相應(yīng)的公開驗(yàn)證密鑰。我們給挑戰(zhàn)者提供秘鑰，我們把公鑰提供給挑戰(zhàn)者和對手。所以對手只知道公開的信息，他的使命是試圖偽造信息。挑戰(zhàn)者知道密鑰，所以他可以簽名。

直觀地，這個游戲的設(shè)置符合現(xiàn)實(shí)世界的條件?，F(xiàn)實(shí)生活中的攻擊者很可能會看到他們的受害者在許多不同文件上的有效簽名。也許攻擊者甚至可以操縱受害者簽署無害的文件，如果這對攻擊者有用。

為了在我們的游戲中建模，我們將允許攻擊者在他選擇的一些文檔上獲得簽名，只要他想要，只要猜測的數(shù)量是合理的。為了直觀地了解我們所指的合理猜測數(shù)，我們將允許攻擊者嘗試100萬次猜測，而不是2的80次方次猜測。（在漸近的術(shù)語中，我們允許攻擊者嘗試一些密鑰大小的多項(xiàng)式的函數(shù)的猜測，但沒有更多（例如，攻擊者無法以指數(shù)方式嘗試許多猜測）。）

一旦攻擊者確信他已經(jīng)看到足夠的簽名，那么攻擊者會選擇一些消息，M，他們將嘗試偽造一個簽名。對M的唯一限制是它必須是攻擊者以前沒有看到簽名的消息（因?yàn)楣粽唢@然可以發(fā)回他被給予的簽名?。Ｌ魬?zhàn)者運(yùn)行驗(yàn)證算法，以確定攻擊者生成的簽名是否是公共驗(yàn)證密鑰下的M上的有效簽名。 如果成功驗(yàn)證，攻擊者將贏得比賽。

圖1.9不可偽造的游戲對手和挑戰(zhàn)者玩不可偽造的游戲。 如果攻擊者能夠在他以前沒有看到的消息上成功輸出一個簽名，他就勝出了。如果他不能，挑戰(zhàn)者勝利，則數(shù)字簽名計劃是不可偽造的。

我們認(rèn)為，當(dāng)且僅當(dāng)對手無論對手使用什么算法時，簽名方案都是不可偽造的，他成功偽造信息的機(jī)會非常小——這么小，以至于我們可以假定它在實(shí)踐中永遠(yuǎn)不會發(fā)生。

實(shí)際問題。有一些實(shí)際的事情，我們需要做的是將算法思想變成可以在實(shí)踐中實(shí)現(xiàn)的數(shù)字簽名機(jī)制。例如，許多簽名算法是隨機(jī)的（特別是比特幣中使用的），因此我們需要一個很好的隨機(jī)源。這個真正的重要性不能低估，因?yàn)椴缓玫碾S機(jī)性將使您的否則安全的算法不安全。

另一個實(shí)際的問題是消息大小。實(shí)際上，您可以簽署的郵件大小有一個限制，因?yàn)閷?shí)際的方案將在有限長度的位串上運(yùn)行。有一個簡單的方法來解決這個限制：簽名消息的哈希，而不是消息本身。如果我們使用具有256位輸出的加密哈希函數(shù)，那么只要我們的簽名方案可以簽署256位消息，我們就可以有效地簽名任何長度的消息。如前所述，由于哈希函數(shù)具有抗沖突性，所以以這種方式將消息的哈希作為消息摘要是安全的。

稍后我們將使用的另一個技巧是你可以簽署哈希指針。如果您簽署了一個哈希指針，那么簽名將覆蓋或保護(hù)整個結(jié)構(gòu)——而不僅僅是哈希指針本身，而是哈希指針鏈所指向的一切。例如，如果你要在區(qū)塊鏈結(jié)尾簽署哈希指針，則結(jié)果是你將有效地對該整個塊鏈進(jìn)行數(shù)字簽名。

ECDSA。現(xiàn)在讓我們進(jìn)入堅果和螺栓。比特幣使用一種稱為橢圓曲線數(shù)字簽名算法（ECDSA）的特定數(shù)字簽名方案。ECDSA是美國政府標(biāo)準(zhǔn)，更新了適用于使用橢圓曲線的早期DSA算法。這些算法多年來已經(jīng)得到了相當(dāng)多的加密分析，并且通常被認(rèn)為是安全的。

更具體地說，比特幣在標(biāo)準(zhǔn)橢圓曲線“secp256k1”上使用了ECDSA，該曲線被估計為128以提供128位的安全性（即，像執(zhí)行2個對稱密鑰加密操作（如調(diào)用哈希函數(shù)）一樣難以打破此算法）。雖然這個曲線是一個已發(fā)布的標(biāo)準(zhǔn)，但它很少在比特幣之外使用，其他使用ECDSA的應(yīng)用程序（如用于安全網(wǎng)頁瀏覽的TLS中的密鑰交換）通常使用更常見的“secp256r1”曲線。這只是Bitcoin的一個怪癖，因?yàn)镾atoshi在系統(tǒng)的早期規(guī)范中選中，現(xiàn)在很難改變。

我們不會詳細(xì)介紹ECDSA的工作原理，因?yàn)樯婕暗揭恍?fù)雜的數(shù)學(xué)問題，理解這本書并不必需了解它。如果你對細(xì)節(jié)感興趣，請參閱本章末尾的進(jìn)一步閱讀部分。但是，對于各種數(shù)量的大小有個了解，這可能是有用的：

Private key: 256bit

Public key, uncompressed: 512bit

Public key, compressed: 257bit

Message to be signed: 256bit

Signature:512bit

請注意，雖然ECDSA技術(shù)上只能在256位長的時間內(nèi)簽署消息，但這并不是一個問題：消息在被簽名前總是散列，因此可有效地對任何大小的消息進(jìn)行有效的簽名。

使用ECDSA，一個很好的隨機(jī)來源是至關(guān)重要的，因?yàn)橐粋€壞的隨機(jī)源可能會泄露你的鑰匙。直觀地說，如果您在生成密鑰時使用不良隨機(jī)，則生成的密鑰可能不會安全。但是，ECDSA（對于那些熟悉DSA的人來說，這是DSA中的一個普遍現(xiàn)象，而不是橢圓曲線變體獨(dú)有的）的一個奇怪之處在于，即使你只在簽名時使用不良隨機(jī)，使用完美的鑰匙，也會泄露您的私鑰。然后是游戲結(jié)束;如果你泄露你的私鑰，對手可以偽造你的簽名。因此，我們需要特別小心在實(shí)踐中使用良好的隨機(jī)性，使用不良隨機(jī)源是其他安全系統(tǒng)的常見缺陷。

邊欄：加密貨幣和加密。 如果你一直在等待Bitcoin中使用哪種加密算法，抱歉讓你失望了。如我們看到的，Bitcoin沒有加密，因?yàn)闆]有什么需要加密的。加密只是現(xiàn)代加密技術(shù)成為可能的一套豐富的技術(shù)之一。他們中的許多，比如承諾方案，都會以某種方式隱藏信息，但他們與加密不同。

自此，完成了我們對加密原語數(shù)字簽名的討論。在下一節(jié)中，我們將討論數(shù)字簽名的一些應(yīng)用，這將被用于構(gòu)建加密貨幣。

1.4公鑰作為身份

我們來看看一個與數(shù)字簽名相伴的好招。這個想法是把一個公鑰，一個數(shù)字簽名方案中的公開驗(yàn)證密鑰之一，等同于系統(tǒng)中一個人或一個演員的身份。如果你看到一個帶有簽名的消息在一個公共密鑰PK下正確地驗(yàn)證，那么你可以想象成pk在說這則消息。你可以將一個公鑰看作一個演員，或一個系統(tǒng)中可以通過簽署這些聲明來發(fā)表聲明的一個派對。從這個角度來說，公鑰是一種身份。為了讓某人為身份pk證明，他們必須知道相應(yīng)的秘密密鑰sk。

將公鑰作為身份處理的結(jié)果是，您可以隨時創(chuàng)建一個新的身份——你只需創(chuàng)建一個新的密鑰對，SK和PK，通過generatekeys運(yùn)行在我們的數(shù)字簽名方案。pk是您可以使用的新公開身份，而sk是相應(yīng)的秘密密鑰，只有您知道，并允許您代表身份pk發(fā)言。因?yàn)楣€很大，你可以使用pk的哈希作為你的身份。 如果你這樣做，那么為了驗(yàn)證一個消息是否來自你的身份，我們必須檢查（1）該pk確實(shí)混編了你的身份，（2）該消息在公鑰pk下驗(yàn)證。

此外，默認(rèn)情況下，你的公鑰基本上看起來是隨機(jī)的，沒有人能夠通過檢查pk（當(dāng)然，一旦你開始使用這個身份進(jìn)行陳述，這些陳述可能會泄漏信息，讓人們可以將pk連接到你的真實(shí)世界身份。我們將在稍后進(jìn)行詳細(xì)討論。）來發(fā)現(xiàn)你的真實(shí)世界身份。 你可以產(chǎn)生一個看起來很隨機(jī)的新鮮身份，看起來像人群中的臉，只有你可以控制。

分權(quán)身份管理。這給我們帶來了分權(quán)身份管理的想法。你可以為你自己注冊一個用戶，而不是搭建一個中央集權(quán)的機(jī)構(gòu)，以便在這系統(tǒng)中注冊為用戶。你不需要發(fā)布用戶名，也不需要通知某人你將要使用特定的名稱。如果你想要一個新的身份，你可以隨時生成一個，想要多少有多少。如果你喜歡被五個不同的名字所知，沒問題！只要做五個身份。如果你想在某一段時間匿名，你可以創(chuàng)建一個新的身份，使用一段時間后把它丟棄。所有這些都可以通過分權(quán)身份管理來實(shí)現(xiàn)，而事實(shí)上，比特幣也是這樣做的。這些身份在比特幣術(shù)語中被稱為地址。你會經(jīng)常在上下文中聽到Bitcoin和加密幣中使用術(shù)語地址，這只是一個公鑰的哈希值。作為這種分權(quán)式身份管理計劃的一部分，這是一種憑空形成的身份。

邊欄：如果沒有中央授權(quán)，你可以產(chǎn)生一個身份的想法似乎是違反直覺的。畢竟，如果有人幸運(yùn)與你產(chǎn)生了相同的密鑰，他們能竊取你的比特幣嗎？

答案是，別人生成相同的256位密鑰的可能性太小了，我們在實(shí)踐中就不用擔(dān)心了。我們所有的意圖和目的都保證這永遠(yuǎn)不會發(fā)生。

更普遍的是，與初學(xué)者的直覺相比，概率系統(tǒng)是難以理解且不可預(yù)知的，往往是相反的——統(tǒng)計理論允許我們精確量化我們感興趣的事件的機(jī)會，并自信地斷言這種系統(tǒng)的行為。

但有一個微妙之處：只有當(dāng)密鑰是隨機(jī)生成的時候，概率保證才是真的。隨機(jī)性的產(chǎn)生通常是實(shí)際系統(tǒng)中薄弱的一個環(huán)節(jié)。如果兩個用戶的計算機(jī)使用相同的隨機(jī)來源或者使用可預(yù)測的隨機(jī)性，則理論保證不再適用。所以在生成密鑰時要使用一個很好的隨機(jī)源，來確保實(shí)際的保證與理論上的匹配是至關(guān)重要的。

乍一看，分權(quán)身份管理可能會導(dǎo)致很大的匿名性和隱私性。畢竟，你可以自己創(chuàng)建一個隨機(jī)的身份，而不是告訴任何人你的真實(shí)身份。但這并不那么簡單。隨著時間的推移，你創(chuàng)建的身份會產(chǎn)生一系列陳述。人們看到這些陳述，因此知道擁有這個身份的人做了一系列的行動。他們可以開始連接點(diǎn)，使用這一系列的動作來推斷關(guān)于你真實(shí)身份的事情。一個觀察者可以隨著時間的推移將這些東西聯(lián)系在一起，并作出推論，導(dǎo)致他們得出結(jié)論，如“哎，這個人的行為很像喬。也許這個人是喬?！?/p>

換句話說，在比特幣的世界你不需要明確地登記或揭示你的真實(shí)身份，但你的行為模式本身可能就是識別。這是一個如比特幣一樣的加密貨幣的基本隱私問題，實(shí)際上我們將把第6章整體付諸實(shí)踐它。

1.5簡單的密碼學(xué)

現(xiàn)在我們從密碼學(xué)轉(zhuǎn)移到加密貨幣。吃我們的加密蔬菜將開始在這里付清，我們將逐漸看到這些片段如何合并在一起，為什么加密操作如哈希函數(shù)和數(shù)字簽名實(shí)際上是有用的。在本節(jié)中，我們將討論兩種非常簡單的加密貨幣。當(dāng)然，這需要本書剩下的大部分內(nèi)容來詳細(xì)講解Bitcoin本身是如何運(yùn)作的含義。

GoofyCoin

第一個是GoofyCoin，它是關(guān)于我們可以想象的最簡單的加密機(jī)制。GoofyCoin只有兩個規(guī)則。第一個規(guī)則是，指定的實(shí)體、愚人，都可以創(chuàng)造新的硬幣，只要他想要，這些新創(chuàng)造的硬幣都屬于他。

為了創(chuàng)建一個硬幣，Goofy生成一個獨(dú)特的硬幣ID uniqueCoinID，他以前從未生成過，并構(gòu)造了字符串“CreateCoin [uniqueCoinID]”。然后他用他的秘密簽名鑰匙計算這個字符串的數(shù)字簽名。該字符串與Goofy的簽名一起，是一枚硬幣。任何人都可以驗(yàn)證包含Goofy有效簽名的CreateCoin語句的硬幣，因此它是有效的硬幣。

GoofyCoin的第二條規(guī)則是，擁有硬幣的人可以將其轉(zhuǎn)讓給其他人。 轉(zhuǎn)移硬幣不僅僅是將硬幣的數(shù)據(jù)結(jié)構(gòu)發(fā)送給收件人——它是使用加密操作來完成的。

讓我們說，Goofy想把他創(chuàng)造的硬幣轉(zhuǎn)給Alice。為了做到這一點(diǎn)，他創(chuàng)建了一個新的聲明，說“付給Alice”，其中“這”是一個哈希指針，引用了所討論的硬幣。正如我們先前所看到的那樣，身份確實(shí)只是公鑰，所以“Alice”是指Alice的公鑰。最后，Goofy簽署代表該聲明的字符串。由于Goofy是最初擁有該硬幣的人，他必須簽署任何花費(fèi)硬幣的交易。一旦代表Goofy的這筆交易簽署的數(shù)據(jù)結(jié)構(gòu)存在，Alice就擁有這個硬幣。她可以向任何人證明她擁有硬幣，因?yàn)樗梢杂肎oofy的有效簽名來提供數(shù)據(jù)結(jié)構(gòu)。此外，它指向由Goofy擁有的有效硬幣。 所以硬幣的有效性和所有權(quán)在系統(tǒng)中是不言而喻的。

一旦Alice擁有硬幣，她可以輪流使用。為了做到這一點(diǎn)，她創(chuàng)造一個聲明，說：“把這個硬幣付給Bob的公鑰”，其中“這”是一個哈希指針，指向由她擁有的硬幣。當(dāng)然，Alice簽署了這聲明。當(dāng)任何人提供這個硬幣時，都可以驗(yàn)證Bob是業(yè)主。他們將跟隨哈希指針鏈回到硬幣的創(chuàng)建，并驗(yàn)證每一步，合法的所有者簽署一個聲明說“把這個硬幣付給[新主人]”。

圖1.10 GoofyCoin貨幣 這里展示的是一個硬幣（底層），花了兩次（中間和頂部）

總而言之，GoofyCoin的規(guī)則是：

·Goofy可以通過簡單地簽署聲明來創(chuàng)建新的硬紙，且他創(chuàng)造的新硬幣擁有唯一的硬幣ID

··擁有硬幣的人可以通過簽署一份聲明“將此硬幣兌換給X”（X指定為公鑰）的聲明將其傳遞給其他人員

·任何人都可以通過跟隨哈希指針鏈回到Goofy的創(chuàng)建，驗(yàn)證一路上所有的簽名，來證明硬幣的有效性

當(dāng)然，GoofyCoin有一個基本的安全問題。讓我們說，Alice把她的硬幣交給了Bob，同時把簽名的聲明發(fā)送給Bob，但沒有告訴任何人。她可以創(chuàng)建另一個簽名的聲明，向查克支付相同的硬幣。對于查克來說，似乎是完美有效的交易，現(xiàn)在他是硬幣的所有者。Bob和查克都有有效的索賠聲稱是這個硬幣的所有者。這被稱為雙花攻擊——Alice花費(fèi)同一枚硬幣兩次。直觀地，我們知道硬幣不應(yīng)該這樣工作。

事實(shí)上，雙花攻擊是任何一個密碼學(xué)必須解決的關(guān)鍵問題之一。GoofyCoin并沒有解決雙重支出攻擊，因此不安全。GoofyCoin是簡單的，它的轉(zhuǎn)移機(jī)制實(shí)際上與比特幣非常類似，但是因?yàn)樗遣话踩模覀儾粫阉鳛橐粋€加密貨幣。

ScroogeCoin

為了解決雙花問題，我們將設(shè)計另一種加密貨幣，我們稱之為ScroogeCoin。ScroogeCoin是由GoofyCoin構(gòu)建的，但在數(shù)據(jù)結(jié)構(gòu)方面卻有點(diǎn)復(fù)雜。

第一個關(guān)鍵想法是，一個稱為Scrooge的指定實(shí)體只發(fā)布一個包含所有發(fā)生過的歷史交易記錄的分類賬。附加屬性確保寫入此分類帳的任何數(shù)據(jù)將永遠(yuǎn)保留。如果分類帳是唯一的，我們可以使用它來防止雙花問題，通過要求所有交易在被接受之前都寫入分類帳。這樣，如果硬幣以前被發(fā)送到不同的所有者，它將公開可見。

為了實(shí)現(xiàn)這個附加功能，Scrooge可以構(gòu)建一個區(qū)塊鏈（我們之前討論的數(shù)據(jù)結(jié)構(gòu)），他將進(jìn)行數(shù)字簽名。它是一系列數(shù)據(jù)塊，每個數(shù)據(jù)塊都有一個交易（實(shí)際上，作為優(yōu)化，我們真的把多個交易放在同一個區(qū)塊中，像Bitcoin那樣）。每一個區(qū)塊都有交易的ID、交易的內(nèi)容以及前一個區(qū)塊的哈希指針。Scrooge對最終的哈希指針進(jìn)行數(shù)字簽名，該指針將綁定整個結(jié)構(gòu)中的所有數(shù)據(jù)，并將與該區(qū)塊鏈一起發(fā)布簽名。

圖1.11 ScroogeCoin區(qū)塊鏈

在ScroogeCoin中，只計算在Scrooge簽署的區(qū)塊鏈中的交易。任何人都可以通過檢查Scrooge在其出現(xiàn)的區(qū)塊上的簽名來驗(yàn)證交易是否被Scrooge認(rèn)可。Scrooge確保他不支持一個試圖雙重支付一個已經(jīng)交易的硬幣的交易。

為什么我們需要一個帶有哈希指針的區(qū)塊鏈，除了每個區(qū)塊都有Scrooge的簽名？這確保了附加屬性。如果Scrooge嘗試向歷史記錄添加或刪除交易，或更改現(xiàn)有交易，由于哈希指針，它將影響所有下面的區(qū)塊。只要有人正在監(jiān)控Scrooge發(fā)布的最新哈希指針，這個變化將是顯而易見的。在一個Scrooge單獨(dú)簽名的系統(tǒng)中，您必須跟蹤Scrooge發(fā)行的每個簽名。區(qū)塊鏈?zhǔn)沟萌魏蝺蓚€人都很容易驗(yàn)證他們是否觀察到與Scrooge簽署的完全相同的歷史交易記錄。

在ScroogeCoin中，有兩種交易。第一種是CreateCoins，就像操作者Goofy可以在GoofyCoin中做一個新的硬幣一樣。在ScroogeCoin中，我們將擴(kuò)展語義，以允許在一個交易中創(chuàng)建多個硬幣。

圖1.12 CreateCoins交易此CreateCoins交易創(chuàng)建多個硬幣。每個硬幣在交易中都有一個序列號。每枚硬幣也有價值;它值一定數(shù)量的ScroogeCoins。最后，每個硬幣都有一個收件人，它是創(chuàng)建時獲得硬幣的公鑰。所以CreateCoins創(chuàng)建一堆不同價值的新硬幣，并將它們分配給作為初始所有者的人。我們指的是CoinIDs的硬幣。一個CoinID是一個交易中該交易ID和硬幣序列號的組合。

如果由Scrooge簽名，一筆CreateCoins交易總是有效的。我們不用擔(dān)心Scrooge什么時候有權(quán)創(chuàng)造硬幣或創(chuàng)造多少，就像我們沒有擔(dān)心在GoofyCoin中，Goofy是如何被選為允許創(chuàng)建硬幣的實(shí)體。

第二種交易是PayCoins。它消耗一些硬幣，也就是銷毀它們，并創(chuàng)建相同總價值的新硬幣。新的硬幣可能屬于不同的人（公鑰）。這筆交易必須由所有付錢的人簽字。因此，如果你是這筆交易中將要使用該硬幣的所有者之一，那么你需要對這筆交易進(jìn)行數(shù)字簽名，以表明這枚硬幣真的很好用。

ScroogeCoin的規(guī)則說，如果下面四件事情是真實(shí)的，PayCoins的交易則是有效的：

··消費(fèi)的硬幣是有效的，也就是說它們是在以前的交易中創(chuàng)建的。

·消費(fèi)的硬幣在以前的交易中沒有被消耗掉。也就是說這不是雙重支付。

·從這筆交易中出來的硬幣總價值等于流入的硬幣總價值。也就是說，只有Scrooge可以創(chuàng)造新的價值。

·交易由所有消費(fèi)硬幣的所有者有效簽署。

圖1.13一個PayCoins的交易

如果滿足所有這些條件，則此PayCoins交易有效，Scrooge將會接受。他會將其寫入歷史，附加到區(qū)塊鏈中，之后每個人都可以看到這個交易發(fā)生了。只有在這一點(diǎn)上，參與者可以接受交易實(shí)際發(fā)生了。直到它發(fā)布，即使前三個條件有效，它也可能被雙重支出交易搶占。

這個系統(tǒng)中的硬幣是不可變的——它們永遠(yuǎn)不會改變、細(xì)分或組合。每個硬幣在一次交易中創(chuàng)建一次，然后在某些其他交易中被消耗。但是，通過使用交易，我們可以獲得與細(xì)分或組合硬幣相同的效果。例如，為了細(xì)分硬幣，Alice創(chuàng)建一個新的交易來消耗那個硬幣，然后生產(chǎn)兩個相同總價值的新硬幣。這兩個新的硬幣可以分配給她。所以盡管硬幣在這個系統(tǒng)中是不可變的，但它具有那些不一成不變的硬幣系統(tǒng)的全部靈活性。

現(xiàn)在，我們來到ScroogeCoin的核心問題。ScroogeCoin將會以這種意義工作，人們可以看到哪些硬幣是有效的。它可以防止雙重支出，因?yàn)槊總€人都可以查看區(qū)塊鏈，并看到所有的交易都是有效的，且每個硬幣只消耗一次。但問題是Scrooge——他的影響力太大。他不能偽造交易，因?yàn)樗荒軅卧靹e人的簽名。但他可以停止批準(zhǔn)一些用戶的交易，否認(rèn)他們的服務(wù)，使他們的硬幣不可用。如果Scrooge是貪婪的（正如他的同名漫畫暗示的），他可以拒絕發(fā)布交易，除非他們向他轉(zhuǎn)移了一些授權(quán)的交易費(fèi)用。當(dāng)然，Scrooge也可以為自己創(chuàng)造盡可能多的新硬幣?；蛘逽crooge可能會厭倦整個系統(tǒng)，并全然停止更新區(qū)塊鏈。

這里的問題是集權(quán)。雖然Scrooge對這個系統(tǒng)很滿意，但作為用戶，我們可能不會這樣做。雖然ScroogeCoin似乎是一個不切實(shí)際的建議，但早期對密碼系統(tǒng)的研究假定，那里確實(shí)會有一些中央信任機(jī)構(gòu)，通常是銀行。畢竟，大多數(shù)真實(shí)世界貨幣確實(shí)有一個值得信賴的發(fā)行人（通常是政府造幣廠），負(fù)責(zé)創(chuàng)建貨幣并確定哪些票據(jù)是有效的。然而，有中央機(jī)關(guān)的加密貨幣在實(shí)踐中基本上沒有起飛。這有很多原因，但事后看來，很難讓人們接受中央授權(quán)的加密機(jī)制。

因此，我們需要解決的中心技術(shù)挑戰(zhàn)是，為了改進(jìn)ScroogeCoin并創(chuàng)建一個可行的系統(tǒng)：我們的系統(tǒng)可以不吝嗇嗎？也就是我們可以擺脫那個集中的數(shù)字吝嗇鬼嗎？我們可以在許多方面擁有像ScroogeCoin一樣運(yùn)行的加密機(jī)制，但沒有任何中央信任機(jī)構(gòu)嗎？

要做到這一點(diǎn)，我們需要弄清楚所有用戶如何就一個已發(fā)布的塊鏈達(dá)成一致，因?yàn)檫@些交易的歷史已經(jīng)發(fā)生了。他們必須一致同意哪些交易是有效的，哪些交易是實(shí)際發(fā)生的。他們還需要能夠以分散的方式將ID分配給事物。最后，新鑄造的硬幣需要以分散的方式（分布式）進(jìn)行控制。如果我們可以解決所有這些問題，那么我們可以建立一個像ScroogeCoin這樣的貨幣，但是沒有一個集權(quán)機(jī)構(gòu)（去中心化）。事實(shí)上，這將是一個非常像比特幣的系統(tǒng)。

進(jìn)一步閱讀

史提芬.列維的加密是一個非常有趣的，以非技術(shù)的眼光看現(xiàn)代密碼學(xué)的發(fā)展和背后的人：

Levy,Steven. C rypto: How the Code Rebels Beat the Government‐‐Saving Privacy in theDigital Age. Penguin, 2001.

列維.巴斯比魯.史提芬：代碼叛軍如何擊敗政府——在數(shù)字時代保護(hù)隱私.企鵝，2001

現(xiàn)代密碼學(xué)是一個相當(dāng)理論的領(lǐng)域。密碼學(xué)家使用數(shù)學(xué)來定義原語、協(xié)議，以正式的方式獲得他們所期待的安全屬性，并基于廣泛接受的關(guān)于特定數(shù)學(xué)任務(wù)的計算硬度的假設(shè)來證明他們是安全的。在本章中，我們使用直觀的語言來討論哈希函數(shù)和數(shù)字簽名。對于有興趣以更為數(shù)學(xué)的方式和更詳細(xì)的方式探索這些和其他加密概念的讀者，我們建議你參考：

Katz,Jonathan, and Yehuda Lindell. Introduction to Modern Cryptography, SecondEdition. CRC Press, 2014.

Katz，Jonathan和Yehuda Lindell。 現(xiàn)代密碼學(xué)導(dǎo)論，第二版。CRC Press，2014。

有關(guān)應(yīng)用密碼學(xué)的介紹，請參閱：

Ferguson,Niels, Bruce Schneier, and Tadayoshi Kohno. Cryptography engineering: designprinciples and practical applications.John Wiley & Sons,2012 .

弗格森，尼爾斯，布魯斯施奈爾和大田孝如。密碼學(xué)工程：設(shè)計原理和實(shí)際應(yīng)用。約翰·威利父子，2012。

使用SHA-2定義的NIST標(biāo)準(zhǔn)是獲取直觀加密標(biāo)準(zhǔn)的好方法。

FIPS PUB 180‐4,Secure HashStandards,Federal Information Processing Standards Publication. InformationTechnology Laboratory, National Institute of Standards and Technology,Gaithersburg, MD, 2008.

FIPS PUB 180-4，安全哈希標(biāo)準(zhǔn)，聯(lián)邦信息處理標(biāo)準(zhǔn)出版物。 信息技術(shù)實(shí)驗(yàn)室，國家標(biāo)準(zhǔn)與技術(shù)研究所，Gaithersburg，MD，2008。

最后，這是描述ECDSA簽名算法的標(biāo)準(zhǔn)化版本論文。

Johnson,Don, Alfred Menezes, and Scott Vanstone. The elliptic curve digital signaturealgorithm (ECDSA). International Journal of Information Security 1.1 (2001):36‐63.

約翰遜，唐，阿爾弗雷德·梅內(nèi)塞斯和斯科特·范斯通。 橢圓曲線數(shù)字簽名算法（ECDSA）。 國際信息安全雜志1.1（2001）：36-63。