Trie

Trieとは？

Trieは、キーの一部を段階的にたどることで、キーと値のデータを保存および取得するツリー状のデータ構造です。

暗号資産では、ブロックチェーンがアカウント、残高、スマートコントラクトのストレージ、トランザクション、証明を整理するための信頼性の高い方法を必要とするため、Trieは重要です。

trieという言葉はretrievalに由来し、通常は「try」と発音されます。

通常のデータベースではキーと値を直接保存することがありますが、Trieはキーをより小さな部分に分割し、それらをパスに沿って配置します。

パス上の各ステップで検索対象が絞り込まれ、システムは完全なキーに対応する値に到達します。

このため、Trieは頻繁に検索、更新、検証する必要があるデータに有用です。

ブロックチェーンシステムでは、Trieは暗号学的ハッシュと組み合わせられ、認証済みデータ構造を作成することがよくあります。

認証済みデータ構造を使うと、ユーザーはデータセット全体をダウンロードしなくても、特定のデータがより大きなデータセットに含まれることを検証できます。

このためTrieは、ノード、ウォレット、ブロックチェーンエクスプローラー、ライトクライアント、スマートコントラクト、ブロックチェーンのスケーリング研究で重要です。

最も有名な暗号資産の例はEthereumのmodified Merkle Patricia trieであり、実行レイヤー全体でキーと値のデータを決定論的かつ暗号学的に検証可能な方法で整理するために使用されます。

暗号資産においてTrieが重要な理由

Trieが暗号資産において重要なのは、ブロックチェーンが多数の独立したコンピューターに同じ状態への合意を求めるためです。

状態とは、アカウント残高、スマートコントラクトコード、ストレージ値、その他の台帳データを含む、ブロックチェーンの現在の状況を指します。

2つのノードが同じブロックを処理する場合、同じ状態ルートに到達する必要があります。

状態ルートは、完全な状態をコンパクトに要約した暗号学的な情報です。

アカウント残高またはストレージ値が1つでも誤って変更されると、結果として得られるルートも変化するはずです。

これにより、ノードはデータベース全体を手動で比較する代わりに、小さなルート値を比較できます。

Ethereum.orgは、Merkle Patricia Trieドキュメントで、Merkle Patricia trieは決定論的かつ暗号学的に検証可能であり、異なる値で状態を変更しようとすると異なる状態ルートハッシュが生成されると説明しています。

この性質は、バリデーターとノードがブロック生成者が正しい結果を計算したかどうかを判断する共通の手段を必要とするため、ブロックチェーンのコンセンサスに不可欠です。

認証済みTrieまたは類似の構造がなければ、大規模なブロックチェーン状態の検証ははるかに困難かつ非効率になります。

基本的なTrieの仕組み

基本的なTrieは、キーをより小さな記号に分割してデータを保存します。

例えば、単語ベースのTrieでは、「cat」「car」「cap」を、最初の2文字である「ca」を共有し、最後の文字で分岐させて保存できます。

この共有プレフィックス構造により、多くのキーが同じ文字列で始まる場合の重複保存を削減できます。

暗号資産システムでは、キーは通常、単純な英単語ではありません。

アドレス、ハッシュ化されたストレージスロット、トランザクションインデックス、エンコード済みの値などがあります。

Trieはキーを部分ごとにたどり、値に到達します。

キーが存在しない場合、有効な値に到達する前にパスが失敗します。

この構造は、理論上、高速な検索、挿入、削除をサポートできます。

ただし、キーが長く、多くのパスに子ノードが1つしかない場合、単純なTrieは非効率になる可能性があります。

このため、ブロックチェーンシステムではPatricia trieやMerkle Patricia trieなど、最適化されたTrie形式がよく使用されます。

Trieとツリーの違い

Trieはツリーの一種ですが、キーとプレフィックスを中心に設計されています。

通常のツリーは、比較、階層、親子関係によって値を整理する場合があります。

Trieは、キーを構成する記号をたどることで値を整理します。

このため、多くのキーがプレフィックスを共有する場合にTrieは特に有用です。

ブロックチェーンではキーが長いバイト文字列になる可能性があるため、単純なツリーが常に最適とは限りません。

Trieでは、値に至るパスをキー自体に直接依存させることができます。

これは、ノードが決定論的に動作する必要がある場合に有用です。

