帶你讀《IPFS原理與實踐》之二：IPFS底層基礎

點選檢視第一章

第2章

IPFS底層基礎

歡迎來到第2章。這一章的内容相對較多，也相對獨立。你可以選擇先閱讀這一章，了解這幾個基礎性系統的設計思路和算法細節；或者暫時跳過這一章，直接去了解IPFS系統設計。在這一章中，我們會着重介紹IPFS的幾個基礎性的子系統和資料結構，包括DHT、BitTorrent、Git和自驗證檔案系統，以及Merkle結構。

2.1　分布式哈希表（DHT）

第1代P2P檔案網絡需要中央資料庫協調，例如在2000年前後風靡一時的音樂檔案分享系統Napster。在Napster中，使用一個中心伺服器接收所有的查詢，伺服器會向用戶端傳回其所需要的資料位址清單。這樣的設計容易導緻單點失效，甚至導緻整個網絡癱瘓。在第2代分布式檔案系統中，Gnutella使用消息洪泛方法（message flooding）來定位資料。查詢消息會公布給全網所有的節點，直到找到這個資訊，然後傳回給查詢者。當然，由于網絡承載力有限，這種盲目的請求會導緻網絡快速耗盡，是以需要設定請求的生存時間以控制網絡内請求的數量。但無論如何，這種方式所需的網絡請求量非常大，很容易造成擁堵。到了第3代分布式檔案系統中，DHT 的創新提供了新的解決方案。DHT（Distributed Hash Table）主要思想如下：全網維護一個巨大的檔案索引哈希表，這個哈希表的條目形如。這裡Key通常是檔案的某個雜湊演算法下的哈希值（也可以是檔案名或者檔案内容描述），而Value則是存儲檔案的IP位址。查詢時，僅需要提供Key，就能從表中查詢到存儲節點的位址并傳回給查詢節點。當然，這個哈希表會被分割成小塊，按照一定的算法和規則分布到全網各個節點上。每個節點僅需要維護一小塊哈希表。這樣，節點查詢檔案時，隻要把查詢封包路由到相應的節點即可。下面介紹3種IPFS引用過的有代表性的分區表類型，分别是Kademlia DHT、Coral DHT和S/Kademlia。

2.1.1　Kademlia DHT

Kademlia DHT是分布式哈希表的一種實作，它的發明人是Petar Maymounkov和 David Mazières。Kademlia DHT擁有一些很好的特性，如下：

• 節點ID與關鍵字是同樣的值域，都是使用SHA-1算法生成的160位摘要，這樣大大簡化了查詢時的資訊量，更便于查詢。
• 可以使用XOR，計算任意兩個節點的距離或節點和關鍵字的距離。
• 查找一條請求路徑的時候，每個節點的資訊是完備的，隻需要進行Log(n)量級次跳轉。
• 可根據查詢速度和存儲量的需求調整每個節點需要維護的DHT大小。

KAD網絡對之前我們說的DHT有較大的改進，一個新來的網絡節點在初次連接配接網絡時會被配置設定一個ID；每個節點自身維護一個路由表和一個DHT，這個路由表儲存網絡中一部分節點的連接配接資訊，DHT用于存放檔案資訊；每個節點優先儲存距離自己更近的節點資訊，但一定確定距離在[2n,2(n+1)-1]的全部節點至少儲存k個（k是常數），我們稱作K-Bucket；每個網絡節點需要優先存儲與自己的ID距離較小的檔案；每次檢索時，計算查詢檔案的哈希值與自己的ID的距離，然後找到與這個距離對應的K-Bucket，向K-Bucket中的節點查詢，接受查詢的節點也做同樣的檢查，如果發現自己存有這個資料，便将其傳回給查詢的節點。

下面我們詳細說明一下KAD網絡算法細節。

1. Kademlia二叉狀态樹

Kademlia網絡的節點ID是由一棵二叉樹維護的，最終生成的二叉樹的特點如下：

• 每個網絡節點從根節點出發，沿着它的最短唯一字首到達。
• 每個網絡節點是葉子節點。圖2-1表示了二叉樹的形成過程，例如這裡黑色的節點ID擁有一個唯一的字首0011。對于任意的一個樹的節點，我們可以沿着它的字首作為路徑，向下分解成一系列不包含自己的子樹。Kademlia二叉樹的建立，需要確定每個網絡的節點都能從樹根沿着它的最短唯一字首的路徑到達。

下面我們介紹一下節點哈希是0011….（一共160位）的子樹劃分方法。

現在我們的網絡上有18個節點，如圖2-1所示。從樹根開始，樹根的字首是空。左子樹和右子樹的編号分别是1和0。因為還存在其他10個節點都有共同的字首0，那麼我們繼續劃分成00和01兩棵子樹，我們的目标節點（哈希值0011…）顯然屬于00這棵子樹。我們繼續檢查，發現還有3個節點是00字首，那麼繼續劃分子樹001、000。哈希位00100…和00101…兩個節點與0011依舊是共有001字首，是以001還不是最短唯一字首，我們再繼續劃分子樹，到0011，那麼不再有其他節點有相同的字首，這條路徑0011就是到樹根最短的路徑，同時0011是最短唯一字首，0011就成為它的網絡ID。

在Kademlia中，每個DHT條目包含對。key是檔案的哈希值，value是節點ID。key和value有相同的值域，都是160位。每一個新加入網絡的計算機都會被随機配置設定一個節點ID值。資料存放在key值與ID值最接近key值的節點上。這樣，我們就需要定義它們的遠近了。XOR運算可以解決這個問題。在160位Hash上，判斷兩個節點x、y的距離遠近的方法是進行二進制運算異或，d(x,y)=x⊕y。兩個二進制位結果相同，它們的異或值是0；如不同，值為1。例如，我們将111010和101011取XOR。

對于異或操作，有如下一些數學性質：

• d(x, x)=0
• d(x, y)>0, iff x≠y
• x, y:d(x, y)=d(y, x)
• d(x, y)+d(y, z)≧d(x, z)
• d(x, y)⊕d(y, z)=d(x, z)
• 存在一對x≧0, y≧0，使得x+y≧x⊕y

我們很自然地發現，如果給定了x，任意一個a(a≧0)會唯一确定另一個節點y，滿足d(x, y)=a。假設這裡的x是我們需要查詢的檔案key，我們隻需要不斷更新y，使得y沿着d(x, y)下降的方向找下去，那麼一定能收斂到距離x最近的點。前面我們提到，檔案就是存放在網絡編号與檔案哈希的XOR最近的幾個節點上。那麼換句話說，隻要沿着XOR距離降低的方向查找，從任意一個網絡節點開始查詢，我們總能找到這個存放檔案的位址。而且每次更新總能篩選掉一半的節點，那麼最多隻需Log N步即可到達。

2.節點路由表K-Bucket

節點路由表用于儲存每個節點與自己一定距離範圍内其他節點的連接配接資訊。每一條路由資訊由如下3部分組成：IP Address、UDP Port、Node ID。KAD路由表将距離分成160個K桶（存放K個資料的桶），分開存儲。編号為i的路由表，存放着距離為[2i,2(i+1)-1]的K條路由資訊。并且每個K桶内部資訊存放位置是根據上次看到的時間順序排列的，最早看到的放在頭部，最後看到的放在尾部。因為網絡中節點可能處于線上或者離線狀态，而在之前經常線上的節點，我們需要通路的時候線上的機率更大，那麼我們會優先通路它（尾部的節點）。

通常來說當i值很小時，K桶通常是空的（以0為例，距離為0自然隻有1個節點，就是自己）；而當i值很大時，其對應K桶的項數又很可能特别多（因為範圍很大）。這時，我們隻選擇存儲其中的K個。在這裡k的選擇需要以系統性能和網絡負載來權衡它的數量。比如，在BitTorrent的實作中，取值為

k＝8。因為每個K-Bucket覆寫距離範圍呈指數增長，那麼隻需要儲存至多160K個路由資訊就足以覆寫全部的節點範圍了。在查詢時使用遞歸方式，我們能證明，對于一個有N個節點的KAD網絡，最多隻需要經過log N步查詢，就可以準确定位到目标節點。

