1. Introduction

2023年の最終日に、VitalikはTwitterで2023年のEthereumのロードマップを共有し、Ethereumの1年間の進捗状況をまとめました。「The Verge」セクションのロードマップでは、Ethereumの技術がブロックチェーンの状態をよりシンプルかつ効率的に検証できる方法について説明されています。そこで言及されている核心コンセプトはVerkle Treesです。では、Verkle Treesとは何か、なぜEthereumがそれを必要としているのか、そしてVerkle Treesがどのように問題を解決するのか？この記事の目的は、暗号学や数学に深く立ち入らずに、Ethereumの理解がある程度ある人々が迅速にVerkle Treesのコンセプトを把握できるようにこれらの質問に回答することです。

2. 検証可能なクエリ

検証可能なクエリ技術は、伝統的なデータベースの分野で広く研究されており、主に外部データベースとの信頼問題を解決するために使用されています。多くのシナリオでは、データ所有者はデータを自分で保管するのではなく、代わりにサードパーティーにデータベースのニーズを委託してデータベースサービス（クラウドデータベースなど）を提供してもらうことがあります。ただし、サードパーティーが常に信頼できるとは限らないため、ユーザーに返されるクエリ結果の信頼性を保証することは難しいです。伝統的なデータベースのための現在の検証可能なクエリソリューションは、主に認証済みデータ構造（ADS）に基づくものと検証可能な計算に基づくものの2つのカテゴリに分類されます。

ADSは、主にMerkle Treesなどの蓄積構造に基づいた従来のデータベースで広く使用されている検証可能なクエリ技術です。暗号ツールの進化とともに、多くの研究者が徐々に、信頼できないクエリに対処するための検証可能な計算技術の利用を探求し始めています。 SNARKなどのZero-Knowledge Proofプロトコルに基づく一部の検証可能な計算スキームは、外部データベースのための検証可能なクエリを間接的にサポートできます。これらのスキームは、さまざまな種類のクエリをサポートし、より少ない検証情報を生成しますが、計算上のオーバーヘッドが大きくなります。

現在、EthereumはMerkle Treesを使用して検証可能なクエリを実装しており、Verkle Tree技術もMerkle Tree技術に基づいています。そのため、まずMerkle Treesを紹介し、それを例にして検証可能なクエリの役割を読者が理解するのを助けましょう。

3. Merkle Trees

3.1. Merkle Treesの定義と特性

マークルツリーは、暗号化に一般的に使用される木構造であり、データの整合性の問題を解決するのに適しています。以下は、典型的なマークルツリー構造です: 葉ノードは元のデータまたはそのハッシュ値を表し、各非葉（内部）ノードにはその子ノードの組み合わせハッシュが含まれています。

Merkle Treesには2つの重要な特性があります:

1. 改ざん耐性：Merkle Treesは通常、衝突耐性ハッシュ関数を使用して構築されるため、同じハッシュ値を生成する2つの異なるメッセージを見つけることは計算上不可能になります。Merkle Treeの構造からは、葉ノード内のトランザクションデータへの任意の変更がツリーのルートハッシュに変更をもたらすことが明らかです。
2. 大規模データセットの効率的な整合性検証: 検証者は、任意のデータの整合性を検証するためにMerkle Treeのルートハッシュのみを保存する必要があります。これは、完全なデータセットを送信せずに、むしろ葉からルートまでのパスに沿って兄弟ノードを使用することで達成されます。これらの兄弟ノードは、検証目的のためにルートハッシュを再構築するために使用できます。

3.2. マークル証明を構築する方法は？

一般的な検証可能なクエリシナリオでは、証明者と検証者がいます。証明者は証明を生成し、それを検証者に送信する必要があります。イーサリアムネットワークに対応する典型的なアプリケーションシナリオでは、軽量ノード（ブロックヘッダーのみを保存するクライアント）がフルノードまたはアーカイブノード（すべてのデータを持つクライアント）からトランザクションデータをクエリし、メルカル証明を取得してクエリ結果が正しいかどうかをローカルで検証します。

Merkleプルーフは次の3つの部分から構成されています:

