Patricia Tree
原文??：Patricia Tree
翻譯：Jisen
Merkle Patricia tries提供一個密碼認證的數據結構，可用于存儲所有（鍵抒抬，值）綁定菱魔，雖然在本文的范圍內箭阶，我們將鍵和值限制為字符串（要刪除此限制晌端，只需使用任何序列化格式其他數據類型）挡篓。它們是完全確定性的婉陷，這意味著具有相同（鍵值）綁定的Patricia trie確保與最后一個字節(jié)完全相同，因此具有相同的根散列官研，提供了O(log(n))插入憨攒、查找和刪除的效率，并且比諸如紅黑樹等更復雜的基于比較的替代方法更容易理解和編碼阀参。
序言：Basic Radix Tries
在一個basic radix trie中，每個節(jié)點看起來如下：
[i0, i1 ... in, value]
其中i0 ... in表示字母的符號（通常是二進制或十六進制）瞻坝，value是節(jié)點處的終端值蛛壳，并且i0 ... in slots中的值是NULL或指向（在本例中為其他節(jié)點的散列）的值。這形成了一個基本(key, value)存儲; 例如所刀，如果您對當前映射dog到trie中的值感興趣衙荐，則應先將其轉換dog為字母表中的字母（given 64 6f 67），然后沿著該路徑追溯到trie浮创，直到讀完該路徑的終端值忧吟。也就是說，您首先要查找key/value數據庫中的根哈希以查找trie的根節(jié)點（基本上是其他節(jié)點的鍵的數組）斩披，請使用索引處的值6作為一個關鍵字（并在key/value數據庫中查找它）使節(jié)點向下一級溜族，然后選擇索引4來查找下一個值，然后選擇該索引的索引6垦沉，依此類推煌抒，直到你遵循路徑：root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7，你查找你擁有的節(jié)點的值并返回結果厕倍。
請注意寡壮，查看“trie”中的內容與底層key/value “數據庫”之間存在差異。它們都定義了key/values的排列讹弯，但底層數據庫可以對鍵進行傳統(tǒng)的1步查找况既，而在查找樹中的鍵時需要多個底層數據庫查找才能達到上述最終值。為了消除歧義组民，讓我們把后者稱為a path棒仍。
radix tries的更新和刪除操作很簡單，可以大致如下定義：
def update(node,path,value):
if path == '':
curnode = db.get(node) if node else [ NULL ] * 17
newnode = curnode.copy()
newnode[-1] = value
else:
curnode = db.get(node) 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,path):
if node is NULL:
return NULL
else:
curnode = db.get(node)
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é)點的指針（對于key/value數據庫中的每個查找key == sha3(rlp(value)）降狠，而不是某些32位或64位內存位置对竣，這可能發(fā)生在用C實現的更傳統(tǒng)的trie中。這為數據結構提供了一種形式的密碼認證;如果給定的trie的根hash是公開的榜配，那么任何人都可以提供一個證明否纬，通過提供節(jié)點上升的每一步，攻擊者不可能提供(path, value)對的證明蛋褥，因為根散列最終基于下面的所有散列临燃，所以任何修改都會改變根散列。
如上所述一次遍歷1 nibble路徑時烙心，大多數節(jié)點包含17個元素的數組膜廊。對于路徑中的下一個十六進制字符（nibble）所保持的每個可能值，都有1索引淫茵，并且在路徑已經完全遍歷的情況下爪瓜，1保持最終目標值。這些17個元素的數組節(jié)點被稱為branch節(jié)點匙瘪。
主要說明：Merkle Patricia Trie
然而铆铆，radix tries有一個主要限制：它們效率低下。如果你想在路徑所在的地方存儲一個（path丹喻，value）綁定（在ethereum狀態(tài)的情況下）薄货，長度為64個字符（nibbles bytes32字節(jié)數），則需要超過一千字節(jié)的額外空間來存儲一層的每個字符碍论，每次查找或刪除將采取完整的64個步驟谅猾。這里介紹的Patricia trie解決了這個問題。
優(yōu)化
Merkle Patricia tries通過為數據結構增加一些額外的復雜性來解決低效率問題鳍悠。Merkle Patricia trie中的節(jié)點是以下之一：
-
NULL（表示為空字符串） -
branch17個item的節(jié)點[ v0 ... v15, vt ] -
leaf2個item的節(jié)點[ encodedPath, value ] -
extension2個item的節(jié)點[ encodedPath, key ]
對于64個字符的路徑税娜，在遍歷該trie的前幾層級后，不可避免地會到達一個至少部分路徑不存在發(fā)散路徑的節(jié)點贼涩。要求這樣的節(jié)點除了目標索引（路徑中的下一個nibble）之外巧涧，在每個索引中都有空值（對于16個十六進制字符中的每一個都是一個值），這將是天真的遥倦。相反谤绳，我們通過設置extension表單的節(jié)點來快速查詢[encodedPath, key]，其中encodedPath包含“部分路徑”以跳過之前的步驟（使用下面描述的緊湊編碼）袒哥，并且key用于下一個數據庫查找缩筛。
在leaf節(jié)點的情況下，可以通過第一個nibble中的一個標志確定encodedPath堡称，上述情況就會發(fā)生瞎抛，并且跳過的“部分路徑”將完成路徑的全部剩余部分。在這種情況下value是目標值本身却紧。
然而桐臊，上面的優(yōu)化引入了一些模糊特性胎撤。
當以nibbles遍歷路徑時，我們可能會以奇數個nibbles來遍歷断凶，但因為所有數據都以bytes格式存儲伤提，所以不可能區(qū)分例如nibble 1和nibble 01（兩者都必須存儲為<01>）。要指定奇數長度认烁，而且部分路徑的前綴是一個標志肿男。
說明：使用可選終止符對十六進制序列進行緊湊編碼
如上所述的奇數與偶數剩余部分路徑長度以及葉節(jié)點與擴展節(jié)點的標記位于任何2項節(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
對于剩余的路徑長度（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'
以下是在Merkle Patricia 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(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
假設我們要包含四個path/value對的trie ('do', 'verb')，('dog', 'puppy')窗价，('doge', 'coin')如庭，('horse', 'stallion')。
首先撼港，我們將兩個paths和values轉換為bytes柱彻。下面，路徑的實際字節(jié)表示被表示<>餐胀，雖然values仍然顯示為字符串，表示''為了易于理解（它們也實際上是bytes）：
<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coin'
<68 6f 72 73 65> : 'stallion'
現在瘤载，我們在底層數據庫中使用以下key/value對構建這樣一個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' ]
當一個節(jié)點在另一個節(jié)點內被引用時否灾，包含H(rlp.encode(x))，其中H(x) = sha3(x) if len(x) >= 32 else x和rlp.encode是RLP編碼函數鸣奔。
請注意墨技，更新一個trie時，如果新創(chuàng)建的節(jié)點的長度大于等于32挎狸，則需要將該key/value對(sha3(x), x)存儲在永久性查找表中扣汪。但是，如果節(jié)點短于此值锨匆，則不需要存儲任何內容因為函數f（x）= x是可逆的崭别。
在以太坊上的嘗試
在Ethereum中的所有merkle嘗試使用Merkle Patricia Trie。
從區(qū)塊頭開始恐锣，這些嘗試中有3個根來自3個這樣的tries茅主。
- stateRoot
- transactionsRoot
- receiptsRoot
State Trie
有一個全局狀態(tài)索引，并隨著時間的推移而更新土榴。其中诀姚，path為：sha3(ethereumAddress)；value為：rlp(ethereumAccount)玷禽。更具體地說赫段，以太坊account是一個包含4個item的數組[nonce,balance,storageRoot,codeHash]呀打。在這一點上值得注意的是，這storageRoot是另一個patricia trie的根：
Storage Trie
Storage Trie是所有合同數據所在的地方糯笙。每個帳戶都有一個單獨的存儲索引贬丛。這個trie的path有點復雜，可以參考這個炬丸。
Transactions Trie
每個區(qū)塊都有單獨的transactions瘫寝。path在這里為：rlp(transactionIndex)。transactionIndex是其開采區(qū)塊內的指標稠炬。排序主要由礦工決定焕阿，因此在開采之前這些數據是未知的。區(qū)塊被挖出后首启，transaction trie不會更新暮屡。
Receipts Trie
每個塊都有自己的1Receipts trie。path在這里為：rlp(transactionIndex)毅桃。transactionIndex是其開采區(qū)塊內的指標褒纲。從不更新。
