マークル・パトリシア・ツリー

マークル・パトリシア・ツリー(Patricia Merkle Trie)は、暗号的に認証されたデータ構造を提供し、すべての (key, value)バインディングを保存するために使用できます。

マークル・パトリシア・ツリーは、完全に決定的な構造であり、同じ(key, value)バインディングを持つツリーは、最後のバイトまで必ず同一になります。 それらが同じルートハッシュを持ち、挿入、検索、削除においてO(log(n))という優れた効率を発揮します。 さらに、レッド・ブラック・ツリーのような比較に基づく複雑な代替案よりも、理解やコーディングが簡単です。

前提知識

このページを理解するには、ハッシュ(opens in a new tab)、マークル ツリー(opens in a new tab)、ツリー(opens in a new tab)、シリアライゼーション(opens in a new tab)に関する基本的な知識が必要です。

基本的な基数ツリー

基本的な基数ツリーでは、すべてのノードは次のようになります。

1    [i_0, i_1 ... i_n, value]

i_0 ... i_nは、アルファベットの記号列(通常は2進数または16進数)を表し、valueはノードの最終値、スロット i_0, i_1 ... i_nの値は、NULLまたは他のノードへのポインタ(イーサリアムの場合はハッシュ値)です。 これにより、基本的な(key, value)型ストアが形成されます。

キーバリューセットに対する順序を永続化するために、基数ツリーのデータ構造を使用するとします。 ツリーで現在dogに対応する値を知るには、最初にdogのアルファベットの文字を変換します(64 6f 67)。次に、値が見つかるまで64 6f 67のパスをたどってツリーを下ります。 つまり、ツリーのルートノードを見つけるために、フラットなキーバリューDBのルートハッシュを調べることから始めます。 これは、他のノードを指すキーの配列として表現されます。 インデックス6の値をキーとして使用し、フラットなキーバリューDBで検索し、ノードを1レベル下げます。 次にインデックス4を選択して次の値を検索し、次にインデックス6を選択します。 root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7のパスをたどり、ノードの値を参照して結果を返します。

「ツリー」で何かを検索することと、下層のフラットなキーバリュー型「データベース」で検索することには、違いがあります。 どちらもキーバリューの配列を定義しますが、下層のデータベースは従来の1ステップのキー検索が実行できます。 ツリーでキーを検索するには、複数のデータベースを検索して上記の最終値を得る必要があります。 あいまいさをなくすために、後者をpathとしましょう。

基数ツリーの更新操作と削除操作は、次のように定義できます。

1    def update(node,path,value):
2        if path == '':
3            curnode = db.get(node) if node else [ NULL ] * 17
4            newnode = curnode.copy()
5            newnode[-1] = value
6        else:
7            curnode = db.get(node) if node else [ NULL ] * 17
8            newnode = curnode.copy()
9            newindex = update(curnode[path[0]],path[1:],value)
10            newnode[path[0]] = newindex
11        db.put(hash(newnode),newnode)
12        return hash(newnode)
13
14    def delete(node,path):
15        if node is NULL:
16            return NULL
17        else:
18            curnode = db.get(node)
19            newnode = curnode.copy()
20            if path == '':
21                newnode[-1] = NULL
22            else:
23                newindex = delete(curnode[path[0]],path[1:])
24                newnode[path[0]] = newindex
25
26            if all(x is NULL for x in newnode):
27                return NULL
28            else:
29                db.put(hash(newnode),newnode)
30                return hash(newnode)
すべて表示

「マークル」基数ツリーは、決定論的に生成された暗号ハッシュダイジェストを使用してノードをリンクすることによって構築されます。 このコンテンツアドレッシング(キーバリューDBでkey == keccak256(rlp(value)))は、格納されたデータの暗号完全性保証を提供します。 特定のツリーのルートハッシュが公に知られている場合、特定の値をツリールートに結合する各ノードのハッシュ値を提供することで、ツリーの内部にあるリーフデータにアクセスして、特定のパスに特定の値が存在していることを証明できます。

攻撃者は、存在しない(path, value)のペアの証明を提供することは不可能です。これはルートハッシュは、結局のところその下のにあるすべてのハッシュ値に基づいているためです。 下層の変更はルートハッシュを変更します。 ハッシュについては、データの構造情報を圧縮して表現し、ハッシュ関数の事前イメージによって保護されていると考えることができます。