1. 完全なデータセットのMerkleツリーのルートハッシュ。
2. 証明する必要があるデータブロック。
3. リーフノードからルートノードまでのパス上のすべての兄弟ノードの値を含むMerkle Path。

これらの中で、Merkleツリーのルートハッシュは信頼できる手段を通じて事前に検証者に送信する必要があり、検証者はこの値を信頼する必要があります。イーサリアムでは、ブロックデータの信頼性はコンセンサスアルゴリズムによって確保され、Merkleツリーのルートハッシュはブロックヘッダーに含まれています。

以下は具体的な例です：証明者が検証者に、データセットに存在する「4」がデータブロックであることを証明する必要がある場合、そして検証者が完全なデータセットのMerkleツリーの信頼できるルートハッシュ「1d25」を保持している場合、証明者は青でマークされたすべてのデータのみを提供すればよいです。セット内にn個のデータがあると仮定すると、任意のデータブロックの正確性を検証するためには最大で𝘭𝘰𝘨₂(𝘯)回のハッシュ計算が必要です。

イーサリアムのライトノードは、異なるデータセット（ステートツリー、トランザクションツリー、レシートツリー）のメルクルツリーのルートを含むブロックヘッダーのみを同期します。ライトノードがツリー内の特定のリーフノードのデータをフルノードにクエリすると、フルノードは対応するメルクルプルーフパスと共に元のデータを返します。これにより、ライトノードはクエリ結果の正確性を信頼できます。

3.3. マークルツリーのバリアント

Merkle Treesの基盤の上に構築すると、それらは他のデータ構造と組み合わせて変更することができ、異なる目的に基づいて新しい特性を実現する。検証可能なクエリシナリオに対応するために、Merkle TreesはMerkle-B Trees（MBT）などのさまざまなインデックス付きデータ構造に拡張することができる。挿入、削除、およびクエリングなどの操作を効率的に実行するために、EthereumチームはMerkle Patricia Tree（MPT）を提案した。

3.3.1. マークルBツリー

Merkle-Bツリー（MBT）は、検証可能な範囲クエリを処理するために主に使用されます。 𝑓をMBTのファンアウト（各ノードの子ノードの数）とします。B+ツリー構造に基づいて、MBTの各内部ノードは、𝑓—1個のインデックスキーと𝑓個の子ノードへのポインタを格納するだけでなく、すべての子ノードのハッシュ値を要約した形式で保持します。以下は、MBT内のリーフノードと内部ノードの構造の表現です。

特定の範囲クエリから返されたデータが指定された範囲に準拠していることを証明する必要がある場合、検証オブジェクト（VO）を計算するサーバーは、まず上位から下位まで2つの検索操作を実行して左右の境界を見つけなければなりません。また、この境界内のすべてのデータと、ルートハッシュへのパスを構築するために必要なすべてのブランチのハッシュも返さなければなりません。

このデータ構造の欠点は、返されたVOが要求されたクエリ範囲内にクエリ結果があることを証明することしかできないが、返された結果が完全であることを証明することはできないということです。

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

単純なMerkle Treeを使用して検証可能なクエリを提供する場合、データの挿入または削除後にMerkleツリールートを再生成する時間がかかるため、重要なものになる可能性があります。さらに、ストレージのために追加のデータ検索ツリーのメンテナンスが必要です。Merkle Patricia Tree（MPT）は、ラディックスツリー（コンパクトなプレフィックスツリー）とMerkle Treeの属性を組み合わせ、挿入、削除、およびクエリをO（log（N））の時間で実行できるようにします。MPTの完全な理解のためには、読者は対象に関する詳細な技術記事を参照することができます。この記事では、MPTを迅速に理解するための基本的な定義と例を紹介するにとどめます。

Ethereumの基本構造は、データがキーと値のペアの形で保存されるキーバリューデータベースを利用しています。MPTも保存のためにキーと値のペアに分解されます。MPTノードの論理構造を以下のように定義します。

• 指数
• パス
• データ

