Merkle Tree概念

image

Merkle Tree缀去，通常也被稱作Hash Tree，顧名思義识脆，就是存儲hash值的一棵樹设联。Merkle樹的葉子是數(shù)據(jù)塊(例如，文件或者文件的集合)的hash值灼捂。非葉節(jié)點是其對應(yīng)子節(jié)點串聯(lián)字符串的hash离例。^[1]

1. Hash

Hash是一個把任意長度的數(shù)據(jù)映射成固定長度數(shù)據(jù)的函數(shù)^[2]。例如悉稠，對于數(shù)據(jù)完整性校驗粘招，最簡單的方法是對整個數(shù)據(jù)做Hash運算得到固定長度的Hash值，然后把得到的Hash值公布在網(wǎng)上偎球，這樣用戶下載到數(shù)據(jù)之后洒扎，對數(shù)據(jù)再次進行Hash運算，比較運算結(jié)果和網(wǎng)上公布的Hash值進行比較衰絮，如果兩個Hash值相等袍冷，說明下載的數(shù)據(jù)沒有損壞∶担可以這樣做是因為輸入數(shù)據(jù)的稍微改變就會引起Hash運算結(jié)果的面目全非胡诗，而且根據(jù)Hash值反推原始輸入數(shù)據(jù)的特征是困難的。^[3]

image

如果從一個穩(wěn)定的服務(wù)器進行下載淌友，采用單一Hash是可取的煌恢。但如果數(shù)據(jù)源不穩(wěn)定，一旦數(shù)據(jù)損壞震庭，就需要重新下載瑰抵，這種下載的效率是很低的。

2. Hash List

在點對點網(wǎng)絡(luò)中作數(shù)據(jù)傳輸?shù)臅r候器联，會同時從多個機器上下載數(shù)據(jù)二汛，而且很多機器可以認(rèn)為是不穩(wěn)定或者不可信的。為了校驗數(shù)據(jù)的完整性拨拓，更好的辦法是把大的文件分割成小的數(shù)據(jù)塊（例如肴颊，把分割成2K為單位的數(shù)據(jù)塊）。這樣的好處是渣磷，如果小塊數(shù)據(jù)在傳輸過程中損壞了婿着，那么只要重新下載這一快數(shù)據(jù)就行了，不用重新下載整個文件。

怎么確定小的數(shù)據(jù)塊沒有損壞哪竟宋？只需要為每個數(shù)據(jù)塊做Hash提完。BT下載的時候，在下載到真正數(shù)據(jù)之前袜硫，我們會先下載一個Hash列表氯葬。那么問題又來了，怎么確定這個Hash列表本事是正確的哪婉陷？答案是把每個小塊數(shù)據(jù)的Hash值拼到一起帚称，然后對這個長字符串在作一次Hash運算，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)秽澳。下載數(shù)據(jù)的時候闯睹，首先從可信的數(shù)據(jù)源得到正確的根Hash，就可以用它來校驗Hash列表了担神，然后通過校驗后的Hash列表校驗數(shù)據(jù)塊楼吃。

image

3. Merkle Tree

Merkle Tree可以看做Hash List的泛化（Hash List可以看作一種特殊的Merkle Tree，即樹高為2的多叉Merkle Tree）妄讯。

在最底層孩锡，和哈希列表一樣，我們把數(shù)據(jù)分成小的數(shù)據(jù)塊亥贸，有相應(yīng)地哈希和它對應(yīng)躬窜。但是往上走，并不是直接去運算根哈希炕置，而是把相鄰的兩個哈希合并成一個字符串荣挨，然后運算這個字符串的哈希，這樣每兩個哈希就結(jié)婚生子朴摊，得到了一個”子哈夏ⅲ“。如果最底層的哈仙醺伲總數(shù)是單數(shù)口锭，那到最后必然出現(xiàn)一個單身哈希，這種情況就直接對它進行哈希運算贩疙，所以也能得到它的子哈希讹弯。于是往上推，依然是一樣的方式这溅，可以得到數(shù)目更少的新一級哈希，最終必然形成一棵倒掛的樹棒仍，到了樹根的這個位置悲靴，這一代就剩下一個根哈希了，我們把它叫做 Merkle Root^[3]莫其。