決定論的な動作とは、同じ入力が与えられた場合に、すべての正直なノードが同じ結果に到達することを意味します。

暗号資産では、ネットワークが回答を決めるために単一の中央データベースサーバーへ依存できないため、決定論的データ構造が重要です。

すべてのフルノードは、同じデータから同じルートを計算できる必要があります。

TrieとMerkle treeの違い

Trieはキーパスによってデータを整理する一方、Merkle treeはリーフを繰り返しハッシュ化し、1つのルートハッシュが残るまでデータを整理します。

Merkle treeは、データセットに対する暗号学的コミットメントを作成するため有用です。

Merkle proofでは、セット全体を公開またはダウンロードすることなく、1つのデータがコミット済みセットに含まれることを示せます。

Trieは、効率的なキーと値の検索をサポートするため有用です。

Merkle Patricia trieは、これらの考え方を組み合わせたものです。

検索にはTrieのようなキーパスを、検証にはMerkle形式のハッシュを使用します。

ブロックチェーンノードにはデータベースへのアクセスと暗号学的証明の両方が必要なため、この組み合わせは強力です。

通常のTrieは値を見つけられますが、その値が信頼できる状態ルートの一部であることを自動的に証明するわけではありません。

通常のMerkle treeはメンバーシップを証明できますが、効率的なキーと値の更新向けに設計されているとは限りません。

Merkle Patricia trieは、Ethereum形式のシステムに対し、検証可能なルートコミットメントを維持しながら変化する状態を管理する手段を提供します。

Patricia trieとは？

Patricia trieは、分岐のない長い区間がある場合にパスを圧縮する、最適化されたTrieです。

PATRICIAはPractical Algorithm To Retrieve Information Coded in Alphanumericの略です。

目的は、次のノードを1つだけ指すノードにスペースを無駄に使わないことです。

通常のTrieでは、途中に意味のある分岐がなくても、長いキーに多数のステップが必要になる場合があります。

Patricia trieは、共有パスのセグメントをよりコンパクトに保存できます。

アドレスやハッシュは長くなる可能性があるため、これはブロックチェーンのキーに有用です。

Ethereum.orgは、Patricia Merkle trieガイドで、Ethereumのデータ構造はEthereumの状態を構成する項目を効率的に取得するよう設計されているため、PATRICIAの特徴を取り入れていると説明しています。

パス圧縮は、たどる、保存する、証明する必要があるノード数を減らすのに役立ちます。

ブロックチェーンの状態には数百万のアカウントと、それ以上のストレージエントリが含まれる可能性があるため、これは重要です。

より小さく効率的な構造は、ノードが少ないオーバーヘッドで状態変更を処理する助けになります。

Merkle Patricia trieとは？

Merkle Patricia trieは、Merkleハッシュ、Trie検索、Patriciaパス圧縮を組み合わせた、認証済みのキーと値のデータ構造です。

MPTと略されることもあります。

Ethereumは、重要な実行レイヤーデータにmodified Merkle Patricia trieを使用しています。

公式のEthereumデータ構造ドキュメントでは、Patricia Merkle triesはキーと値のペアを決定論的かつ暗号学的に認証されたTrieへエンコードすると説明されています。

EthereumにおいてMPTは、単一のルートハッシュを使用して大規模な状態データベースにコミットすることを可能にします。

ルートハッシュはブロックデータに保存され、トランザクション実行後の状態のフィンガープリントとして機能します。

ノードがブロック提案者と異なる状態ルートを計算した場合、何かが誤っていると判断できます。

これは、MPTがEthereumの実行モデルにとって重要である理由の一つです。

MPTは、ローカルデータベースの更新とグローバルコンセンサスを結び付けるのに役立ちます。

また、既知のルートに対してアカウントまたはストレージデータを証明できるMerkle proofもサポートします。

Ethereumのmodified Merkle Patricia trie

Ethereumのバージョンは、modified Merkle Patricia trieと呼ばれることが多いです。

Ethereum Yellow Paperでは、Ethereumはworld-state mappingをmodified Merkle Patricia treeで維持し、ルートノードハッシュがシステム全体の状態の安全な識別子として機能できると、Ethereum Yellow Paperで説明されています。

つまり、Trieルートは完全なアカウント状態セットにコミットします。

