大家都知道，目前BT應(yīng)用的發(fā)展具有一個非常顯著的趨勢，那就是用來交換電影、游戲、ISO等大尺寸的數(shù)據(jù)文件。然而我們也能夠觀察到另一個事 實，那就是：下載文件所對應(yīng)的索引文件(.torrent)也越來越大，越來越難以下載；這是因為在索引文件中保存了被下載文件中所有數(shù)據(jù)塊的20字節(jié) SHA1校驗值，而文件越大，數(shù)據(jù)塊越多，則.torrent文件越長(塊數(shù)=文件長度/數(shù)據(jù)塊長，Bit Torrent標準協(xié)議建議塊長一般不超過512KB)。

索引文件長度的膨脹將直接加重索引服務(wù)器的下載負擔，因為所有BT用戶均必須從服務(wù)器上下載同一份.torrent文件，而這一下載行為本身是集中 式的，因而導致系統(tǒng)的擴展性受到較大限制，尤其是用于交換熱門資源時；另一方面，為避免索引文件過大，人們在發(fā)布種子、制作索引文件時不得不采用增加其基 本數(shù)據(jù)塊長度(比如2MB)的方式來減少數(shù)據(jù)塊總數(shù)，這將有可能對端對端數(shù)據(jù)交換性能造成一系列負面影響：因為塊長越小，越能幫助我們及時地發(fā)現(xiàn)傳輸錯 誤，試想在2MB塊長的情況下，用戶直到下載完整個數(shù)據(jù)塊時才通過校驗發(fā)現(xiàn)傳輸有誤，然后不得不再次重傳整個2MB塊，這顯然較塊長為512KB時更加浪 費帶寬和時間。歸根到底，導致上述麻煩的根本原因在于這么一個事實：“.torrent中包含了所有數(shù)據(jù)塊的SHA1校驗信息”。

