Merkle Patricia Trie是完全確定性的堤舒，這意味著具有相同（鍵仅父，值）綁定的Patricia trie具有相同的根hash搪泳，具有O(log(n) )插入查找和刪除的效率楚殿，而且比基于比較的查找方法如紅黑樹更容易理解和編碼哮兰。
1 基本的radix trie
基本的radix trie像下面這樣(節(jié)點(diǎn)類型只有一種：分支節(jié)點(diǎn)):
[i0, i1 ... in, value] //前面存放索引贺纲， 后面存放value（可選）
比如key='dog', 轉(zhuǎn)換為16進(jìn)制是64 6f 67航闺。
在底層key/value數(shù)據(jù)庫中,先找到根節(jié)點(diǎn)hash, 根節(jié)點(diǎn)就是一個其他節(jié)點(diǎn)hash的list, 然后在list的索引=6取出i5,是下一級節(jié)點(diǎn)的hash值, 在底層數(shù)據(jù)庫中根據(jù)該hash值找到該節(jié)點(diǎn)的list, 這樣一級一級往下找,最后找到對應(yīng)的value.
root → 6 → 4 → 6 → 15 → 6 → 7
這個和底層扁平數(shù)據(jù)庫查詢不一樣, 扁平數(shù)據(jù)庫對key查找一次就行,在trie中要在底層數(shù)據(jù)庫中查找多次才能找到value, 為了消除歧義，讓我們將后者稱為 **路徑** 猴誊。
代碼實(shí)現(xiàn)大致如下:
# node: 節(jié)點(diǎn)數(shù)據(jù)
# path/value 數(shù)據(jù)對
def update(node,path,value): #插入一個空path, 表示新建一個trie樹
if path == '':
#新建擴(kuò)展節(jié)點(diǎn)或者使用傳入的節(jié)點(diǎn)數(shù)據(jù)
curnode = db.get(node) if node else [ NULL ] * 17
newnode = curnode.copy()
newnode[-1] = value #保存該path的value
else: # path非空
#新建擴(kuò)展節(jié)點(diǎn)或者使用傳入的節(jié)點(diǎn)數(shù)據(jù)
curnode = db.get(node) if node else [ NULL ] * 17
newnode = curnode.copy()
#創(chuàng)建下一級節(jié)點(diǎn)
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)
可見上述代碼沒有考慮數(shù)據(jù)存儲空間和查找性能, Patricia Trie是壓縮trie樹, 更適合工程上使用.
2 radix trie結(jié)合merkle
merkle出現(xiàn)在: 指向下一級節(jié)點(diǎn)的指針是使用 節(jié)點(diǎn)的確定性加密hash ** ** （對于key/value型數(shù)據(jù)庫,每次查詢 key == sha3(rlp(value)) 潦刃， 而不是傳統(tǒng)意義上下一級節(jié)點(diǎn)地址的指針(C語言實(shí)現(xiàn))。
這為數(shù)據(jù)結(jié)構(gòu)提供了一種密碼認(rèn)證;
如果給定的trie的根哈希是公開的懈叹，則任何人都可以 通過給出給定path上的所有節(jié)點(diǎn), 來證明在給定path上存在一個給定值 乖杠，對于攻擊者,不可能提供一個不存在的（path，value）對的證明, 因?yàn)楦Ｗ罱K基于它下面的所有哈希澄成，所以任何修改都會改變根哈希胧洒。
在如上所述一次遍歷一個半字節(jié)的path中，大多數(shù)節(jié)點(diǎn)是包含17個元素的數(shù)組墨状。 前16個索引代表path中的下一個十六進(jìn)制字符（半字節(jié)）所保持的每個可能值卫漫，以及在路徑已經(jīng)完全遍歷的情況下保存的最終目標(biāo)值。 這17個元素的數(shù)組節(jié)點(diǎn)被稱為 分支節(jié)點(diǎn) ** ** 肾砂。
3 Merkle Trie 結(jié)合Patricia
radix tries 從查找性能和空間占用方面效率都比較低, Patricia 樹通過擴(kuò)展節(jié)點(diǎn)解決該問題.
擴(kuò)展節(jié)點(diǎn)的形式是 [ encodedPath, key ] , encodepath是壓縮路徑編碼, 通過第一個半字節(jié)標(biāo)識和葉子結(jié)點(diǎn)進(jìn)行區(qū)分.
當(dāng)以半字節(jié)遍歷路徑時列赎，我們可能會以 奇數(shù) 個半字節(jié)來遍歷，但是因?yàn)樗械臄?shù)據(jù)都是以 字節(jié)格式 存儲的镐确，所以不可能區(qū)分例如 半字節(jié)1和半字節(jié)01 （都是 必須保存為<01>）包吝。 要指定奇數(shù)長度，部分路徑前面加上一個 標(biāo)志 源葫。如下:
odd是奇數(shù)長度, 不需要附加一個0, even是偶數(shù)長度,需要附加一個0
def compact_encode(hexarray):
term = 1 if hexarray[-1] == 16 else 0 # 16表示結(jié)束符
if term: hexarray = hexarray[:-1] # 將結(jié)束符去掉
oddlen = len(hexarray) % 2 # 計(jì)算是否是奇數(shù)長度
flags = 2 * term + oddlen # 奇數(shù)長度帶16=>3 不帶16=>1 偶數(shù)長度帶16=>2 不帶16=>0
if oddlen: # 奇數(shù)長度
hexarray = [flags] + hexarray
else: #偶數(shù)長度需要補(bǔ)0
hexarray = [flags] + [0] + hexarray
# hexarray 現(xiàn)在有一個奇數(shù)長度, 第一個 nibble 是 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, 16]
'20 0f 1c b8'
> [ f, 1, c, b, 8, 16]
'3f 1c b8'
Merkle Patricia trie中獲取節(jié)點(diǎn)的代碼(待驗(yàn)證):
# path格式是半字節(jié)的list
# node是節(jié)點(diǎn)數(shù)據(jù)的hash值
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: # 表示是葉子節(jié)點(diǎn)或擴(kuò)展節(jié)點(diǎn)
(k2, v2) = curnode
k2 = compact_decode(k2) #將半子節(jié)數(shù)據(jù)組裝為字節(jié),并加上flag,去掉16
if k2 == path[:len(k2)]: # curnode是擴(kuò)展節(jié)點(diǎn)
return get(v2, path[len(k2):]) # 去掉部分路徑
else:
return ''
elif len(curnode) == 17: # 表示是分支節(jié)點(diǎn)
return get_helper(curnode[path[0]],path[1:])
# path是正常key的字符串
def get(node,path):
path2 = []
for i in range(len(path)):
path2.push(int(ord(path[i]) / 16)) # 壓入前半個字節(jié)
path2.push(ord(path[i]) % 16) # 壓入后半個字節(jié)
path2.push(16) # 再壓入結(jié)束符16, 表示是葉子節(jié)點(diǎn)
return get_helper(node,path2) # 格式如: [ f, 1, c, b, 8, 16]
4 例子
4個path/value pairs :
('do', 'verb'),
('dog', 'puppy'),
('doge', 'coin'),
('horse', 'stallion') .
將path和value轉(zhuǎn)換為bytes類型,<>表示bytes, value實(shí)際上還是也是,方便理解還是寫成字符串:
<64 6f> : 'verb' <64 6f 67> : 'puppy' <64 6f 67 65> : 'coin' <68 6f 72 73 65> : 'stallion'
在底層數(shù)據(jù)庫中存儲的key/value對: 一個trie樹
一個節(jié)點(diǎn)被另一個節(jié)點(diǎn)引用時, 引用方式是H(rlp.encode(x)), 其中 H(n) = sha3(n) if len(n) ≥ 32 else n ; rlp.encode表示rlp編碼
上述:
- 根節(jié)點(diǎn)中<16>: 1表示擴(kuò)展奇數(shù)節(jié)點(diǎn), 6表示公共的key
- hashA是分支節(jié)點(diǎn): hashB和hashC的位置表示key=4, key=8
- hashC中: 20表示葉子偶數(shù)節(jié)點(diǎn),6f 72 73 65表示剩余的key
- hashD是分支節(jié)點(diǎn): 'verb'表示上一級擴(kuò)展節(jié)點(diǎn)的value
6 以太坊block中的默克爾-帕特里夏樹
有3種類型的樹:
- 狀態(tài)樹 stateRoot
是全局的樹
path = sha3(ethereumAddress) 以太坊賬戶地址
value = rlp([nonce,balance,storageRoot,codeHash]) 交易次數(shù), 賬戶余額,存儲樹,合約代碼hash
其中storageRoot是另一個trie樹,存儲合約的所有數(shù)據(jù),每個賬戶都有各自的樹獨(dú)立存儲
- 交易樹 transactionsRoot
每個block都有一個交易樹
path = rlp(transactionIndex) 該交易在block中的索引, 順序由礦工決定
value = 交易記錄
該樹生成后永遠(yuǎn)不會被修改
- 憑證樹 receiptsRoot
同上