アカウント状態には、nonce、残高、ストレージルート、コードハッシュなどのデータが含まれます。

スマートコントラクトのストレージもTrie構造を通じて整理されます。

トランザクションが残高またはコントラクトのストレージ値を変更すると、該当するTrieパスが変化します。

その変更は、親ハッシュに影響しながらルートまで伝播します。

最終的な状態ルートは、更新されたブロックチェーン状態を反映します。

このように、小さなハッシュで膨大な量の変化する状態データを表現できます。

modified MPTは、Ethereumノードがブロック実行の正しさを独立して検証できる理由の一つです。

Merkle Patricia trieのノード

Merkle Patricia trieは複数の種類のノードを使用します。

Ethereum.orgは、MPTドキュメントで、null node、branch node、leaf node、extension nodeを挙げています。

null nodeは空の値を表します。

branch nodeは複数の可能な次のパスを指すことができます。

leaf nodeは、最終的にエンコードされたパスと値を保存します。

extension nodeは共有パスのセグメントを保存し、別のノードを指します。

これらのノードタイプにより、Trieはスパースなキーと値のデータを効率的に保存できます。

スパース構造とは、多数の可能なキーが存在する一方、実際に値を持つキーは一部に限られる構造です。

Ethereumのキーは、1 nibbleが半バイトとなるnibbleで表現されることがよくあります。

nibbleを使うことで、Trieは各branch nodeで最大16通りのパスを選択できます。

この設計により、Trieは16進数のキーパスを予測可能な方法でたどれます。

State trie

State trieは、Ethereumのworld stateにコミットするTrieです。

world stateには、すべてのアカウントとそのアカウントデータが含まれます。

各アカウントは、秘密鍵で管理される外部所有アカウント、またはコードで管理されるコントラクトアカウントです。

State trieは、アカウントアドレスをエンコード済みアカウントデータに対応付けます。

状態ルートは、ブロックのトランザクション処理後におけるこのTrieのルートハッシュです。

バリデーターがブロックを検証する際は、トランザクションを再実行し、結果として得られる状態ルートを計算します。

Ethereum.orgのVerkle treesロードマップページでは、検証済みブロックとは、計算された状態ルートハッシュがブロック提案者から提供されたルートと一致するブロックであると説明されています。

このため、State trieはブロック検証の中心です。

クライアントソフトウェアに隠された単なるストレージの詳細ではありません。

状態遷移が有効であることをEthereumが証明する仕組みの一部です。

Storage trie

Storage trieは、特定アカウントのスマートコントラクトストレージを保存するTrieです。

各スマートコントラクトアカウントには、独自のStorage trieを指すストレージルートがあります。

このStorage trieは、ストレージキーをストレージ値に対応付けます。

例えば、トークンコントラクトでは、残高、allowance、供給データ、設定値をストレージに保存する場合があります。

各値はストレージスロットを通じて表現できます。

ユーザーがトークンを送付すると、残高が更新されるため、コントラクトストレージが変化する場合があります。

このストレージ変更により、コントラクトのStorage trieルートが更新されます。

その後、State trie内のアカウントデータも、アカウントのストレージルートが変化したため更新されます。

これにより、1つのストレージスロットから全体の状態ルートまで、暗号学的コミットメントの連鎖が作られます。

この連鎖によりストレージ証明が可能になります。

Transaction trie

Transaction trieは、ブロックに含まれるトランザクションにコミットするTrieです。

各ブロックには、そのブロックのトランザクションを要約するトランザクションルートがあります。

これにより、ノードおよびクライアントはブロックデータに対してトランザクションの含有を検証できます。

Transaction trieは、現在のアカウント状態ではなくブロック内容を表すため、State trieとは異なります。

State trieは、トランザクションがアカウントとコントラクトを更新するたびに変化します。

Transaction trieは、特定ブロックにどのトランザクションが含まれたかを記録します。

トランザクションの含有と状態への影響は関連しているものの同一ではないため、この区別は重要です。

トランザクションはブロックに含まれていても、実行時に失敗することがあります。

Transaction trieは含有を証明でき、Receipt trieは実行結果の詳細を示せます。

トランザクションを確認するユーザーは、ブロックへの含有がトランザクション全体の一部にすぎないことを理解すべきです。

Receipt trie