基数ツリーの最小単位(1つの16 進数文字、すなわち4ビットの2進数)を「ニブル」と呼びます。 上記のように一度に1つのニブルでパスを横断している間、ノードは最大で16の子を参照することができますがvalue要素を含んでいます。 そのため、ノードは長さ17の配列として表されます。 これらの17要素配列を「ブランチノード」と呼びます。

マークル・パトリシア・ツリー

基数ツリーには、1つの大きな制限があります。それは、非効率的であることです。 イーサリアムのようにパスが64文字長 (bytes32単位のニブル数)の1つの(path, value)のバインディングを格納する場合、1文字を格納する1レベルに、1キロバイト以上のスペースが必要となり、また、それぞれの検索または削除には、64ステップが必要です。 次に紹介するパトリシア・ツリーは、この問題を解決します。

最適化

マークル・パトリシア・ツリーのノードは、以下のいずれかです。

1. NULL (空文字列を表す)
2. branch 17アイテムのノード [ v0 ... v15, vt ]
3. leaf 2アイテムのノード [ encodedPath, value ]
4. extension 2アイテムのノード [ encodedPath, key ]

64文字のパスでは、ツリーの最初のいくつかのレイヤーを横断した後、少なくとも下方の一部に分岐パスが存在しないノードに到達することは避けらません。 パスに沿って最大15のNULLのスパースノードを作成する必要性を回避するために、[ encodedPath, key ]フォームのextensionノードを設定することで下りへショートカットをします。このencodedPathは、次へスキップするための「部分パス」を含みます(後述のコンパクトエンコーディングを使用)。そして、key は、次のDBルックアップ用です。

leafノードは、encodedPathの最初のニブルのフラグでマークできます。パスは、前のノードのすべてのパスのフラグメントをエンコードし、valueを直接調べることができます。

しかし、上記の最適化は、次の問題があります。

パスをニブルで横断する場合、すべてのデータがbytes形式で格納されているため、ニブルの数が奇数になる場合があります。 例えば、ニブル1とニブル01を区別することはできません(両方とも<01>として格納される必要があります)。 奇数の長さを指定するには、部分パスの前にフラグをつけます。

仕様: オプショナルターミネーターを使用した16進数シーケンスのコンパクトエンコーディング

上記の残りの部分パス長が偶数または奇数かと、リーフまたは拡張ノードかを表すフラグは両方、あらゆる「2アイテムのノード」の部分パスの最初のニブルにあります。 結果は、次の通りになります。

1hex char    bits    |    node type partial     path length
2----------------------------------------------------------
3   0        0000    |       extension              even
4   1        0001    |       extension              odd
5   2        0010    |   terminating (leaf)         even
6   3        0011    |   terminating (leaf)         odd

偶数の残りのパス長 (0または2)の場合 、もう一つの0の「パディング」のニブルが常に続きます。

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term: hexarray = hexarray[:-1]
4        oddlen = len(hexarray) % 2
5        flags = 2 * term + oddlen
6        if oddlen:
7            hexarray = [flags] + hexarray
8        else:
9            hexarray = [flags] + [0] + hexarray
10        // hexarray now has an even length whose first nibble is the flags.
11        o = ''
12        for i in range(0,len(hexarray),2):
13            o += chr(16 * hexarray[i] + hexarray[i+1])
14        return o
すべて表示

例：

