在區塊鏈中， merkle樹充當著一個代表性的角色，一個區塊中的所有交易信息都被它歸納總結，大大提高區塊鏈的效率。下面先講一下區塊鏈（以比特幣系統為例）中為什麼要用merkle樹這個方法，並且引申出
比特幣輕錢包的實現基礎--簡化支付驗證（SPV）。不會像單純講技術那樣枯燥的，相信用過btc錢包的都會對本文感興趣。大家都知道，比特幣網絡中所有產生的交易都要打包進區塊中，一般情況下，一個區塊中包含幾百上千筆交易是很常見的。由於比特幣的去中心化特性，網絡中的每個節點必須是獨立，自給自足的，也就是每個節點必須存儲一個區塊鏈的完整副本。在2014年4月，比特幣網絡中一個全節點要存儲、處理所有區塊的數據，需要佔用15GB的空間，並且隨著越來越多的人使用比特幣，每個月以超過1GB的速度在增長。到如今，完整的下載比特幣所有的區塊數據，也就是運行一個全節點，需要200GB以上的空間...
這樣的規則隨著日益劇增的全節點所需空間，越來越難以讓人遵守，難道讓每個人都去運行一個全節點嗎？還有節點就是區塊鏈網絡中的完全參與者，他們要遵守節點必須驗證交易和區塊，再加上想要與其他節點交互、下載新區塊，對網絡流量也是有一定要求的，節點要做的會越來越麻煩，並且效率低下。
於是中本聰在比特幣白皮書中提出了對這個問題的解決方案：簡化支付驗證（Simplified Payment Verification, SPV）。SPV 是一個比特幣輕節點，也就是我們大部分人在電腦安裝的輕量級的比特幣錢包，理論上來說，要驗證一筆交易，錢包需要遍歷所有的區塊找到和該筆交易相關的所有交易進行逐個驗證才是可靠的。但有了SPV就不用這麼麻煩了，它不需要同步下載整個區塊鏈的數據即不用運行全節點就可以驗證支付，也不需要驗證區塊和交易，用戶只需要保存所有的區塊頭就可以了。要知道，區塊頭包含著區塊的必要屬性，僅80個字節大小，而區塊體當中包含著成百上千筆交易，每筆交易一般要400多個字節大小。
這裡需要注意的是，SPV強調的是驗證支付，不是驗證交易。這兩個概念是不同的。驗證支付，比較簡單，只需要判斷用於支付的那筆交易是否被驗證過，以及得到網絡多少次確認（即有多少個區塊疊加）。而交易驗證則複雜的多，需要驗證賬戶餘額是否足夠支出、是否存在雙重支付、交易腳本是否通過等問題，一般這個操作是由全節點的礦工來完成。
為了實現SPV，需要有一種方式來檢查一個區塊是否包含了某筆交易，而不用去下載整個區塊。這就是merkle樹所要完成的事。先來看看什麼是merkle樹吧。
1.概念
Merkle tree（默克爾樹），常叫它merkle樹，是一種哈希二叉樹，在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構，每個節點代表一條結構化數據。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用於實現數據快速查詢。
2.結構
由一個根節點、一組中間節點和一組葉節點組成。葉節點包含存儲數據或其哈希值，中間節點是它的兩個孩子節點內容的哈希值，根節點也是由它的兩個子節點內容的哈希值組成。所以Merkle樹也稱哈希樹。
3.特點
技術特點就不多講了，主要特點就是：底層（葉子節點）數據的任何變動，都會逐級向上傳遞到其父節點，一直到Merkle樹的根節點使得根節點的哈希值發生變化。
4.總結原理
區塊鏈中每個區塊都會有一個 Merkle 樹，它從葉子節點（樹的底部）開始，一個葉子節點就是一個交易哈希。葉子節點的數量必須是雙數，但是並非每個塊都包含了雙數的交易。如果一個塊裡面的交易數為單數，那麼就將最後一個葉子節點（也就是 Merkle 樹的最後一個交易，不是區塊的最後一筆交易）複製一份湊成雙數。
從下往上，兩兩成對，連接兩個節點哈希，將組合哈希作為新的哈希。新的哈希就成為新的樹節點。重複該過程，直到僅有一個節點，也就是樹根。根哈希然後就會當做是整個塊交易的唯一標示，將它保存到區塊頭，然後用於工作量證明。
以上就是對於merkle樹的介紹，感興趣的話，後面不妨跟著阿深一起一層層剝開區塊鏈，歡迎大家轉發評論。如果對你有幫助不勝榮幸。
閱讀更多 深淺區塊 的文章
