連Ethereum都在用！用一個例子徹底理解DHT

什麼是DHT? 為甚麼要發明DHT?

前言

若讀者是區塊鏈從業人員或者愛好者，那麼DHT這個名詞對讀者來說應該不陌生。DHT全名為Distributed Hash Table，中文翻成分散式雜湊表。在這篇文章當中，筆者將引導讀者認識DHT優雅簡潔的設計，並介紹DHT兩大經典：Chord 與 Kademlia。

紙條協定

首先，我們用一個簡單的例子：紙條協定，來理解什麼是DHT。

假設我們想滿足以下需求：

需求
在上課時傳紙條給87號同學，問他的小考分數

我們稱以下的限制條件為紙條協定：

紙條協定
1. 紙條正面需須標註目標T，紙條背面須標註請求
2. S與T的距離為其二人座位的直線距離
3. T的鄰員都知道T的小考分數
4. S只知道坐在S鄰員的座號並寫在鄰員名單中
5. S只能傳紙條給在S鄰員名單中的R且R與T的距離須小於S與T的距離

在遵守紙條協定的情形下，我們可以這樣做：

分數查詢
1. 紙條正面寫著「給87號」，背面寫著「你小考幾分?」
2. 任何知道87號小考分數的人，都可以在紙條上寫上分數後將紙條傳回給我
3. 每個拿到紙條的人都只能往87號位置的方向傳遞
4. 87號或其鄰員收到紙條後，寫上分數並按原路線回傳
5. 我收到回傳的紙條，背面寫著「87分不能再高了」，得知87號同學的分數是87分

什麼是DHT?

紙條協定即是一種簡化的DHT：一種能夠需求透過訊息接力到特定群體再加以處理的機制。DHT顧名思義就是分散式的雜湊表，而雜湊表是一種能高效進行資料讀取/寫入的資料結構。雜湊表的名稱源自雜湊函數：雜湊函數可以將任意的資料映射到固定長度的隨機字串，由於函數具有單向性與唯一性，因此這個隨機字串可以作為辨識資料的指紋，或稱為鍵值(Key)。若想讀取雜湊表的資料(Value)，只需提供鍵值，雜湊表即可取得映射到該鍵值的完整資料。

使用雜湊表就像用座號查小考分數，只要知道鍵值(座號)，便可快速地找到內容(分數)。

DHT則多了「分散」的特性，如同每個座號只需要記住自己及鄰員的小考分數即可，不需要記住全班的分數。若想得知任何一人的分數，只要透過紙條協定將紙條傳給知道分數的人(該員或其鄰員)即可。

DHT的原理

若想達到分散式的特性，則必須要有類似紙條協定這樣的訊息接力機制，這種機制一般被稱為基於鍵值的路由(Key-based Routing)。而擔任接力重要任務的鄰員名單則被稱為路由表(Routing Table)，參與者則被稱為節點(Node)，每個節點都有自己的節點編號(Node ID)，鍵值與節點標號都被稱為識別符(Identifier)。

DHT跟紙條協定有以下幾點不同：

1. 距離的定義：紙條協定的距離為空間上的直線距離；DHT的距離為邏輯上的距離(Logic Distance)。例如Kademlia是用兩個識別符的XOR運算結果來定義距離。
2. 路由表的內容：在紙條協定中，路由表只包含自己周圍最近的人；DHT的路由表則分開記錄不同的距離區間。
3. 路由表的更新機制：紙條協定中的鄰員是固定的，不需要更新路由表；DHT的路由表是動態的，隨時都有新成員加入/退出，必須要有更新的機制。
4. 效能：紙條協定的查詢時間與目標的距離成正比，距離若增加2倍，則查詢時間也增加2倍；DHT則非常高效，距離若增加N倍，查詢時間只需增加 logN 倍。

為什麼要發明DHT?

DHT是奠基於網路網路之上的覆蓋網路(Overlay Network)，或可稱為點對點網路(Peer-to-peer Network)，具有以下幾個重要特性：

1. 開放性：參與者可以動態地加入/退出
2. 釋出冗余資源：參與者的閒置資源能夠被有效利用
3. 去中心化：不需要中心化的協調者(Coordinator)也能運作
4. 可擴展性：使用者的需求可以大致平均地分配給每個參與者，提升了整體能處理的需求總量，參與者的增長也意謂著需求處理能力的增長

綜合以上，針對日益不足的頻寬以及過度中心化網際網路，DHT作為一種更具去中心化與可擴整性的解決方案被發明出來了。

DHT可以拿來做什麼?

1. 檔案分享：基於DHT的BitTorrent服務能夠更高效地實現大檔案的上傳/下載
2. 域名查詢：基於DHT的DNS服務能夠擁有更好的負載均衡特性
3. 具有抗審查性的通訊軟體：基於DHT的通訊軟體，由於其去中心化與點對點傳輸的特性，使得其能夠抵抗特定團體對通訊內容的審查

而在Ethereum中，DHT僅作為一種高效的同儕節點選擇機制(Peer Selection)。

DHT中的經典：Chord & Kademlia

DHT的概念是利用訊息接力來以滿足使用者對資源的需求，在這樣的大框架之下，各家DHT設計方案多是在下列幾點有所不同：

1. 邏輯距離的定義
2. 路由表的組成
3. 路由路的更新機制

我們接下來就來看看Chord與Kademlia這兩個最知名的DHT。

Chord

Chord於2001年被Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishna等人發表，根據Google Scholar的統計數字，Chord的原始論文被引用了超過13000次，由此可見Chord是一個學術界研究的熱門項目。

所有可能出現的識別符的集合，我們稱之為鍵值空間(Key Space)。我們以m表示識別符的位元數，若m=160，則鍵值空間大小為2¹⁶⁰。