當節點x收到一個消息時，發送者y的IP位址就被用來更新對應的K桶，具體步驟如下。

1）計算自己和發送者的ID距離：d(x,y)=x⊕y。

2）通過距離d選擇對應的K桶進行更新操作。

3）如果y的IP位址已經存在于這個K桶中，則把對應項移到該K桶的尾部；如果y的IP位址沒有記錄在該K桶中，則：

①如果該K桶的記錄項小于k個，則直接把y的(IP address,UDP port,Node ID)資訊插入隊列尾部。

②如果該K桶的記錄項大于k個，則選擇頭部的記錄項（假如是節點z）進行RPC_PING操作。

• 如果z沒有響應，則從K桶中移除z的資訊，并把y的資訊插入隊列尾部。
• 如果z有響應，則把z的資訊移到隊列尾部，同時忽略y的資訊。

K桶的更新機制非常高效地實作了一種把最近看到的節點更新的政策，除非線上節點一直未從K桶中移出過。也就是說，線上時間長的節點具有較高的可能性繼續保留在K桶清單中。采用這種機制是基于對Gnutella網絡上大量使用者行為習慣的研究結果，即節點的線上機率與線上時長為正比關系，如圖2-2所示。

可以明顯看出，使用者線上時間越長，他在下一時段繼續線上的可能性就越高。是以，通過把線上時間長的節點留在K桶裡，可以明顯增加K桶中的節點在下一時間段仍然線上的機率，這利于保持KAD網絡的穩定性和減少網絡維護成本（不需要頻繁建構節點的路由表）。

（1）路由查詢機制

KAD技術最大特點之一就是能夠提供高效的節點查找機制，并且還可以通過參數調節查找的速度。假如節點x要查找ID值為t的節點，Kad按照如下遞歸操作步驟進行路由查找：

1）計算到t的距離：d(x,t)=x⊕t。

2）從x的第log(d)個K桶中取出個節點的資訊，同時進行FIND_NODE操作。如果這個K桶中的資訊少于個，則從附近多個桶中選擇距離最接近d的總共個節點。

3）對接受到查詢操作的每個節點，如果發現自己就是t，則回答自己是最接近t的；否則測量自己和t的距離，并從自己對應的K桶中選擇個節點的資訊給x。

4）x對新接收到的每個節點都再次執行FIND_NODE操作，此過程不斷重複執行，直到每一個分支都有節點響應自己是最接近t的。

5）通過上述查找操作，x得到了k個最接近t的節點資訊。

這裡強調，是k個最接近t的節點資訊，而不是完全資訊相等，因為網絡中可能根本不存在ID為t的節點。也是為權衡性能而設立的一個參數，就像K一樣。在BitTorrent實作中，取值為＝3。這個遞歸過程一直持續到x＝t，或者路由表中沒有任何關于t的資訊。由于每次查詢都能從更接近t的K桶中擷取資訊，這樣的機制保證了每一次遞歸操作都能夠至少獲得距離減半（或距離減少1bit）的效果，進而保證整個查詢過程的收斂速度為O(logN)，這裡N為網絡全部節點的數量。

上述是查詢節點ID的方法，對于檔案查詢也是一樣的方法。差別僅在于進行FIND_Value操作，查找自己是否儲存ID為t的檔案。檔案查詢過程的收斂速度同樣是O(LogN)。

（2）節點加入和離開

如果節點u要加入KAD網絡，它必須和一個已經在KAD網絡中的節點，比如w，取得聯系。u首先把w插入自己适當的K桶中，對自己的節點ID執行一次FIND_NODE操作，然後根據接收到的資訊更新自己的K桶内容。通過對自己鄰近節點由近及遠的逐漸查詢，u完成了仍然是空的K桶資訊的建構，同時也把自己的資訊釋出到其他節點的K桶中。在KAD網絡中，每個節點的路由表都表示為一棵二叉樹，葉子節點為K桶，K桶存放的是有相同ID字首的節點資訊，而這個字首就是該K桶在二叉樹中的位置。這樣，每個K桶都覆寫了ID空間的一部分，全部K桶的資訊加起來就覆寫了整個160bit的ID空間，而且沒有重疊。

以節點u為例，其路由表的生成過程如下：

1）最初，u的路由表為一個單個的K桶，覆寫了整個160bit ID空間。

2）當學習到新的節點資訊後，則u會嘗試把新節點的資訊，根據其字首值插入對應的K桶中。

①該K桶沒有滿，則新節點直接插入這個K桶中；

②該K桶已經滿了：如果該K桶覆寫範圍包含了節點u的ID，則把該K桶分裂為兩個大小相同的新K桶，并對原K桶内的節點資訊按照新的K桶字首值進行重新配置設定；如果該K桶覆寫範圍沒有包含節點u的ID，則直接丢棄該新節點資訊。

3）上述過程不斷重複，直到滿足路由表的要求。達到距離近的節點的資訊多、距離遠的節點的資訊少的結果，這樣就保證了路由查詢過程能快速收斂。

節點離開KAD網絡不需要釋出任何資訊，等待節點離線的時間足夠長，其他網絡節點通路它失效後，便會自動将其移出各自的路由表，那麼這一節點也就離開了。

2.1.2　Coral DSHT

Coral協定是在2004年，由紐約大學的Michael Freedman、Eric Freudenthal和David Nazieres發明的一套内容分發網絡系統（Content Delivery Network）。CDN的設計是為了避開網際網路傳輸瓶頸，并且降低内容供應伺服器的網絡壓力，使得内容能更快速、更穩定地傳遞給用戶端。CDN的基本思想是在網絡部署一些節點伺服器，并且建立一套虛拟網絡。網絡中節點伺服器之間實時更新連接配接資訊、延時資訊、使用者距離參數等，然後将使用者的請求重定向到最适合的節點伺服器上。這樣做有諸多好處，首先，通過節點伺服器中轉，使用者通路網頁的速度大大提高了；其次，節點伺服器會緩存内容伺服器的查詢資訊，那麼也降低了内容伺服器的網絡負載；最後，内容伺服器有可能出現暫時的離線，那麼使用者同樣能通過節點伺服器中的緩存讀取。

Coral DSHT則是Coral CDN最核心的部件之一。我們在2.1.1節中闡述過，Kademlia協定使用的是XOR距離，即資訊永遠是存儲在XOR距離最近的節點中。而這并沒有考慮實際網絡的情況，例如節點之間的延時、資料的位置。這樣會浪費大量網絡帶寬和存儲空間。Coral解決了這個問題，不同于經典的DHT方式，Coral首先對所有的節點評估連接配接情況，然後根據循環時間（Round-Trip Time）劃分為幾個等級（Coral中是3層），L2(<20ms)、L1(<60ms)、L0（其他）。Coral還提供了兩個操作接口，put和get，用于添加和查找一個鍵值對，以确定從哪一個等級的DSHT中查詢。後面我們會較長的描述它是如何實作的。

Coral DSHT（Distributed Sloppy hash table）适用于軟狀态的鍵值對檢索，也就是同一個Key可能會儲存多個Value。這種機制能把給定的Key映射到網絡中的Coral伺服器位址。比如，使用DSHT來查詢距離使用者較近的域名伺服器；查詢擁有特定網站緩存資訊的伺服器；定位周圍的節點來最小化請求延時。

1.索引機制和分層

Coral對路由表的處理也比較特殊，每一個Coral節點根據它們的延時特性放在不同的DSHT中。同一個DSHT的節點被稱為一個叢集（Cluster），每個叢集有一個最大延時時間，稱為叢集直徑（Diameter）。而整個系統會預先設定一個直徑，稱為等級（Level）。在每個等級劃分下，每個節點都會是某一個DSHT的成員。一組節點隻有滿足兩兩直徑小于第i個等級的極限時，它們才能成為一個叢集。在Coral中，将DSHT分成了三層，Level-2對應兩兩延時小于20毫秒，Level-1對應兩兩延時小于60毫秒，Level-0對應其他的全部節點。Coral在詢問時，也會優先請求等級更高、相應時間更短的節點。如果失敗了，才會在下一級節點中請求。這樣的設計不但降低了查詢的延時，也更可能優先獲得臨近節點的傳回資料。

