Merkle Patricia Tree[1]，梅克爾帕特里夏樹(shù)，提供了一個(gè)基于加密學(xué)的，自校驗(yàn)防篡改的數(shù)據(jù)結(jié)構(gòu)，用來(lái)存儲(chǔ)鍵值對(duì)關(guān)系。后文中將簡(jiǎn)稱為MPT。盡管在本規(guī)范范圍內(nèi)，我們限定鍵值的類型只能是字符串（但仍對(duì)所有的類型適用，因?yàn)橹恍杼峁┮粋€(gè)簡(jiǎn)單的序列化和反序化機(jī)制，將要存儲(chǔ)的類型與字符串進(jìn)行轉(zhuǎn)換即可）。
MPT是確定的。確定性是指同樣內(nèi)容的鍵值，將被保證找到同樣的結(jié)果，有同樣的根哈希。關(guān)于效率方面，對(duì)樹(shù)的插入，查找，刪除的時(shí)間復(fù)雜度控制在O(log(n))。相較于紅黑樹(shù)來(lái)說(shuō)，MPT更好理解和編碼實(shí)現(xiàn)。
1. 前言：基數(shù)樹(shù)（Radix Tree）
在一個(gè)標(biāo)準(zhǔn)的基數(shù)樹(shù)里，要存儲(chǔ)的數(shù)據(jù)，按下述所述：
[i0, i1, ... iN, value]
其中的i0到iN的表示一般是二進(jìn)制或十六進(jìn)制的格式的字母符號(hào)。value表示的是樹(shù)節(jié)點(diǎn)中存儲(chǔ)的最終值。每一個(gè)i0到iN槽位的值，要么是NULL，要么是指向另一個(gè)節(jié)點(diǎn)的指針（在當(dāng)前這個(gè)場(chǎng)景中，存儲(chǔ)的是其它節(jié)點(diǎn)的哈希值）。這樣我們就實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的鍵值對(duì)存儲(chǔ)。舉個(gè)例子來(lái)說(shuō)，如果你想在這個(gè)基數(shù)樹(shù)中，找到鍵dog所對(duì)應(yīng)的值。首先需要將dog轉(zhuǎn)換為比如ascii碼值（十六進(jìn)制表示是646f67）。然后按字母序形成一個(gè)逐層向下的樹(shù)。沿著字母組成的路徑，在樹(shù)的底部葉節(jié)點(diǎn)上，即找到dog對(duì)應(yīng)的值。具體來(lái)說(shuō)，首先找到存儲(chǔ)這個(gè)鍵值對(duì)數(shù)據(jù)的根節(jié)點(diǎn)，找到下一層的第6個(gè)節(jié)點(diǎn)，然后再往下一層，找到節(jié)點(diǎn)4，然后一層一層往下找，直到完成了路徑 root -> 6 -> 4 -> 6 -> f -> 6 -> 7。這樣你將最終找到值的對(duì)應(yīng)節(jié)點(diǎn)。
基數(shù)樹(shù)的更新和刪除操作比較簡(jiǎn)單，可以按下面的定義：
def update(node,key,value):
if key == '':
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[key[0]],key[1:],value)
newnode[key[0]] = newindex
db.put(hash(newnode),newnode)
return hash(newnode)
def delete(node,key):
if key == '' or node is NULL:
return NULL
else:
curnode = db.get(node)
newnode = curnode.copy()
newindex = delete(curnode[key[0]],key[1:])
newnode[key[0]] = newindex
if len(filter(x -> x is not NULL, newnode)) == 0:
return NULL
else:
db.put(hash(newnode),newnode)
return hash(newnode)
1.1 數(shù)據(jù)校驗(yàn)問(wèn)題 - Merkle Tree
基數(shù)樹(shù)的節(jié)點(diǎn)關(guān)系，一般是使用比如C語(yǔ)言的32位或64位的內(nèi)存地址指針來(lái)串聯(lián)起來(lái)的。但在以太坊中為了實(shí)現(xiàn)數(shù)據(jù)的防篡改及校驗(yàn)，我們引入了Merkle Tree，使用節(jié)點(diǎn)的哈希值來(lái)建立節(jié)點(diǎn)關(guān)系。這樣，如果一個(gè)給定的前綴的根哈希值是已知的，那么任何人都可以根據(jù)這個(gè)前綴來(lái)檢查。對(duì)于一個(gè)攻擊者，不可能能證明一個(gè)不存在鍵值對(duì)存在，因?yàn)楦Ｗ罱K依賴所有的下面的哈希值，所以任何的修改都會(huì)導(dǎo)致根哈希值的改變。
1.2 效率問(wèn)題 - Patricia樹(shù)
基數(shù)樹(shù)另一個(gè)主要的缺陷是低效。即使你只想存一個(gè)鍵值對(duì)，但其中的鍵長(zhǎng)度有幾百字符長(zhǎng)，那么每個(gè)字符的那個(gè)層級(jí)你都需要大量的額外空間。每次查找和刪除都會(huì)有上百個(gè)步驟。在這里我們引入Patricia樹(shù)來(lái)解決這個(gè)問(wèn)題。
2. 核心規(guī)范
2.1 鍵數(shù)據(jù)的編碼算法
在介紹完整規(guī)范前，我們先介紹一個(gè)對(duì)鍵的編碼算法，十六進(jìn)制序列的帶可選結(jié)束標(biāo)記的壓縮編碼。傳統(tǒng)的編碼十六進(jìn)制字符串的方式，是將他們轉(zhuǎn)為了十進(jìn)制。比如0f1248表示的是三個(gè)字節(jié)的[15，18，72]。然而，這個(gè)方式有點(diǎn)小小的問(wèn)題，如果16進(jìn)制的字符長(zhǎng)度為奇數(shù)呢。在這種情況下，就沒(méi)有辦法知道如何將十六進(jìn)制字符對(duì)轉(zhuǎn)為十進(jìn)制了。額外的，MPT需要一個(gè)額外的特性，十六進(jìn)制字符串，在結(jié)束節(jié)點(diǎn)上，可以有一個(gè)特殊的結(jié)束標(biāo)記（一般用T表示）。結(jié)束標(biāo)記僅在最后出現(xiàn)，且只出現(xiàn)一次。或者說(shuō)，并不存在一個(gè)結(jié)束標(biāo)記，而是存在一個(gè)標(biāo)記位，標(biāo)記當(dāng)前節(jié)點(diǎn)是否是一個(gè)最終結(jié)點(diǎn)，存著我們要查找的值。如果不含結(jié)束標(biāo)記，則是表明還需指向下一個(gè)節(jié)點(diǎn)繼續(xù)查找。
為了解決上述的這些問(wèn)題。我們強(qiáng)制使用最終字節(jié)流第一個(gè)半字節(jié)（半個(gè)字節(jié)，4位，也叫nibble），編碼兩個(gè)標(biāo)記位。標(biāo)記是否是結(jié)束標(biāo)記和當(dāng)前字節(jié)流的奇偶性（不算結(jié)束標(biāo)記），分別存儲(chǔ)在第一個(gè)半字節(jié)的低兩位。如果數(shù)據(jù)是偶數(shù)長(zhǎng)，我們引入一個(gè)0值的半字節(jié)，來(lái)保證最終是偶數(shù)長(zhǎng)，由此可以使用字節(jié)來(lái)表示整個(gè)字節(jié)流。編碼方式可以參考：
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
上面的代碼可以看出來(lái)，如果要表示的是T結(jié)尾的字符串，term值取1，否則取0。如果為奇數(shù)長(zhǎng)，取值1，否則取值0。由于term標(biāo)記是兩個(gè)標(biāo)記中的較高位，所以將term乘2來(lái)左移一位。如果不算后面的結(jié)束標(biāo)記的字節(jié)流是奇數(shù)的，就不補(bǔ)位。如果是偶數(shù)數(shù)位，就補(bǔ)一個(gè)值為零的半字節(jié)。
一些實(shí)際的轉(zhuǎn)換例子：
> [ 1, 2, 3, 4, 5 ]
'\x11\x23\x45' ( Here in python, '\x11#E' because of its displaying unicodes. )
//不含結(jié)束，所以沒(méi)有結(jié)束標(biāo)記，由于字節(jié)流是奇數(shù)，標(biāo)記位取值1，不補(bǔ)位，所以前面只補(bǔ)一個(gè)半字節(jié)就好。
> [ 0, 1, 2, 3, 4, 5 ]
'\x00\x01\x23\x45'
//不含結(jié)束標(biāo)記的偶數(shù)，且由于是偶數(shù)第一個(gè)nibble是0，由于是偶數(shù)位，需要補(bǔ)一個(gè)值為零的nibble，所以是00。緊跟后面的值。
> [ 0, 15, 1, 12, 11, 8, T ]
'\x20\x0f\x1c\xb8'
//由于有結(jié)束標(biāo)記，除結(jié)束標(biāo)記的長(zhǎng)度為偶數(shù)，所以第一個(gè)nibblie是2，由于是偶數(shù)長(zhǎng)補(bǔ)位一個(gè)值為0的nibble，所以最后加20。
> [ 15, 1, 12, 11, 8, T ]
'\x3f\x1c\xb8'
//由于有結(jié)束標(biāo)記，且為奇數(shù)，第一個(gè)值為3，又由于是奇數(shù)不需要補(bǔ)位，值是3加后面的值。
2.2 Merkle Patricia Tree
MPT在解決低效的問(wèn)題時(shí)，對(duì)當(dāng)前的數(shù)據(jù)結(jié)構(gòu)進(jìn)行了一些改進(jìn)。MPT的節(jié)點(diǎn)類型定義如下。
- NULL（空字符串）
- 兩個(gè)元素的數(shù)組[k, v]（又名鍵值對(duì)節(jié)點(diǎn)）
- 一個(gè)17個(gè)元素的數(shù)組。[v0 ... v15, vt]。（又名分支結(jié)點(diǎn)）
思路是，是當(dāng)出現(xiàn)一些一個(gè)元素的節(jié)點(diǎn)，但卻有很長(zhǎng)路徑的情況時(shí)，將這種層級(jí)關(guān)系縮減為一個(gè)鍵值對(duì)節(jié)點(diǎn)[k, v]。其中鍵值為層級(jí)樹(shù)的路徑元素，使用為上述編碼的十六進(jìn)制串，值為節(jié)點(diǎn)的哈希值，就像標(biāo)準(zhǔn)的基數(shù)樹(shù)一樣。另外，我們?cè)黾恿艘粋€(gè)概念的優(yōu)化，關(guān)于內(nèi)部節(jié)點(diǎn)不能存值，只有那些沒(méi)有孩子節(jié)點(diǎn)的可以存值。但為了讓這個(gè)鍵值對(duì)存儲(chǔ)方案變得更通用，可以同時(shí)存儲(chǔ)dog和doge。我們?cè)黾恿艘粋€(gè)結(jié)束標(biāo)記16到字母表，所以不會(huì)存在一個(gè)值被錯(cuò)誤指向到另一個(gè)值的情況。
對(duì)于一個(gè)鍵值對(duì)節(jié)點(diǎn)，兩個(gè)元素的數(shù)組[k, v]。v只能是一個(gè)值或者節(jié)點(diǎn)。
- 當(dāng)v是一個(gè)值時(shí)，k必須是含結(jié)束標(biāo)記的半字節(jié)按上述的緊湊的編碼串。
- 當(dāng)v是指向另一個(gè)節(jié)點(diǎn)時(shí)，k必須是不含結(jié)束標(biāo)記的半字節(jié)按上述的緊湊編碼串。
對(duì)于一個(gè)分支結(jié)點(diǎn)，一個(gè)17個(gè)元素的數(shù)組[ v0 ... v15, vt]。在v0到v15的每個(gè)元素，要么是一個(gè)節(jié)點(diǎn)，要么是空，而vt則總是一個(gè)值，或空。所以如果只是在v0到v15中的其中一個(gè)元素中存儲(chǔ)值，我們應(yīng)該使用鍵值對(duì)節(jié)點(diǎn)，其中的k是對(duì)包含結(jié)尾標(biāo)記的一個(gè)空的半字節(jié)列表編碼結(jié)果。
下面是在MPT中獲取一個(gè)節(jié)點(diǎn)的代碼：
def get_helper(node,key):
if key == []: 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 == key[:len(k2)]:
return get(v2, key[len(k2):])
else:
return ''
elif len(curnode) == 17:
return get_helper(curnode[key[0]],key[1:])
def get(node,key):
key2 = []
for i in range(len(key)):
key2.push(int(ord(key) / 16))
key2.push(ord(key) % 16)
key2.push(16)
return get_helper(node,key2)
例子，假設(shè)我們有一個(gè)樹(shù)有這樣一些值('dog', 'puppy'), ('horse', 'stallion'), ('do', 'verb'), ('doge', 'coin')。首先，我們將它們轉(zhuǎn)為十六進(jìn)制格式：
[ 6, 4, 6, 15, 16 ] : do => 'verb'
//64 6f
[ 6, 4, 6, 15, 6, 7, 16 ] : dog => 'puppy'
//64 6f 67
[ 6, 4, 6, 15, 6, 7, 6, 5, 16 ] : doge => 'coin'
//64 6f 67 65
[ 6, 8, 6, 15, 7, 2, 7, 3, 6, 5, 16 ] : horse => 'stallion'
//68 6f 72 73 65
創(chuàng)建的樹(shù)，如下圖所示：
ROOT: [ '\x16', A ]
A: [ '', '', '', '', B, '', '', '', C, '', '', '', '', '', '', '', '' ]
B: [ '\x00\x6f', D ]
D: [ '', '', '', '', '', '', E, '', '', '', '', '', '', '', '', '', 'verb' ]
E: [ '\x17', F ]
F: [ '', '', '', '', '', '', G, '', '', '', '', '', '', '', '', '', 'puppy' ]
G: [ '\x35', 'coin' ]
C: [ '\x20\x6f\x72\x73\x65', 'stallion' ]
樹(shù)的構(gòu)造邏輯是root結(jié)點(diǎn)，要構(gòu)造一個(gè)指向下一個(gè)結(jié)點(diǎn)的kv節(jié)點(diǎn)。先對(duì)鍵編碼，由于當(dāng)前節(jié)點(diǎn)不是結(jié)束結(jié)點(diǎn)，存值的鍵為奇數(shù)字符數(shù)，所以前導(dǎo)值為1，又由于奇數(shù)不補(bǔ)位，最終存鍵為0x16。它指向的是一個(gè)全節(jié)點(diǎn)A。下一層級(jí)，要編碼的是d和h的第二個(gè)半字節(jié)，4和6。所以在A節(jié)點(diǎn)的第五個(gè)位置（從零開(kāi)始）和第七個(gè)位置，我們可以看到分別被指向到了B和C兩個(gè)節(jié)點(diǎn)。對(duì)于B節(jié)點(diǎn)往后do，dog，doge來(lái)說(shuō)。他們緊接著的都是一個(gè)編碼為6f的o字符。所以這里，B節(jié)點(diǎn)被編碼為指向D的kv結(jié)點(diǎn)，數(shù)據(jù)是指向D節(jié)點(diǎn)的。其中鍵值存6f，由于是指向另一個(gè)節(jié)點(diǎn)的kv節(jié)點(diǎn)，不包含結(jié)束標(biāo)記，且是偶數(shù)，需要補(bǔ)位0，得到00，最終的編碼結(jié)果是006f。后續(xù)節(jié)點(diǎn)也以此類推。
當(dāng)在一個(gè)節(jié)點(diǎn)中引用另一個(gè)節(jié)點(diǎn)時(shí)，其中包含的是H(rlp.encode(x))。其中哈希算法是H(x) = sha3(x) if len(x) >= 32 else x，這里的rlp.encode，是使用RLP編碼函數(shù)的方法。需要注意的是當(dāng)更新一個(gè)超過(guò)32字節(jié)前綴時(shí)，你需要保存鍵值對(duì)(sha3(x), x)在一個(gè)持久化的只查表中。當(dāng)小于32字節(jié)時(shí)，則不需要轉(zhuǎn)存任何東西。因?yàn)閒(x)始終等于它本身值x。
關(guān)于作者
專注基于以太坊（Ethereum）的相關(guān)區(qū)塊鏈（Blockchain）技術(shù)，了解以太坊，Solidity，Truffle，web3.js。
個(gè)人博客: http://me.tryblockchain.org
版權(quán)所有，轉(zhuǎn)載注明出處