1    > [ 1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [ 0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [ 0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [ f, 1, c, b, 8, 10]
8    '3f 1c b8'

以下は、パトリシア・マークル・ツリーでノードを取得する拡張コードです。

1    def get_helper(node,path):
2        if path == []: return node
3        if node = '': return ''
4        curnode = rlp.decode(node if len(node) < 32 else db.get(node))
5        if len(curnode) == 2:
6            (k2, v2) = curnode
7            k2 = compact_decode(k2)
8            if k2 == path[:len(k2)]:
9                return get(v2, path[len(k2):])
10            else:
11                return ''
12        elif len(curnode) == 17:
13            return get_helper(curnode[path[0]],path[1:])
14
15    def get(node,path):
16        path2 = []
17        for i in range(len(path)):
18            path2.push(int(ord(path[i]) / 16))
19            path2.push(ord(path[i]) % 16)
20        path2.push(16)
21        return get_helper(node,path2)
すべて表示

ツリーの例

次の4つのパスバリューのペアを含むツリーが必要だとします。 ('do', 'verb')、('dog', 'puppy')、('doge', 'coin')、('horse', 'stallion')

まず、パスと値(バリュー)の両方をbytesに変換します。 以下では、pathsを実際のバイト表現 <>によって表示しています。しかし、 valuesは、分かりやすいように文字列として''で表示しています(実際はbytes) 。

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coin'
4    <68 6f 72 73 65> : 'stallion'

それでは、下層のデータベースで、次のようなキーバリューのペアを持つこのようなツリーを構築します。

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashD ]
4    hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

1つのノードが内部の別のノードから参照されるとき、含まれているのは、H(rlp.encode(x))であり、H(x) = keccak256(x) if len(x) >= 32 else xとrlp.encodeは、RLPエンコーディング関数です。

ツリーを更新するとき、新しく作成されたノードの長さが32以上の場合、キーバリューのペア(keccak256(x), x)を永続的なルックアップテーブルに格納する必要があることに注意してください。 ただし、ノードがそれよりも短い場合、関数 function f(x) = x は可逆であるため、何も格納する必要はありません。

イーサリアムのツリー

イーサリアムの実行レイヤーのすべてのマークルツリーは、マークル・パトリシア・ツリーを使用しています。

ブロックヘッダーに、これらのツリーの3つから、3つのルートがあります。

1. stateRoot (ステートルート)
2. transactionsRoot (トランザクションルート)
3. receiptsRoot (レシートルート)

ステート(状態)ツリー

グローバルの状態ツリーが1つあり、クライアントがブロックを処理するたびに更新されます。 その中では、 pathは常にkeccak256(ethereumAddress)であり、valueは常にrlp(ethereumAccount)です。 より具体的には、イーサリアムのaccountは、4つのアイテムの配列[nonce,balance,storageRoot,codeHash]です。 この点において、このstorageRootが、もう一つのパトリシア・ツリーであることは非常に重要です。

ストレージツリー

ストレージツリーは、 すべてのコントラクトデータが存在する場所です。 アカウントごとに個別のストレージツリーがあります。 与えられたアドレスにある、特定のストレージポジションの値を取得するには、ストレージアドレスであるストレージに格納されたデータの整数のポジションと、ブロックIDが必要です。 これらは、JSON-RPC APIで定義されているeth_getStorageAtに引数として渡すことができます。アドレス0x295a70b2de5e3953354a6a8344e616ed314d7251ストレージスロット0のデータを取得する例は、次のようになります。

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}
4

ストレージの他の要素を取得するのは、ストレージツリーのポジションを最初に計算する必要があるため、より複雑になります。 ポジションは、アドレスとストレージポジションのkeccak256ハッシュとして計算され、両方とも長さ32バイト長になるように左からゼロが足されます。 例えば、アドレス 0x391694e7e0b0cce554cb130d723a9d27458f9298のストレージスロット1のデータの位置は、次のようになります。

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

Gethコンソールでは、これは次のように計算できます。

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

よって、pathはkeccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>)となります。 これを使用して、前と同様にストレージツリーからデータを取得できます。

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

注: イーサリアムアカウントのstorageRootは、コントラクトアカウントでなければ、デフォルトで空になります。

トランザクションツリー

ブロックごとに個別のトランザクションツリーがあり、ここでも(key, value)ペアが格納されます。 パスは、ここではrlp(transactionIndex)で、以下によって決定される値に対応するキーを表します。

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

詳細については、EIP 2718(opens in a new tab)のドキュメントを参照してください。

レシートツリー

すべてのブロックは、それぞれのレシートツリーを持っています。 ここでのpathは、rlp(transactionIndex)です。 transactionIndexは、マイニングされたブロックのインデックスです。 レシートツリーは更新されることはありません。 トランザクションと同様に、現在のレシートとレガシーのレシートがあります。 レシートツリーで特定のレシートをクエリーするには、ブロックのトランザクションのインデックス、レシートのペイロード、トランザクションタイプが必要となります。 返されるレシートは、TransactionTypeとReceiptPayloadの集まったものとして定義されるReceiptタイプまたは、rlp([status, cumulativeGasUsed, logsBloom, logs])として定義されるLegacyReceiptタイプとなります。

詳細については、EIP 2718(opens in a new tab)のドキュメントを参照してください。

参考文献

• 変更されたマークル・パトリシア・ツリー — イーサリアムにおける状態の保存方法(opens in a new tab)
• イーサリアムのマークリング(opens in a new tab)
• イーサリアムツリーの理解(opens in a new tab)