2.基于鍵值對的路由層

Coral的鍵值對與Kademlia一樣，都是由SHA-1哈希計算得來的，有160bit。每個節點的ID是由它的IP位址通過SHA-1運算出來的。我們在此可以通過Put指令儲存一個對，用來表明Key和Value是接近的；也可以通過Get指令，來查詢對于同一個Key，節點的遠近順序如何。具體的計算方法和路由方法與在2.1.1節中講的Kademlia協定是一樣的。

3. Sloppy 存儲

在Kademlia協定中，資料會直接儲存到XOR更近的節點。但實際情況是，如果某些資料非常熱門，其他節點也會大量查詢，會是以造成擁塞，我們稱作Hot-Spot；同時，一個緩存鍵值對存儲了過多的值，我們稱其為Tree-saturation。Sloppy存儲就是希望規避這兩種情況發生。

每一個Coral節點定義有兩種異常狀态，Full和Loaded。Full狀态定義為：在目前節點R，已經存在L個對使得Key=k，并且這L個鍵值對的生存周期都大于新值的1/2。Loaded狀态定義為：對于給定的Key=k，在過去的一分鐘裡已經收到超過特定次請求。

那麼Coral在執行存儲操作的時候分為兩步進行。

第1步為前向查詢，Coral會持續疊代查找距離Key更近的節點ID，這一點和Kademlia協定完全一樣。每一個節點傳回兩個資訊，其一，該節點是否加載，其二，對于該Key，這一節點存儲有幾個Value，每一個Value的實效時間是多長。用戶端根據接收到的這些資訊決定這些節點是否可以存儲新的值。前向查詢的過程會一直繼續，直到用戶端找到一個距離Key值最近的可連接配接節點。如果對某個節點查詢異常，這一節點将不再繼續疊代查詢。可連接配接節點将被逐一壓進堆棧裡。

第2步為反向查詢，用戶端從第1步中得到了可以存放的節點清單。那麼按照距離Key從近到遠的順序，依次嘗試添加對到這些節點。如果操作失敗，比如在此時有其他節點也進行了插入，這一節點成為FULL狀态，那麼用戶端将放棄存儲這一節點，将其從堆棧内彈出，并嘗試下一個節點，直到被成功存儲。

取回的操作其實是存放操作的逆過程，在此不贅述。

2.1.3　S/Kademlia DHT

Kademlia用于完全開放的P2P網絡，如果不提供任何安全措施，它很容易受到來自惡意節點發動的各類攻擊。由此Ingmar Baumgart和Sebastian Mies二人設計了一種更安全的S/Kademlia（S/K）協定。基于Kademlia協定，S/K協定在節點ID中加入隐式身份認證和兄弟廣播（sibling Broadcast）。這樣，S/K就有能力抵禦常見的日蝕攻擊（eclipse attack）和女巫攻擊（Sybil attack）了。

1. Kademlia面臨的攻擊

按照受到攻擊的結構來看，攻擊主要分為兩類，第1類攻擊是針對路由表控制網絡中部分節點；第2類則是惡意消耗占用節點的資源。前者包括日蝕攻擊、女巫攻擊、流失攻擊（Churn attack）和對抗路由攻擊。

（1）日蝕攻擊

如果一個節點在網絡中能夠自由選擇它的ID，攻擊者可以在網絡中安放一些惡意節點，使得資訊都必須經由惡意節點傳遞。那麼這樣一來，惡意節點就能夠在網絡中将一個或幾個節點從網絡中隐藏掉。隻要惡意節點不能自由選擇ID或者很難通過政策修改其他節點的K-Bucket，這一攻擊就能避免了。我們從2.1.1節得知，KAD會優先請求K-Bucket中的長時間線上的節點，一旦被攻擊節點的K-Bucket是非滿的，惡意節點就有機會加入攻擊節點的K-Bucket，那麼攻擊者隻要擁有足夠長的線上時間就能實作攻擊了。

（2）女巫攻擊

在開放的對等網絡裡，攻擊者可以假冒多個ID，用少數網絡節點控制多個虛假身份。KAD網絡難以控制節點的數量，那麼攻擊者僞造大量虛假節點身份，就能控制部分網絡。通常情況下可以通過消耗一定的系統和計算資源提高女巫攻擊者的成本。當然，這也隻能改善并不能杜絕。

（3）流失攻擊

攻擊者擁有網絡的一些節點，即惡意節點，這可能會在網絡中引發大量流量流失，進而導緻網絡穩定性降低。

（4）對抗路由攻擊

惡意節點在收到查詢指令後，不是按照KAD的要求傳回距離Key最接近的網絡節點，而是轉移給同夥節點。同夥節點也做同樣的操作，而不傳回給查詢節點所需要的資訊，那麼這樣一來查詢就會失效。我們發現，整個過程中必須将查詢資訊傳遞給惡意節點，這一攻擊才能發動。那麼我們可以在查詢時，設計算法并行地查詢，并且每一條查詢路徑不相交。這樣一來，隻要并行查詢的路徑中有一條不碰到惡意節點，查詢就能成功了。

2. S/K防護方式

S/K協定就是做出了上述的幾個改進：為了避免日蝕攻擊和女巫攻擊，S/K需要節點不能自由選擇節點ID，不能大批量生成ID，同時不能竊取和僞裝其他節點的ID。這一方法可以通過非對稱加密確定節點身份不被竊取，我們可以設定一定的計算量障礙，強迫節點進行一定的哈希運算來確定不能自由選擇和批量生産ID。

為了避免對抗路由攻擊，我們需要并行查找不相交的路徑。

（1）安全的節點配置設定政策

S/K節點ID配置設定政策方案有3個要求：節點不能自由選擇其ID；不能生成多個ID；不能僞裝和竊取其他節點的ID。

為了實作這些要求，S/K設定了如下方法增加攻擊的難度。每個節點在接入前必須解決兩個密碼學問題，靜态問題是：産生一對公鑰和私鑰，并且将公鑰做兩次哈希運算後，具有c1個前導零。那麼公鑰的一次哈希值，就是這個節點的NodeID。動态問題是：不斷生成一個随機數X，将X與NodeID求XOR後再求哈希，哈希值要求有c2個前導零。靜态問題保證節點不再能自由選擇節點ID了，而動态問題則提高了大量生成ID的成本。那麼女巫攻擊和日蝕攻擊将難以進行。

為確定節點身份不被竊取，節點需要對發出的消息進行簽名。考慮安全性，可以選擇隻對IP位址和端口進行弱簽名；或者對整個消息進行簽名，以保證消息的完整性。在其他節點接收到消息時，首先驗證簽名的合法性，然後檢查節點ID是否滿足上述兩個難題的要求。我們發現，對于網絡其他節點驗證資訊的合法性，它的時間複雜度僅有(1)；但是對于攻擊者，為了生成這樣一個合法的攻擊資訊，其時間複雜度是（2c1+2c2）。合理選取c1和c2，就能有效避免這3種攻擊方式了。

（2）不相交路徑查找算法

在KAD協定中，我們進行一次查詢時，會通路節點中的個K-Bucket中的節點，這個K-Bucket是距離我們需要查詢的Key最近的。收到回複後，我們再進一步對傳回的節點資訊排序，選擇前個節點繼續疊代進行請求。很明顯，這樣做的缺點是，一旦傳回的其他節點資訊是一組惡意節點，那麼這個查詢很可能就會失敗了。

為解決這個問題，S/K提出的方案如下：每次查詢選擇k個節點，放入d個不同的Bucket中。這d個Bucket并行查找，Bucket内部查找方式和KAD協定完全相同。這樣一來，d條查找路徑就能做到不相交。對于任意一個Bucket，有失效的可能，但是隻要d個Bucket中有一條查詢到了所需要的資訊，這個過程就完成了。

通過不相交路徑查找，能解決對抗路由攻擊。S/K協定将Kademlia協定改進後，針對常見的攻擊，其安全性能大大提高了。

