本文將講解 Merkle Tree，為什麼講解 Merkle Tree 呢？ 地球上大部分人應該連它的名字都沒有聽過。Merkle Tree 是由電腦科學家 Ralph Merkle 在很多年前提出的，並以他本人的名字來命名，中文翻譯過來叫默克爾樹，也叫雜湊樹。Merkle Tree 號稱區塊鏈面試必考題，因為的確太常用了。說到根本上 Merkle Tree 就是用來做完整性校驗的，所謂的完整性校驗，就是檢查一下資料有沒有損壞或者被惡意篡改。Merkle Tree 的最大的應用場合就是在點對點網路上，Git 版本控制系統，IPFS 協議以及比特幣以太坊等等專案，都用到了它。
雜湊 Hash
Merkle Tree 如果直接去看定義，會看到一張比較複雜的圖，可能會把你一下子嚇到，然後就不想學了。但是別忘了，Merkle Tree 還有另外一個名字，叫雜湊樹。先講雜湊，再講什麼是雜湊列表，最後在遞進到雜湊樹，這樣三步下來，每一步都其實很好理解，保證你能一下子就掌握 Merkle Tree 的概念。
先介紹什麼是雜湊。其實要實現完整性校驗，最簡單的方法就是對要校驗的整個的資料檔案做個雜湊運算，把得到的雜湊值公佈在網上，這樣我們把資料下載到手之後，再次運算一下雜湊值，如果運算結果相等，就表示我們下載過程中檔案沒有任何的損壞。因為雜湊的最大特點是，如果資料稍微變了一點點，那麼經過雜湊運算，得到的雜湊值將會變得面目全非。沒有人可以把資料篡改了，同時還能保證資料的雜湊不變。
這種簡單的採用雜湊的方式做資料運算，比較適合資料本身不做分割，同時是放在一臺伺服器上的情況。例如，如果去某個公司網站上去下載他們的一個軟體，就會看到公司網站上公佈了這個下載包的雜湊值，這個雜湊值非常重要，因為有了這串數，我們就可以放心的去下載這個軟體，下載完做一下完整性校驗，就知道這個軟體沒有損壞。甚至可以放心從其他的不可信網站上去下載這個軟體包，因為有了校驗機制，也一樣可以保證這個包是跟官方的包絲毫不差的。
雜湊列表 Hash List
但是在去中心化網路，或者叫點對點網路上，資料往往都是拆分成很多小碎片去下載的，而且其中很多機器可以認為是不穩定或者是不可信的，這時需要有更加巧妙的做法。最簡單的方式就是用 Hash List ，也就是雜湊列表。
實際中，點對點網路在傳輸資料的時候，其實都是把比較大的一個檔案，切成小的資料塊。這樣的好處是，如果有一個小塊資料在傳輸過程中損壞了，那我只要重新下載這一個資料塊就行了，不用重新下載整個檔案。當然這就要求對每個資料塊計算雜湊值，所有這些小資料塊的雜湊值都是兄弟關係，這樣大家就組成了一個雜湊列表。BT 下載的時候，在下載真正的資料之前，會先下載一個雜湊列表的，這個就是所謂的種子檔案。有了各個 hash 之後，資料本身就可以從任意的機器上下載了，不用管那些機器是否是安全可信的。
這時有一個問題就出現了，那麼多的雜湊，我們怎麼保證它們本身都是正確的呢？
答案是我們需要一個根雜湊，根就是樹根的根。把每個小塊的雜湊值拼到一起，然後對整個這個長長的字串再做一次雜湊運算，最終的結果就是雜湊列表的根雜湊。於是，如果我們能夠保證從一個絕對可信的網站，或者從我們的朋友手裡拿到一個正確的根雜湊，就可以用它來校驗雜湊列表中的每一個雜湊都是正確的，進而可以保證下載的每一個資料塊的正確性了。
Hash List 也就是雜湊列表形式，就非常適合在點對點網路上儲存的大型資料了。
Merkle Tree 雜湊樹
其實 Merkle Tree 本身也算是一個雜湊列表，只不過是在這個基礎上又引入了樹形結構，從而獲得了更高的靈活性。
我們先說電腦科學中的樹的概念，樹跟自然界一棵樹有著類似的結構，只不過電腦科學中的樹通常都是倒著畫，根在上面，然後一路往下開枝散葉。舉一個最簡單的例子，所有的檔案都存放在一個資料夾中，這個資料夾就叫根資料夾，根就是樹根的意思，這個資料夾又會包含其他資料夾，子資料夾中又會包含孫子輩的資料夾。這樣層層的包含或者說從屬關係，畫成圖就是一棵倒掛的樹，而這個結構就是電腦科學中隨處可見的樹的概念，怎麼樣，簡單吧？
然後就說到主角 Merkle Tree 了。在最底層，和雜湊列表一樣，我們把資料分成小的資料塊，有相應的雜湊和它對應。但是往上走，並不是直接去運算根雜湊，而是把相鄰的兩個雜湊合併成一個字串，然後運算這個字串的雜湊，這樣每兩個雜湊就結婚生子，得到了一個”子雜湊“。如果最底層的雜湊總數是單數，那到最後必然出現一個單身雜湊，這種情況就直接對它進行雜湊運算，所以也能得到它的子雜湊。於是往上推，依然是一樣的方式，可以得到數目更少的新一級雜湊，最終必然形成一棵倒掛的樹，到了樹根的這個位置，這一代就剩下一個根雜湊了，我們把它叫做 Merkle Root 。需要補充一下的是，根雜湊有時候也叫主雜湊 Master Hash ，也有人叫它頂雜湊 Top Hash ，因為畫圖的時候通常都是倒著畫這根樹，反正不管叫什麼，說的都是一個東西。
於是我們看到 Merkle Tree 比普通的雜湊列表稍微複雜了一點點，那麼優點是什麼呢？相對於 Hash List，Merkle Tree 的明顯的一個好處是可以單獨拿出一個分支來（作為一個小樹）對部分資料進行校驗，這給很多使用場合就帶來了雜湊列表所不能比擬的靈活和高效能。
Merkle Tree 是三個概念的疊加，一個是雜湊，第二個是雜湊列表，第三個是樹。
總結
本節的內容就是為了講清楚 Merkle Tree 這個概念，內容差不多了，來總結一下。雜湊和樹都是電腦科學中最基礎最重要的兩個概念，可以用在很多不同場合。單個雜湊不能擔當大檔案在分散式點對點網路上的校驗工作，於是我們有了雜湊列表的概念。 Merkle Tree 可以認為是雜湊列表的一個變體，讓雜湊列表變得更加靈活高效，因為每次校驗都可以單純拿出樹的一個分支來操作。