Merkle Patricia Tree（MPT）の文脈では、「index」とはキー値のキーを指し、一方、「path」と「data」を組み合わせることでキー値の値を構成します。インデックスは実際にMerkleツリーノードのハッシュを格納し、パスはターゲットノードを見つけるためにプレフィックスツリーで使用されるパス文字列に対応します。Ethereumはパス文字列として16進数文字列を使用しているため、MPTの幅は16です。データはパスに対応するターゲットデータです。

以下は、圧縮された接頭辞で最適化されたMPTの例であり、次のキーと値のペアデータを格納しています:

{

'cab8': '犬',

‘cabe’: ‘cat’,

‘39’: ‘chicken’,

'395': 'アヒル'、

‘56f0’: ‘馬’

}

データ「duck」をパス「395」を使用して見つけるには、ルートハッシュから始めて、ハッシュA、ハッシュC、およびハッシュDを通過して最終的にターゲットデータに到達します。以下はステップバイステップのガイドです。

1. ルートハッシュ：これはMerkle Patricia Tree（MPT）のエントリーポイントであり、最初のノードを見つけるために使用します。
2. hashA: ルートハッシュに基づいて、hashAで識別されるノードまたはコンテンツを取得します。パスが「395」であるため、「3」に導くツリーの一部を探しています。
3. hashC：hashAのコンテンツにアクセスした後、経路を続けます。次のセグメント「9」は、あなたをhashCに導きます。
4. hashD: 最後に、道を進むと、最後のセグメント「5」があなたを hashD に向かわせ、そこには値「duck」が含まれています。

パスの各ステップで、MPTはラディックスツリーの特性を利用して、キーに基づいて正しいパスを見つけるためのものと、データの整合性をハッシュリンクを介して確保するためのMerkle Treeの両方の特性を活用します。ツリー内の「パス」は、通常、16進エンコーディングで表現され、これはツリーのブランチングファクターと対応しています。パス内の各ノードには、十分なハッシュポインタ（子ノードへのポインタ）と値が含まれており、データの整合性を検証し、ツリー内をナビゲートするための情報が提供されています。

リアルMPTでは、パスとデータは特定の形式でエンコードされ、保存されます。また、拡張ノードやリーフノードなどの追加ノードの種類が、さまざまなシナリオで効率的な構造を最適化するのに役立ちます。

4. ベクトルコミットメント

コミットメント[1]スキームは、データのプライバシーと整合性を保証する暗号プリミティブです。ゼロ知識証明や安全な多者計算などのシナリオで広く使用されています。基本的なコミットメントスキームは、コミットフェーズとリベール（またはオープン）フェーズに分かれています。

1. コミットフェーズ：このフェーズでは、コミッターは暗号アルゴリズムを使用してメッセージをコミット値にバインドし、このコミット値を受信者に送信します。この段階では、コミットには隠蔽とバインディングの2つの特性があります。隠蔽は、コミットされたメッセージの内容がコミッター以外の誰にもわからないことを保証します。バインディングは、一度コミットが行われると、コミッターを含む誰にも変更できないことを保証します。
2. 公開フェーズ：このフェーズでは、コミッターは受信者に対して、受け取ったコミットメント値が元のメッセージへの有効なコミットメントであることを証明することができます。コミットメントは正しさの特性を持っており、つまり、コミッターと受信者の両方がプロトコルを正しく守れば、受信者はコミットフェーズ中に受け取ったコミットメント値が元のメッセージへの有効なコミットメントであると納得することになります。

ベクトルコミットメントは、Catalanoらによって提案された特別なコミットメントスキームであり、コミッターが順序付けられたメッセージのセット 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ へのコミットメントを行い、任意の指定された位置でオープンして（公開して）メッセージ 𝑚𝑖 がi番目のコミットされたメッセージであることを証明することを可能にします。ベクトルコミットメントでは、バインディングとは、同じ位置をオープンして異なるメッセージを表示することができないことを意味します。

ベクトルコミットメントスキームは通常、次のアルゴリズムで構成されています。

5. Verkle Trees

5.1. Verkle Treesの定義と特性

定義：Verkle Trees = ベクトルコミットメント + Merkle Trees。