2.2　塊交換協定（BitTorrent）

BitTorrent是一種内容分發協定，它的開創者是美國程式員Bram Cohen（也是著名遊戲平台Steam的設計者）。BitTorrent采用内容分發和點對點技術，幫助使用者互相更高效地共享大檔案，減輕中心化伺服器的負載。BitTorrent網絡裡，每個使用者需要同時上傳和下載下傳資料。檔案的持有者将檔案發送給其中一個或多個使用者，再由這些使用者轉發給其他使用者，使用者之間互相轉發自己所擁有的檔案部分，直到每個使用者的下載下傳全部完成。這種方法可以減輕下載下傳伺服器的負載，下載下傳者也是上傳者，平攤帶寬資源，進而大大加快檔案的平均下載下傳速度。

2.2.1　BitTorrent術語含義

以下是BitTorrent中涉及的術語。

• torrent：它是伺服器接收的中繼資料檔案（通常結尾是.Torrent）。這個檔案記錄了下載下傳資料的資訊（但不包括檔案自身），例如檔案名、檔案大小、檔案的哈希值，以及Tracker的URL位址。
• tracker：是指網際網路上負責協調BitTorrent 用戶端行動的伺服器。當你打開一個torrent時，你的機器連接配接tracker，并且請求一個可以接觸的peers清單。在傳輸過程中，用戶端将會定期向tracker送出自己的狀态。tracker的作用僅是幫助peers互相達成連接配接，而不參與檔案本身的傳輸。
• peer：peer是網際網路上的另一台可以連接配接并傳輸資料的計算機。通常情況下，peer沒有完整的檔案。peer之間互相下載下傳、上傳。
• seed：有一個特定torrent完整拷貝的計算機稱為seed。檔案初次釋出時，需要一個seed進行初次共享。
• swarm：連接配接一個torrent的所有裝置群組。
• Chocking：Chocking阻塞是一種臨時的拒絕上傳政策，雖然上傳停止了，但是下載下傳仍然繼續。BitTorrent網絡下載下傳需要每個peer互相上傳，對于不合作的peer，會采取臨時的阻斷政策。
• Pareto效率：帕累托效率（Pareto efficiency）是指資源配置設定已經到了物盡其用的階段，對任意一個個體進一步提升效率隻會導緻其他個體效率下降。此時說明系統已經達到最優狀态了。
• 針鋒相對（Tit-fot-Tat）：又叫一報還一報，是博弈論中一個最簡單的政策。以合作開局，此後就采取以其人之道還治其人之身的政策。它強調的是永遠不先背叛對方，除非自己被背叛。在BitTorrent中表現為，Peer給自己貢獻多少下載下傳速度，那麼也就貢獻多少上傳速度給他。

2.2.2　P2P塊交換協定

1.内容的釋出

現在我們從流程上解釋，一個新檔案是如何在BitTorrent網絡上傳播的。新的檔案發行，需要從seed開始進行初次分享。首先，seed會生成一個擴充名為.torrent的檔案，它包含如下資訊：檔案名、大小、tracker的URL。一次内容釋出至少需要一個tracker和一個seed，tracker儲存檔案資訊和seed的連接配接資訊，而seed儲存檔案本身。一旦seed向tracker注冊，它就開始等待為需要這個torrent的peer上傳相關資訊。通過.torrent檔案，peer會通路tracker，擷取其他peer/seed的連接配接資訊，例如IP和端口。tracker和peer之間隻需要通過簡單的遠端通信，peer就能使用連接配接資訊，與其他peer/seed溝通，并建立連接配接下載下傳檔案。

2.分塊交換

前面我們提到，peer大多是沒有完整的拷貝節點的。為了跟蹤每個節點已經下載下傳的資訊有哪些，BitTorrent把檔案切割成大小為256KB的小片。每一個下載下傳者需要向他的peer提供其擁有的片。為了確定檔案完整傳輸，這些已經下載下傳的片段必須通過SHA-1算法驗證。隻有當片段被驗證是完整的時，才會通知其他peer自己擁有這個片段，可以提供上傳。

3.片段選擇算法

上面我們發現，BitTorrent内容分享的方式非常簡單實用。但是，直覺上我們會發現如何合理地選擇下載下傳片段的順序，對提高整體的速度和性能非常重要。如果某片段僅在極少數peer上有備份，則這些peer下線了，網絡上就不能找到備份了，所有peer都不能完成下載下傳。針對這樣的問題，BitTorrent提供了一系列片段選擇的政策。

• 優先完成單一片段：如果請求了某一片段的子片段，那麼本片段會優先被請求。這樣做是為了盡可能先完成一個完整的片段，避免出現每一個片段都請求了同一個子片段，但是都沒有完成的情況。
• 優先選擇稀缺片段：選擇新的片段時，優先選擇下載下傳全部peer中擁有者最少的片段。擁有者最少的片段意味着是大多數peer最希望得到的片段。這樣也就降低了兩種風險，其一，某個peer正在提供上傳，但是沒有人下載下傳（因為大家都有了這一片段）；其二，擁有稀缺片段的peer停止上傳，所有peer都不能得到完整的檔案。
• 第一個片段随機選擇：下載下傳剛開始進行的時候，并不需要優先最稀缺的。此時，下載下傳者沒有任何片斷可供上傳，是以，需要盡快擷取一個完整的片斷。而最少的片斷通常隻有某一個peer擁有，是以，它可能比多個peer都擁有的那些片斷下載下傳得慢。是以，第一個片斷是随機選擇的，直到第一個片斷下載下傳完成，才切換到“優先選擇稀缺片段”的政策。
• 結束時取消子片段請求：有時候，遇到從一個速率很慢的peer請求一個片斷的情況，在最後階段，peer向它的所有的peer都發送對某片斷的子片斷的請求，一旦某些子片斷到了，那麼就會向其他peer發送取消消息，取消對這些子片斷的請求，以避免浪費帶寬。

2.2.3　阻塞政策

不同于HTTP協定，BitTorrent中檔案分享完全依賴每個peer，是以每個peer都有義務來共同提高共享的效率。對于合作者，會根據對方提供的下載下傳速率給予同等的上傳速率回報。對于不合作者，就會臨時拒絕對它的上傳，但是下載下傳依然繼續。阻塞算法雖不在P2P協定的範疇，但是對提高性能是必要的。一個好的阻塞算法應該利用所有可用的資源，為所有下載下傳者提供一緻可靠的下載下傳速率，并适當懲罰那些隻下載下傳而不上傳的peer，以此來達到帕累托最優。

1. BitTorrent的阻塞算法

某個peer不可能與無限個peer進行連接配接，通常情況隻能連接配接4個peer。那麼怎麼控制才能決定選擇哪些peer連接配接使得下載下傳速度達到最優？我們知道，計算目前下載下傳速度其實很難，比如使用20秒輪詢方式來估計，或者從長時間網絡流量來估計，但是這些方法都不太可行，因為流量随着時間産生的變化太快了。頻繁切換阻塞/連接配接的操作本身就會帶來很大的資源浪費。BitTorrent網絡每10秒重新計算一次，然後維持連接配接狀态到下一個10秒才會計算下一次。

2.最優阻塞

如果我們隻考慮下載下傳速度，就不能從目前還沒有使用的連結中去發現可能存在的更好的選擇。那麼，除了提供給peer上傳的連結，還有一個始終暢通的連結叫最優阻塞。不論目前的下載下傳情況如何，它每間隔30秒就會重新計算一次哪一個連結應該是最優阻塞。30秒的周期足夠達到最大上傳和下載下傳速率了。

3.反對歧視

在特殊情況下，某個peer可能被全部的peer阻塞了，那麼很顯然，通過上面的方法，它會一直保持很低的下載下傳速度，直到經曆下一次最優阻塞。為了減少這種問題，如果一段時間過後，從某個peer那裡一個片斷也沒有得到，那麼這個peer會認為自己被對方“怠慢”了，于是不再為對方提供上傳。

4.完成後的上傳

