在區(qū)塊鏈中脯倚， merkle樹(shù)充當(dāng)著一個(gè)代表性的角色纲酗，一個(gè)區(qū)塊中的所有交易信息都被它歸納總結(jié)脚猾，大大提高區(qū)塊鏈的效率霍狰。下面先講一下區(qū)塊鏈（以比特幣系統(tǒng)為例）中為什么要用merkle樹(shù)這個(gè)方法抡草，并且引申出比特幣輕錢(qián)包的實(shí)現(xiàn)基礎(chǔ)--簡(jiǎn)化支付驗(yàn)證（SPV）。不會(huì)像單純講技術(shù)那樣枯燥的蔗坯，相信用過(guò)btc錢(qián)包的都會(huì)對(duì)本文感興趣渠牲。
?
大家都知道，比特幣網(wǎng)絡(luò)中所有產(chǎn)生的交易都要打包進(jìn)區(qū)塊中步悠，一般情況下，一個(gè)區(qū)塊中包含幾百上千筆交易是很常見(jiàn)的瘫镇。由于比特幣的去中心化特性鼎兽，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)必須是獨(dú)立，自給自足的铣除，也就是每個(gè)節(jié)點(diǎn)必須存儲(chǔ)一個(gè)區(qū)塊鏈的完整副本谚咬。在2014年4月，比特幣網(wǎng)絡(luò)中一個(gè)全節(jié)點(diǎn)要存儲(chǔ)尚粘、處理所有區(qū)塊的數(shù)據(jù)择卦，需要占用15GB的空間，并且隨著越來(lái)越多的人使用比特幣郎嫁，每個(gè)月以超過(guò)1GB的速度在增長(zhǎng)秉继。到如今，完整的下載比特幣所有的區(qū)塊數(shù)據(jù)泽铛，也就是運(yùn)行一個(gè)全節(jié)點(diǎn)尚辑，需要200GB以上的空間...
這樣的規(guī)則隨著日益劇增的全節(jié)點(diǎn)所需空間，越來(lái)越難以讓人遵守盔腔，難道讓每個(gè)人都去運(yùn)行一個(gè)全節(jié)點(diǎn)嗎杠茬？還有節(jié)點(diǎn)就是區(qū)塊鏈網(wǎng)絡(luò)中的完全參與者，他們要遵守節(jié)點(diǎn)必須驗(yàn)證交易和區(qū)塊弛随，再加上想要與其他節(jié)點(diǎn)交互瓢喉、下載新區(qū)塊，對(duì)網(wǎng)絡(luò)流量也是有一定要求的舀透，節(jié)點(diǎn)要做的會(huì)越來(lái)越麻煩栓票，并且效率低下。
于是中本聰在比特幣白皮書(shū)中提出了對(duì)這個(gè)問(wèn)題的解決方案：簡(jiǎn)化支付驗(yàn)證（Simplified Payment Verification, SPV）盐杂。SPV是一個(gè)比特幣輕節(jié)點(diǎn)逗载，也就是我們大部分人在電腦安裝的輕量級(jí)的比特幣錢(qián)包哆窿，理論上來(lái)說(shuō)，要驗(yàn)證一筆交易厉斟，錢(qián)包需要遍歷所有的區(qū)塊找到和該筆交易相關(guān)的所有交易進(jìn)行逐個(gè)驗(yàn)證才是可靠的挚躯。但有了SPV就不用這么麻煩了，它不需要同步下載整個(gè)區(qū)塊鏈的數(shù)據(jù)即不用運(yùn)行全節(jié)點(diǎn)就可以驗(yàn)證支付擦秽，也不需要驗(yàn)證區(qū)塊和交易码荔，用戶只需要保存所有的區(qū)塊頭就可以了。要知道感挥，區(qū)塊頭包含著區(qū)塊的必要屬性缩搅，僅80個(gè)字節(jié)大小，而區(qū)塊體當(dāng)中包含著成百上千筆交易触幼，每筆交易一般要400多個(gè)字節(jié)大小硼瓣。
這里需要注意的是，SPV強(qiáng)調(diào)的是驗(yàn)證支付置谦，不是驗(yàn)證交易堂鲤。這兩個(gè)概念是不同的。驗(yàn)證支付媒峡，比較簡(jiǎn)單瘟栖，只需要判斷用于支付的那筆交易是否被驗(yàn)證過(guò)，以及得到網(wǎng)絡(luò)多少次確認(rèn)（即有多少個(gè)區(qū)塊疊加）谅阿。而交易驗(yàn)證則復(fù)雜的多半哟，需要驗(yàn)證賬戶余額是否足夠支出、是否存在雙重支付签餐、交易腳本是否通過(guò)等問(wèn)題寓涨，一般這個(gè)操作是由全節(jié)點(diǎn)的礦工來(lái)完成。
為了實(shí)現(xiàn)SPV贱田，需要有一種方式來(lái)檢查一個(gè)區(qū)塊是否包含了某筆交易缅茉，而不用去下載整個(gè)區(qū)塊。這就是merkle樹(shù)所要完成的事男摧。先來(lái)看看什么是merkle樹(shù)吧蔬墩。
1.概念
Merkle tree（默克爾樹(shù)），常叫它merkle樹(shù)耗拓，是一種哈希二叉樹(shù)拇颅，在計(jì)算機(jī)科學(xué)中，二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)乔询，每個(gè)節(jié)點(diǎn)代表一條結(jié)構(gòu)化數(shù)據(jù)樟插。通常子樹(shù)被稱作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）。二叉樹(shù)常被用于實(shí)現(xiàn)數(shù)據(jù)快速查詢。
2.結(jié)構(gòu)
由一個(gè)根節(jié)點(diǎn)黄锤、一組中間節(jié)點(diǎn)和一組葉節(jié)點(diǎn)組成搪缨。葉節(jié)點(diǎn)包含存儲(chǔ)數(shù)據(jù)或其哈希值，中間節(jié)點(diǎn)是它的兩個(gè)孩子節(jié)點(diǎn)內(nèi)容的哈希值鸵熟，根節(jié)點(diǎn)也是由它的兩個(gè)子節(jié)點(diǎn)內(nèi)容的哈希值組成副编。所以Merkle樹(shù)也稱哈希樹(shù)。
3.特點(diǎn)
技術(shù)特點(diǎn)就不多講了流强，主要特點(diǎn)就是：底層（葉子節(jié)點(diǎn)）數(shù)據(jù)的任何變動(dòng)痹届，都會(huì)逐級(jí)向上傳遞到其父節(jié)點(diǎn)，一直到Merkle樹(shù)的根節(jié)點(diǎn)使得根節(jié)點(diǎn)的哈希值發(fā)生變化打月。
4.總結(jié)原理
區(qū)塊鏈中每個(gè)區(qū)塊都會(huì)有一個(gè) Merkle 樹(shù)队腐，它從葉子節(jié)點(diǎn)（樹(shù)的底部）開(kāi)始，一個(gè)葉子節(jié)點(diǎn)就是一個(gè)交易哈希奏篙。葉子節(jié)點(diǎn)的數(shù)量必須是雙數(shù)柴淘，但是并非每個(gè)塊都包含了雙數(shù)的交易。如果一個(gè)塊里面的交易數(shù)為單數(shù)秘通，那么就將最后一個(gè)葉子節(jié)點(diǎn)（也就是 Merkle 樹(shù)的最后一個(gè)交易悠就，不是區(qū)塊的最后一筆交易）復(fù)制一份湊成雙數(shù)。
從下往上充易，兩兩成對(duì)，連接兩個(gè)節(jié)點(diǎn)哈希荸型，將組合哈希作為新的哈希盹靴。新的哈希就成為新的樹(shù)節(jié)點(diǎn)。重復(fù)該過(guò)程瑞妇，直到僅有一個(gè)節(jié)點(diǎn)稿静，也就是樹(shù)根。根哈希然后就會(huì)當(dāng)做是整個(gè)塊交易的唯一標(biāo)示辕狰，將它保存到區(qū)塊頭改备，然后用于工作量證明。
以上就是對(duì)于merkle樹(shù)的介紹蔓倍，感興趣的話悬钳，后面不妨跟著阿深一起一層層剝開(kāi)區(qū)塊鏈，歡迎大家轉(zhuǎn)發(fā)評(píng)論偶翅。如果對(duì)你有幫助不勝榮幸默勾。