在p2p網(wǎng)絡(luò)下載網(wǎng)絡(luò)之前癞尚，先從可信的源獲得文件的Merkle Tree樹根耸三。一旦獲得了樹根，就可以從其他從不可信的源獲取Merkle tree浇揩。通過可信的樹根來檢查接受到的Merkle Tree仪壮。如果Merkle Tree是損壞的或者虛假的，就從其他源獲得另一個Merkle Tree胳徽，直到獲得一個與可信樹根匹配的Merkle Tree积锅。

Merkle Tree和Hash List的主要區(qū)別是，可以直接下載并立即驗證Merkle Tree的一個分支养盗。因為可以將文件切分成小的數(shù)據(jù)塊缚陷，這樣如果有一塊數(shù)據(jù)損壞，僅僅重新下載這個數(shù)據(jù)塊就行了往核。如果文件非常大箫爷，那么Merkle tree和Hash list都很到，但是Merkle tree可以一次下載一個分支聂儒，然后立即驗證這個分支虎锚，如果分支驗證通過，就可以下載數(shù)據(jù)了衩婚。而Hash list只有下載整個hash list才能驗證窜护。

image

Merkle Tree的特點

1. MT是一種樹，大多數(shù)是二叉樹谅猾，也可以多叉樹柄慰，無論是幾叉樹，它都具有樹結(jié)構(gòu)的所有特點税娜；
2. Merkle Tree的葉子節(jié)點的value是數(shù)據(jù)集合的單元數(shù)據(jù)或者單元數(shù)據(jù)HASH坐搔。
3. 非葉子節(jié)點的value是根據(jù)它下面所有的葉子節(jié)點值，然后按照Hash算法計算而得出的敬矩。^[4][5]

通常概行，加密的hash方法像SHA-2和MD5用來做hash。但如果僅僅防止數(shù)據(jù)不是蓄意的損壞或篡改弧岳，可以改用一些安全性低但效率高的校驗和算法凳忙，如CRC。

Second Preimage Attack: Merkle tree的樹根并不表示樹的深度禽炬，這可能會導(dǎo)致second-preimage attack涧卵，即攻擊者創(chuàng)建一個具有相同Merkle樹根的虛假文檔。一個簡單的解決方法在Certificate Transparency中定義：當(dāng)計算葉節(jié)點的hash時腹尖，在hash數(shù)據(jù)前加0x00柳恐。當(dāng)計算內(nèi)部節(jié)點是，在前面加0x01。另外一些實現(xiàn)限制hash tree的根乐设，通過在hash值前面加深度前綴讼庇。因此，前綴每一步會減少近尚，只有當(dāng)?shù)竭_葉子時前綴依然為正蠕啄，提取的hash鏈才被定義為有效。

Merkle Tree的操作

1. 創(chuàng)建Merckle Tree

加入最底層有9個數(shù)據(jù)塊戈锻。

step1：（紅色線）對數(shù)據(jù)塊做hash運算歼跟，Node_0i = hash(Data_0i), i=1,2,…,9

step2: （橙色線）相鄰兩個hash塊串聯(lián)，然后做hash運算舶沛，Node_1((i+1)/2) = hash(Node_0i+Node_0(i+1)), i=1,3,5,7;對于i=9, Node_1((i+1)/2) = hash(Node_0i)

step3: （黃色線）重復(fù)step2

step4：（綠色線）重復(fù)step2

step5：（藍色線）重復(fù)step2嘹承，生成Merkle Tree Root

image

易得，創(chuàng)建Merkle Tree是O(n)復(fù)雜度(這里指O(n)次hash運算)如庭，n是數(shù)據(jù)塊的大小叹卷。得到Merkle Tree的樹高是log(n)+1。

2. 檢索數(shù)據(jù)塊

為了更好理解坪它，我們假設(shè)有A和B兩臺機器骤竹，A需要與B相同目錄下有8個文件，文件分別是f1 f2 f3 ....f8往毡。這個時候我們就可以通過Merkle Tree來進行快速比較蒙揣。假設(shè)我們在文件創(chuàng)建的時候每個機器都構(gòu)建了一個Merkle Tree。具體如下圖:

image

從上圖可得知开瞭，葉子節(jié)點node7的value = hash(f1),是f1文件的HASH;而其父親節(jié)點node3的value = hash(v7, v8)懒震，也就是其子節(jié)點node7 node8的值得HASH。就是這樣表示一個層級運算關(guān)系嗤详。root節(jié)點的value其實是所有葉子節(jié)點的value的唯一特征个扰。