Receipt trieは、ブロックのトランザクションレシートにコミットするTrieです。

レシートには、トランザクション実行の結果が記録されます。

チェーンのルールおよびクライアント表示に応じて、ステータス、使用ガス、ログ、イベント関連データを含めることができます。

レシートは、ウォレット、エクスプローラー、インデクサー、分散型アプリケーションにとって重要です。

例えば、トークン送付イベントはトランザクションログから読み取られることがよくあります。

Receipt trieは、それらの結果をブロックデータにコミットするのに役立ちます。

これにより、クライアントは特定のレシートがブロックに属することを検証できます。

開発者にとって、レシート証明はクロスチェーンメッセージング、ブリッジ、分析ツール、証明ベースのアプリケーションの構築で重要になる場合があります。

ユーザーにとって、Receipt trieは通常見えません。

ただし、ユーザーがトランザクションの成功または失敗を確認する際に依存するエクスプローラーデータを支えています。

Trie root

Trie rootは、Trie内のすべてのデータを要約する最上位ハッシュです。

Trie内の値が変更されると、ルートも変化するはずです。

このため、ルートは完全なデータセットに対するコンパクトなコミットメントとなります。

Ethereumでは、ブロックヘッダーに重要なデータ構造を要約するルートが含まれます。

状態ルートはブロック後の状態を要約します。

トランザクションルートはブロックのトランザクションを要約します。

レシートルートはブロックのトランザクションレシートを要約します。

これらのルートは、独立したノードが中央サーバーを信頼せずに何が起きたかで合意することを支えます。

誤ったルートは、ノードの計算またはブロック提案者のデータが想定される結果と一致しないことを示します。

暗号資産では、これはハッシュ化が生データを検証可能なコンセンサスに変える実用的な方法の一つです。

Merkle proofとTrie

Merkle proofは、ある値がより大きなコミット済みデータ構造に含まれることを証明するデータセットです。

Trieでは、証明には通常、ルートから証明対象の値に至るパス上のノードが含まれます。

検証者は証明データを段階的にハッシュし、その結果を既知のルートと比較できます。

計算されたルートが信頼するルートと一致すれば、ハッシュの前提のもとで証明は有効です。

これにより、ライトクライアントまたはスマートコントラクトは、完全な状態を保存せずに特定の値を検証できます。

例えば、ある証明は、特定アカウントが既知の状態ルート時点で特定の残高を持っていたことを示すことができます。

また、スマートコントラクトのストレージスロットが特定の値を持っていたことも示せます。

ストレージ証明は、ブリッジ、クロスチェーンアプリケーション、ロールアップ、過去の状態検証に有用です。

ただし、正確なTrie形式、エンコード、ルートがチェーンルールと一致する必要があるため、証明の生成および検証は複雑になる可能性があります。

証明は、検証者が照合対象のルートを信頼する場合にのみ意味を持ちます。

Trieとライトクライアント

ライトクライアントは、フルノードが保存および処理するすべての情報を保存・処理しないブロックチェーンクライアントです。

ライトクライアントは、コンパクトな証明、ヘッダー、信頼できる暗号学的コミットメントに依存します。

ルートハッシュは大規模な状態にコミットできるため、Trieはライトクライアントを支えます。

ライトクライアントは、データベース全体をダウンロードする代わりに、小さな証明を既知のルートに対して検証できます。

これは、フルノードを実行できないモバイルウォレット、組み込みデバイス、ブラウザ、アプリケーションにとって重要です。

ただし、現在のMerkle Patricia trie証明は、一部の用途では大きくなる可能性があります。

Ethereum.orgは、Verkle treesドキュメントで、現在のMerkle trie witnessはstateless clientを効率的にサポートするには大きすぎると説明しています。

このため、Ethereumの研究者はVerkle treesおよびその他の状態コミットメントの改善を研究しています。

目標は、セキュリティを弱めずに検証をより軽量化することです。

したがってTrieは、現在のノードだけでなく、将来のブロックチェーンスケーリング設計にとっても重要です。

Trieとstateless client

Stateless clientは、現在の完全な状態をローカルに保存せずにブロックを検証できるクライアントです。

完全な状態データベースを保持する代わりに、クライアントはブロックとともにwitnessを受け取ります。

Witnessには、ブロックの状態遷移を検証するために必要な状態フラグメントと証明データが含まれます。

