Merkle樹是使區(qū)塊鏈發(fā)揮作用的基本組成部分蚊俺。雖然理論上可以在沒有Merkle樹的情況下制作區(qū)塊鏈（只需創(chuàng)建直接包含每筆交易的巨型區(qū)塊），但這樣做會帶來巨大的可擴展性挑戰(zhàn)碎浇，可以說大多數(shù)功能強大的電腦都沒有運行這種區(qū)塊鏈的能力。感謝Merkle樹，使以太坊可以運行在所有計算機和筆記本電腦上趾唱，智能手機甚至是物聯(lián)網設備也可以。那么這些Merkle樹究竟是如何工作的蜻懦，它們現(xiàn)在和未來都有什么價值呢甜癞？
首先，基礎知識宛乃。從最普遍的意義上講悠咱，Merkle樹是一種將大量“數(shù)據(jù)塊”哈希在一起的方法蒸辆，它依賴于將數(shù)據(jù)塊拆分成不同部分，其中每個部分又可以包含幾個小部分析既，然后取每部分的哈希值并重復相同的過程躬贡，繼續(xù)這樣做，直到剩余的哈涎刍担總數(shù)只變?yōu)橐粋€：根哈希拂玻。
Merkle樹最常見和最簡單的形式是二元Mekle樹，其中一個桶總是由兩個相鄰的塊或散列組成; 它可以描述如下：
那么這種奇怪的哈希算法有什么好處呢空骚？為什么不將所有塊連接成一個大塊并使用常規(guī)哈希算法呢纺讲？答案是它允許一種稱為Merkle樣張? Proof的簡潔機制：
Merkle證明包括一個數(shù)據(jù)塊，樹的根哈希囤屹，以及由從該數(shù)據(jù)塊到根的路徑上的所有哈希組成的“分支”熬甚。閱讀證明的人可以驗證哈希（至少對于該分支）在Merkle樹中從該數(shù)據(jù)塊一直往上到根哈希是一致的，以此證明給定的塊確實原本就是在樹中的那個位置肋坚。Merkle的應用很簡單：假設有一個大型數(shù)據(jù)庫乡括，并且數(shù)據(jù)庫的全部內容都存儲在Merkle樹中，其中Merkle樹的根是公開的并且是可信的（例如智厌，它由可信方進行數(shù)字簽名诲泌，或者由proof of work證明）。然后铣鹏，想要在數(shù)據(jù)庫上進行鍵值查找的用戶（例如“告訴我位置85273中的對象”）可以要求Merkle Proof來證明索要查找的值確實是在具有該特定根的數(shù)據(jù)庫中的位置85273敷扫。它可以被用于認證的小量數(shù)據(jù)，如哈希诚卸，也可以擴展到也驗證很大的數(shù)據(jù)庫葵第。
比特幣中的Merkle證明
Merkle proof最開始應用是在比特幣中，由Satoshi Nakamoto在2009年描述和創(chuàng)建合溺。比特幣區(qū)塊鏈使用Merkle樣張來存儲每個塊中的事務：
這提供了Nakamoto描述為“簡化的支付驗證”的功能：不用下載每個交易和每個區(qū)塊卒密，“輕客戶端”只需下載Block Header，Block Header的80字節(jié)數(shù)據(jù)只包含五項：
前一個標題的哈希值
時間戳
采礦難度值
工作證明nonce隨機數(shù)
Merkle樹的根哈希棠赛，包含該塊的tx哮奇。
如果輕客戶端想要確定一個tx是否在鏈中，它可以簡單地索取Merkle證明睛约，該證明表明特定tx處于一個Merkle哈希樹中鼎俘，這個哈希數(shù)的根哈希位于主鏈的某個區(qū)塊的Block Header中。
這讓我們走得很遠辩涝，但比特幣式的輕型客戶確實有其局限性而芥。例如，雖然他們可以證明某個區(qū)塊包含某個交易膀值，但他們無法證明當前的狀態(tài)（例如棍丐，數(shù)字資產持有，名稱注冊沧踏，金融合約的狀態(tài)等）歌逢。你現(xiàn)在有多少比特幣？比特幣輕客戶端可以使用一個協(xié)議翘狱，該協(xié)議涉及查詢多個節(jié)點秘案，并相信其中至少有一個會通知您地址中的任何特定交易支出，這對于該用例非常有用潦匈，但對于其他更復雜的應用程序它還不夠; tx效果的確切性質可能取決于幾個先前交易的影響阱高，這些tx本身依賴于以前的tx，因此茬缩，最終您必須驗證整個鏈中的每個tx赤惊。為了解決這個問題，以太坊將Merkle樹概念向前推進了一步凰锡。
以太坊中的Merkle證明
以太坊中的每個Block Header不是僅包含一個Merkle樹未舟，而是包含三種objects的三種樹：
Transaction交易 樹
收據(jù)Receipts（實質上是顯示每筆交易影響的數(shù)據(jù)）樹
狀態(tài)State 樹
這允許使用更高級的輕客戶端協(xié)議，允許輕客戶端輕松制作或者獲得多種可以被驗證為正確的對問題的查詢答案（以下是問題）：
此交易是否已包含在特定區(qū)塊中掂为？
告訴我過去30天內該地址發(fā)出的X類型的事件（例如裕膀，達到目標的眾籌合同）的所有情況
我?guī)舻漠斍坝囝~是多少？
這個帳戶存在嗎勇哗？
5昼扛、假裝在此合同上運行此交易。輸出會是什么欲诺？
第一個由tx樹處理; 第三個和第四個由狀態(tài)State樹處理抄谐，第二個由收據(jù)Receipt樹處理。前四個計算相當簡單; 服務器只是找到對象瞧栗，獲取Merkle分支（從該對象到樹根的哈希列表）并返回此分支給light客戶端斯稳。
第五個也由狀態(tài)樹處理，但計算方式更復雜迹恐。在這里挣惰，我們需要構建一個可以稱為Merkle狀態(tài)轉換證明Merkle state transition proof的東西。從本質上講殴边，它是一個證據(jù)憎茂，用來聲明“如果您在帶有Merkle根root的狀態(tài)State下，運行tx T锤岸，結果將是具有root的狀態(tài)S'竖幔，同時給出記錄L和輸出O”（“輸出”作為以太坊中的概念存在，因為每個tx都是函數(shù)調用;它在理論上不是必要的）是偷。
為了計算該證明拳氢，服務器在本地創(chuàng)建一個fake block假塊募逞，將狀態(tài)設置為S，并假裝是一個輕客戶端去執(zhí)行tx馋评。也就是說放接，如果執(zhí)行tx的過程要求客戶確定某個帳戶的余額，則此輕客戶端會進行余額balance查詢留特。如果輕客戶端需要檢查特定合約的存儲中的特定項目纠脾，則此輕客戶端會對其進行查詢，依此類推蜕青。服務器正確地“響應”它自己的所有查詢苟蹈，但跟蹤它發(fā)回的所有數(shù)據(jù)。然后右核，服務器將來自所有這些假的輕客戶端請求的數(shù)據(jù)的組合作為證據(jù)發(fā)送給真的客戶端（此客戶端應該是提出這第5個查詢的客戶端）慧脱。然后客戶端執(zhí)行完全相同的過程，但使用提供的證據(jù)作為其數(shù)據(jù)庫; 如果其真實執(zhí)行的結果與服務器聲明的結果（也就是服務器作為假的輕客戶端執(zhí)行之后然后發(fā)回的結果）相同蒙兰，則客戶端接受證明磷瘤。
帕特里夏樹Patricia Trees
上面提到最簡單的Merkle樹是二元Merkle樹; 然而，以太坊中使用的樹木更復雜 - 這是您在我們的文檔中聽到的“Merkle Patricia樹”搜变。本文不會詳細說明; 推薦兩邊文章看https://github.com/ethereum/wiki/wiki/Patricia-Tree與https://easythereentropy.wordpress.com/2014/06/04/understanding-the-ethereum-trie/采缚，在本文我也會做一些基本的說明
二叉Merkle樹是非常好的數(shù)據(jù)結構，用于驗證“列表”格式的信息; 基本上就是挠他，一系列的塊一個接一個扳抽。對于tx樹（上文提到的第一種樹）來說，應用二叉Merkle樹很好殖侵，因為一旦樹被創(chuàng)建贸呢，編輯樹所花費的時間并不重要，因為樹被創(chuàng)建一次然后永久不變拢军。
然而楞陷，對于狀態(tài)說樹，情況復雜一些茉唉。以太坊中的狀態(tài)基本上由鍵值映射組成固蛾，其中鍵是賬戶地址，值是帳戶聲明account declarations度陆，account declarations列出了每個帳戶的余額艾凯，隨機數(shù)，代碼和存儲（存儲本身就是樹）懂傀。例如趾诗，Morden testnet起源狀態(tài)genesis State如下：
{
? ? "0000000000000000000000000000000000000001": {
? ? ? ? "balance": "1"
? ? },
? ? "0000000000000000000000000000000000000002": {
? ? ? ? "balance": "1"
? ? },
? ? "0000000000000000000000000000000000000003": {
? ? ? ? "balance": "1"
? ? },
? ? "0000000000000000000000000000000000000004": {
? ? ? ? "balance": "1"
? ? },
? ? "102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {
? ? ? ? "balance": "1606938044258990275541962092341162602522202993782792835301376"
? ? }
}
然而，與事務歷史不同蹬蚁，狀態(tài)需要經常更新：帳戶的余額balance和隨機數(shù)nonce經常被更改恃泪，而且經常插入新帳戶郑兴，并且經常插入和刪除存儲的密鑰（the balance and nonce of accounts is often changed, and what's more, new accounts are frequently inserted, and keys in storage are frequently inserted and deleted）。因此悟泵，期望的是一種可以在插入杈笔，更新編輯或刪除操作之后能快速計算新的樹根，而無需重新計算整個樹的數(shù)據(jù)結構糕非。還有兩個非常理想的次要屬性：
樹的深度是有限的，即使攻擊者故意制作tx以使樹盡可能深球榆。? ? 否則朽肥，攻擊者可以通過操縱樹來執(zhí)行拒絕服務攻擊，使得每個更新變得非常慢持钉。
樹的根僅取決于數(shù)據(jù)衡招，而不取決于更新的順序。? 以不同的順序進行更新甚至從頭開始重新計算樹得到的應該是相同的樹根每强。
該Patricia樹始腾，簡單來說，也許是我們可以來同時實現(xiàn)所有這些性能最接近的一種解決方法空执。關于它如何工作的最簡單的解釋是浪箭，存儲value的key被encoded到您必須從樹中取下的“路徑path”中。每個節(jié)點有16個子節(jié)點辨绊，因此路徑由十六進制編碼確定：例如奶栖，key“dog”的十六進制編碼的鍵是6 4 6 15 6 7，所以你將從根開始门坷，沿著第6個child宣鄙，然后是第4個，依此類推默蚌，直到你到達終點冻晤。在實踐中，我們可以進行一些額外的優(yōu)化绸吸，以便在樹稀疏時使過程更有效鼻弧，但這是基本原則。上面提到的兩篇文章 更詳細地描述所有功能惯裕。