一旦某個peer完成下載下傳任務了，就不再以它的下載下傳速率決定為哪些peer提供上傳服務。至此開始，該peer優先選擇網絡環境更好、連接配接速度更快的其他peer，這樣能更充分地利用上傳帶寬。

2.3　版本控制（Git）

1.版本控制類型

版本控制系統是用于記錄一個或若幹檔案内容變化，以便将來查閱特定版本修訂情況的系統。例如我們在做開發時，版本控制系統會幫我們實作對每一次修改的備份，可以友善地回到之前的任意一個版本。實作版本控制的軟體有很多種類，大緻可以分為三類：本地版本控制系統、中心化版本控制系統、分布式版本控制系統。

（1）本地版本控制系統

許多人習慣用複制整個項目目錄的方式來儲存不同的版本，或許還會改名加上備份時間以示差別。這麼做唯一的好處就是簡單，但是特别容易犯錯。有時候會混淆所在的工作目錄，一不小心會寫錯檔案或者覆寫其他檔案。為了解決這個問題，人們很久以前就開發了許多種本地版本控制系統，大多都是采用某種簡單的資料庫來記錄檔案的曆次更新差異。

其中最流行的一種稱為RCS，現今許多計算機系統上都還能看到它的蹤影。甚至在流行的 Mac OS X 系統上安裝了開發者工具包之後，也可以使用 RCS指令。它的工作原理是在硬碟上儲存更新檔集（更新檔是指檔案修訂前後的變化）；通過應用所有的更新檔，可以重新計算出各個版本的檔案内容。

（2）中心化版本控制系統

接下來人們又遇到一個問題：如何讓不同系統上的開發者協同工作？于是，中心化版本控制系統（Centralized Version Control Systems，CVCS）應運而生，如圖2-3所示。這類系統，諸如 CVS、Subversion 及 Perforce 等，都有一個單一的集中管理的伺服器，儲存所有檔案的修訂版本，而協同工作的人們都通過用戶端連到這台伺服器，取出最新的檔案或者送出更新。多年以來，這已成為版本控制系統的标準做法。

這種做法帶來了許多好處，特别是相較于老式的本地VCS有優勢。每個人都可以在一定程度上看到項目中的其他人正在做些什麼，而管理者也可以輕松掌控每個開發者的權限。并且管理一個 CVCS 要遠比在各個用戶端上維護本地資料庫來得輕松容易。這種方案最顯而易見的缺點是中央伺服器的單點故障。如果中央伺服器當機1小時，那麼在這1小時内，誰都無法送出更新，也就無法協同工作。如果中心資料庫所在的磁盤發生損壞，又沒有及時做備份，毫無疑問你将丢失所有資料，包括項目的整個變更曆史，隻剩下人們在各自機器上保留的單獨快照。本地版本控制系統也存在類似問題，隻要整個項目的曆史記錄被儲存在單一位置，就有丢失所有曆史更新記錄的風險。

（3）分布式版本控制系統

為了避免中心化版本控制系統單點故障的風險，分布式版本控制系統（Distributed Version Control System，DVCS）面世了。這類系統有Git、Mercurial、Bazaar及Darcs等，用戶端并不隻提取最新版本的檔案快照，而是把代碼倉庫完整地鏡像下來。它的系統架構如圖2-4所示。這麼一來，任何一處協同工作用的伺服器發生故障，事後都可以用任何一個鏡像出來的本地倉庫恢複。因為每一次的克隆操作，實際上都是一次對代碼倉庫的完整備份。

更進一步，許多這類系統都可以指定與若幹不同的遠端代碼倉庫進行互動。借此，你就可以在同一個項目中，分别和不同工作小組的人互相協作。你可以根據需要設定不同的協作流程，比如層次模型式的工作流，而這在以前的集中式系統中是無法實作的。

2.快照流

Git和其他版本控制系統的主要差别在于Git儲存資料的方法。從概念上來區分，其他大部分系統以檔案變更清單的方式存儲資訊，這類系統（CVS、Subversion、Perforce、Bazaar 等）将它們儲存的資訊看作一組随時間逐漸累積的檔案差異關系，如圖2-5所示。

Git不按照以上方式儲存資料。反之，Git 更像把資料看作對小型檔案系統的一組快照，如用2-6所示。每次你送出更新或在Git中儲存項目狀态時，它将為全部檔案生成一個快照并儲存這個快照的索引。為了效率，如果檔案沒有修改，Git不再重新存儲該檔案，而是隻保留一個連結指向之前存儲的檔案。Git 儲存資料的方式更像是一個快照流。

Git存儲的是資料随時間改變的快照。

這是Git與其他版本控制系統的重要差別。是以 Git 綜合考慮了以前每一代版本控制系統延續下來的問題。Git更像一個小型的檔案系統，提供了許多以此為基礎建構的優秀工具，而不隻是一個簡單的版本控制系統。稍後我們在讨論Git分支管理時，将探究這種方式帶來的好處。

3.本地執行操作

在Git中的絕大多數操作都隻需要通路本地檔案和資源，一般不需要來自網絡上其他計算機的資訊。相比于中心化版本控制系統嚴重的網絡延時，在本地加載Git要快許多。因為你在本地磁盤上就有項目的完整曆史，是以大部分操作看起來瞬間就完成了。

舉個例子，要浏覽項目的曆史，Git不需外連到伺服器去擷取曆史，然後再顯示出來，它隻需直接從本地資料庫中讀取，你就能立即看到項目曆史。如果你想檢視目前版本與一個月前的版本之間引入的修改，Git會查找到一個月前的檔案做一次本地的差異計算，而不是由遠端伺服器處理或從遠端伺服器拉回舊版本檔案再在本地處理。

這也意味着當你處于離線狀态時，也可以進行幾乎所有的操作。比如：在飛機或火車上想做些工作，你能愉快地送出，直到有網絡連接配接時再上傳；回家後 VPN 用戶端不正常，你仍能工作。而使用其他系統，做到如此是不可能的或很費力的。比如，用 Perforce，你沒有連接配接伺服器時幾乎不能做任何事；用 Subversion 和 CVS，你能修改檔案，但不能向資料庫送出修改（因為你的本地資料庫離線了）。這看起來不是大問題，但是你可能會驚喜地發現它帶來的巨大的不同。

4.隻添加資料

我們所執行的 Git 操作，本質都是在 Git 資料庫中增加操作資料。Git上的操作幾乎都是可逆的。同其他 VCS 一樣，未送出更新将有可能丢失或弄亂修改的内容；一旦你将修改快照送出到 Git 系統中，就難再丢失資料。這使得 Git 在版本控制領域成為一個非常優秀的工具，因為我們可以盡情做各種修改嘗試，而仍有回流的機會。

5.完整性校驗

Git中所有資料在存儲前都會計算校驗和，然後以校驗和來引用。這意味着不可能在 Git 不知情時更改任何檔案内容或目錄内容。這個功能由 Git 在底層實作。若你在編輯過程中丢失資訊或損壞檔案，Git就能發現。

Git用以計算校驗的雜湊演算法是SHA-1。Git會将檔案的内容或目錄結構一同計算，得出它們的哈希值，確定檔案和路徑的完整性。Git 中使用這種哈希值的情況很多，你将經常看到這種哈希值。實際上，Git 資料庫中儲存的資訊都是以檔案内容的哈希值來索引的，而不是檔案名。

6.工作區與工作狀态

Git有3種狀态，你的檔案可能處于其中之一：已送出（committed）、已修改（modified）和已暫存（staged）。已送出表示資料已經安全地儲存在本地資料庫中；已修改表示修改了檔案，但還沒儲存到資料庫中；已暫存表示對一個已修改檔案的目前版本做了标記，使之包含在下次送出的快照中。

由此引入Git項目的3個工作區域的概念：工作目錄、Git倉庫及暫存區域。Git倉庫包括本地倉庫和遠端倉庫。

1）工作目錄：直接編輯修改的目錄。工作目錄是将項目中某個版本獨立提取出來的内容放在磁盤上供你使用或修改。

2）Git 倉庫：儲存項目的中繼資料和對象資料庫。這是 Git 中最重要的部分，從其他計算機複制倉庫時，複制的就是這裡的資料。