Please note：Vitalik Buterin, the co-founder of イーサリアム, has a ブログVerkleツリーを紹介するために特に専念された投稿。この章では、彼のブログに基づいた背景と数学的知識をいくつか追加しています。以下のテキストの一部のデータやイラストは、彼のブログから派生しています。

Verkle Trees（VTs）は、Merkle Treesよりも小さな証明を提供することを特徴としています。数十億のエントリー規模のデータの場合、Merkleツリーはサイズ約1KBの証明を生成するかもしれませんが、Verkleツリーの証明は150バイト未満になることがあります。このコンパクトな証明サイズは、「」を実装する際に有利です。ステートレスクライアント”.

Verkleツリーの構造は、Merkle Patricia Tree（MPT）の構造といくぶん似ています。ここにその構造の例があります。Verkleツリーのノードは次のようになります：（i）空、（ii）キーとそれに対応する値を含む葉ノード、または（iii）固定された数の子ノードを持つ内部ノード。この子の数はツリーの「幅」とも呼ばれています。

VT（Verkle Trees）とMPT（Merkle Patricia Trees）の違いは、主に、木の幅（またはファンアウト、つまり、木のノードが持つ子ノードの数を指す）がどのように効率に影響するかにあります。MPTの場合、幅が大きいと効率が低くなりやすくなります。なぜなら、より大きな幅はより多くの兄弟ノードを意味し、これはMPTの更新時間が長くなり、プルーフサイズも大きくなる可能性があるからです。一方、VTの場合、より広い木の幅はより小さなプルーフをもたらします。ただし、幅があまりにも大きすぎると、プルーフを生成するのにかかる時間が長くなる可能性があります。

イーサリアムの@vbuterin"/verkle_tree_eip">VTの設計提案には、256の幅が提案されており、これはMPTの現行の16よりも大幅に大きいです。このような大きな幅は、ベクトルコミットメントなどの高度な暗号技術の使用によってVTで実現可能です。この圧縮技術により、Verkle Treesは証明サイズに関係なくコンパクトな証明を可能にします。この圧縮技術により、Verkle Treesは証明サイズに関係なく効率的にスケーリングできます。次のテキストでは、上記で言及された機能について詳しく説明します。

5.2. コミットメントとVerkleツリーの証明

MPTで証明が生成される方法を見てみましょう：証明には、ルートノードからターゲットリーフノードまでのパス上のすべてのサイドノード（または姉妹ノード）のハッシュ値を含める必要があります。 例として「4ce」を取ると、以下の図で赤でマークされた部分が、返される証明に含まれる必要があるノードです。

Verkleツリーでは、兄弟ノードを提供する必要はありません。代わりに、パスと追加データを証拠として提供するだけです。

VTのコミットメントを生成する方法は？ 計算に使用されるハッシュ関数は従来のハッシュではなく、ベクトルコミットメントを使用しています。

ハッシュ関数をベクトルコミットメントからのコミット生成アルゴリズムに置き換えた後、いわゆるルートハッシュは今やルートコミットメントとなりました。ノードのデータに改ざんが加えられると、最終的にはルートコミットメントに影響を及ぼします。

証明を生成する方法は？ 下の図に示すように、提供する必要があるのは3つのサブプルーフだけです。各サブプルーフは、パス上のノードが親ノード内の特定の位置に存在することを証明できます。幅が広いほど、レイヤーが少なくなり、それに応じて、必要なサブプルーフも少なくなります。

実用的な実装では、多項式コミットメントが利用されています（ベクトルコミットメントのために簡単かつ効率的に実装できます）、多項式へのコミットメントを可能にします。最もユーザーフレンドリーな多項式コミットメントスキームは、「KZGコミットメント” と “弾丸証明スタイルの多項式コミットメント（前者はコミットメントサイズが48バイトであり、後者は32バイトです）。

KZGコミットメントと証明を使用する場合、各中間ノードの証明はわずか96バイトであり、基本的なMerkleツリー（幅が256であると仮定する）と比較してほぼ3倍のスペースを節約します。

MerkleツリーやVerkleツリー上の操作の理論的な時間複雑性は次のとおりです:

これまでに導入されたVerkle証明スキームはかなり基本的です。実際、さらに高度な最適化戦略が利用可能です。