有什么辦法讓我們既能獲得較小的塊長而又能減少索引文件長度？Merkle哈希樹校驗方式為我們提供了一個很好的思路，它試圖從校驗信息獲取及實際 校驗過程兩個方面來改善上述問題。先說說什么是哈希樹，以最簡單的二叉方式為例，如下圖所示，設(shè)某文件共13個數(shù)據(jù)塊，我們可以將其padding到 16(2的整數(shù)次方)個塊(注意，padding的空白塊僅用于輔助校驗，而無需當作數(shù)據(jù)進行實際傳輸)，每個塊均對應(yīng)一個SHA1校驗值，然后再對它們 進行反復的兩兩哈希，直到得出一個唯一的根哈希值為止(root hash, H0)，這一計算過程便構(gòu)成了一棵二元的Merkle哈希樹，樹中最底層的葉子節(jié)點(H15~H30)對應(yīng)著數(shù)據(jù)塊的實際哈希值，而那些內(nèi)部節(jié)點 (H1~H14)我們則可以將其稱為“路徑哈希值”，它們構(gòu)成了實際塊哈希值與根哈希值H0之間的“校驗路徑”，比如，數(shù)據(jù)塊8所對應(yīng)的實際哈希值為 H23，則有：SHA1(((SHA1(SHA1(H23,H24),H12),H6),H1)應(yīng)該等于H0。當然，我們也可以進一步采用n元哈希樹來進 行上述校驗過程，其過程是類似的。

采用Merkle哈希樹校驗方式能夠極大地減小.torrent文件的尺寸，這是因為，一旦采用這種方式來校驗數(shù)據(jù)塊，那么便沒有必要 在.torrent文件中保存所有數(shù)據(jù)塊的校驗值了，其中僅需保存一個20字節(jié)的SHA1哈希值即可，即整個下載文件的根哈希值H0。想象一下一個3、 4GB的文件，其對應(yīng).torrent文件卻只有100-200字節(jié)的樣子？heh

下面，讓我們來看看其數(shù)據(jù)塊交換及校驗的詳細過程：

1. 以下載某大文件F為例，為啟動BT交換，每一個client均必須從索引服務(wù)器中下載F所相應(yīng)的.torrent文件，從而得到文件長度、數(shù)據(jù)塊長及根哈希值H0等必要信息；
2. 任一client均可通過輪詢Tracking服務(wù)器或者是DHT方式來定位其他參與交換F數(shù)據(jù)的peer，進而與之建立TCP連接進行P2P文件交換，其定位peer的方式基本上沒有什么改變。
3. 當client從某一peer下載一個數(shù)據(jù)塊時，它將事先向peer發(fā)出相應(yīng)的校驗查詢請求，要求對方提供校驗當前下載塊所需的路徑哈 希值，這一過程可以很方便地通過擴展標準的Peer Wire Protocol實現(xiàn)。以上圖為例，當client下載的是數(shù)據(jù)塊8時，在下載開始之前，它將要求peer提供校驗塊8所需的全部路徑哈希值：H24、 H12、H6和H1；
4. 當client下載完某數(shù)據(jù)塊之后，它將對其進行哈希樹校驗；仍以校驗塊8為例，client將首先計算出塊8的哈希值H23'，然后 再根據(jù)peer所提供的信息依次計算各層路徑哈希值，直至求得一個唯一的根校驗值H0'，如果H0'等于.torrent文件中的H0，則數(shù)據(jù)塊下載無 誤，校驗通過；反之則校驗失敗。
5. 一旦某數(shù)據(jù)塊校驗通過，與其哈希樹校驗過程相關(guān)的所有路徑哈希值均可以作為cache緩存下來，而不管其究竟是從peer查詢所得的， 還是由client自身計算所得的；但值得注意的是，如果該數(shù)據(jù)塊的校驗未通過，則其所有相關(guān)的路徑哈希值均不能被cache，而只能被廢棄，因為此時我 們無法保證peer所提供的路徑哈希值的正確性(不能排除peer故意提供錯誤路徑哈希值和哈希值傳輸出錯的可能)。例如，所有與塊8校驗相關(guān)的路徑哈希 包括：H24、H12、H6、H1、H11、H5、H2，其中前面4個經(jīng)查詢peer所得，而后面3個則由client自己計算所得。塊8驗證的結(jié)果將決 定這7個路徑哈希是否可信及是否能被cache。
6. 當一定數(shù)量的路徑哈希值被緩存之后，后繼數(shù)據(jù)塊的校驗過程將被極大簡化。此時我們可以直接利用校驗路徑上層次最低的已知路徑哈希值來對 數(shù)據(jù)塊進行部分校驗，而無需每次都校驗至根哈希值H0，這主要是因為：某一路徑哈希值被cache這一事實本身便能夠證明其是可信的；例如，在塊8校驗完 成之后，client無需進行額外的peer查詢便可以直接對塊9進行校驗，因此它已經(jīng)知道了H24的值，并且通過塊8的校驗過程驗證了H24的正確性； 而當client需要對塊10進行校驗時，它僅需向peer查詢H26一個校驗值即可，由于我們已經(jīng)知道了H12值，因此對塊10的校驗僅需2次SHA1 哈希即可：一次是計算塊哈希H25，一次是計算SHA1(H25，H26)，并比較其等不等于H12。同理，當需要驗證塊12時，由于已知 H6，client僅需查詢2個路徑哈希(H28和H14)和3次SHA1計算(H27、SHA1(H27,H28)和SHA1(H13,H14))即 可。緩存的路徑哈希值越多，則后繼數(shù)據(jù)塊校驗越容易，速度也越快。
7. 為了進一步提高校驗效率，可以考慮在.torrent文件上再做做文章：令其保存整個哈希樹中最上面的若干層路徑哈希值，而不僅僅只是 一個根哈希值H0，底層的路徑哈希值則仍然依靠詢問peer或client自身計算所得，從而實現(xiàn).torrent文件尺寸與校驗效率的有效折衷。

最后再來看看上述算法的時空效率如何。假設(shè)某文件的總塊數(shù)為M，將其padding至N個塊(N＝2^p)，塊長為K，不難看出：

1. 為了校驗整個文件，共需緩存Sum(2^i)：i=0 to p，即2N-1個20字節(jié)的SHA1哈希值(包括根哈希值、所有路徑哈希值和塊哈希值)。以512KB為塊長的一個4GB的文件為例，M=8000，則 N=8192，p=13，所需存儲空間為(2*8192-1)*20=327660 Bytes=319KB，其緩沖區(qū)較普通校驗方式翻倍，但即便如此，校驗所需的數(shù)據(jù)量仍完全可以接受，即使在最糟糕的情況下：完全不用cache、全部依 賴peer查詢來獲得這些校驗值，也無非總共增加了1個基本塊不到的流量而已，而且這些流量還是通過P2P方式得到的。
2. 在無校驗失敗的理想情況下，校驗整個文件共需M次塊長為K的SHA1計算，和N-1次長度為20字節(jié)的SHA1運算。即，以哈希樹方式 校驗塊長512KB的4GB文件，共需進行8000次長度為512KB的SHA1計算，同時外加8191次長為2*20字節(jié)的路徑哈希計算，與普通校驗方 式相比，后者是哈希樹額外引入的開銷，但由于每次路徑哈希的計算量非常小，其影響幾可忽略。

綜上所述，通過采用哈希樹校驗方式，我們可以將諸多校驗所需哈希值的獲取工作分散在P2P數(shù)據(jù)交換時捎帶進行，而不是從.torrent文件中集中 獲取，從而有利于緩解索引服務(wù)器集中下載瓶頸，優(yōu)化Peer to Peer數(shù)據(jù)傳輸性能；在實現(xiàn)上述目的的同時，哈希樹校驗機制仍能保證以P2P方式獲取的校驗信息的可靠性，在小塊長的情況下，惡意peer幾乎無法通過 故意提供錯誤路徑哈希值的方式來實現(xiàn)有效的服務(wù)拒絕攻擊。采用這種方式，我們所需付出的額外代價主要包括幾近1倍的校驗緩存空間及其SHA1計算量的增 長，但是經(jīng)過簡要分析不難看出其實際影響不甚明顯，這對于換取較小的塊長、提高大文件P2P交換效率而言是值得的。Merkle哈希樹校驗方式與分布式哈 希表技術(shù)勢必能夠幫助BitTorrent協(xié)議進一步克服自身的非結(jié)構(gòu)化缺陷，取得更大的應(yīng)用發(fā)展。