マークル・パトリシア・トライ
イーサリアムの状態（すべてのアカウント、残高、スマートコントラクトの総体）は、コンピューターサイエンスにおいて一般的にマークル・ツリーとして知られるデータ構造の特別なバージョンにエンコードされます。この構造は、ツリーに組み込まれたすべての個別のデータ間に検証可能な関係を作り出し、データに関する証明に使用できる単一のルート値を生成するため、暗号技術における多くのアプリケーションで役立ちます。
イーサリアムのデータ構造は「変更されたマークル・パトリシア・トライ」です。この名前は、PATRICIA（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)に関する基本的な知識があると役立ちます。この記事では、まず基本的な基数ツリー（radix tree） (opens in a new tab)について説明し、その後、イーサリアムのより最適化されたデータ構造に必要な変更を徐々に紹介します。
基本的な基数トライ
基本的な基数トライでは、すべてのノードは次のようになります。
[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の値を鍵として使用し、フラットな鍵/値DBで検索して、1つ下のレベルのノードを取得します。次にインデックス4を選んで次の値を検索し、次にインデックス6を選ぶというように進め、パスroot -> 6 -> 4 -> 6 -> 15 -> 6 -> 7をたどった後、ノードの値を検索して結果を返します。
「トライ」で何かを検索することと、基盤となるフラットな鍵/値「DB」で検索することには違いがあります。どちらも鍵/値の配置を定義しますが、基盤となるDBは従来の1ステップでの鍵の検索が可能です。トライで鍵を検索するには、上記で説明した最終的な値に到達するために、基盤となるDBでの複数回の検索が必要になります。曖昧さをなくすため、後者をpathと呼ぶことにします。
基数トライの更新および削除操作は、次のように定義できます。
def update(node_hash, path, value):
curnode = db.get(node_hash) if node_hash else [NULL] * 17
newnode = curnode.copy()
if path == "":
newnode[-1] = value
else:
newindex = update(curnode[path[0]], path[1:], value)
newnode[path[0]] = newindex
db.put(hash(newnode), newnode)
return hash(newnode)
def delete(node_hash, path):
if node_hash is NULL:
return NULL
else:
curnode = db.get(node_hash)
newnode = curnode.copy()
if path == "":
newnode[-1] = NULL
else:
newindex = delete(curnode[path[0]], path[1:])
newnode[path[0]] = newindex
if all(x is NULL for x in newnode):
return NULL
else:
db.put(hash(newnode), newnode)
return hash(newnode)
「マークル」基数ツリーは、決定論的に生成された暗号ハッシュダイジェストを使用してノードをリンクすることによって構築されます。このコンテンツアドレッシング（鍵/値DBのkey == keccak256(rlp(value))）は、保存されたデータの暗号技術的な整合性を保証します。特定のトライのルートハッシュが公に知られている場合、基盤となるリーフデータにアクセスできる人なら誰でも、特定の値とツリールートを結ぶ各ノードのハッシュを提供することで、トライが特定のパスに特定の値を含んでいるという証明を構築できます。
ルートハッシュは最終的にそれ以下のすべてのハッシュに基づいているため、攻撃者が存在しない(path, value)ペアの証明を提供することは不可能です。基盤となるデータを少しでも変更すれば、ルートハッシュが変わってしまいます。ハッシュは、ハッシュ関数の原像計算困難性（pre-image protection）によって保護された、データに関する構造情報の圧縮表現と考えることができます。
基数ツリーの最小単位（例：1つの16進文字、または4ビットのバイナリ数）を「ニブル（nibble）」と呼びます。上記のようにパスを1ニブルずつたどる際、ノードは最大16個の子を参照できますが、value要素も含まれます。したがって、これらを長さ17の配列として表現します。この17要素の配列を「ブランチノード（branch nodes）」と呼びます。
マークル・パトリシア・トライ
基数トライには1つの大きな制限があります。それは非効率であるということです。イーサリアムのようにパスが64文字（bytes32のニブル数）の長さである場合、1つの(path, value)バインディングを保存するには、文字ごとに1つのレベルを保存するために1キロバイト以上の余分なスペースが必要になり、各検索や削除には完全に64ステップかかります。以下で紹介するパトリシア・トライは、この問題を解決します。
最適化
マークル・パトリシア・トライのノードは、次のいずれかです。
NULL（空の文字列として表現）branch17項目のノード[ v0 ... v15, vt ]leaf2項目のノード[ encodedPath, value ]extension2項目のノード[ 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「パディング」ニブルが続きます。
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は偶数の長さになり、最初のニブルがフラグになります。
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, 10]
'20 0f 1c b8'
> [f, 1, c, b, 8, 10]
'3f 1c b8'
マークル・パトリシア・トライでノードを取得するための拡張コードは次のとおりです。
def get_helper(node_hash, path):
if path == []:
return node_hash
if node_hash == "":
return ""
curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
if len(curnode) == 2:
(k2, v2) = curnode
k2 = compact_decode(k2)
if k2 == path[: len(k2)]:
return get(v2, path[len(k2) :])
else:
return ""
elif len(curnode) == 17:
return get_helper(curnode[path[0]], path[1:])
def get(node_hash, path):
path2 = []
for i in range(len(path)):
path2.push(int(ord(path[i]) / 16))
path2.push(ord(path[i]) % 16)
path2.push(16)
return get_helper(node_hash, path2)
トライの例
4つのパス/値のペア('do', 'verb')、('dog', 'puppy')、('doge', 'coins')、('horse', 'stallion')を含むトライが必要だとします。
まず、パスと値の両方をbytesに変換します。以下では、理解しやすくするために、パスの実際のバイト表現は<>で示されていますが、値は依然として文字列として''で示されています（これらも実際にはbytesになります）。
<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coins'
<68 6f 72 73 65> : 'stallion'
次に、基盤となるDBに以下の鍵/値のペアを持つトライを構築します。
rootHash: [ <16>, hashA ]
hashA: [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
hashB: [ <00 6f>, hashC ]
hashC: [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashD: [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]
あるノードが別のノード内で参照される場合、含まれるのはlen(rlp.encode(node)) >= 32であればkeccak256(rlp.encode(node))、そうでなければnodeです。ここで、rlp.encodeはRLPエンコーディング関数です。
トライを更新する際、新しく作成されたノードの長さが32以上である場合、鍵/値のペア(keccak256(x), x)を永続的なルックアップテーブルに保存する必要があることに注意してください。ただし、ノードがそれより短い場合は、関数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のデータの位置は次のようになります。
keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))
ゴー・イーサリアム（ゲス）のコンソールでは、これは次のように計算できます。
> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
undefined
> web3.sha3(key, {"encoding": "hex"})
"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)であり、次によって決定される値に対応する鍵を表します。
if legacyTx:
value = rlp(tx)
else:
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)のドキュメントに記載されています。