5.3. 最適化：証明のマージ

5.3.1. アイデア

あるパス上の各コミットメントの証明を生成することと比較して、多項式コミットメントの特性を利用することで、「パス上のすべてのコミットメント間の親子関係を証明し、要素数を無制限に含む固定サイズの証明を実現する」ことができます。これがどのように実現されているかを具体的に理解するには、説明のために数学的知識をいくつか紹介する必要があります。この記事では数学的な式がいくつか登場しますが、原則として証明の暗号部分はカバーしません。具体的な方法については、参照してください。ランダム評価を通じてマルチプルーフを実装するスキーム.

5.3.2. 数学的導出

ます、数学における多項式の基本的な概念についていくつか紹介しましょう。多項式の次数簡約、または多項式の次数簡約をどのように行うかを説明します。

多項式 𝑃(𝑥) とその値 𝑦₁ (𝑥₁ での値) を知っていると仮定します，つまり 𝑃(𝑥₁) = 𝑦₁ です。

今、新しい多項式 𝑃(𝑥) - 𝑦₁ を考えます。この多項式は、(𝑥 = 𝑥₁) で値がゼロになります。なぜなら 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0 だからです。

したがって、多項式𝑃(𝑥) - 𝑦₁ は𝑥 = 𝑥₁ で根を持ちます，これは(𝑥 - 𝑥₁ )が𝑃(𝑥) - 𝑦₁ の因数であることを意味します。

言い換えると、次の形式で表すことができます：[ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥)は、𝑃(𝑥)の次数よりも1少ない次数の別の多項式です。これは、(𝑥 - 𝑥₁)が1次因子であるため、多項式の総次数が減少するためです。

ベクトル内の単一の値を証明するためにKZGをどのように使用しますか？

KZG10のコミットメントを例に取ると、多項式 𝑃(𝑥) について、その多項式コミットメントが [ 𝑃(𝑠) ]₁ であるとします。

先に説明したように、多項式 𝑃(𝑥) について、𝑃(𝑧) = 𝑦 である場合、𝑄(𝑘) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧) となります

今、証明者は多項式𝑃(𝑥)が𝑃(𝑧) = 𝑦を満たす証明を生成できます：[ 𝑄(𝑠) ]₁を計算して検証者に送信します。

検証者は、𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) を検証する必要があります。

ベクトル内の複数の値を証明するためにKZGをどのように使用するのですか？

ベクトル内の複数の値を示す証明を構築できます。次のようになります:

この方法を使用すると、検証する必要がある同じベクトル内のデータポイントの数に関係なく、一定サイズの証明のみが必要です。

今、KZGコミットメントアルゴリズムの観点から最適化なしでVerkle Treeスキームを見てみましょう。

セクション「ベクトル内の単一の値を証明するためにKZGを使用する方法」から構築方法を使用すると、検証者は各多項式𝑓ᵢ(𝑥)の元多項式と商多項式のコミットメントを構築することができ、合計で𝟐﹡𝑚 KZGコミットメントが得られます。検証者はこれらのコミットメントを全て検証のための証拠として送信します。

ただし、前述のように、このアプローチには複数の証明を生成する必要があり、検証者も複数の検証計算を実行する必要があります。複数のコミットメント証明を圧縮する方法を見つける必要があります。

プルーフのマージ

プローバーは検証のために証拠[ 𝑞( 𝑠 )]₁を検証者に送信します。

このスキームによって生成される証拠は、1つのコミットメント、2つの証明、および1つの値で構成され、データサイズは一定です。最終的に、Verkleツリーでの証明のマージ最適化の後、検証可能なデータオブジェクトが検証者に送信されます。

1. 一定サイズの証拠
2. 証明する葉のデータ（キーと値のペア）
3. 葉から根へのパス上のすべてのノードのコミットメント値（ツリー幅が256で2³²ノードの場合、平均深さは4であり、コミットメント値が3つだけ必要）

𝑥ᵢと𝑦ᵢは明示的に提供する必要はありません。すべて計算できます。

5.3.3. パフォーマンス

Verkleツリーの証明マージングスキームに関して、生成された証明の具体的なサイズは次のとおりです（行の単位は十億です）。