假如A上的文件5與B上的不一樣。我們怎么通過兩個機器的merkle treee信息找到不相同的文件? 這個比較檢索過程如下:

Step1. 首先比較v0是否相同,如果不同葱色，檢索其孩子node1和node2.

Step2. v1 相同递宅，v2不同。檢索node2的孩子node5 node6;

Step3. v5不同苍狰，v6相同办龄，檢索比較node5的孩子node 11 和node 12

Step4. v11不同，v12相同淋昭。node 11為葉子節(jié)點俐填，獲取其目錄信息。

Step5. 檢索比較完畢翔忽。

以上過程的理論復(fù)雜度是Log(N)玷禽。過程描述圖如下:

image

從上圖可以得知真?zhèn)€過程可以很快的找到對應(yīng)的不相同的文件赫段。

3. 更新呀打，插入和刪除

雖然網(wǎng)上有很多關(guān)于Merkle Tree的資料矢赁，但大部分沒有涉及Merkle Tree的更新、插入和刪除操作贬丛，討論Merkle Tree的檢索和遍歷的比較多撩银。我也是非常困惑，一種樹結(jié)構(gòu)的操作肯定不僅包括查找豺憔，也包括更新额获、插入和刪除的啊。后來查到stackexchange上的一個問題恭应，才稍微有點明白抄邀，原文見[6]。

對于Merkle Tree數(shù)據(jù)塊的更新操作其實是很簡單的昼榛，更新完數(shù)據(jù)塊境肾，然后接著更新其到樹根路徑上的Hash值就可以了，這樣不會改變Merkle Tree的結(jié)構(gòu)胆屿。但是奥喻，插入和刪除操作肯定會改變Merkle Tree的結(jié)構(gòu)，如下圖非迹，一種插入操作是這樣的：

image

插入數(shù)據(jù)塊0后(考慮數(shù)據(jù)塊的位置)环鲤，Merkle Tree的結(jié)構(gòu)是這樣的：

image

而[6]中的同學(xué)在考慮一種插入的算法，滿足下面條件：

• re-hashing操作的次數(shù)控制在log(n)以內(nèi)
• 數(shù)據(jù)塊的校驗在log(n)+1以內(nèi)
• 除非原始樹的n是偶數(shù)憎兽，插入數(shù)據(jù)后的樹沒有孤兒冷离，并且如果有孤兒，那么孤兒是最后一個數(shù)據(jù)塊
• 數(shù)據(jù)塊的順序保持一致
• 插入后的Merkle Tree保持平衡

然后上面的插入結(jié)果就會變成這樣：

image

根據(jù)[6]中回答者所說纯命，Merkle Tree的插入和刪除操作其實是一個工程上的問題西剥，不同問題會有不同的插入方法。如果要確保樹是平衡的或者是樹高是log(n)的扎附，可以用任何的標(biāo)準(zhǔn)的平衡二叉樹的模式蔫耽，如AVL樹，紅黑樹留夜，伸展樹匙铡，2-3樹等。這些平衡二叉樹的更新模式可以在O(lgn)時間內(nèi)完成插入操作碍粥，并且能保證樹高是O(lgn)的鳖眼。那么很容易可以看出更新所有的Merkle Hash可以在O((lgn)²)時間內(nèi)完成（對于每個節(jié)點如要更新從它到樹根O(lgn)個節(jié)點，而為了滿足樹高的要求需要更新O(lgn)個節(jié)點）嚼摩。如果仔細分析的話钦讳，更新所有的hash實際上可以在O(lgn)時間內(nèi)完成矿瘦，因為要改變的所有節(jié)點都是相關(guān)聯(lián)的，即他們要不是都在從某個葉節(jié)點到樹根的一條路徑上愿卒，或者這種情況相近缚去。

[6]的回答者說實際上Merkle Tree的結(jié)構(gòu)(是否平衡，樹高限制多少)在大多數(shù)應(yīng)用中并不重要琼开，而且保持?jǐn)?shù)據(jù)塊的順序也在大多數(shù)應(yīng)用中也不需要易结。因此，可以根據(jù)具體應(yīng)用的情況柜候，設(shè)計自己的插入和刪除操作搞动。一個通用的Merkle Tree插入刪除操作是沒有意義的。

Merkle Tree的應(yīng)用

1. 數(shù)字簽名

最初Merkle Tree目的是高效的處理Lamport one-time signatures渣刷。 每一個Lamport key只能被用來簽名一個消息鹦肿，但是與Merkle tree結(jié)合可以來簽名多條Merkle。這種方法成為了一種高效的數(shù)字簽名框架辅柴，即Merkle Signature Scheme箩溃。

