Patricia木
※Patricia Treeの翻訳です。原文が非常に読み辛い文章で訳すのに苦労しました。ある程度文章を補ったりしていますが、分かりにくかったらすみません。基本的には、既存のMerkle木とPatricia木を組み合わせたという理解で良いかと思います。
Merkle Patricia木（Merkle Patricia tree）は暗号学的に信頼性のあることが証明されたデータ構造であり、あらゆる鍵（key）と値（value）の結合を格納するのに使用することができる。ただし、本文書の範囲では、鍵及び値の型を文字列（訳注：バイト配列のことと思われる）に制限するものとする（この制限を取り払うには、単に他のデータ型を格納する際に、任意の直列化（serialization）形式を使用するようにすれば良い）。本データ構造は完全に決定性がある（deterministic）。すなわち、同一の鍵と値の結合を有する2つのPatricia木は最初から最後のバイトまで完全に同一であることが保証され、そのため、根（root）のハッシュ値は同一となる。また、挿入、探索及び削除に関して、O(log(n))という優等な効率性を示す。更には、赤黒木（red-black tree）のような、Patricia木と同等の役割を果たすものの、比較に基づいていてより複雑であるデータ構造と比べると、本データ構造はその仕組みについて理解して、原始コードとして記述するのが非常に容易である。
序文：基本的な基数木（radix tree）
基本的な基数木では、全ての節（node）は次のような形状をしている。
[ value, i0, i1 ... in ]
i0 ... inはアルファベットの記号を表す（しばしば2進数や16進数である）。valueは節における末端の値である。i0 ... inに入る値はNULL又は他の節へのポインタ（ただし、我々の仕様では、他の節のハッシュ値へのポインタ）である。これは鍵と値を格納する基本的なデータ構造である。たとえば、基数木において、dogという鍵に結び付けられている現在の値を知りたいのならば、最初にdogをアルファベットに変換し（16進数を使用している場合には、646f67を得る）、次に鍵に対応する道（path）を辿ってその道の末端まで木の中を下降し、最後に末端の節の値を読み取る。すなわち、最初に鍵と値を格納するデータ構造の中に含まれる根のハッシュ値を調べて根を取得し、次に根の子である6の節を調べて1つ下の水準（level）の節を取得し、次にその節の子である4の節を調べて・・・、次にその節の子である6の節を調べて・・・という風に、root -> 6 -> 4 -> 6 -> f -> 6 -> 7という道を辿る。そうして、最後の節の値を調べ、結果を返す。
基数木の更新と削除の操作は単純であり、大まかには以下のように定義できる。
def update(node,key,value):
if key == '':
curnode = db.get(node) if node else [ NULL ] * 17
newnode = curnode.copy()
newnode['value'] = 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)
基数木の「Merkle」である部分は、節へのポインタとして、C言語で実装されたより従来型の木とは異なり、32ビットや64ビットのメモリ領域ではなく節に対する決定性がある暗号学的なハッシュ値が使用されているという事実に現れている。これはデータ構造に対して一種の暗号学的な証明を与える。所与の木の根のハッシュ値が公に知られているのならば、誰でも木が特定の鍵に対して所与の値を有しているという証明を、鍵に対応する節から根に至るまでの道の途上にあるそれぞれの節があれば、与えることができる。結局のところ、根のハッシュ値はその下に接続されている全ての節のハッシュ値に基づいており、そのため、木に対する如何なる変更でも根のハッシュ値を変化させるので、攻撃者が実際には存在しない鍵と値の結合に対する存在証明を行うことは不可能である。
しかしながら、基数木には1つの大きな欠点がある。それは、非効率性である。鍵が数百文字であるような鍵と値の結合を単に1つだけ基数木に格納したい場合であっても、1文字毎に1水準下の節を作らなければならないので、1文字毎に1キロバイトを超える余分な領域が必要になる。しかも、それぞれの探索や削除は数百の段階を要する。そこで、この問題を解決するためにPatricia木を導入する。
仕様：終端記号を任意に含む16進数列の、余分な領域を使用しない符号化
16進数列を余分な領域を使用しないで符号化する従来の方法は、2進数（訳注：バイト配列のことと思われる）に変換することであった。すなわち、0f1248という16進数列は15, 18, 72という3つのバイトに変換される。しかしながら、この方法には1つちょっとした問題がある。もし16進数列の長さが奇数だったら、どうすれば良いのか？ このような場合、たとえば、0f1248とf1248を区別する方法がない。しかも、我々がMerkle Patricia木でこの方法を使用しようとすると、16進数列の末尾に特別の記号である（'T'と表される）「終端記号」を付加することができるようにしなければならない。終端記号は16進数列の中で1度のみ、また、末尾のみに入れることができる。そのため、終端記号の存在を示すビットを、更なる別の節のハッシュ値ではなく実際の値が格納されている末端の節の符号化であることを示すビットと見做すことができる。
この両方の問題を解決するため、最終的なバイト配列の最初のニブルには、元の16進数列の（'T'記号を除いた）長さが奇数であるかどうかを示すフラグと、元の16進数列の末尾に終端記号が付加されているかどうかを示すフラグの、2つのフラグを符号化するようにした。これらは最初のニブルの最下位ビットから数えて2つ分のビットにそれぞれ配置される。長さが偶数である16進数列の場合には、最初のニブルを挿入しただけでは結果として生じる16進数列の長さが奇数になってしまうので、最初のニブルの直ぐ後に（値が0の）2番目のニブルを挿入し、結果として生じる16進数列の長さを偶数にし、整数個のバイトで表現できるようにしなければならない。本仕様に従って、我々は以下のような符号化処理を作った。
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 ]
'\x11\x23\x45'
> [ 0, 1, 2, 3, 4, 5 ]
'\x00\x01\x23\x45'
> [ 0, 15, 1, 12, 11, 8, T ]
'\x20\x0f\x1c\xb8'
> [ 15, 1, 12, 11, 8, T ]
'\x3f\x1c\xb8'
主たる仕様：Merkle Patricia木
Merkle Patricia木はより複雑な機構をデータ構造に追加することによって非効率性の問題を解決する。Merkle Patricia木の節は次の何れかである。
1.NULL（空の配列として表される）
2.2つの要素を持つ配列 [ key, value ]
3.17個の要素を持つ配列 [ v0 ... v15, vt ]
木に含まれるある道において、その道の途上にあるそれぞれの節がただ1つの要素だけしか持たない場合には、それらの節の代わりに[ key, value ]の節を1つ作ることによって複数の節を1つの節に纏めるというのが、この木の発想である。鍵は根から任意の節に至るまでの、16進数で表される道を与える。この16進数は上述の余分な領域を使用しない符号化方式を用いて符号化されている。また、値は標準的な基数木の場合と同様に、単に節のハッシュ値である。更に、我々はもう1つの概念的な変更も加えた。内部節（internal node）は最早値を有せず、子を持たない葉（leaf）のみが値を有する。しかしながら、鍵と値を格納するデータ構造が如何なる鍵をも格納できるようにするには、'dog'という鍵と'doge'という鍵を同時に格納できなければならないので、単純にアルファベットに終端記号（16）を付加することにして、値に至る道の途上で決して別の値に行き当たらないようにする。節は別の節の中で、H(rlp.encode(x))という形で参照されている。ここで、len(x) >= 32である場合には、H(x) = sha3(x)である。そうでない場合には、H(x) = xである。また、rlp.encodeはRLP符号化関数である。木を更新する際には、length >= 32であるような節を作成する場合には永続的な探索表に鍵と値の結合である(sha3(x), x)を格納しなければならないが、そうでない場合には関数f(x) = xは可逆的であるから何も格納する必要がないことに注意しなければならない。
以下がMerkle Patricia木の中に含まれる節を取得する拡張されたコードである。
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)
例：
鍵と値の結合('dog', 'puppy'), ('horse', 'stallion'), ('do', 'verb'), ('doge', 'coin')を含む木があると仮定する。最初に、鍵を16進数列の形式に変換する。
[ 6, 4, 6, 15, 16 ] : 'verb'
[ 6, 4, 6, 15, 6, 7, 16 ] : 'puppy'
[ 6, 4, 6, 15, 6, 7, 6, 5, 16 ] : 'coin'
[ 6, 8, 6, 15, 7, 2, 7, 3, 6, 5, 16 ] : 'stallion'
そして、木を構築する。
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' ]
