本文翻譯自：https://github.com/ethereum/wiki/wiki/Patricia-Tree#state-trie

目錄：

• 什么是MPTree
• 序言：基本 Radix Tries
• 主要說明：MP Trie
• 優(yōu)化
• 說明：有可選終止符的16進制序列的壓縮編碼
• 示例
• 以太坊里的Tries
  State Trie
  Storage Trie
  Transactions Trie
  Receipts Trie

一桐玻、MPTree

MP tries提供了一種加密認證數(shù)據(jù)結(jié)構(gòu)，可用來保存所有的（key value)對，本文我們所使用的key和value都是字符串類型（你也可以使用其他數(shù)據(jù)類型的序列化格式）隔显。這種數(shù)據(jù)結(jié)構(gòu)非常明確护赊，只要是同樣的（key,value）對就會是完全一樣照激，從而保證有同樣的根hash趋箩，在這種結(jié)構(gòu)中着绊，增加畦娄、查找又沾、刪除的時間復雜度是 O(log(n))弊仪，相對于其他基于比較的算法（如紅黑Tries)，這種結(jié)構(gòu)非常易于理解和編碼實現(xiàn)杖刷，

導讀：基本的基數(shù)嘗試(Radix Tries)

在一個基礎(chǔ)的radix trie, 每個節(jié)點如下所示

[i0, i1 ... in, value]

這里的 i0 ... in 代表著字母表的符號（通常是二進制或十六進制）励饵， value就是節(jié)點最終的值。i0 ... in 上的值可以是空滑燃，或者是指向其他節(jié)點的指針（在本例中役听，就是其他節(jié)點的hash值）。這組成一個基本的(key,value)存儲不瓶。比如禾嫉，如果你想知道key是dog的value值是多少，首先你需要將dog轉(zhuǎn)化為字母表里字母（比如64 6f 67）蚊丐，然后沿著trie找到完整路徑上字母連起來是dog的值熙参。也就是說，你先在普通的key/value數(shù)據(jù)庫中找到trie的根結(jié)點（通常是指向其他節(jié)點key的數(shù)組）麦备，使用索引6作為key來找下一層的節(jié)點孽椰，再選擇索引4來找下一個節(jié)點，再選擇索引6凛篙，以此類推黍匾，如果你沿著 根結(jié)點 -> 6 -> 4 -> 6 -> 15 -> 6 -> 7的路徑，就能找到節(jié)點的值并返回結(jié)果呛梆。

需要注意的是锐涯，trie和潛在的扁平key/value“DB”是有差別的。盡管他們都是key/value對填物，不過在潛在的DB中是可以象傳統(tǒng)數(shù)據(jù)庫查找那樣纹腌，一步就找到Key值，但在trie中滞磺，則需要花上更多步來查找如上所述的key升薯，為避免混淆，在trie中會使用路徑來表示击困。

在radix tries里的更新涎劈、刪除操作是非常簡單的，大體可用如下代碼表示：

def update(node_hash, path, value):

 if path == '':

 curnode = db.get(node_hash) if node else [ NULL ] * 17

 newnode = curnode.copy()

 newnode[-1] = value

 else:

 curnode = db.get(node_hash) if node else [ NULL ] * 17

 newnode = curnode.copy()

 newindex = update(curnode[path[0]], path[1:], value)

 newnode[path[0]] = newindex

 db.put(hash(newnode), newnode)

 return hash(newnode)

def delete(node_hash, path):

 if node_hash is NULL:

 return NULL

 else:

 curnode = db.get(node_hash)

 newnode = curnode.copy()

 if path == '':

 newnode[-1] = NULL

 else: 

 newindex = delete(curnode[path[0]],path[1:])

 newnode[path[0]] = newindex

 if len(filter(x -> x is not NULL, newnode)) == 0:

 return NULL

 else:

 db.put(hash(newnode), newnode)

 return hash(newnode)

