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

イーサリアムの状態 (あらゆるアカウント、残高、スマートコントラクトの全体) は、コンピューターサイエンスでマークルツリーとして一般的に知られている特殊なバージョンのデータ構造にエンコードされます。この構造は、ツリー内のすべての個々のデータ間に検証可能な関係を構築し、そのデータに関する事柄を証明するために使用できる単一のルート値が結果として得られるため、多くの暗号技術アプリケーションで有用です。

イーサリアムのデータ構造は「修正版マークル・パトリシア・トライ」です。これは、PATRICIA (The Practical Algorithm To Retrieve Information Coded in Alphanumeric) のいくつかの機能を借用し、イーサリアムの状態を構成するアイテムを効率的にデータ取得(retrieval)できるよう設計されていることから、そのように名付けられました。

マークル・パトリシア・トライは決定的かつ暗号学的に検証可能です。状態ルートを生成する唯一の方法は、状態の個々の部分から計算することであり、2つの状態が同一であることは、ルートハッシュとそれに至るハッシュ(マークルプルーフ)を比較することで容易に証明できます。反対に、同じルートハッシュで2つの異なる状態を生成することはあり得ません。また、異なる値で状態を変更しようとすると、異なる状態のルートハッシュになります。理論上、この構造は挿入、検索、削除においてO(log(n))という効率性の「聖杯」を提供します。

近い将来、イーサリアムはバークルツリー構造に移行する計画です。これにより、将来のプロトコル改善に向けた多くの新たな可能性が開かれるでしょう。

前提条件

このページをよりよく理解するためには、ハッシュ (opens in a new tab)、マークルツリー (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 はアルファベット(通常はバイナリまたは16進数)の記号を表し、value はノードの終端値で、i_0, i_1 ... の中の値は i_nスロットは、NULLか、他のノードへのポインタ(この場合はハッシュ)です。これにより、基本的な(key, value)ストアが形成されます。

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

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

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

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

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

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

基数ツリーの原子単位(例: 1つの16進文字、または4ビットの2進数)を「ニブル」と呼ぶことにします。上記のように、一度に1ニブルずつパスをたどる場合、ノードは最大16個の子を参照できますが、value要素も含むことができます。そのため、ノードは長さ17の配列として表されます。これらの17要素配列を「ブランチノード」と呼びます。

マークル・パトリシア・トライ

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

最適化

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

NULL (空文字列として表現)
branch 17項目のノード [ v0 ... v15, vt ]
leaf 2項目のノード [ encodedPath, value ]
extension 2項目のノード [ encodedPath, key ]

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

encodedPathの最初のニブルにあるフラグでマークできるleafノードの場合、パスは先行するすべてのノードのパスフラグメントをエンコードしており、valueを直接検索できます。

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

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

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

上述した_残りの部分パス長が奇数か偶数か_と、_リーフノードか拡張ノードか_の両方を示すフラグは、任意の2項目ノードの部分パスの最初のニブルに格納されます。結果は、次の通りになります。

16進数文字	ビット	ノードタイプ部分	パス長
0	0000	拡張子	偶数
1	0001	拡張子	奇数
2	0010	終端（リーフ）	偶数
3	0011	終端（リーフ）	奇数

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

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term:
4            hexarray = hexarray[:-1]
5        oddlen = len(hexarray) % 2
6        flags = 2 * term + oddlen
7        if oddlen:
8            hexarray = [flags] + hexarray
9        else:
10            hexarray = [flags] + [0] + hexarray
11        # hexarrayは、最初のニブルがフラグである偶数の長さを持ちます。
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        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_hash, path):
2        if path == []:
3            return node_hash
4        if node_hash == "":
5            return ""
6        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
7        if len(curnode) == 2:
8            (k2, v2) = curnode
9            k2 = compact_decode(k2)
10            if k2 == path[: len(k2)]:
11                return get(v2, path[len(k2) :])
12            else:
13                return ""
14        elif len(curnode) == 17:
15            return get_helper(curnode[path[0]], path[1:])
16
17    def get(node_hash, path):
18        path2 = []
19        for i in range(len(path)):
20            path2.push(int(ord(path[i]) / 16))
21            path2.push(ord(path[i]) % 16)
22        path2.push(16)
23        return get_helper(node_hash, path2)
すべて表示

トライの例

('do', 'verb')、('dog', 'puppy')、('doge', 'coins')、('horse', 'stallion')という4つのパス/値のペアを含むトライが必要だとします。

まず、パスと値の両方をbytesに変換します。以下では、_パス_の実際のバイト表現は<>で示しますが、_値_は理解しやすいように''で示される文字列として表示されています(これらも実際にはbytesになります):

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

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

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

あるノードが別のノード内で参照される場合、含まれるのはlen(rlp.encode(node)) >= 32であればkeccak256(rlp.encode(node))、そうでなければnodeです。ここでrlp.encodeはRLPエンコーディング関数です。

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

イーサリアムにおけるトライ

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

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

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

状態トライ

グローバルの状態ツリーが1つあり、クライアントがブロックを処理するたびに更新されます。ここでは、pathは常にkeccak256(ethereumAddress)であり、valueは常にrlp(ethereumAccount)です。具体的には、イーサリアムのaccountは[nonce,balance,storageRoot,codeHash]の4項目からなる配列です。この時点で、このstorageRootが別のパトリシア・トライのルートであることは注目に値します。

ストレージ・トライ

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

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

ストレージの他の要素を取得するのは、ストレージツリーのポジションを最初に計算する必要があるため、より複雑になります。この位置は、アドレスとストレージの位置の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>)となります。これを使用して、前と同様にストレージツリーからデータを取得できます。

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
{"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型のいずれかになります。