Ethereum.orgは、stateless clientおよびVerkle treeロードマップで、stateless clientは完全な状態データベースのローカルコピーの代わりに、状態データへのwitnessを使用すると説明しています。

課題は、現在のMerkle trie構造に基づくwitnessが大きくなりすぎる可能性があることです。

大きなwitnessは、P2Pネットワーク全体で迅速に共有する必要があるため問題です。

強力な帯域幅を持つ高性能マシンだけが対応できる場合、ネットワークはより中央集権的になります。

より優れたTrieまたはツリー構造は、witnessサイズを縮小し、より多くのユーザーにとって検証を容易にできます。

このため、データ構造の設計は分散化と直接結び付いています。

低レベルの技術的詳細に見えるデータ構造が、ノードを実行できる人に影響する可能性があります。

TrieとVerkle trees

Verkle treesは、Ethereumの状態データ構造における提案済みのアップグレード経路です。

Verkle treeは目的の面ではMerkle treeに似ていますが、より小さなwitnessをサポートするためにベクトルコミットメントを使用します。

Ethereum.orgは、公式のVerkle treesロードマップで、Verkle treesはノードがブロック検証能力を失うことなく、大量の状態データの保存をやめる助けになると説明しています。

これは、Ethereumの現在のState trieが大きく、軽量な検証が難しいため重要です。

Verkle treesは、stateless client向けにwitnessをより小さく、より実用的にすることを目的に設計されています。

Merkle Patricia triesと同じものではありません。

状態アクセスおよび検証を改善するための、将来を見据えた取り組みの一部です。

用語集の読者にとって重要な点は、Trieが解決済みの固定的なテーマではないことです。

ネットワークには、より優れたスケーラビリティ、より低いハードウェア要件、より高い証明効率が必要なため、ブロックチェーンのデータ構造は進化を続けています。

Trieを理解すると、Verkle treesが研究されている理由を理解しやすくなります。

Trieとガスコスト

Trie操作は、ブロックチェーンのパフォーマンスおよび取引コストに影響する可能性があります。

トランザクションが状態を読み書きする際、クライアントはTrie関連データにアクセスし更新する必要がある場合があります。

スマートコントラクトのストレージ書き込みは、永続的な状態を変更するため、コストが高くなります。

永続的な状態の変更は、結果をネットワークが保存・検証する必要があるため、一時的な計算を行うよりもコストが高くなります。

トークン送付では、コントラクトストレージ内の残高が更新される場合があります。

DeFiトランザクションでは、複数のコントラクトにまたがる多数のストレージスロットが更新される場合があります。

各更新は、状態の増大とTrieの維持作業に寄与する可能性があります。

これは、ブロックチェーン開発者がストレージ最適化を重視する理由の一つです。

効率的なスマートコントラクトの作成は、ユーザーの手数料を節約するだけではありません。

ネットワークに対する長期的な状態負荷を軽減することでもあります。

Trieとスマートコントラクトストレージ

スマートコントラクトストレージは、開発者にとってTrieが最も重要となる領域の一つです。

コントラクトがデータを恒久的に保存すると、そのデータはブロックチェーン状態の一部になります。

コントラクトのストレージルートは、コントラクトのStorage trieにコミットします。

すべてのストレージ変数は、最終的にストレージスロットを通じて表現されます。

mappingや配列などの複雑なSolidityデータ型は、コンパイラのルールに従ってストレージスロットにエンコードされます。

ユーザーがコントラクトを操作すると、これらのスロットが読み取られたり変更されたりする場合があります。

開発者は、ストレージが単なるプログラミング上の利便性ではないことを理解すべきです。

ストレージは、暗号学的にコミットされたグローバルデータベースの一部です。

不適切なストレージ設計は、ガスコストを増加させ、証明を大きくし、アップグレードリスクを生む可能性があります。

適切なストレージ設計は、コントラクトをより低コストで、明確にし、監査しやすくできます。

Trieとブロックチェーンエクスプローラー

ブロックチェーンエクスプローラーは、ユーザーに読みやすい情報を表示するため、ブロックチェーンのデータ構造、インデックス、クライアントデータに依存します。

ユーザーはアドレスを検索し、残高、トークン送付、コントラクト呼び出し、トランザクション履歴を確認できます。