3）暫存區域：是一個檔案，儲存了下次将送出的檔案清單資訊，一般在 Git 倉庫中。有時候也被稱作“索引”，不過一般還是叫暫存區域。

定義了這3個工作區域，工作流程就很清晰了。基本的Git工作流程如下：

1）在工作目錄中修改檔案。

2）暫存檔案，将檔案的快照放入暫存區域。

3）送出更新，找到暫存區域的檔案，将快照永久性存儲到 Git 倉庫。

如果Git倉庫中儲存着的特定版本檔案，就屬于已送出狀态。如果做了修改并已放入暫存區域，就屬于已暫存狀态。如果自上次取出後，做了修改但還沒有放到暫存區域，就是已修改狀态。

7.分支

為了了解Git分支的實作方式，我們需要回顧一下Git是如何儲存資料的。Git儲存的不是檔案差異或者變化量，而是一系列檔案快照。在 Git中送出時，會儲存一個送出（commit）對象，該對象包含一個指向暫存内容快照的指針，包含本次送出的作者等相關附屬資訊，包含零個或多個指向該送出對象的父對象指針：首次送出是沒有直接祖先的，普通送出有一個祖先，由兩個或多個分支合并産生的送出則有多個祖先。

為直覺起見，我們假設在工作目錄中有3個檔案，準備将它們暫存後送出。暫存操作會對每一個檔案計算校驗和，然後把目前版本的檔案快照儲存到 Git 倉庫中（Git使用blob類型的對象存儲這些快照），并将校驗和加入暫存區域。

$ git add README test.rb LICENSE

$ git commit -m 'initial commit of my project'

當使用git commit建立一個送出對象前，Git 會先計算每一個子目錄（本例中就是項目根目錄）的校驗和，然後在 Git 倉庫中将這些目錄儲存為樹（tree）對象。之後 Git 建立的送出對象，除了包含相關送出資訊以外，還包含着指向這個樹對象（項目根目錄）的指針，如此它就可以在将來需要的時候，重制此次快照的内容了。

現在，Git倉庫中有5個對象：3個表示檔案快照内容的 blob 對象；1個記錄着目錄樹内容及其中各個檔案對應 blob 對象索引的 tree 對象；以及1個包含指向 tree 對象（根目錄）的索引和其他送出資訊中繼資料的 commit 對象。概念上來說，倉庫中的各個對象儲存的資料和互相關系看起來如圖2-7所示。

做些修改後再次送出，那麼這次的送出對象會包含一個指向上次送出對象的指針。兩次送出後，倉庫曆史會變成圖2-8所示的樣子。

現在來談分支。Git中的分支本質上僅是個指向commit對象的可變指針。Git使用 master 作為分支的預設名字。第一個分支也常被稱為主幹。主幹可被克隆為其他分支，每條分支的可變指針在每次送出時都會自動向前移動，如

圖2-9所示。

2.4　自驗證檔案系統（SFS）

自驗證檔案系統（Self-Certifying File System，SFS）是由David Mazieres和他的導師M. Frans Kaashoek在其博士論文中提出的。SFS是為了設計一套整個網際網路共用的檔案系統，全球的SFS系統都在同一個命名空間下。在SFS中，分享檔案會變得十分簡單，隻需要提供檔案名就行了。任何人都能像Web一樣，搭建起SFS伺服器，同時任意一個用戶端都能連接配接網絡中任意一個伺服器。

直覺上，我們可以感受到，要實作一個全球共享的檔案系統，最大的障礙莫過于如何讓服務端為用戶端提供認證。一個我們能想到的思路就是每個伺服器都使用非對稱加密，生成一對私鑰和公鑰。用戶端使用伺服器的公鑰來驗證伺服器的安全連接配接。那麼這樣又有一個新問題，如何讓用戶端在最初獲得伺服器的公鑰呢？在不同的需求場景下，使用者對密鑰管理的要求是不同的，又如何實作密鑰管理的可擴充性呢？

SFS則使用了一種解決方案，一種新的方式，它将公鑰資訊嵌入檔案名中，這個做法命名為“自驗證檔案名”。那麼顯然，這樣做以後我們就無須在檔案系統内部實作密鑰管理了。這部分密鑰管理的功能可以加入使用者對檔案命名的規則中。這樣一來給使用者的加密方式帶來很多便利，使用者可以根據需求，自行選擇需要的加密方式。

SFS核心思想有如下幾點：

• SFS檔案系統具備自驗證路徑名稱，不需要在檔案系統内部實作密鑰管理。
• 在SFS上易于架設各種密鑰管理機制，包括各類組合機制。
• SFS将密鑰管理與密鑰分發解耦。
• 實作全球範圍的檔案系統。

2.4.1　SFS設計

1.安全性

SFS系統的安全性可以由兩部分定義：檔案系統本身的安全性和密鑰管理的安全性。換句話說，安全性意味着攻擊者未經許可不能讀取或者修改檔案系統；而對于使用者的請求，檔案系統一定會給使用者傳回正确的檔案。

• 檔案系統本身的安全性：SFS除非明确指明允許匿名通路，否則使用者如果需要讀取、修改、删除或者對檔案進行任何篡改，都需要提供正确的密鑰。用戶端與伺服器始終在加密的安全通道中進行通信，通道需要確定雙方的身份，以及資料完整性和實時性（避免攻擊者截獲資料包，并将其重新發送，欺騙系統，這稱為重播攻擊）。
• 密鑰管理的安全性：僅僅依靠檔案系統的安全保護并不能滿足使用者的各類需求，使用者可以使用密鑰管理來達到更進階别的安全性。使用者可以使用預先設定的私鑰，或使用多重加密，再或者使用由第三方公司提供的檔案系統來通路經過認證的檔案伺服器。使用者可以從中靈活、輕松地建構各種密鑰管理機制。

2.可擴充性

因為SFS定位是全球範圍共享的檔案系統，是以SFS應該具有良好的可擴充性能。無論使用者是希望以密碼認證方式讀取個人檔案，還是浏覽公共伺服器上的内容，SFS都應該能很好地相容。

在SFS系統的設計中，任何在Internet網絡内擁有域名或IP位址的伺服器，都能部署為SFS伺服器，并且過程十分簡單，甚至無須請求注冊權限。SFS通過3個屬性實作它的擴充：全網共享的命名空間，用于實作密鑰管理的原語集， 以及子產品化設計。

• 全局命名空間：在任意一個用戶端登入的SFS都具有相同的命名空間。雖然SFS中在每個用戶端都會共享相同的檔案，但是沒有任何人能控制全局的命名空間；每個人都能添加新的伺服器到這個命名空間裡。
• 密鑰管理的原語集：SFS還允許使用者在檔案名解析期間使用任意算法來查找和驗證公鑰。不同的使用者可以采用不同的技術認證相同的伺服器；SFS允許他們安全地共享檔案緩存。
• 子產品化設計：用戶端和伺服器在設計時就大量使用了子產品化設計，程式之間大多使用設計好的接口進行通信。這樣，更新疊代系統各個部分，或者添加新的功能特性會非常簡單。

2.4.2　自驗證檔案路徑

自驗證檔案系統的一個重要的特性，就是在不依賴任何外部資訊的條件下，利用加解密來控制權限。這是因為，如果SFS使用本地配置檔案，那麼顯然這與全局檔案系統的設計相悖；如果使用一個中心化伺服器來輔助連接配接，使用者可能産生不信任。那麼，如何在不依賴外部資訊的情況下，來安全地擷取檔案資料呢？SFS提出了一種新的方式，即通過可以自我證明身份的路徑名實作。

SFS路徑中包含了構成與指定伺服器建構連接配接的需要的全部資訊，例如網絡位址和公鑰。SFS檔案路徑包含3部分：

（1）伺服器位置

告知SFS用戶端檔案系統伺服器的位址，它可以是IP位址或者DNS主機名。

（2）HostID

告知SFS如何與伺服器建構安全的連接配接通道。為了確定連接配接的安全性，每個SFS用戶端都有一個公鑰，而Host ID通常設定為主機名與公鑰的哈希。通常情況下，SFS會按照SHA-1函數計算。

