hello，大家好，我們第四期的區塊鏈技術分享來啦，這一次讓大家久等了
~~
這一期我們分享merkle tree——默克爾樹。看到本期文章標題的時候，可能大部分人已經這樣了
雖然默克爾樹大家很陌生，但是提到默克爾樹相關的應用，大部分程式設計師肯定接觸過。merkle tree 最大的應用場合就是在點對點網路，Git 版本控制系統、IPFS 協議、比特幣以及以太坊等等。同時merkle tree也是區塊鏈面試大機率會被問到的問題，所以這一期我們就來聊一下比特幣網路中的merkle tree。
merkle tree的資料結構
merkle tree是計算機科學家Ralph Merkle在1987年發明的。就是這位大佬（找不到好看的圖了，大家將就看）
論文題目是《A digital signature based on a conventional encryption function》翻譯成中文大概的意思是：基於常規加密函式的數字簽名，旨在構建更好的數字簽名。這個是merkle tree的起源。
那麼在比特幣網路中，merkle tree是如何應用的？
在區塊鏈網路中，所有的區塊呈鏈狀連線。
每個區塊展開可以分為區塊頭block header和區塊體block body。關於區塊頭block header的欄位解釋，請參考區塊鏈技術之雜湊指標。
根據上面的圖可以看出，所有的交易都儲存在block body裡面，block body就是一顆merkle tree，並且只有葉子節點儲存的是交易，也就是圖中的tx（transaction），因此葉子節點也被稱為data block，非葉子節點儲存的都是雜湊值。
merkle tree就是一個hash二叉樹，父節點是兩個子節點的double sha256的結果，葉子節點就是交易的content的double sha256結果；
最下面那一層就是交易資料data block，每一個交易都可以計算出一個hash，從而層層向上，得到merkle root。
但是由於blockchain裡面都merkle運算要求葉子節點是偶數，所以，當一個區塊內包含當交易數量為奇數時，把最後一個交易複製一份，湊成偶數。
最後就是把merkle root儲存在區塊頭中，交易資料被儲存在區塊體中，其實中間當那些hash並沒有被儲存，它們只是運算過程資料。
默克爾樹大多用來進行完整性驗證，比如分散式環境下，從多臺主機獲取資料，怎麼驗證獲取的資料是否正確呢，只要驗證Merkle樹根雜湊一致，即可。
例如，上圖中tx1資料塊被篡改了，那麼錯誤會傳導到計算hash(tx1)，接著傳導到計算hash(hash(tx1)+hash(tx2))，最後傳導到根雜湊，導致根雜湊的不一致。因此，任何底層資料塊（data blocks）的變化，最終都會傳導到根雜湊，也就是區塊頭中的默克爾根。
merkle proof
那麼說了這麼多，merkle tree到底有什麼用呢？
在比特幣網路中，merkle tree一個重要的用途就是提供merkle proof。
在解釋merkle proof之前，我們先講一下比特幣網路中的節點。
2.1 什麼是節點？
在加密貨幣中，凡是連線到該網路的任何計算機，都被稱為節點。
在區塊鏈中，存在一種冗餘備份的現象。
如果所有節點都需要儲存全網的所有交易及其他資料資訊，則不可避免的會出現一些弊端，比如，使用者想建立一個自己的區塊鏈節點進行專案開發，而不需要參加共識過程（不需要挖礦），那麼進行資料的同步將是一項特別龐大的工作，既耗時又費資源。
2.2 全節點和輕節點
因此，這個時候比特幣網路中的節點就可以分為兩類：全節點和輕節點。
- 全節點，儲存有全網交易資料，又能完成相關驗證交易，獨立完成與對等節點的連線。這類節點在本地儲存了一個完整的區塊鏈網路（儲存了所有區塊的block header和block body），在其上可進行任何查詢、交易的驗證與廣播，正因為有這樣的節點存在，更加使得去中心化成為了可能，同時使得區塊鏈網路更加安全。全節點一直線上，最重要的是參與挖礦，尋找最長合法鏈並辨別分叉。
- 輕節點，輕節點不需要儲存所有交易內容，利用merkle tree的特性，它只需包含block header以及與自己相關的交易細節，並透過Merkle證明來判斷交易是否在當前的區塊鏈交易列表中。輕節點並不一直線上，與全節點不同，它只能檢測哪一條是最長鏈，但無法知道是否是最長合法鏈，因為輕量級節點無法驗證大多數交易的合法性，也無法驗證區塊鏈網路釋出的區塊的正確性。例如，手機上的比特幣的錢包的應用，就是一個輕節點，只儲存block header。
這個時候存在一個問題，如何向一個輕節點證明，某個交易已經被寫入到區塊鏈裡面？
解答這個問題之前，我們再區分兩個名詞：支付驗證和交易驗證。
交易驗證非常複雜，涉及到驗證是否有足夠餘額可供支出、是否存在雙花、指令碼能否透過等等，通常由執行全節點的礦工來完成。
支付驗證則比較簡單，只判斷用於“支付”的那筆交易是否已經被驗證過，並得到了多少的算力保護（多少確認數）。
如何向一個輕節點證明，某個交易已經被寫入到區塊鏈裡面？指的是“支付驗證“，而不是“交易驗證”。這個就要用到merkle proof。
某個輕節點想知道圖中標為黃色的tx交易是不是被寫到區塊鏈裡面？輕節點沒有儲存交易列表，只儲存了根雜湊值。
1. 那麼這個輕節點就會向某個全節點發出請求，請求給出包括這個待驗證支付的merkle proof。
2. 全節點收到請求後，只要把圖中紅色的H（）發給輕節點；
3. 輕節點在本地就可以計算出H（）；
4. 那麼輕節點就可以計算出一個merkle root，輕節點只需要將計算出的根雜湊值與block header裡面的儲存根雜湊值進行比較，就可以驗證這個交易是不是被寫入了區塊鏈。
因此，SPV（Simplified Payment Verification，簡單支付驗證，這個概念比特幣白皮書裡面提到過，可以參考[001]比特幣白皮書中英文翻譯及解析）驗證的過程：
1. 從網路上獲取並儲存最長鏈的所有block header至本地;
2. 計算該交易的hash值tx_hash;
3. 定位到包含該tx_hash所在的區塊，驗證block header是否包含在已知的最長鏈中;
4. 從區塊中獲取構建merkle tree所需的hash值;
5. 根據這些hash值計算merkle_root_hash;
6. 若計算結果與block header中的merkle_root_hash相等，則交易真實存在。
7. 根據該block header所處的位置，確定該交易已經得到多少個確認。
這個過程裡面還用到了一個重要的資料結構叫bloom filter，布隆過濾器。布隆過濾器的應用不止在SPV的驗證，以太坊的資料結構裡面也用到了布隆過濾器，如果你是一個產品經理你肯定知道UV這個重要的指標，那麼布隆過濾器在UV統計中也發揮了重要的作用。所以，下一期我們分享布隆過濾器和SPV。
總結
1. merkle tree就是一個hash二叉樹，父節點是兩個子節點的double sha256的結果，葉子節點就是交易的content的double sha256結果；
2. 最下面那一層就是交易資料，每一個交易都可以計算出一個hash，從而層層向上，得到merkle root。但是由於blockchain裡面都merkle運算要求葉子節點是偶數，所以，當一個區塊內包含當交易數量為奇數時，把最後一個交易複製一份，湊成偶數。最後就是把merkle root儲存在區塊頭中，交易資料被儲存在區塊體中，其實中間當那些hash並沒有被儲存，它們只是運算過程資料。
3. merkle tree被廣泛運用於區塊鏈中，但其實P2P下載中merkle tree的應用更為廣泛。
OK，本期分享就這麼多，下期我們分享bloom filter布隆過濾器和SPV驗證。
本文參考：
- 《區塊鏈技術與應用》公開課；
- 《區塊鏈：技術驅動金融》。
