本篇文章主要介紹比特幣中的數(shù)據(jù)結(jié)構(gòu)：Merkle Tree痊土。
一把篓、Merkle Tree
Merkle Tree翻譯中文的意思是梅克爾樹(shù)纫溃。Merkle Tree是BTC的區(qū)塊中的交易組織方式，它和傳統(tǒng)的二叉樹(shù)主要區(qū)別在于Merkle tree的指針均為Hash指針纸俭。
下圖就是一個(gè)Merkle Tree
在這個(gè)merkle tree 中最底層的葉子節(jié)點(diǎn)表示的是數(shù)據(jù)塊data block皇耗，在區(qū)塊鏈中代表的就是交易信息tx，圖中總共由8個(gè)tx塊揍很，對(duì)其從左往右編號(hào)為1-8郎楼。在tx塊這一層的上面三層均為hash指針，在最頂層為包含兩個(gè)hash指針的節(jié)點(diǎn)窒悔，對(duì)這個(gè)節(jié)點(diǎn)取hash值便可以得到這顆merkle tree的根hash值merkle root呜袁。這個(gè)根hash值是存儲(chǔ)在區(qū)塊中的。區(qū)塊分為block header和block body 兩部分简珠，根hash值存儲(chǔ)在block header中阶界，但在bloker header 并不存儲(chǔ)具體的交易內(nèi)容，而在blocker body里存有交易列表聋庵。比特幣中的節(jié)點(diǎn)由兩種膘融，一種為全節(jié)點(diǎn)，包括blocker header 和blocker body,另一種為輕節(jié)點(diǎn)僅有blocker header祭玉。觀察merkle tree這種數(shù)據(jù)結(jié)構(gòu)氧映，所有的節(jié)點(diǎn)相連均使用了hash指針，顯然是使用這種數(shù)據(jù)結(jié)構(gòu)可以確保數(shù)據(jù)是無(wú)法被篡改的脱货，一旦想要修改某個(gè)交易信息tx岛都，就必須往上修改hash指針中的hash值律姨，而修改了hash指針中的hash值就必須再修改上一層hash指針中的hash值，如此以往直到根hash指針臼疫，你只需要保存根hash的值不被篡改就可以保證所有交易不被篡改择份。通過(guò)使用這種數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)merkle proof,它的應(yīng)用場(chǎng)景主要是在節(jié)點(diǎn)為輕節(jié)點(diǎn)的情形下，輕節(jié)點(diǎn)種僅有根hash的值烫堤，如果交易發(fā)生荣赶，要如何向輕節(jié)點(diǎn)證明已經(jīng)將交易寫(xiě)入?yún)^(qū)塊中，也就是merkle proof的過(guò)程塔逃，具體過(guò)程如圖讯壶。圖中描述的是向輕節(jié)點(diǎn)證明黃色的交易塊tx,也就是編號(hào)3已經(jīng)寫(xiě)入?yún)^(qū)塊鏈中merkle proof的過(guò)程。首先輕節(jié)點(diǎn)要向全節(jié)點(diǎn)發(fā)出請(qǐng)求湾盗，請(qǐng)求能證明黃色方塊在這顆merkle tree中的mekle proof伏蚊。之后全節(jié)點(diǎn)將返回給輕節(jié)點(diǎn)圖中標(biāo)注紅色的hash值，在有了紅色的hash值之后格粪，輕節(jié)點(diǎn)能在本地計(jì)算出所有綠色的hash值躏吊，進(jìn)而計(jì)算出根hash的值，再和blocker header中原先保存的根hash值進(jìn)行對(duì)比即可知道交易是否已經(jīng)寫(xiě)入?yún)^(qū)塊中帐萎。這個(gè)過(guò)程其實(shí)就是在二叉樹(shù)從葉子節(jié)點(diǎn)出發(fā)找到一條到達(dá)節(jié)點(diǎn)的路徑比伏，所以merkle proof 的時(shí)間復(fù)雜度是log(n)級(jí)別的。