使用SHA-1主要考慮了計算的簡易性，以及一個能接受的安全等級。SHA-1的輸出是固定的20位元組，它比公鑰短得多。同時SHA-1能為SFS提供足夠的密碼學保護，找到一對合法的伺服器位置與公鑰對來滿足要求，它的構造難度非常大。

（3）在遠端伺服器上檔案的位址

前面兩個資訊是為了找到目标伺服器并建構安全連接配接，最後隻需要提供檔案的位置、定位需求的檔案即可。整個自驗證檔案路徑的形式如下：

即給定一個IP位址或域名作為位置，給定一個公鑰/私鑰對，确定相應的Host ID，運作SFS伺服器軟體，任何一個伺服器都能通過用戶端将自己加入SFS中，而無須進行任何的注冊過程。

2.4.3　使用者驗證

自驗證的路徑名能幫助使用者驗證伺服器的身份，而使用者驗證子產品則是幫助伺服器驗證哪些使用者是合法的。與伺服器身份驗證一樣，找到一種能用于所有使用者身份驗證的方法同樣是很難達到的。是以SFS把使用者身份驗證與檔案系統分開。外部軟體可以根據伺服器的需求來設計協定驗證使用者。

SFS引入了Agent用戶端子產品來負責使用者認證工作。當使用者第一次通路SFS檔案系統時，用戶端會加載通路并通知Agent這一事件。然後，Agent會向遠端伺服器認證這個使用者。從伺服器角度來看，這部分功能從伺服器搬到了一個外部認證的通道。Agent和認證伺服器之間通過SFS傳遞資訊。如果驗證者拒絕了驗證請求，Agent可以改變認證協定再次請求。如此一來，可以實作添加新的使用者驗證資訊卻不需要修改實際的真實檔案系統。如果使用者在檔案伺服器上沒有注冊過，Agent在嘗試一定次數以後拒絕使用者的身份驗證，并且将授權使用者以匿名方式檔案系統。另外，一個Agent也能友善地通過多種協定連接配接任意給定的伺服器，這些設計都會非常友善、快捷和靈活。

2.4.4　密鑰撤銷機制

有些時候伺服器的私鑰可能會被洩露，那麼原有的自驗證檔案路徑可能會錯誤地定位到惡意攻擊者設定的伺服器。為了避免這種情況發生，SFS提供了兩種機制來控制： 密鑰撤銷指令和Host ID阻塞。密鑰撤銷指令隻能由檔案伺服器的擁有者發送，它的發送目标是全部的使用者。這一指令本身是自驗證的。而Host ID阻塞是由其他節點發送的，可能與檔案伺服器擁有者沖突，每一個驗證的Agent可以選擇服從或者不服從Host ID阻塞的指令。如果選擇服從，對應的Host ID就不能被通路了。

密鑰撤銷指令的形式如下：

在這裡PathRevoke字段是一個常量；Location是需要撤銷密鑰的自驗證路徑名稱；NULL是為了保持轉發指針指令的統一性，在這裡将轉發指針指向一個空路徑，意味着原有指針失效了；這裡Public_Key是失效前的公鑰；Secret_Key是私鑰。這一條資訊能夠確定撤銷指令是由伺服器所有者簽發的。

當SFS用戶端軟體看到吊銷證書時，任何要求通路撤銷位址的請求都會被禁止。服務端會通過兩種方式擷取密鑰撤銷指令：SFS連接配接到伺服器的時候，如果通路到已經撤銷的位址或路徑，它會收到由伺服器傳回的密鑰撤銷指令；使用者初次進行自認證路徑名時，用戶端會要求Agent檢查其是否已經被撤銷，Agent會傳回相應的結果。撤銷指令是自驗證的，是以分發撤銷指令并不是那麼重要，我們可以很友善地請求其他源頭發送的撤銷指令。

2.5　Merkle DAG和Merkle Tree

對于IPFS，Merkle DAG和Merkle Tree是兩個很重要的概念。Merkle DAG是IPFS的存儲對象的資料結構，Merkle Tree則用于區塊鍊交易的驗證。Merkle Tree通常也被稱為哈希樹（Hash Tree），顧名思義，就是存儲哈希值的一棵樹；而Merkle DAG是默克爾有向無環圖的簡稱。二者有相似之處，也有一些差別。

從對象格式上，Merkle Tree的葉子是資料塊（例如，檔案、交易）的哈希值。非葉節點是其對應子節點串聯字元串的哈希。Merkle DAG的節點包括兩個部分，Data和Link；Data為二進制資料，Link包含Name、Hash和Size這3個部分。從資料結構上看，Merkle DAG是Merkle Tree更普适的情況，換句話說，Merkle Tree是特殊的Merkle DAG。從功能上看，後者通常用于驗證資料完整性，而前者大多用于檔案系統。

下面我們對這兩種資料結構和用法詳細解釋。

2.5.1　Merkle Tree

1. Hash

Hash是一個把任意長度的資料映射成固定長度資料的函數。例如，對于資料完整性校驗，最簡單的方法是對整個資料做Hash運算，得到固定長度的Hash值，然後把得到的Hash值公布在網上，這樣使用者下載下傳到資料之後，對資料再次進行Hash運算，将運算結果與網上公布的Hash值進行比較，如果兩個Hash值相等，說明下載下傳的資料沒有損壞。可以這樣做是因為輸入資料的任何改變都會引起Hash運算結果的變化，而且根據Hash值反推原始輸入資料是非常困難的。如果從穩定的伺服器進行資料下載下傳，采用單一Hash進行驗證是可取的。但現實中資料的下載下傳會發生各種意外，如連結中斷。一旦資料損壞，就需要重新下載下傳，這種下載下傳方式的效率低下。

2. Hash List

在點對點網絡中做資料傳輸的時候，會同時從多個機器上下載下傳資料，而且可以認為很多機器是不穩定或者不可信的。為了校驗資料的完整性，更好的辦法是把大的檔案分割成小的資料塊（例如，分割成2KB為機關的資料塊）。這樣的好處是，如果小塊資料在傳輸過程中損壞了，那麼隻要重新下載下傳這一塊資料即可，不需要重新下載下傳整個檔案。那麼，如何确定資料塊的完整性呢？隻需要為每個資料塊計算Hash值。BT下載下傳的時候，在下載下傳到真正資料之前，我們會先下載下傳一個Hash清單。那麼問題又來了，怎麼确定這個Hash清單本身是正确的呢？答案是把每個小塊資料的Hash值拼到一起，然後對這個長字元串再做一次Hash運算，這樣就得到Hash清單的根Hash（Top Hash或Root Hash）。下載下傳資料的時候，首先從可信的資料源得到正确的根Hash，就可以用它來校驗Hash清單了，然後即可通過校驗後的Hash清單校驗資料塊的完整性。

3. Merkle Tree

Merkle Tree可以看作Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree，即樹高為2的多叉Merkle Tree）。

在最底層，和Hash清單一樣，把資料分成小的資料塊，有相應的Hash與它對應。但是往上走，并不是直接去運算根Hash，而是把相鄰的兩個Hash合并成一個字元串，然後運算這個字元串的Hash。這樣每兩個Hash就“結婚生子”，得到了一個“子Hash”。如果最底層的Hash總數是單數，那到最後必然出現一個“單身Hash”，這種情況就直接對它進行Hash運算，是以也能得到它的“子Hash”。于是往上推，依然是一樣的方式，可以得到數目更少的新一級Hash，最終形成一棵倒挂的樹，樹根位置就是樹的根Hash，我們把它稱為Merkle Root。

在P2P網絡下載下傳之前，先從可信的源獲得檔案的Merkle Tree樹根。一旦獲得了樹根，就可以從其他從不可信的源擷取Merkle Tree。通過可信的樹根來檢查接收到的Merkle Tree。如果Merkle Tree是損壞的或者是虛假的，就從其他源獲得另一個Merkle Tree，直到獲得一個與可信樹根比對的Merkle Tree。

4. Merkle Tree的特點

