在以太坊數(shù)據(jù)結(jié)構(gòu)中，Merkle Patricia Trie始終是個(gè)繞不過去的坎，世界狀態(tài)，交易货葬，交易收據(jù)等都是以這種樹的形式存儲(chǔ)在區(qū)塊鏈數(shù)據(jù)庫(kù)中，并將樹root hash保存在區(qū)塊頭里劲够≌鹜埃可以說(shuō)不弄懂這種樹的原理就沒有辦法真正明白以太坊的數(shù)據(jù)存儲(chǔ)方式。
大家都知道在以太坊cpp版本和go版本采用的是
levelDb這種數(shù)據(jù)庫(kù)征绎，這種數(shù)據(jù)庫(kù)存儲(chǔ)的是[key, value]對(duì)蹲姐。而實(shí)際上以太坊存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)也是[key, value]對(duì)，以狀態(tài)state為例人柿，key是address淤堵，value是[nonce, balance, storageRoot, codeHash]。那么問題來(lái)了顷扩，以太坊為什么不直接按[key, value來(lái)存儲(chǔ)數(shù)據(jù)，而要費(fèi)那么大勁用樹型結(jié)構(gòu)來(lái)存儲(chǔ)呢慰毅？
答案是為了安全性隘截。
而為了引進(jìn)Merkle Patricia Trie，我們要先來(lái)看一種簡(jiǎn)單的樹汹胃。
Radix Trees
中文翻譯為前綴樹婶芭，這是一種用來(lái)查詢的數(shù)據(jù)結(jié)構(gòu)。每次遍歷key的一個(gè)字符着饥，直到找到對(duì)應(yīng)的值犀农。
比如有下面幾個(gè)數(shù)據(jù)：('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')，存儲(chǔ)在Radix Trees里是這樣的：
其中圓圈里是值宰掉，
key的字符組成查詢路徑呵哨，路徑是doge時(shí)的查詢過程為d->o->g->e，需要查詢4次轨奄，而路徑為horse時(shí)查詢需要5次孟害，因此這種樹查詢雖然可行，但是效率不高挪拟。我們后面可以看到以太坊是怎么解決這個(gè)問題的挨务。解決了查詢，然后為了安全性，我們引入了
Merkle Trees谎柄。
Merkle Trees
Merkle Trees又名Hash Trees丁侄，數(shù)據(jù)都存儲(chǔ)在葉節(jié)點(diǎn)，父節(jié)點(diǎn)則存儲(chǔ)葉節(jié)點(diǎn)的hash值朝巫，一級(jí)一級(jí)向上鸿摇， 直到根節(jié)點(diǎn)。因此如果修改了葉節(jié)點(diǎn)的數(shù)據(jù)捍歪，則父節(jié)點(diǎn)hash值就會(huì)改變户辱，根節(jié)點(diǎn)hash值也會(huì)改變，從而很快就可以驗(yàn)證數(shù)據(jù)是否正確糙臼。
保證數(shù)據(jù)不被篡改庐镐，這是區(qū)塊鏈技術(shù)的基礎(chǔ)。
Merkle Patricia Trie
以太坊Merkle Patricia Trie是結(jié)合了上面兩種樹的數(shù)據(jù)結(jié)構(gòu)变逃，兼顧了查詢和安全性必逆。
查詢
前面不是說(shuō)過Radix Trees查詢效率不行嗎？那就進(jìn)行優(yōu)化揽乱，將路徑里相同部分提取出來(lái)名眉，作為共同路徑，從而減少樹的高度凰棉，提供查詢效率损拢。
還是用上面的例子，合并路徑后的樹變?yōu)椋?br>
可以看到將
do和horse作為共同路徑后撒犀，查詢doge的路徑變成了do->g->e福压，只需要查詢3次，而horse只需要查詢一次就夠了或舞。
安全性
節(jié)點(diǎn)與節(jié)點(diǎn)之間的聯(lián)系不再采用內(nèi)存指針的方式荆姆，而是采用hash值的方式，比如上圖中的puppy這個(gè)值的節(jié)點(diǎn)存儲(chǔ)執(zhí)行下一個(gè)節(jié)點(diǎn)的hash值映凳，然后將這個(gè)hash值與實(shí)際節(jié)點(diǎn)對(duì)應(yīng)關(guān)系存儲(chǔ)在[key, value]的數(shù)據(jù)庫(kù)中胆筒。當(dāng)有人篡改coin節(jié)點(diǎn)值時(shí)，也必須要修改puppy節(jié)點(diǎn)里的hash值诈豌，然后verb節(jié)點(diǎn)里hash值也需要修改仆救，直到根節(jié)點(diǎn)，所以我們只需要驗(yàn)證根節(jié)點(diǎn)的hash值矫渔，就知道底層數(shù)據(jù)是否正確派桩。
節(jié)點(diǎn)類型
按功能不同，存在4種節(jié)點(diǎn)：
- NULL節(jié)點(diǎn)
- 分支節(jié)點(diǎn)蚌斩，含有17項(xiàng)數(shù)據(jù)铆惑，[ v0 ... v15, vt ]
- 葉節(jié)點(diǎn)范嘱，含有2項(xiàng)數(shù)據(jù)，[ encodedPath, value ]
- 擴(kuò)展節(jié)點(diǎn)员魏，含有兩項(xiàng)數(shù)據(jù)丑蛤，[ encodedPath, key ]
Merkle Patricia Trie查詢路徑是以nibble(半個(gè)字節(jié)）作為單位。
分支節(jié)點(diǎn)中的前16項(xiàng)數(shù)據(jù)v0-v15分別對(duì)應(yīng)16進(jìn)制的0-0xF撕阎，是用nibble作為索引受裹，可以快速進(jìn)行查詢，比如路徑nibble是0xa虏束，則取分支節(jié)點(diǎn)0xa位置的值棉饶。分支節(jié)點(diǎn)對(duì)應(yīng)圖上的分叉節(jié)點(diǎn)。
葉節(jié)點(diǎn)和擴(kuò)展節(jié)點(diǎn)都是兩項(xiàng)镇匀，只是value不同照藻，那么怎么區(qū)分他們呢？
以太坊是采用添加前綴的方式汗侵，根據(jù)節(jié)點(diǎn)類型和路徑長(zhǎng)度是否是奇偶數(shù)來(lái)添加不同的前綴幸缕。
有一個(gè)對(duì)應(yīng)表：
| hex char | bits | node type partial | path length |
|---|---|---|---|
| 0 | 0000 | extension | even(偶數(shù)) |
| 1 | 0001 | extension | odd(奇數(shù)) |
| 2 | 0010 | terminating (leaf) | even(偶數(shù)) |
| 3 | 0011 | terminating (leaf) | odd(奇數(shù)) |
可以看到前綴為0或者1時(shí)表示擴(kuò)展節(jié)點(diǎn)，2或者3時(shí)表示葉節(jié)點(diǎn)晰韵。
另外前綴為0或者2時(shí)发乔，需要變更為00或20.
例子1
我們用一個(gè)例子來(lái)說(shuō)明：
圖中右上角有4個(gè)
[key, value]對(duì)，我們要存儲(chǔ)這4對(duì)數(shù)據(jù)雪猪。key每個(gè)方框里是一個(gè)nibble栏尚。
- 從這四個(gè)路徑中可以提取出公共路徑
a7，因此可以建立一個(gè)擴(kuò)展節(jié)點(diǎn)A, [00 a7, hashB]只恨，a7是一個(gè)偶數(shù)長(zhǎng)度的擴(kuò)展節(jié)點(diǎn)译仗，前綴為00，hashB是下一個(gè)節(jié)點(diǎn)B的hash值坤次。 - 下一個(gè)
nibble取值有1, 7, f，因此節(jié)點(diǎn)B為一個(gè)分支節(jié)點(diǎn)斥赋，其中index為1缰猴，7，f的位置保存下一個(gè)節(jié)點(diǎn)的hash值疤剑，value為空滑绒。這個(gè)分支節(jié)點(diǎn)為：[ EMPTY, hashC, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, hashD, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, hashE, value]。
hashC, hashD, hashE為下一層節(jié)點(diǎn)的hash值 - 因?yàn)槌霈F(xiàn)了分支隘膘，我們來(lái)看1這個(gè)分支疑故，這個(gè)分支后沒有分支，所以后續(xù)的1355可以作為一個(gè)葉節(jié)點(diǎn)弯菊，為[20 1355, 45.0ETH]纵势，這里1355為偶數(shù)長(zhǎng)度的葉節(jié)點(diǎn)，所以前綴為20。
- 再來(lái)看7這個(gè)分支钦铁，后續(xù)又有d3這共同路徑软舌，因此創(chuàng)建一個(gè)擴(kuò)展節(jié)點(diǎn)D，[00 d3, hashF]牛曹，'d3'是一個(gè)偶數(shù)長(zhǎng)度的擴(kuò)展節(jié)點(diǎn)佛点，前綴為00，
hashF是下一個(gè)節(jié)點(diǎn)F的hash值黎比。 -
d3之后又出現(xiàn)分支3和9超营，因此又出現(xiàn)一個(gè)分支節(jié)點(diǎn)，其中index為3和9的位置保存下一個(gè)節(jié)點(diǎn)的hash值阅虫，value為空演闭。這個(gè)節(jié)點(diǎn)為：[ EMPTY, EMPTY, EMPTY, hashG, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, hashH, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, value] - 剩下的就是兩個(gè)葉節(jié)點(diǎn)，分別為[37, 1.00WEI]和[37, 0.12ETH]书妻，這兩個(gè)都是奇數(shù)長(zhǎng)度的葉節(jié)點(diǎn)船响，因此前綴為3。
- 其他節(jié)點(diǎn)可以按同樣的方法分析躲履。
例子2
我們?cè)儆们懊娴?code>('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')做例子來(lái)說(shuō)明分析過程见间。
由于是采用nibble作為路徑單位，所以先將路徑和值都寫為字節(jié)形式：
<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coin'
<68 6f 72 73 65> : 'stallion'
那么在數(shù)據(jù)庫(kù)中存儲(chǔ)形式為：
rootHash: [ <16>, hashA ]
hashA: [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ]
hashC: [ <20 6f 72 73 65>, 'stallion' ]
hashB: [ <00 6f>, hashD ]
hashD: [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE: [ <17>, hashF ]
hashF: [ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]
hashG: [ <35>, 'coin' ]
我們來(lái)模擬一下真實(shí)的查詢過程工猜，假如我們要查詢doge這個(gè)key對(duì)應(yīng)的值是多少米诉。
-
rootHash已知(存儲(chǔ)在區(qū)塊頭中)，那么從levelDb中讀出key為rootHash的值篷帅，也就是[ <16>, hashA ]史侣，這是一個(gè)擴(kuò)展節(jié)點(diǎn)，路徑為6魏身，剩下路徑為4,6,f,6,7,6,5惊橱，并得到下一個(gè)節(jié)點(diǎn)hashA - 在
levelDb中讀出key為hashA的值，也就是 [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ]箭昵，nibble為4税朴，在位置4讀出下一個(gè)節(jié)點(diǎn)hashB，剩余路徑為6,f,6,7,6,5 - 在
levelDb中讀出key為hashB的值家制，也就是[ <00 6f>, hashD ]正林，這是一個(gè)路徑為6f的擴(kuò)展節(jié)點(diǎn)，因此剩余路徑為6,7,6,5颤殴，并得到下一個(gè)節(jié)點(diǎn)hashD - 在
levelDb中讀出key為hashD的值觅廓，也就是 [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]，nibble為6涵但，在位置6讀出下一個(gè)節(jié)點(diǎn)hashE杈绸，剩余路徑為7,6,5 - 在
levelDb中讀出key為hashE的值帖蔓，也就是 [ <17>, hashF ]，這是一個(gè)路徑為7的擴(kuò)展節(jié)點(diǎn)蝇棉，因此剩余路徑為65讨阻，并得到下一個(gè)節(jié)點(diǎn)hashF - 在
levelDb中讀出key為hashF的值，也就是[ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]篡殷，nibble為6钝吮，在位置6讀出下一個(gè)節(jié)點(diǎn)hashG，剩余路徑為5 - 在
levelDb中讀出key為hashG的值板辽，也就是[ <35>, 'coin' ]奇瘦，這是一個(gè)路徑為5的葉節(jié)點(diǎn)，正好和我們的剩余路徑吻合劲弦，因此我們就得到了最終的值coin耳标。
可見以太坊為了安全性真的增加了不少?gòu)?fù)雜性，降低了效率邑跪。
以太坊中的應(yīng)用
以太坊中實(shí)際情況還要復(fù)雜次坡，數(shù)據(jù)還需要通過RLP編碼。
- State Trie(世界狀態(tài)樹)
路徑是sha3(ethereumAddress)画畅，value是rlp([nonce,balance,storageRoot,codeHash]) - Transactions Trie(交易樹)
路徑是rlp(transactionIndex)砸琅，value是rlp(transaction) - Receipts Trie(交易收據(jù)樹)
路徑是rlp(transactionIndex)，value是rlp(transaction receipt)
參考
Understanding Trie Databases in Ethereum
Modified Merkle Patricia Trie Specification (also Merkle Patricia Tree)
