如果對區(qū)塊鏈有些基本的了解，那應(yīng)該經(jīng)常聽到一個詞叫merkle tree，那么merkle tree到底是做什么用的呢，這里來簡單的探討一下。
首先我們需要知道在區(qū)塊鏈網(wǎng)絡(luò)中有兩種類型的節(jié)點，一種節(jié)點叫full node，顧名思義，這種節(jié)點的特點就是它存儲著整個區(qū)塊鏈數(shù)據(jù)的完整備份，包括從區(qū)塊鏈創(chuàng)世之初到現(xiàn)在的所有交易，所以這些數(shù)據(jù)量是很龐大的，會占據(jù)驚人的磁盤空間。還有一種節(jié)點叫spv(simple payment node)，有時候我們使用的是手機這類設(shè)備，存儲空間有限，那就只需要下載每個區(qū)塊的header信息（類似索引）就可以了，這樣就會大大節(jié)省存儲空間和帶寬。
這樣對spv節(jié)點就產(chǎn)生了一個問題，如果我發(fā)起了一筆交易，怎樣確認這筆交易已經(jīng)被包含在區(qū)塊鏈中了呢？（畢竟節(jié)點中沒有存儲所有的交易信息）
先不管merkle tree，有一個笨辦法，在區(qū)塊header中會存儲有一個hash值，這個hash值是這個區(qū)塊中所有交易的hash值的hash：hash in header = hash(交易1+交易2+交易3+......)。當我們想確認交易X是否存在于區(qū)塊M時，我們可以詢問附近的一個full node，這個full node是不可信任的，它可能會告知我們假信息，所以需要它把區(qū)塊M的所有交易的hash值都發(fā)給我們，然后我們來做比對，[hash in header of block M]（這個值是存儲在我們本地區(qū)塊header中值得信賴的值）是否等于 hash(交易1+交易2+...+交易X+...)，而這些交易的hash值是full node發(fā)給我們的。如果相等，表示交易X已經(jīng)被確認，否則表示這個節(jié)點給了我們假信息或者交易未被確認。
似乎很美好，但是這樣就又會產(chǎn)生一個問題，如果區(qū)塊M中包含了一千筆交易，為了確認一筆交易就需要傳輸這一千筆交易的信息，對速度帶寬等的消耗都是很大的。merkle tree就是為了解決這一個問題而產(chǎn)生的（學(xué)過算法的同學(xué)知道二叉樹的時間復(fù)雜度是logN）。
觀察下圖，就是一個典型的merkle tree：
L1，L2，L3，L4代表區(qū)塊中的所有的四筆交易，如果我們想確認L3是否被包含在區(qū)塊中，需要full node給我們哪些信息呢？觀察樹的結(jié)構(gòu)很容易知道，只需要給hash
1-1和hash 0就可以了，在spv本地block header中的hash值是top hash的值，這樣只需要傳輸2個hash值就可以了，這樣傳輸?shù)男畔⒘烤妥優(yōu)榱薼ogN。
