Patricia Tree
原文??：Patricia Tree
翻譯：Jisen
Merkle Patricia tries提供一個(gè)密碼認(rèn)證的數(shù)據(jù)結(jié)構(gòu)，可用于存儲(chǔ)所有（鍵，值）綁定，雖然在本文的范圍內(nèi)，我們將鍵和值限制為字符串（要?jiǎng)h除此限制，只需使用任何序列化格式其他數(shù)據(jù)類型）。它們是完全確定性的，這意味著具有相同（鍵值）綁定的Patricia trie確保與最后一個(gè)字節(jié)完全相同，因此具有相同的根散列，提供了O(log(n))插入、查找和刪除的效率，并且比諸如紅黑樹等更復(fù)雜的基于比較的替代方法更容易理解和編碼。
序言：Basic Radix Tries
在一個(gè)basic radix trie中，每個(gè)節(jié)點(diǎn)看起來如下：
[i0, i1 ... in, value]
其中i0 ... in表示字母的符號(hào)（通常是二進(jìn)制或十六進(jìn)制），value是節(jié)點(diǎn)處的終端值，并且i0 ... in slots中的值是NULL或指向（在本例中為其他節(jié)點(diǎn)的散列）的值。這形成了一個(gè)基本(key, value)存儲(chǔ); 例如，如果您對(duì)當(dāng)前映射dog到trie中的值感興趣，則應(yīng)先將其轉(zhuǎn)換dog為字母表中的字母（given 64 6f 67），然后沿著該路徑追溯到trie，直到讀完該路徑的終端值。也就是說，您首先要查找key/value數(shù)據(jù)庫(kù)中的根哈希以查找trie的根節(jié)點(diǎn)（基本上是其他節(jié)點(diǎn)的鍵的數(shù)組），請(qǐng)使用索引處的值6作為一個(gè)關(guān)鍵字（并在key/value數(shù)據(jù)庫(kù)中查找它）使節(jié)點(diǎn)向下一級(jí)，然后選擇索引4來查找下一個(gè)值，然后選擇該索引的索引6，依此類推，直到你遵循路徑：root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7，你查找你擁有的節(jié)點(diǎn)的值并返回結(jié)果。
請(qǐng)注意，查看“trie”中的內(nèi)容與底層key/value “數(shù)據(jù)庫(kù)”之間存在差異。它們都定義了key/values的排列，但底層數(shù)據(jù)庫(kù)可以對(duì)鍵進(jìn)行傳統(tǒng)的1步查找，而在查找樹中的鍵時(shí)需要多個(gè)底層數(shù)據(jù)庫(kù)查找才能達(dá)到上述最終值。為了消除歧義，讓我們把后者稱為a path。
radix tries的更新和刪除操作很簡(jiǎn)單，可以大致如下定義：
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”部分出現(xiàn)這樣一個(gè)事實(shí)，即一個(gè)節(jié)點(diǎn)的確定性密碼散列用作指向該節(jié)點(diǎn)的指針（對(duì)于key/value數(shù)據(jù)庫(kù)中的每個(gè)查找key == sha3(rlp(value)），而不是某些32位或64位內(nèi)存位置，這可能發(fā)生在用C實(shí)現(xiàn)的更傳統(tǒng)的trie中。這為數(shù)據(jù)結(jié)構(gòu)提供了一種形式的密碼認(rèn)證;如果給定的trie的根hash是公開的，那么任何人都可以提供一個(gè)證明，通過提供節(jié)點(diǎn)上升的每一步，攻擊者不可能提供(path, value)對(duì)的證明，因?yàn)楦⒘凶罱K基于下面的所有散列，所以任何修改都會(huì)改變根散列。
如上所述一次遍歷1 nibble路徑時(shí)，大多數(shù)節(jié)點(diǎn)包含17個(gè)元素的數(shù)組。對(duì)于路徑中的下一個(gè)十六進(jìn)制字符（nibble）所保持的每個(gè)可能值，都有1索引，并且在路徑已經(jīng)完全遍歷的情況下，1保持最終目標(biāo)值。這些17個(gè)元素的數(shù)組節(jié)點(diǎn)被稱為branch節(jié)點(diǎn)。
主要說明：Merkle Patricia Trie
然而，radix tries有一個(gè)主要限制：它們效率低下。如果你想在路徑所在的地方存儲(chǔ)一個(gè)（path，value）綁定（在ethereum狀態(tài)的情況下），長(zhǎng)度為64個(gè)字符（nibbles bytes32字節(jié)數(shù)），則需要超過一千字節(jié)的額外空間來存儲(chǔ)一層的每個(gè)字符，每次查找或刪除將采取完整的64個(gè)步驟。這里介紹的Patricia trie解決了這個(gè)問題。
優(yōu)化
Merkle Patricia tries通過為數(shù)據(jù)結(jié)構(gòu)增加一些額外的復(fù)雜性來解決低效率問題。Merkle Patricia trie中的節(jié)點(diǎn)是以下之一：
-
NULL（表示為空字符串） -
branch17個(gè)item的節(jié)點(diǎn)[ v0 ... v15, vt ] -
leaf2個(gè)item的節(jié)點(diǎn)[ encodedPath, value ] -
extension2個(gè)item的節(jié)點(diǎn)[ encodedPath, key ]
對(duì)于64個(gè)字符的路徑，在遍歷該trie的前幾層級(jí)后，不可避免地會(huì)到達(dá)一個(gè)至少部分路徑不存在發(fā)散路徑的節(jié)點(diǎn)。要求這樣的節(jié)點(diǎn)除了目標(biāo)索引（路徑中的下一個(gè)nibble）之外，在每個(gè)索引中都有空值（對(duì)于16個(gè)十六進(jìn)制字符中的每一個(gè)都是一個(gè)值），這將是天真的。相反，我們通過設(shè)置extension表單的節(jié)點(diǎn)來快速查詢[encodedPath, key]，其中encodedPath包含“部分路徑”以跳過之前的步驟（使用下面描述的緊湊編碼），并且key用于下一個(gè)數(shù)據(jù)庫(kù)查找。
在leaf節(jié)點(diǎn)的情況下，可以通過第一個(gè)nibble中的一個(gè)標(biāo)志確定encodedPath，上述情況就會(huì)發(fā)生，并且跳過的“部分路徑”將完成路徑的全部剩余部分。在這種情況下value是目標(biāo)值本身。
然而，上面的優(yōu)化引入了一些模糊特性。
當(dāng)以nibbles遍歷路徑時(shí)，我們可能會(huì)以奇數(shù)個(gè)nibbles來遍歷，但因?yàn)樗袛?shù)據(jù)都以bytes格式存儲(chǔ)，所以不可能區(qū)分例如nibble 1和nibble 01（兩者都必須存儲(chǔ)為<01>）。要指定奇數(shù)長(zhǎng)度，而且部分路徑的前綴是一個(gè)標(biāo)志。
說明：使用可選終止符對(duì)十六進(jìn)制序列進(jìn)行緊湊編碼
如上所述的奇數(shù)與偶數(shù)剩余部分路徑長(zhǎng)度以及葉節(jié)點(diǎn)與擴(kuò)展節(jié)點(diǎn)的標(biāo)記位于任何2項(xiàng)節(jié)點(diǎn)的部分路徑的第一個(gè)nibble中。它們導(dǎo)致以下結(jié)果：
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
對(duì)于剩余的路徑長(zhǎng)度（0或2），另一個(gè)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é)點(diǎn)的擴(kuò)展代碼：
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
假設(shè)我們要包含四個(gè)path/value對(duì)的trie ('do', 'verb')，('dog', 'puppy')，('doge', 'coin')，('horse', 'stallion')。
首先，我們將兩個(gè)paths和values轉(zhuǎn)換為bytes。下面，路徑的實(shí)際字節(jié)表示被表示<>，雖然values仍然顯示為字符串，表示''為了易于理解（它們也實(shí)際上是bytes）：
<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coin'
<68 6f 72 73 65> : 'stallion'
現(xiàn)在，我們?cè)诘讓訑?shù)據(jù)庫(kù)中使用以下key/value對(duì)構(gòu)建這樣一個(gè)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' ]
當(dāng)一個(gè)節(jié)點(diǎn)在另一個(gè)節(jié)點(diǎn)內(nèi)被引用時(shí)，包含H(rlp.encode(x))，其中H(x) = sha3(x) if len(x) >= 32 else x和rlp.encode是RLP編碼函數(shù)。
請(qǐng)注意，更新一個(gè)trie時(shí)，如果新創(chuàng)建的節(jié)點(diǎn)的長(zhǎng)度大于等于32，則需要將該key/value對(duì)(sha3(x), x)存儲(chǔ)在永久性查找表中。但是，如果節(jié)點(diǎn)短于此值，則不需要存儲(chǔ)任何內(nèi)容因?yàn)楹瘮?shù)f（x）= x是可逆的。
在以太坊上的嘗試
在Ethereum中的所有merkle嘗試使用Merkle Patricia Trie。
從區(qū)塊頭開始，這些嘗試中有3個(gè)根來自3個(gè)這樣的tries。
- stateRoot
- transactionsRoot
- receiptsRoot
State Trie
有一個(gè)全局狀態(tài)索引，并隨著時(shí)間的推移而更新。其中，path為：sha3(ethereumAddress)；value為：rlp(ethereumAccount)。更具體地說，以太坊account是一個(gè)包含4個(gè)item的數(shù)組[nonce,balance,storageRoot,codeHash]。在這一點(diǎn)上值得注意的是，這storageRoot是另一個(gè)patricia trie的根：
Storage Trie
Storage Trie是所有合同數(shù)據(jù)所在的地方。每個(gè)帳戶都有一個(gè)單獨(dú)的存儲(chǔ)索引。這個(gè)trie的path有點(diǎn)復(fù)雜，可以參考這個(gè)。
Transactions Trie
每個(gè)區(qū)塊都有單獨(dú)的transactions。path在這里為：rlp(transactionIndex)。transactionIndex是其開采區(qū)塊內(nèi)的指標(biāo)。排序主要由礦工決定，因此在開采之前這些數(shù)據(jù)是未知的。區(qū)塊被挖出后，transaction trie不會(huì)更新。
Receipts Trie
每個(gè)塊都有自己的1Receipts trie。path在這里為：rlp(transactionIndex)。transactionIndex是其開采區(qū)塊內(nèi)的指標(biāo)。從不更新。