在radix trie中的Merkle部分阅茶，是因為指向節(jié)點的是該節(jié)點的加密哈希指針蛛枚，每次在數(shù)據(jù)庫中查找key/value， key == sha(rlp(value))脸哀，這和用C語言來實現(xiàn)的傳統(tǒng)trie不同坤候。這種方式給數(shù)據(jù)結(jié)構(gòu)做了加密認證，如果一個給定的trie根hash是公開的企蹭，所有人都能夠證明白筹，這個trie有一個特定的值，the trie has a given value at a specific path by providing the nodes going up each step of the way.

攻擊者用錯誤的(path,value)是不可能通過的谅摄，因為根hash最xgtu是基于其下所有的hash值的徒河，下面結(jié)點的變更都會引起根hash值的變化。

每次沿著路徑送漠，如上一次一個nibble,大多數(shù)的節(jié)點是一個有17位元素的數(shù)組顽照， 1 index for each possible value held by the next hex character (nibble) in the path, 還有一位在路徑結(jié)束時，用來標注最終的目標值闽寡。這些17位的元素數(shù)組節(jié)點被稱作分支結(jié)點代兵。

二、Main specification: Merkle Patricia Trie

然而爷狈，radix tries有一個主要的問題：效率太低植影，如果你需要保存64位長的（nibble數(shù)量，byte32)涎永，光是每層一個字母思币，你需要的存儲空間就是上千字節(jié)，每次查找和刪除也需要64步羡微。所以引入了The Patricia trie 來進行優(yōu)化谷饿。

優(yōu)化

MP tries給數(shù)據(jù)結(jié)構(gòu)增加了點復雜度，從來解決操作上的低效妈倔。MP tries上的節(jié)點有以下四種：
1博投、NULL（代表字符空串）
2、分支節(jié)點：一個17位的節(jié)點[ v0 ... v15, vt ]
3盯蝴、葉子節(jié)點 一個2位的節(jié)點[ encodedPath, value ]
4毅哗、拓展節(jié)點：一個2位節(jié)點[ encodedPath, key ]

64字母路徑會不可避免地遇到這種情況：在經(jīng)過前面幾層后會遇到一個節(jié)點，部分路徑不會有分叉结洼，這時如果設置一個每個索引都是空的黎做，只有目標索引才有值（指向下一個nibble)是完全沒必要的。相應的松忍，我們會建立一個拓展節(jié)點來表示蒸殿，這個拓展節(jié)點的結(jié)構(gòu)是[ encodedPath, key ]，encodedPath包含有部分路徑鸣峭，用來向下跳進（ 使用如下所示的壓縮編碼方式)宏所，key則為下一個db查找。

如果是葉子結(jié)點摊溶，在它的encodedPath中的第一個nibble會有標識位來說明爬骤，當上述情況發(fā)生時，也可以設置為部分路徑來結(jié)束剩下的路徑莫换，在這種節(jié)點中霞玄，value就是它自己的目標值了骤铃。

不過，上述的優(yōu)化又帶來了新的問題：

當查找路徑時坷剧，可能是奇數(shù)個nibble惰爬，不過由于所有的數(shù)據(jù)是字節(jié)形式，它們之間可能會沒有區(qū)別惫企。比如撕瞧，nibble1,和nibble01是一樣的（都表示為<01>),為了表示長度是奇數(shù)，這些部分路徑會有個前綴標識位狞尔。

三丛版、Specification: Compact encoding of hex sequence with optional terminator

用來表示部分路徑的奇數(shù)位和偶數(shù)位差別，還有葉子節(jié)點和拓展節(jié)點的類型標識位偏序，就在部分路徑第一個nibble上页畦，如下表所示：

hex char bits | node type partial path length

0 0000 | extension even

1 0001 | extension odd

2 0010 | terminating (leaf) even

3 0011 | terminating (leaf) odd

對余下路徑長度的偶數(shù)（標識位是0或2），另一個0補丁nibble通常如下所示：

def compact_encode(hexarray):

 term = 1 if hexarray[-1] == 16 else 0 

 if term: hexarray = hexarray[:-1]

 oddlen = len(hexarray) % 2

 flags = 2 * term + oddlen

 if oddlen:

 hexarray = [flags] + hexarray

 else:

 hexarray = [flags] + [0] + hexarray

 // hexarray now has an even length whose first nibble is the flags.

 o = ''

 for i in range(0,len(hexarray),2):

 o += chr(16 * hexarray[i] + hexarray[i+1])

 return o