上記のデータは、幅256のツリーを使用し、KZGコミットメントスキーム（コミットメントサイズ48バイト）を採用し、ツリーの利用を最大化した場合を想定しています。実際には、情報の完全にランダムな分布の場合、ツリーの深さは約60%増加し、各要素のサイズは30バイト増加します。Bulletproofスキームを使用する場合、コミットメントサイズは32バイトになります。

5.4. 証明者と検証者の計算負荷

1. プルーフ生成：証明者による証明の生成コストは、ツリーの幅に関連していますが、各アトミック操作には比較的低い計算コストが必要です。そのため、幅が256から1024のVerkleツリーはアルゴリズムの観点から優れたパフォーマンスを発揮します。
2. プルーフ検証：Vitalikは、検証アルゴリズムが非常に速く、通常、数千の値を検証する場合でも、100ms以内に完了することができると述べています。
3. Verkleツリーを更新する際：ツリーを更新するには、値や構造の変更に伴い、パスに沿ってすべての中間コミットメント値を再計算する必要があります。しかし、Vitalikは、多項式コミットメントアルゴリズムのいくつかの特性により、代替コミットメント値を事前に計算し、格納することで、更新中の計算時間コストを削減する方法を設計することが可能であると述べています。これにより、本質的に空間と時間を交換することができます。

6. 結論

以下は、ビタリック・ブログのオリジナルの文章です。最後に補足として1つの段落を追加しました。

Verkleツリーは、Merkleプルーフを強化する強力なアップグレードであり、はるかに小さなプルーフサイズを可能にします。各レベルですべての「姉妹ノード」を提供する必要がなくなり、証明者は各葉ノードからルートまでのすべてのコミットメント間の親子関係を証明する単一の証明のみを提供する必要があります。これにより、理想的なMerkleツリーと比較してプルーフサイズを約6〜8倍削減し、Ethereumが今日使用しているhexary Patriciaツリーと比較して20〜30倍以上削減することができます（！！）。

実装するためにはより複雑な暗号化が必要ですが、スケーラビリティの大幅な向上の機会を提供します。中期的には、SNARKsはさらなる改善をもたらす可能性があります。すでに効率的なVerkleプルーフ検証器にSNARKを適用して、証人のサイズをほぼゼロに減らすか、SNARKが大幅に改善された場合（たとえば、GKR、または非常にSNARKに適したハッシュ関数、またはASICを介して）に、SNARKされたMerkleプルーフに切り替えることができます。さらに、量子コンピューティングの台頭に伴い、Verkleツリーが依存する線形同型写像を不安定にするため、STARKされたMerkleプルーフにハッシュを使用する必要があります。しかし現時点では、これらはより高度な技術で得られるスケーリングの利益と同じスケーリングの利益をもたらし、すでに効率的に実装するために必要なすべてのツールが揃っています。

現在、多くのEthereumクライアントがVerkleツリーの実装と関連するテストネットワークを提供しています。コミュニティは、Verkle Treesが本ネットワークでいつ導入されるかについて議論を続けています。2024年または2025年のハードフォークアップグレードで実装される可能性があります。EthereumのVerkleツリーに関する詳細情報は、こちらを参照してください。https://verkle.info/ .

7. 参照

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. 知識の最小開示証明. Journal of computer and system sciences, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. Vector commitments and their applications[C]//Public-KeyCryptography–PKC 2013: 16th International Conference on Practice and Theory in Public- Key Cryptography, Nara, Japan, February 26–March 1, 2013. Proceedings 16. Springer, 2013: 55–72.

免責事項：

1. この記事は[ZAN]から転載されたもので、すべての著作権は元の著者に帰属します[アントチェーンオープンラボとZAN]. もし、この転載に対する異議がある場合は、お問い合わせください。Gate Learnチームがそれを迅速に処理します。
2. 責任の免責事項：この記事で表現されている意見は、著者個人のものであり、投資アドバイスを構成するものではありません。
3. 他の言語への記事の翻訳はGate Learnチームによって行われます。特に言及されていない限り、翻訳された記事のコピー、配布、または盗用は禁止されています。