Chord將鍵值空間表示為一個環(Ring)，稱之為識別符環(Identifier Ring)，識別符以順時針方向遞增，距離則定義為一點以順時針方向抵達另一點會經過的識別符數量，由於環具有方向性，因此距離是非對稱的，例如：一個6位元的環共有2⁶個識別符，節點標號21到節點編號30的距離為9；然而節點編號30到節點標號21的距離為23。

對環上的任一識別符來說，其順時針方向碰到的第一個節點被稱為後任者(Successor)；其逆時針方向碰到的第一個節點被稱為前任者(Predecessor)。在紙條協定中，我們指定某鍵值(座號)及其四周鄰員負責某鍵值的內容(分數)；Chord則指定：給定任一鍵值，該鍵值的後任者需負責該鍵值的寫入/讀取。如下圖所示，N14需負責K10的寫入/讀取；N32需負責K24及K30的寫入/讀取。

Chord Identifier Ring

正如同紙條協定中任一人都可以傳紙條詢問其他人的分數，環上任一節點都可以發起對鍵值的查詢。如果該節點不知道查詢結果，則接力給下一個節點。

在紙條協定中，收到紙條的人如果不知道分數，他只能接力給隔壁的人；在Chord則可以有更高效的做法：Chord的路由表也被稱為Finger Table，共分成m個欄位，可以存m個節點。Chord高效的訣竅在於：路由表的第i個欄位的節點是距離自身識別符 2^(i-1) 以上的後任者。以下圖左為例，N8的路由表中，第1欄的節點是N14，是N8+2⁰的後任者；第2欄的節點也是N14，是N8+2¹的後任者；第4欄的節點則是N21，是N8+2³的後任者。於是，距離與目標愈遠，接力所前進的距離愈長；距離愈近，接力所前進的距離也會愈短。

有了這樣的路由表，收到訊息的節點首先比對位於路由表第1欄的後任者是否是目標的後任者，若有則向該節點詢問鍵值的內容；若沒有則向不大於目標中最大的後任者發出接力訊息。直到查詢鍵值的後任者位於路由表第1欄為止。如下圖右所示：

Chord Finger Table and Key Lookup

而當新節點加入網路時，新節點除了計算自己的路由表之外，還需更新自己的前任者第1欄的後任者為自己，以確保訊息接力正確，流程如下：

New Node Joins Chord

Kademlia

Kademlia於2002年被Petar Maymounkov和David Mazieres兩人發表，如果說易於分析的Chord是學界的鍾愛，那麼強健實用的Kademlia就是業界與開發者的首選了：BitTorrent是第一個基於DHT的大規模檔案應用，Ethereum也使用Kademlia作為節點選擇機制，IPFS更引入改良後的S/Kademlia作為核心。

Kademlia的鍵值空間可以表示成一棵二元樹(Binary Tree)，識別符可表示為葉節點(Leaf Node)，而識別符之距離則定義為XOR運算結果，根據XOR的真值表，只有當兩個位元相異時結果才為真。

XOR True Table

也就是說，兩識別符距離可以視為其差異程度。兩個識別符位元完全相反時，差異度最大，距離也最大；反之，兩相同之識別符差異度最小，距離為0。Kademlia對距離的概念與Chord非常相似，唯一不同的是，XOR運算是對稱的，Chord環則不對稱，距離會隨著起終點不同而不同。

Kademlia Key Space and Routing Table

如同Chord，Kademlia的路由表也切分成不同的距離區間，然而，Kademlia的路由表有著更多的巧思：

1. Chord的路由表每個距離區間只對應一個節點；Kademlia的路由表每個距離區間則對應一個包含k個節點的k桶(k-buckets)，每個k桶都對應一個距離區間：第1欄的k桶對應距離[2⁰, 2¹)；第2欄的k桶對應距離[2¹, 2²)，以此類推，第i欄的k桶對應距離[2^(i-1), 2^i)。Kademlia指定：距離鍵值最近的k個鄰員需負責鍵值的寫入/讀取 — 這就是Kademlia的強健性遠大於Chord的原因，因為Kademlia的資料冗余是Chord的k倍(k的預設值為20)。
2. 由於XOR運算的特性，每個k桶可以被視為一個子樹，第1欄的子樹與自身識別符僅有1個位元不同；第2欄的子樹有2個位元不同，以此類推。Chord的查詢過程可以視為從環上的一點跳至另一點；Kademlia的查詢過程可視為從一棵子樹跳到另一棵子樹，直到找到與目標最近的子樹為止。因此，Kademlia跟Chord一樣都是屬於高效的二元搜尋。
3. Kademlia的距離對稱性使得每個新節點加入後可以同步更新其每個新鄰員的路由表，大幅增加網路效率。而最近更新的節點，則會是k桶當中的查詢的第一順位，這又再次增加了Kademlia的強健性。

Kademlia Key Lookup

Kademlia的簡潔與強健使得它廣受開發者的青睞，連Ethereum也用上它作為流言散播協定(Gossip Protocol)的節點選擇機制。

總結

最後我們回到紙條協定：

紙條協定
1. 紙條正面需須標註目標T，紙條背面須標註請求
2. S與T的距離為其二人座位的直線距離
3. T的鄰員都知道T的小考分數
4. S只知道坐在S鄰員的座號並寫在鄰員名單中
5. S只能傳紙條給在S鄰員名單中的R且R與T的距離須小於S與T的距離

DHT藉由路由表(第4點)及接力規則(第5點)的互相配合，達到去中心化及可擴展性的特性。然而，DHT開放的特性也易招致惡意攻擊，究竟DHT存在哪些弱點？DHT能不能拿來實作分散式帳本？筆者將於下篇文章分曉。