版權(quán)聲明： https://blog.csdn.net/weixin_37504041/article/details/80474636
中本聰在他的創(chuàng)世論文中一個(gè)概念，就是SPV，中文意思是簡(jiǎn)單支付驗(yàn)證，從這里我們可以看出SPV指的是“支付驗(yàn)證”而不是“交易驗(yàn)證”，那這兩者有什么區(qū)別嗎？簡(jiǎn)單的說就是支付驗(yàn)證只需驗(yàn)證該筆交易是否被確認(rèn)過了，而交易驗(yàn)證是需要驗(yàn)證該筆交易是否滿足一些條件如“余額”是否足夠，還有該筆交易有沒有存在雙花等等一些問題，只有一切都沒什么問題后該筆交易才算驗(yàn)證通過，可以看出交易驗(yàn)證要比支付驗(yàn)證更加復(fù)雜，所以它一般是由挖礦節(jié)點(diǎn)來完成的，而支付驗(yàn)證只要普通的輕錢包就可以完成。那現(xiàn)在有一個(gè)問題了，SPV是如何實(shí)現(xiàn)的？答案就是默克爾樹，也就是今天要講的主題，理解了默克爾樹之后在回過頭來就能理解SPV了。
什么是Merkle Tree？
默克爾樹是一種二叉樹，由一組葉節(jié)點(diǎn)、一組中間節(jié)點(diǎn)和一個(gè)根節(jié)點(diǎn)構(gòu)成，看下圖：
來簡(jiǎn)單講一下這幅圖，我們從最底部開始看，D0、D1、D2和D3是葉子節(jié)點(diǎn)包含的數(shù)據(jù)，也就是葉子節(jié)點(diǎn)的value，繼續(xù)往上看，N0、N1、N2和N3是就是葉子節(jié)點(diǎn)，它是將數(shù)據(jù)（也就是D0、D1、D2和D3）進(jìn)行hash運(yùn)算后得到的hash值；繼續(xù)往上看，N4和N5是中間節(jié)點(diǎn)，它們各是N0和N1經(jīng)過hash運(yùn)算得到的哈希值以及N2和N3經(jīng)過hash運(yùn)算得到的哈希值，注意，它們是把相鄰的兩個(gè)葉子結(jié)點(diǎn)合并成一個(gè)字符串，然后運(yùn)算這個(gè)字符串的哈希；接著往上，Root節(jié)點(diǎn)是N4和N5經(jīng)過hash運(yùn)算后得到的哈希值，這就是這顆默克爾樹的根哈希。
分析到這里我們大概可以知道在默克爾樹中最下面的大量的葉節(jié)點(diǎn)包含基礎(chǔ)數(shù)據(jù)；每個(gè)中間節(jié)點(diǎn)是它的兩個(gè)葉子節(jié)點(diǎn)的哈希，根節(jié)點(diǎn)也是由它的兩個(gè)子節(jié)點(diǎn)的哈希，代表了默克爾樹的頂部。
還有從默克爾樹的結(jié)構(gòu)可以看出，任意一個(gè)葉子節(jié)點(diǎn)的交易被修改，葉子節(jié)點(diǎn)hash值就會(huì)變更，最終根節(jié)點(diǎn)的hash值就會(huì)改變。所以確定的根節(jié)點(diǎn)的hash值可以準(zhǔn)確的作為一組交易的唯一摘要。
現(xiàn)在可以總結(jié)一下默克爾樹的特點(diǎn)：
1.首先是它的樹的結(jié)構(gòu)，默克爾樹常見的結(jié)構(gòu)是二叉樹，但它也可以是多叉樹，它具有樹結(jié)構(gòu)的全部特點(diǎn)。
2.默克爾樹的基礎(chǔ)數(shù)據(jù)不是固定的，想存什么數(shù)據(jù)由你說了算，因?yàn)樗灰獢?shù)據(jù)經(jīng)過哈希運(yùn)算得到的hash值。
3.默克爾樹是從下往上逐層計(jì)算的，就是說每個(gè)中間節(jié)點(diǎn)是根據(jù)相鄰的兩個(gè)葉子節(jié)點(diǎn)組合計(jì)算得出的，而根節(jié)點(diǎn)是根據(jù)兩個(gè)中間節(jié)點(diǎn)組合計(jì)算得出的，所以葉子節(jié)點(diǎn)是基礎(chǔ)。
如何通過Merkle樹驗(yàn)證一筆交易？
大概了解了什么是默克爾樹后，可能會(huì)有一個(gè)疑問，就是默克爾樹是如何驗(yàn)證一筆交易的？也就是我們上文提到的SPV（支付驗(yàn)證）?？聪旅嬉环鶊D:
假設(shè)我們要驗(yàn)證區(qū)塊中存在Hash值為9Dog:64（綠色框）的交易，我們僅需要知道1FXq:18、ec20、8f74（黃色框）即可計(jì)算出781a、5c71與Root節(jié)點(diǎn)（藕粉色框）的哈希，如果最終計(jì)算得到的Root節(jié)點(diǎn)哈希與區(qū)塊頭中記錄的哈希（6c0a）一致，即代表該交易在區(qū)塊中存在。這是因?yàn)槲疑衔奶岬降膬蓚€(gè)點(diǎn)，一個(gè)是默克爾樹是從下往上逐層計(jì)算的，所以只要知道相鄰的另一個(gè)節(jié)點(diǎn)的hash值就可以一直往上計(jì)算直到根節(jié)點(diǎn)，另一個(gè)是根節(jié)點(diǎn)的hash值可以準(zhǔn)確的作為一組交易的唯一摘要，依據(jù)這兩點(diǎn)就可以來驗(yàn)證一筆交易是否存在。
比特幣中的默克爾樹
介紹完默克爾樹的基本知識(shí)，我們來看一下比特幣中的默克爾樹長(zhǎng)什么樣，看下面一幅圖：
可以看到區(qū)塊頭包含了根節(jié)點(diǎn)的hash值，而中間節(jié)點(diǎn)、葉子節(jié)點(diǎn)還有基礎(chǔ)數(shù)據(jù)在放在了區(qū)塊體中。
這里有一點(diǎn)需要提的就是在比特網(wǎng)絡(luò)中的Merkle樹是二叉樹，所以它需要偶數(shù)個(gè)葉子節(jié)點(diǎn)。如果僅有奇數(shù)個(gè)交易需要?dú)w納，那最后的交易就會(huì)被復(fù)制一份以構(gòu)成偶數(shù)個(gè)葉子節(jié)點(diǎn)，這種偶數(shù)個(gè)葉子節(jié)點(diǎn)的樹也被稱為平衡樹。
默克爾樹的典型應(yīng)用場(chǎng)景
默克爾樹的應(yīng)用場(chǎng)景其實(shí)很廣泛，比較典型的就是P2P下載。在點(diǎn)對(duì)點(diǎn)網(wǎng)絡(luò)中作數(shù)據(jù)傳輸?shù)臅r(shí)候，會(huì)同時(shí)從多個(gè)機(jī)器上下載數(shù)據(jù)，而且很多機(jī)器可以認(rèn)為是不穩(wěn)定或者不可信的。為了校驗(yàn)數(shù)據(jù)的完整性，更好的辦法是把大的文件分割成小的數(shù)據(jù)塊（例如，把分割成2K為單位的數(shù)據(jù)塊）。這樣的好處是，如果小塊數(shù)據(jù)在傳輸過程中損壞了，那么只要重新下載這一快數(shù)據(jù)就行了，不用重新下載整個(gè)文件。
怎么確定小的數(shù)據(jù)塊沒有損壞哪？只需要為每個(gè)數(shù)據(jù)塊做Hash。BT下載的時(shí)候，在下載到真正數(shù)據(jù)之前，我們會(huì)先下載一個(gè)Hash列表。那么問題又來了，怎么確定這個(gè)Hash列表本事是正確的哪？答案是把每個(gè)小塊數(shù)據(jù)的Hash值拼到一起，然后對(duì)這個(gè)長(zhǎng)字符串在作一次Hash運(yùn)算，這樣就得到Hash列表的根Hash。下載數(shù)據(jù)的時(shí)候，首先從可信的數(shù)據(jù)源得到正確的根Hash，就可以用它來校驗(yàn)Hash列表了，然后通過校驗(yàn)后的Hash列表校驗(yàn)數(shù)據(jù)塊。
除了P2P下載外，默克爾樹還可以被用來快速比較大量的數(shù)據(jù)，因?yàn)楫?dāng)兩個(gè)默克爾樹根相同時(shí)，則意味著所代表的數(shù)據(jù)必然相同。還有就是可以用來實(shí)現(xiàn)零知識(shí)證明（零知識(shí)證明指的是證明者能夠在不向驗(yàn)證者提供任何有用的信息的情況下，使驗(yàn)證者相信某個(gè)論斷是正確的。舉個(gè)例子，你要我向你證明我擁有某一把鑰匙，這個(gè)時(shí)候我不需要直接拿鑰匙給你看，而是用這個(gè)鑰匙開鎖拿出所在柜子中的某一樣?xùn)|西給你看以此來證明我擁有這把鑰匙），關(guān)于零知識(shí)證明以后有時(shí)間再講，ZCash就是采用零知識(shí)證明來達(dá)到交易匿名的目的，有興趣可以去查找資料。
---------------------
作者：kuber_123
來源：CSDN
原文：https://blog.csdn.net/weixin_37504041/article/details/80474636
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請(qǐng)附上博文鏈接！