2. P2P網(wǎng)絡(luò)

在P2P網(wǎng)絡(luò)中，Merkle Tree用來確保從其他節(jié)點接受的數(shù)據(jù)塊沒有損壞且沒有被替換碌识，甚至檢查其他節(jié)點不會欺騙或者發(fā)布虛假的塊碾篡。大家所熟悉的BT下載就是采用了P2P技術(shù)來讓客戶端之間進行數(shù)據(jù)傳輸，一來可以加快數(shù)據(jù)下載速度筏餐，二來減輕下載服務(wù)器的負(fù)擔(dān)开泽。BT即BitTorrent，是一種中心索引式的P2P文件分分析通信協(xié)議^[7]魁瞪。

要進下載必須從中心索引服務(wù)器獲取一個擴展名為torrent的索引文件（即大家所說的種子）穆律，torrent文件包含了要共享文件的信息，包括文件名导俘，大小峦耘，文件的Hash信息和一個指向Tracker的URL[8]。Torrent文件中的Hash信息是每一塊要下載的文件內(nèi)容的加密摘要旅薄，這些摘要也可運行在下載的時候進行驗證辅髓。大的torrent文件是Web服務(wù)器的瓶頸，而且也不能直接被包含在RSS或gossiped around(用流言傳播協(xié)議進行傳播)少梁。一個相關(guān)的問題是大數(shù)據(jù)塊的使用洛口，因為為了保持torrent文件的非常小，那么數(shù)據(jù)塊Hash的數(shù)量也得很小凯沪，這就意味著每個數(shù)據(jù)塊相對較大第焰。大數(shù)據(jù)塊影響節(jié)點之間進行交易的效率，因為只有當(dāng)大數(shù)據(jù)塊全部下載下來并校驗通過后妨马，才能與其他節(jié)點進行交易挺举。

就解決上面兩個問題是用一個簡單的Merkle Tree代替Hash List杀赢。設(shè)計一個層數(shù)足夠多的滿二叉樹，葉節(jié)點是數(shù)據(jù)塊的Hash湘纵，不足的葉節(jié)點用0來代替脂崔。上層的節(jié)點是其對應(yīng)孩子節(jié)點串聯(lián)的hash。Hash算法和普通torrent一樣采用SHA1瞻佛。其數(shù)據(jù)傳輸過程和第一節(jié)中描述的類似脱篙。

image

3. Trusted Computing

可信計算是可信計算組為分布式計算環(huán)境中參與節(jié)點的計算平臺提供端點可信性而提出的∩吮可信計算技術(shù)在計算平臺的硬件層引入可信平臺模塊(Trusted Platform，TPM)文搂，實際上為計算平臺提供了基于硬件的可信根(Root of trust适刀，RoT)。從可信根出發(fā)煤蹭，使用信任鏈傳遞機制笔喉，可信計算技術(shù)可對本地平臺的硬件及軟件實施逐層的完整性度量，并將度量結(jié)果可靠地保存再TPM的平臺配置寄存器(Platform configuration register硝皂，PCR)中常挚，此后遠程計算平臺可通過遠程驗證機制(Remote Attestation)比對本地PCR中度量結(jié)果，從而驗證本地計算平臺的可信性稽物⊙僬保可信計算技術(shù)讓分布式應(yīng)用的參與節(jié)點擺脫了對中心服務(wù)器的依賴，而直接通過用戶機器上的TPM芯片來建立信任贝或，使得創(chuàng)建擴展性更好吼过、可靠性更高、可用性更強的安全分布式應(yīng)用成為可能[10]咪奖〉脸溃可信計算技術(shù)的核心機制是遠程驗證(remote attestation),分布式應(yīng)用的參與結(jié)點正是通過遠程驗證機制來建立互信,從而保障應(yīng)用的安全。

image

文獻[10]提出了一種基于Merkle Tree的遠程驗證機制羊赵，其核心是完整性度量值哈希樹趟佃。

首先,RAMT 在內(nèi)核中維護的不再是一張完整性度量值列表(ML),而是一棵完整性度量值哈希樹(integrity measurement hash tree,簡稱IMHT).其中,IMHT的葉子結(jié)點存儲的數(shù)據(jù)對象是待驗證計算平臺上被度量的各種程序的完整性哈希值,而其內(nèi)部結(jié)點則依據(jù)Merkle 哈希樹的構(gòu)建規(guī)則由子結(jié)點的連接的哈希值動態(tài)生成。

