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