舉例：

[ 1, 2, 3, 4, 5, ...]

'11 23 45'

[ 0, 1, 2, 3, 4, 5, ...]

'00 01 23 45'

[ 0, f, 1, c, b, 8, 10]

'20 0f 1c b8'

[ f, 1, c, b, 8, 10]

'3f 1c b8'

這里拓展編碼禽车，如何得到MP trie中的一個節(jié)點：

def get_helper(node,path):

 if path == []: return node

 if node = '': return ''

 curnode = rlp.decode(node if len(node) < 32 else db.get(node))

 if len(curnode) == 2:

 (k2, v2) = curnode

 k2 = compact_decode(k2)

 if k2 == path[:len(k2)]:

 return get_helper(v2, path[len(k2):])

 else:

 return ''

 elif len(curnode) == 17:

 return get_helper(curnode[path[0]],path[1:])

def get(node,path):

 path2 = []

 for i in range(len(path)):

 path2.push(int(ord(path[i]) / 16))

 path2.push(ord(path[i]) % 16)

 path2.push(16)

 return get_helper(node,path2)

示例Trie
假設我們需要一個Trie寇漫，包括四個path/value對，('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion').

首先殉摔，我們需要把path和value都轉(zhuǎn)換為字節(jié)州胳，如下所示。路徑實際的字符表示會外打<>逸月，value仍然用字符串‘’顯示栓撞，for easier comprehension (they, too, would actually be bytes):

<64 6f> : 'verb'

<64 6f 67> : 'puppy'

<64 6f 67 65> : 'coin'

<68 6f 72 73 65> : 'stallion'

現(xiàn)在，我們用下面的key/value對構(gòu)建了一個Trie

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' ]

示例中的根hash = <59 91 bb 8c 65 14 14 8a 29 db 67 6a 14 ac 50 6c d2 cd 57 75 ac e6 3c 30 a4 fe 45 77 15 e9 ac 84>.

When one node is referenced inside another node, what is included is H(rlp.encode(x)), where H(x) = sha3(x) if len(x) >= 32 else x and rlp.encode is the RLP encoding function.

需要注意碗硬，當更新trie時瓤湘，需要存儲key/value對(sha3(x), x),保存在一個持續(xù)的查找表，如果新創(chuàng)始的節(jié)點長度>=32恩尾。不過如此這個節(jié)點32短弛说，就什么都不用管，因為function f(x) = x是可逆的

四翰意、以太坊里的Tries

以太坊里的merket tries結(jié)構(gòu)使用的都是MP Trie

先看區(qū)塊頭木人，可以發(fā)現(xiàn)有三個根哈希指向三個tries:

• stateRoot
• transactionRoot
• receiptsRoot

State Trie

• 以太坊里有一個全局狀態(tài)Trie,隨時都在更新。這其中冀偶，路徑的值是sha3(ethereumAddress)醒第，value值則是rlp(ethereumAccount)。一個以太坊 account 是一個4元數(shù)組[nonce,balance,storageRoot,codeHash]进鸠。需要指出的是這里的storageRoot是另一個patricia tree的根稠曼。

Storage Trie

這里所有有效的合約數(shù)據(jù)。每個帳戶都有單獨的storage trie客年。在這個表里霞幅，path還是有些復雜的

Transactions Trie

每個區(qū)塊都有一個單獨的事件trie. Path是rlp(transactionIndex)漠吻。transactionIndexj 是它自己挖出來序列位。順序大多數(shù)情況下是由礦工來決定的蝗岖，因此沒挖出聲來侥猩，這些交易的序號是沒人知道。當區(qū)塊挖出來后抵赢，這個交易trie就不會再變了。

Receipts Trie

每個區(qū)塊都有自己的Receipts trie. 這里的path是rlp(transactionIndex). transactionIndex是被挖出來自己挖出來的的索值唧取。從不更新铅鲤。