其次,為了維護IMHT 葉子結(jié)點的完整性,RAMT 需要使用TPM 中的一段存儲器來保存IMHT 可信根哈希的值昧捷。

再次,RAMT 的完整性驗證過程基于認(rèn)證路徑(authentication path)實施.認(rèn)證路徑是指IMHT 上從待驗證葉子結(jié)點到根哈希的路徑闲昭。

4. IPFS

IPFS(InterPlanetary File System)是很多NB的互聯(lián)網(wǎng)技術(shù)的綜合體，如DHT( Distributed HashTable料身，分布式哈希表)汤纸，Git版本控制系統(tǒng)，Bittorrent等芹血。它創(chuàng)建了一個P2P的集群，這個集群允許IPFS對象的交換啰扛。全部的IPFS對象形成了一個被稱作Merkle DAG的加密認(rèn)證數(shù)據(jù)結(jié)構(gòu)败潦。

IPFS對象是一個含有兩個域的數(shù)據(jù)結(jié)構(gòu):

• Data – 非結(jié)構(gòu)的二進制數(shù)據(jù)，大小小于256kB
• Links – 一個Link數(shù)據(jù)結(jié)構(gòu)的數(shù)組囊蓝。IPFS對象通過他們鏈接到其他對象

Link數(shù)據(jù)結(jié)構(gòu)包含三個域：

• Name – Link的名字
• Hash – Link鏈接到對象的Hash
• Size – Link鏈接到對象的累積大小，包括它的Links

image

通過Name和Links令蛉，IPFS的集合組成了一個Merkle DAG（有向無環(huán)圖）聚霜。

image

對于小文件（<256kB），是一個沒有Links的IPFS對象珠叔。

image

對于大文件蝎宇，被表示為一個文件塊(<256kB)的集合。只有擁有最小的Data的對象來代表這個大文件祷安。這個對象的Links的名字都為空字符串姥芥。

image

image

目錄結(jié)構(gòu)：目錄是沒有數(shù)據(jù)的IPFS對象，它的鏈接指向其包含的文件和目錄汇鞭。

image

IPFS可以表示Git使用的數(shù)據(jù)結(jié)構(gòu)凉唐，Git commit object。Commit Object主要的特點是他有一個或多個名為’parent0’和‘parent1’等的鏈接（這些鏈接指向前一個版本）霍骄，以及一個名為object的對象(在Git中成為tree)指向引用這個commit的文件系統(tǒng)結(jié)構(gòu)台囱。

image

5. BitCoin和Ethereum^[12][13]

Merkle Proof最早的應(yīng)用是Bitcoin，它是由中本聰在2009年描述并創(chuàng)建的读整。Bitcoin的Blockchain利用Merkle proofs來存儲每個區(qū)塊的交易簿训。

image

而這樣做的好處，也就是中本聰描述到的“簡化支付驗證”（Simplified Payment Verification绘沉，SPV）的概念:一個“輕客戶端”（light client）可以僅下載鏈的區(qū)塊頭即每個區(qū)塊中的80byte的數(shù)據(jù)塊煎楣，僅包含五個元素，而不是下載每一筆交易以及每一個區(qū)塊：

• 上一區(qū)塊頭的哈希值
• 時間戳
• 挖礦難度值
• 工作量證明隨機數(shù)（nonce）
• 包含該區(qū)塊交易的Merkle Tree的根哈希

如果客戶端想要確認(rèn)一個交易的狀態(tài)车伞，它只需簡單的發(fā)起一個Merkle proof請求择懂，這個請求顯示出這個特定的交易在Merkle trees的一個之中，而且這個Merkle Tree的樹根在主鏈的一個區(qū)塊頭中另玖。

但是Bitcoin的輕客戶端有它的局限困曙。一個局限是，盡管它可以證明包含的交易谦去，但是它不能進行涉及當(dāng)前狀態(tài)的證明（如數(shù)字資產(chǎn)的持有慷丽，名稱注冊，金融合約的狀態(tài)等）鳄哭。