インターフェースの背後では、ブロックチェーン自体は状態とブロックデータをより技術的な形式で保存しています。

Trieはこのデータへのコミットを支え、エクスプローラーはデータをインデックス化して表示します。

ユーザーは、エクスプローラーが閲覧ツールであり、それ自体が唯一の真実の情報源ではないことを理解すべきです。

真実の情報源は、ノードにより検証され、ルートを通じてコミットされたブロックチェーンデータです。

エクスプローラーに遅延またはインデックスエラーがあっても、基盤となるチェーンは正しい場合があります。

このため、開発者および上級ユーザーは、ノード、証明、複数の情報源を通じてデータを検証することがよくあります。

Trie rootは、エクスプローラーが構築できる暗号学的な基盤をチェーンに提供します。

エクスプローラーはデータを人間が読める形にしますが、Trieはデータを検証可能にする助けとなります。

Trieとロールアップ

ロールアップは、オフチェーンまたはレイヤー2の状態を追跡するために、独自の状態ツリーまたはTrieを使用する場合があります。

ロールアップには、現在の状態にコミットし、状態遷移が有効であることを証明する手段が必要です。

一部のロールアップは、ゼロ知識証明、不正証明、Merkle proof、その他のコミットメント構造を使用します。

正確なデータ構造がEthereumのMPTでない場合でも、同じ基本的な考え方が見られることが多いです。

システムは、コンパクトなルートを使用して大規模な状態にコミットします。

ユーザーまたはコントラクトは、そのルートに対して主張を検証できます。

このためTrieを学ぶことは、ロールアップのアーキテクチャを理解する助けになります。

ロールアップは、単により安価なトランザクションのためだけのものではありません。

状態コミットメント、証明生成、データ可用性、検証にも関わります。

Trieのような構造は、これらのシステムを可能にする基盤の一つです。

Trieとブリッジ

ブリッジは、別のチェーンからのイベント、残高、メッセージ、ストレージ値を検証するために証明を使用する場合があります。

ブリッジは、トランザクションが発生したこと、またはストレージ値が変化したことを証明する必要がある場合があります。

送信先チェーンまたは検証者が送信元チェーンの信頼できるルートを把握している場合、Trie proofはこのような主張の検証に役立ちます。

ただし、ブリッジのセキュリティはTrie proof自体以上の多くの要素に左右されます。

バリデーターセット、リレイヤー、ライトクライアントロジック、ファイナリティの前提、スマートコントラクトの安全性、アップグレード制御にも依存する可能性があります。

信頼するルートが脆弱または侵害された情報源から得られた場合、正しい証明であっても安全ではない可能性があります。

このため、ユーザーは「proof」という言葉がブリッジをリスクフリーにするとは考えるべきではありません。

証明は、安全な検証モデルと結び付いている必要があります。

Trieはデータ含有のための強力なツールを提供しますが、ブリッジ設計では多くの追加リスクを扱う必要があります。

適切なブリッジ分析では、送信元チェーンの状態から送信先チェーンの操作までの信頼経路全体を確認します。

Trieとセキュリティ

Trieは、データ改ざんを検出しやすくすることでセキュリティを向上させます。

誰かが保存済みの値を変更すると、パスに沿ったハッシュも変化するはずです。

その変更により、異なるルートが生成されるはずです。

計算されたルートを想定ルートと比較するノードは、不一致を検出できます。

これは暗号学的完全性の重要な部分です。

ただし、Trieそれ自体は完全なセキュリティソリューションではありません。

Trieは、ユーザーが悪意あるトランザクションに署名することを防げません。

Trieは、スマートコントラクトのバグを修正できません。

Trieは、不正確なオラクル価格を正しくできません。

Trieは、ブリッジが誤ったルートを信頼する場合に資金を保護できません。

Trieはデータ完全性の証明に役立ちますが、アプリケーションのセキュリティには安全なコード、適切な鍵管理、監査、堅牢なプロトコル設計が依然として必要です。

ブロックチェーンシステムにおけるTrieの利点

Trieの1つ目の利点は、整理されたキーと値の保存です。

2つ目の利点は、独立したノードが同じ結果に到達することを支える決定論的検索です。

3つ目の利点は、Patricia形式の最適化を使用した場合の共有プレフィックス圧縮です。

