大部分材料都會提到區塊中保存了merkle根，并且利用它作交易真實性驗證。但是具體如何作這個真實性驗證，沒有一篇文章可以通俗的講出來。本文假設你已經知道區塊鏈中merkle tree的原理，現在想搞明白具體怎么來實現交易真實性驗證。
Merkle Tree
這個小節簡述一下merkle的原理，具體詳解會另外寫文章，你關注我的文章即可。簡單說，merkle tree就是一個hash二叉樹，父節點是兩個子節點的double sha256的結果，葉子節點就是交易的content的double sha256結果。
blockchain merkle tree
上圖中最下面那一層就是交易數據，每一個交易都可以計算出一個hash，從而層層向上，得到merkle root。但是由于blockchain里面都merkle運算要求葉子節點是偶數，所以，當一個區塊內包含當交易數量為奇數時，把最后一個交易復制一份，湊成偶數。
最后就是把merkle root保存在區塊頭中，交易數據被保存在區塊體中，其實中間當那些hash并沒有被保存，它們只是運算過程數據。
SPV
為什么要搞這么復雜？直接把所有交易數據保存起來了，要驗證交易是否存在還不簡單嗎？之所以要這么干，是因為比特幣發明之初，中本聰想到有一種輕錢包的設計，這就是SPV（簡化支付驗證，Simplified Payment Verification）。
輕錢包并不保存完整的區塊鏈，而是只保存每一個區塊的區塊頭。區塊體保存了完整的交易信息，而交易信息需要的存儲量大部分都是交易頭的千倍以上。所以，如果只保存交易頭，就可以極大的減少本地客戶端存儲的區塊鏈信息。
但是，不能因此讓區塊鏈無法工作啊。如果這個時候輕錢包要對某一個交易進行驗證，而本地又沒有這個交易的信息，那怎么驗證呢？這時，區塊頭里面的merkle root就要起作用了。
驗證路徑
在講述輕錢包的驗證過程之前，我們需要知道如何在merkle tree里面做驗證。我們已知merkle tree里面父節點和子節點的運算關系，因此，當我們要證明一個葉子節點存在于這棵樹時，只需要得到從該葉子節點到根的運算過程里面需要的那些hash即可，并不需要所有葉子節點參與計算。
merkle驗證路徑
你可能覺得有點奇怪，為什么不直接把所有的葉子節點告訴它就行了，你用所有葉子節點能算出root hash就驗證通過了。但事實就是這樣，因為每一個父節點hash一定是由兩個子節點hash運算得到，所以，我們只需要挑選出所有參與運算的節點，就可以證明這個葉子節點存在于樹中。這樣可以減少hash運算的次數。而這些被挑選出來的節點，以及它們之間的層級關系，就是驗證路徑，即上圖中merkle root那個盒子下面的所有盒子。
如何證明交易的真實性？
比特幣網絡中的交易，只有已經被記錄到區塊鏈，并且已經得到6個確認的，才被認為是真實的，只有基于這些真實交易發起的新交易（輸入與輸出的概念），才是合法的。
我們詢問一個交易是否真實，往往基于以下前提：
- 我們在問一個交易是否已被記錄到區塊鏈中
- 而且這個交易所在的區塊鏈是最長的哪一條，沒有在分叉鏈上
- 當每個節點接收到一條交易廣播時，我們要查詢作為一筆新交易的輸入的真實性
- 礦工對交易進行打包之前，對所有的輸入進行真實性驗證（在礦工接收到交易信息時就已經驗證過了，打包的時候驗證2000條交易信息不可能）
那么對于SPV輕錢包而言，怎么知道一個交易是否真實的呢？SPV拿到一個交易信息之后（比如接收到一筆錢），并不能確認這個交易是否合法，因此要對這個交易的輸入進行驗證。但是它只拿到了單個交易的信息，而沒有本地的完整區塊鏈數據，因此，SPV要拿著這個交易的信息向網絡發起查詢請求，這個請求被稱為merkle block message。當其他有完整區塊鏈數據的客戶端收到這個請求之后，利用傳過來的交易信息在自己的區塊鏈數據庫中進行查詢，并把驗證路徑返回給請求源，SPV拿到驗證路徑之后，再做一次merkle校驗，確認無誤之后，就認為這個交易是可信的。
現在的問題是：
- 怎么從區塊鏈里面查一個交易？
- 怎么獲取merkle驗證路徑？
- 怎么確保網絡上這個返回的驗證路徑不是偽造的？
從區塊鏈查交易
區塊鏈的數據結構是離散的，比特幣里面一個區塊被保存在一個文件里面，要得到一個交易的驗證路徑，必須得到這個交易所在的區塊鏈。這是一個復制的查詢過程，可能需要把所有的區塊都遍歷一遍才能找到。因此，blockchain.info這樣的網站孕育而生，幫助你通過一個信息查這個信息在區塊鏈上的所有相關記錄。但是對于客戶端而言，可沒那么容易，它不能信任blockchain.info這個網站，只能信任自己本地存儲的區塊鏈。所以，只能用比較合理的算法，去優化交易查詢。
一種設計是，把每一個區塊的數據結構修改為關系型數據庫，通過關系型數據庫，可以用sql語句快速查詢。但是，要遍歷查詢所有區塊鏈，是比較浪費的。還有一種想法是，利用交易的時間戳來快速定位區塊位置，在臨近的幾個區塊中快速找到它。
如何獲取merkle驗證路徑？
實際上，merkle的驗證路徑生成的前提是已經存在一棵完整的merkle樹。市面上有很多merkle樹的實現包，有的包直接給出來getProof的方法來獲取某個葉子節點的驗證路徑。
在客戶端收到merkle block message之后，要執行下面的步驟：
- 通過上述方法找到包含該交易的區塊
- 檢查該區塊是否是整個網絡中最長鏈條里面的
- 取出所有交易生成merkle tree，利用getProof方法得到該交易的驗證路徑
- 將該驗證路徑發送回請求源
SPV得到響應之后，要做如下驗證：
- 同步區塊鏈，確保是整個網絡中最長的一條
- 先拿到merkle root去區塊鏈中查找，確保該merkle root hash是在鏈條中
- 利用拿到的驗證路徑，再進行一次merkle校驗，確保驗證路徑全部合法
為什么SPV還要再做一次merkle校驗呢？主要是為了確保響應方發送的驗證路徑的有效性。
確保驗證路徑的真實性
上面提到了SPV還要做一次merkle校驗，這也是“不信任”的表現之一。我們并不確保響應我們的節點不會作弊或欺詐，因此，我們要自己進行校驗。但是，有沒有可能雖然校驗過程順利，但是實際上校驗路徑是偽造的呢？
我們來做一個假設：1）merkle root為真；2）交易為假；3）路徑中的hash可真可假。這個假設是否成立？
我們知道，不同字符串碰撞到同一個sha256的概率極小，那么double sha256的概率就是它的平方，而merkle root是經過一層一層計算上來的，如果一個區塊只有一個（或2個）交易，那么就是double^(2+1) sha256，而如果是4個交易，就有double^(4 + 2 + 1) sha256，更何況一個區塊有那么多交易，要經過merkle運算得到一個相同的hash，幾乎是不可能的，因此，在merkle驗證中用一個偽造的交易hash來得到一個已知來merkle root是不可能的。
如果還想更進一步校驗，可以在區塊頭中存儲區塊打包的交易的數量，這樣就可以知道從交易hash到merkle root需要經過幾層的運算。這也是一個檢驗點。
小結
merkle tree被廣泛運用于區塊鏈中，但并不是只有區塊鏈使用它來進行校驗。比如一些p2p下載，如迅雷，就需要把文件分割為小塊文件，每塊都有一個hash，每塊從不同的網絡節點下載，最后組成一個完整的文件，但是也需要進行hash驗證，它也可以使用merkle來進行驗證。merkle tree也不一定是二叉樹，可以是任意樹結構。而在以太坊中，merkle驗證還不夠用，增加了Patricia Tree驗證，合起來稱為“Merkle Patricia Tree”。