Bitcoin如何查詢你當(dāng)前有多少幣要糊？一個比特幣輕客戶端，可以使用一種協(xié)議妆丘，它涉及查詢多個節(jié)點锄俄，并相信其中至少會有一個節(jié)點會通知你局劲，關(guān)于你的地址中任何特定的交易支出，而這可以讓你實現(xiàn)更多的應(yīng)用奶赠。但對于其他更為復(fù)雜的應(yīng)用而言鱼填，這些遠遠是不夠的。一筆交易影響的確切性質(zhì)（precise nature）毅戈，可以取決于此前的幾筆交易苹丸，而這些交易本身則依賴于更為前面的交易，所以最終你可以驗證整個鏈上的每一筆交易苇经。為了解決這個問題赘理，Ethereum的Merkle Tree的概念，會更進一步塑陵。

Ethereum的Merkle Proof

每個以太坊區(qū)塊頭不是包括一個Merkle樹感憾，而是為三種對象設(shè)計的三棵樹：

• 交易Transaction
• 收據(jù)Receipts(本質(zhì)上是顯示每個交易影響的多塊數(shù)據(jù))
• 狀態(tài)State

image

這使得一個非常先進的輕客戶端協(xié)議成為了可能，它允許輕客戶端輕松地進行并核實以下類型的查詢答案：

• 這筆交易被包含在特定的區(qū)塊中了么令花？
• 告訴我這個地址在過去30天中，發(fā)出X類型事件的所有實例（例如凉倚，一個眾籌合約完成了它的目標(biāo)）
• 目前我的賬戶余額是多少兼都？
• 這個賬戶是否存在？
• 假如在這個合約中運行這筆交易稽寒，它的輸出會是什么扮碧？

第一種是由交易樹（transaction tree）來處理的；第三和第四種則是由狀態(tài)樹（state tree）負(fù)責(zé)處理杏糙，第二種則由收據(jù)樹（receipt tree）處理慎王。計算前四個查詢?nèi)蝿?wù)是相當(dāng)簡單的。服務(wù)器簡單地找到對象宏侍，獲取Merkle分支赖淤，并通過分支來回復(fù)輕客戶端。

第五種查詢?nèi)蝿?wù)同樣也是由狀態(tài)樹處理谅河，但它的計算方式會比較復(fù)雜咱旱。這里，我們需要構(gòu)建一個Merkle狀態(tài)轉(zhuǎn)變證明（Merkle state transition proof）绷耍。從本質(zhì)上來講吐限，這樣的證明也就是在說“如果你在根S的狀態(tài)樹上運行交易T，其結(jié)果狀態(tài)樹將是根為S'褂始，log為L诸典，輸出為O” （“輸出”作為存在于以太坊的一種概念，因為每一筆交易都是一個函數(shù)調(diào)用崎苗；它在理論上并不是必要的）狐粱。

為了推斷這個證明舀寓，服務(wù)器在本地創(chuàng)建了一個假的區(qū)塊，將狀態(tài)設(shè)為 S脑奠，并在請求這筆交易時假裝是一個輕客戶端基公。也就是說，如果請求這筆交易的過程宋欺，需要客戶端確定一個賬戶的余額轰豆，這個輕客戶端(由服務(wù)器模擬的)會發(fā)出一個余額查詢請求。如果需要輕客戶端在特點某個合約的存儲中查詢特定的條目齿诞，這個輕客戶端就會發(fā)出這樣的請求酸休。也就是說服務(wù)器(通過模擬一個輕客戶端)正確回應(yīng)所有自己的請求，但服務(wù)器也會跟蹤它所有發(fā)回的數(shù)據(jù)祷杈。

然后斑司，服務(wù)器從上述的這些請求中把數(shù)據(jù)合并并把數(shù)據(jù)以一個證明的方式發(fā)送給客戶端。

然后但汞，客戶端會進行相同的步驟宿刮，但會將服務(wù)器提供的證明作為一個數(shù)據(jù)庫來使用。如果客戶端進行步驟的結(jié)果和服務(wù)器提供的是一樣的話私蕾，客戶端就接受這個證明僵缺。

image

MPT(Merkle Patricia Trees)

前面我們提到，最為簡單的一種Merkle Tree大多數(shù)情況下都是一棵二叉樹踩叭。然而磕潮，Ethereum所使用的Merkle Tree則更為復(fù)雜，我們稱之為“梅克爾.帕特里夏樹”（Merkle Patricia tree）容贝。