4つ目の利点は、TrieをMerkleハッシュと組み合わせた場合の暗号学的検証です。

5つ目の利点は、ユーザーがルートに対して特定データを検証できる証明サポートです。

6つ目の利点は状態コミットメントであり、ブロックチェーンが小さなハッシュで大規模なデータベースを要約する助けになります。

7つ目の利点は、ライトクライアントおよびstateless client研究との互換性です。

これらの利点により、Trieは本格的なブロックチェーンプロトコル設計に登場します。

Trieは抽象的なコンピューターサイエンスにとどまりません。

実際のネットワークが金融データを保存、検証、更新するのを支えます。

Trieの制約

Trieを正しく実装することは複雑になる可能性があります。

エンコードルールを正確に守らなければ、ルートは一致しません。

多くのパスまたは兄弟ノードが必要な場合、証明は大きくなる可能性があります。

状態の増大により、基盤となるデータベースはノードにとって重くなる可能性があります。

状態の更新には、多数のデータベース読み取りおよび書き込みが必要になる場合があります。

異なるクライアント実装は、同じTrieルールに合意する必要があります。

ノードが古い証明を提供する必要がある場合、過去の状態には追加ストレージが必要になる場合があります。

Merkle Patricia trieのwitnessは大きいため、Ethereumはより効率的な将来の構造としてVerkle treesを研究しています。

これらの制約は、Trieが悪いことを意味するものではありません。

ブロックチェーンのデータ構造には、検証、保存、更新コスト、証明サイズ、分散化の間のトレードオフがあることを意味します。

Trieに関するよくある誤解

1つ目の誤解は、Trieが通常のツリーと同じであるというものです。

Trieはキーパスのデータ構造である一方、一般的なツリーは多様な階層を表現できます。

2つ目の誤解は、Trieが自動的に暗号学的セキュリティを提供するというものです。

基本的なTrieは、ハッシュまたは別のコミットメント手法と組み合わせなければ、証明の安全性を提供しません。

3つ目の誤解は、状態ルートが状態全体を直接保存するというものです。

状態ルートは状態に対するコンパクトなコミットメントにすぎず、完全なデータベース自体ではありません。

4つ目の誤解は、Merkle proofが文脈なしに永久に何かを証明するというものです。

証明は、特定の信頼できるルートおよび正しいチェーンルールとの関係においてのみ意味を持ちます。

5つ目の誤解は、ユーザーはTrieを気にする必要がないというものです。

ほとんどのユーザーはTrieを直接操作しませんが、Trieはウォレット証明、ブロック検証、ブリッジセキュリティ、ネットワークの分散化に影響します。

開発者はTrieをどう捉えるべきか

開発者は、Trieをブロックチェーンの状態コミットメントシステムの一部として捉えるべきです。

スマートコントラクトを書く際、最終的にTrie rootに影響する状態変更を作成しています。

ウォレットまたはインデクサーを構築する際、Trieで裏付けられた状態由来のデータに依存する場合があります。

ブリッジまたは証明システムを構築する際、Trie proofを検証する必要がある場合があります。

コントラクトを最適化する際は、永続ストレージにネットワーク全体のコストがあることを覚えておくべきです。

プロトコルを設計する際には、メンバーシップ証明、非メンバーシップ証明、履歴証明、ストレージ証明のどれが必要かを理解すべきです。

これらの証明ニーズは、データ構造の選択に影響する場合があります。

開発者はすべてのdAppでTrieを手動実装する必要はありません。

ただし、Trieを理解することで、ブロックチェーンストレージに関する誤った前提を避けられます。

また、低レベルのクライアントルールが非常に重要である理由も理解しやすくなります。

トレーダーとユーザーはTrieをどう捉えるべきか

トレーダーおよび一般ユーザーは、Trie rootを手動で計算する必要はありません。

ただし、ブロックチェーン上の残高とコントラクト状態が、ウォレット内の単純なスクリーンショットとして保存されているわけではないことを理解すべきです。

それらは検証可能なグローバル状態の一部です。

トランザクションが残高を変更すると、その変更はチェーン内の暗号学的コミットメントを更新します。

このため、トランザクションハッシュ、ブロック番号、状態ルートを検証に使用できます。

ユーザーにとって実用的な教訓は、スクリーンショットやメッセージよりもオンチェーン検証を信頼することです。