Merkle Tree是一種樹，大多數是二叉樹，也可以是多叉樹。無論是幾叉樹，它都具有樹結構的所有特點。

1）Merkle Tree的葉子節點的value是資料集合的單中繼資料或者單中繼資料Hash。

2）非葉子節點的value是根據它下面所有的葉子節點值，按照雜湊演算法計算而得出的。

通常，使用雜湊演算法（例如：SHA-2 和 MD5）來生成資料的Hash值。但如果目的僅僅是防止資料不被蓄意的損壞或篡改，可以使用安全性低但效率高的校驗算法，如CRC。

Merkle Tree和Hash List的主要差別是，可以直接下載下傳并立即驗證Merkle Tree的一個分支。因為可以将檔案切分成小的資料塊，這樣如果有一塊資料損壞，僅僅重新下載下傳這個資料塊就行了。如果檔案非常大，那麼Merkle Tree和Hash List都很大，但是Merkle Tree可以一次下載下傳一個分支，然後立即驗證這個分支，如果分支驗證通過，就可以下載下傳資料了；而Hash List隻有下載下傳整個Hash List才能驗證。

5. Merkle Tree的應用

• 數字簽名：最初Merkle Tree的目的是高效處理Lamport單次簽名。每一個Lamport密鑰隻能被用來簽名一個消息，但是與Merkle Tree結合起來可以簽名多個消息。這種方法成為一種高效的數字簽名架構，即Merkle簽名方法。
• P2P網絡：在P2P網絡中，Merkle Tree用來確定從其他節點接收的資料塊沒有損壞且沒有被替換，甚至檢查其他節點不會欺騙或者釋出虛假的塊。在2.2節中，我們提到了BitTorrent使用P2P技術來讓用戶端之間進行資料傳輸，一來可以加快資料下載下傳速度，二來減輕下載下傳伺服器的負擔。一個相關的問題是大資料塊的使用，因為為了保持torrent檔案非常小，那麼資料塊Hash的數量也得很小，這就意味着每個資料塊相對較大。大資料塊影響節點之間進行交易的效率，因為隻有當大資料塊全部下載下傳下來并通過校驗後，才能與其他節點進行交易。為解決上面兩個問題：用一個簡單的Merkle Tree代替Hash List。設計一個層數足夠多的滿二叉樹，葉節點是資料塊的Hash，不足的葉節點用0來代替。上層的節點是其對應孩子節點串聯的Hash。Hash算法和普通torrent一樣采用SHA-1。
• 比特币：Merkle Proof最早的應用是Bitcoin（比特币），它是由中本聰在2009年描述并建立的。Bitcoin的Blockchain利用Merkle proofs來存儲每個區塊的交易。而這樣做的好處也就是中本聰描述到的“簡化支付驗證”（Simplified Payment Verification，SPV）的概念：一個“輕用戶端”（light client）可以僅下載下傳鍊的區塊頭，即每個區塊中的80位元組的資料塊，僅包含5個元素，而不是下載下傳每一筆交易以及每一個區塊。5個元素為上一區塊頭的Hash值、時間戳、挖礦難度值、工作量證明随機數（nonce）以及包含該區塊交易的Merkle Tree的根Hash。

如果用戶端想要确認一個交易的狀态，它隻需簡單地發起一個Merkle Proof請求，這個請求顯示出這個特定的交易在Merkle Tree的一個葉子節點之中，而且這個Merkle Tree的樹根在主鍊的一個區塊頭中。但是Bitcoin的輕用戶端有它的局限。一個局限是，盡管它可以證明包含的交易，但是它不能進行涉及目前狀态的證明（如數字資産的持有、名稱注冊、金融合約的狀态等）。Bitcoin如何查詢你目前有多少币？一個比特币輕用戶端可以使用一種協定，它涉及查詢多個節點，并相信其中至少會有一個節點會通知你關于你的位址中任何特定的交易支出，而這可以讓你實作更多的應用。但對于其他更為複雜的應用而言，這些是遠遠不夠的。影響一筆交易的确切性質（precise nature），取決于此前的幾筆交易，而這些交易本身則依賴于更為前面的交易，是以最終你可以驗證整個鍊上的每一筆交易。

2.5.2　Merkle DAG

Merkle DAG的全稱是 Merkle Directed Acyclic Graph（默克有向無環圖）。它是在Merkle Tree的基礎上建構的，Merkle Tree由美國計算機學家Merkle于1979年申請了專利。Merkle DAG跟Merkle tree很相似，但不完全一樣，比如Merkle DAG不需要進行樹的平衡操作、非葉子節點允許包含資料等。Merkle DAG是IPFS的核心概念。Merkle DAG也是Git、Bitcoin和dat等技術的核心。散列樹由内容塊組成，每個内容塊由其加密散列辨別。你可以使用其散列引用這些塊中的任何一個，這允許你建構使用這些子塊的散列引用其“子塊”的塊樹。ipfs add指令将從你指定的檔案的資料中建立Merkle DAG。執行此操作時，它遵循unixfs資料格式。這意味着你的檔案被分解成塊，然後使用“連結節點”以樹狀結構排列，以将它們連接配接在一起。給定檔案的“散列”實際上是DAG中根節點（最上層）的散列。

1. Merkle DAG的功能

Merkle DAG在功能上與Merkle Tree有很大不同， 上面我們提到Merkle Tree主要是為了驗證，例如驗證數字簽名，以及比特币Merkle Proof。而對于Merkle DAG，它的目的有如下3個。

• 内容尋址：使用多重Hash來唯一識别一個資料塊的内容。
• 防篡改：可以友善地檢查Hash值來确認資料是否被篡改。
• 去重：由于内容相同的資料塊Hash值是相同的，很容易去掉重複的資料，節省存儲空間。

其中第3條是IPFS系統最為重要的一個特性，在IPFS系統中，每個Blob的大小限制在256KB（暫定為256KB，這個值可以根據實際的性能需求進行修改）以内，那些相同的資料就能通過Merkle DAG過濾掉，隻需增加一個檔案引用，而不需要占據存儲空間。

2.資料對象格式

在IPFS中定義了Merkle DAG的對象格式。IPFS Object是存儲結構，我們前面提到IPFS會限制每個資料大小在256KB以内。在IPFS Object對象裡，我們儲存有兩個部分，一個是Link，用于儲存其他的分塊資料的引用；另一個是data，為本對象内容。Link主要包括3個部分，分别是Link的名字、Hash和Size，如以下代碼所示。在這裡Link隻是對一個IPFS Object的引用，它不再重複存儲一個IPFS對象了。

使用Git和Merkle DAG的集合會極大減少存儲空間消耗。這是因為，對源檔案的修改如果使用Merkle DAG來存儲，那麼修改的内容可能隻是很少的一部分。我們不再需要将整個修改後的檔案再做一次備份了。這也就是IPFS節省存儲空間的原因。

2.6　本章小結

在這一章裡，我們詳細讨論了IPFS的幾個基礎性系統和資料結構，包括DHT、BitTorrent、Git和SFS，以及Merkle結構。DHT是本章的重點和難點， 我們學習了3種著名的DHT設計，分别是Kademlia、Coral DSHT和S/K Kademlia。讀者重點關注三者各自的側重點和實作的差別。DHT是分布式存儲的基本方式，Kademlia使得其完全去中心化，Coral提升了DHT的效率，而S/K Kademlia則大大提升了系統的安全性。BitTorrent協定應當重點關注其塊交換協定的優化和經濟學政策，對于不合作的節點，通過信用機制給出相應的懲罰，例如流量限制或者網絡阻塞；在Filecoin的設計中，系統會沒收它們的擔保品。在Git版本控制系統中，隻儲存每個版本與原始版本的差異，而不做全部的拷貝。IPFS也是基于此原理，與現有檔案系統相比，存儲方式更節省空間。自驗證檔案系統的核心思想是在檔案路徑中隐含驗證身份的密鑰，IPFS系統也利用了這一方式，確定所有檔案在同一命名空間下，同時不犧牲安全性。最後我們學習了Merkle資料結構，讀者應重點關注Merkle Tree和Merkle DAG的差別和用途。