對于驗證屬于list格式（本質(zhì)上來講自脯，它就是一系列前后相連的數(shù)據(jù)塊）的信息而言，二叉Merkle Tree是非常好的數(shù)據(jù)結(jié)構(gòu)斤富。對于交易樹來說膏潮，它們也同樣是不錯的，因為一旦樹已經(jīng)建立茂缚，花多少時間來編輯這棵樹并不重要戏罢，樹一旦建立了，它就會永遠存在并且不會改變脚囊。

但是龟糕，對于狀態(tài)樹，情況會更復(fù)雜些悔耘。以太坊中的狀態(tài)樹基本上包含了一個鍵值映射讲岁，其中的鍵是地址，而值包括賬戶的聲明、余額缓艳、隨機數(shù)nounce校摩、代碼以及每一個賬戶的存儲（其中存儲本身就是一顆樹）。例如阶淘，摩登測試網(wǎng)絡(luò)（the Morden testnet ）的創(chuàng)始狀態(tài)如下所示：

image

然而衙吩，不同于交易歷史記錄，狀態(tài)樹需要經(jīng)常地進行更新：賬戶余額和賬戶的隨機數(shù)nonce經(jīng)常會更變溪窒，更重要的是坤塞，新的賬戶會頻繁地插入，存儲的鍵（ key）也會經(jīng)常被插入以及刪除澈蚌。我們需要這樣的數(shù)據(jù)結(jié)構(gòu)摹芙，它能在一次插入、更新宛瞄、刪除操作后快速計算到樹根浮禾，而不需要重新計算整個樹的Hash。這種數(shù)據(jù)結(jié)構(gòu)同樣得包括兩個非常好的第二特征：

• 樹的深度是有限制的份汗，即使考慮攻擊者會故意地制造一些交易盈电，使得這顆樹盡可能地深。不然杯活，攻擊者可以通過操縱樹的深度挣轨，執(zhí)行拒絕服務(wù)攻擊（DOS attack），使得更新變得極其緩慢轩猩。
• 樹的根只取決于數(shù)據(jù)，和其中的更新順序無關(guān)荡澎。換個順序進行更新均践，甚至重新從頭計算樹，并不會改變根摩幔。

MPT是最接近同時滿足上面的性質(zhì)的的數(shù)據(jù)結(jié)構(gòu)彤委。MPT的工作原理的最簡單的解釋是，值通過鍵來存儲或衡，鍵被編碼到搜索樹必須要經(jīng)過的路徑中焦影。每個節(jié)點有16個孩子，因此路徑又16進制的編碼決定：例如封断，鍵‘dog’的16進制編碼是6 4 6 15 6 7斯辰，所以從root開始到第六個分支，然后到第四個坡疼，再到第六個彬呻，再到第十五個，這樣依次進行到達樹的葉子。

在實踐中闸氮，當(dāng)樹稀少時也會有一些額外的優(yōu)化剪况，我們會使過程更為有效，但這是基本的原則蒲跨。

6. 其他應(yīng)用

用到Merkle Tree的應(yīng)用還有很多译断，比如Git，Amazon Dynamo或悲，Apache Wave Protocol孙咪，Tahoe-LAFS backup system，Certificate Transparency framework隆箩，NoSQL systems like Apache Cassadra and Riak等

參考

Merkle Tree學(xué)習(xí)

[1] https://en.wikipedia.org/wiki/Merkle_tree

[2] https://en.wikipedia.org/wiki/Hash_function#Hash_function_algorithms

[3] http://www.reibang.com/p/458e5890662f

[4] http://blog.csdn.net/xtu_xiaoxin/article/details/8148237

[5] http://blog.csdn.net/yuanrxdu/article/details/22474697?utm_source=tuicool&utm_medium=referral

[6] http://crypto.stackexchange.com/questions/22669/merkle-hash-tree-updates

[7] https://en.wikipedia.org/wiki/BitTorrent

[8] 梁成仁, 李健勇, 黃道穎, 等. 基于 Merkle 樹的 BT 系統(tǒng) torrent 文件優(yōu)化策略[J]. 計算機工程, 2008, 34(3): 85-87.

[9] http://bittorrent.org/beps/bep_0030.html

[10] 徐梓耀, 賀也平, 鄧靈莉. 一種保護隱私的高效遠程驗證機制[J]. Journal of Software, 2011, 22(2).

[11] http://whatdoesthequantsay.com/2015/09/13/ipfs-introduction-by-example/

[12] https://www.weusecoins.com/what-is-a-merkle-tree/

[13] http://www.8btc.com/merkling-in-ethereum