入金が見つからない場合、トランザクションハッシュとエクスプローラーデータが重要です。

ブリッジが別のチェーンを検証すると主張する場合、証明モデルが重要です。

ウォレットが残高を表示する場合、その残高は最終的にチェーン状態まで追跡可能であるべきです。

Trieは、舞台裏でこの検証を可能にします。

FAQ

暗号資産におけるTrieとは何ですか？

暗号資産におけるTrieは、キーパスによってデータを整理し、検証を支えるために暗号学的ハッシュと組み合わせられることが多い、キーと値のデータ構造です。

trieはどのように発音しますか？

Trieは通常、「try」と発音されます。

EthereumがTrieを使用する理由は何ですか？

Ethereumは、modified Merkle Patricia triesを使用し、暗号学的ルートハッシュを通じて状態、トランザクション、レシート、スマートコントラクトストレージをエンコードおよび検証します。

Merkle Patricia trieとは何ですか？

Merkle Patricia trieは、Trie検索、Patriciaパス圧縮、Merkleハッシュを組み合わせたデータ構造です。

State trieとは何ですか？

State trieは、ブロックチェーンの現在のアカウントおよびコントラクト状態にコミットするデータ構造です。

Storage trieとは何ですか？

Storage trieは、スマートコントラクトアカウントのストレージ値にコミットする、コントラクト固有のTrieです。

Trie rootとは何ですか？

Trie rootは、Trieに保存されるすべてのデータを要約する最上位ハッシュです。

Trie内の1つの値が変化するとどうなりますか？

1つの値が変化すると、そのパスに沿ったハッシュが変化し、最終的なルートも変化するはずです。

TrieはMerkle treeと同じですか？

いいえ。Trieはキーパスによってデータを整理し、Merkle treeは主にリーフの反復ハッシュ化によってデータを整理します。

Merkle proofとは何ですか？

Merkle proofは、既知のルートによってコミットされたより大きなデータ構造に値が属することを証明するデータセットです。

Trieがライトクライアントに重要なのはなぜですか？

Trieにより、ライトクライアントはブロックチェーン状態全体をダウンロード・保存する代わりに、証明を用いて特定データを検証できます。

Verkle treesとは何ですか？

Verkle treesは、現在のMerkle trie構造より小さなwitnessを作成できる、提案済みの状態データ構造アップグレードです。

ユーザーはTrieを直接操作しますか？

ほとんどのユーザーはTrieを直接操作しませんが、Trieは残高、レシート、ストレージ証明、ブロック検証の背後にある検証を支えています。

Trieはリスクフリーですか？

いいえ。Trieはデータ完全性に役立ちますが、スマートコントラクトのバグ、ウォレットのミス、ブリッジリスク、不適切なアプリケーション設計をなくすものではありません。

まとめ

Trieは、ブロックチェーンシステムがキーと値のデータを整理・取得するのに役立つキーパス型データ構造です。

暗号資産においてTrieは、暗号学的ハッシュと組み合わせることで特に強力になります。

この組み合わせにより、コンパクトなルートハッシュを使って膨大なブロックチェーンデータにコミットできる認証済みデータ構造が作られます。

Ethereumのmodified Merkle Patricia trieは、状態ルート、ストレージルート、トランザクションルート、レシートルート、Merkle proofを支える最もよく知られた例です。

Trieは、独立したノードがブロック処理後に同じ状態に到達したことを検証する助けになります。

また、特定のアカウント、トランザクション、レシート、ストレージデータが既知のブロックチェーンルートに属することを証明できます。

ただしTrieには、実装の複雑さ、ストレージ負荷、更新コスト、大きなwitnessサイズなどのトレードオフもあります。

これらのトレードオフは、Ethereumがより小さなwitnessとstateless clientのより良いサポートに向けてVerkle treesを研究している理由の一つです。

開発者にとってTrieは、スマートコントラクトのストレージと証明設計に慎重な検討が必要な理由を説明します。

ユーザーにとってTrieは、ブロックチェーンデータが単に信頼されるだけでなく、検証できる理由を説明します。

暗号資産用語集においてTrieは、ブロックチェーン状態、暗号学的証明、ノード検証、スケーラブルな分散型ネットワークの将来を支える基盤的なデータ構造として理解すべきです。