マークル ツリーと比較して、バークル ツリーは、ETH2.0 アップグレードの重要な部分としてプルーフ サイズが大幅に改善されました。サイズが 10 億のデータになると、マークル ツリー証明は 1kB かかりますが、バークル ツリー証明は 150 バイト以下しか必要としません。  Verkle Tree の概念は 2018 年に提案されました (詳細については、 を参照してください)。 Sin7Y による第 23 回テクニカル レビューでは、Verkle Tree の原理を説明します。 こちら マークルの木 Verkle ツリーを掘り下げる前に、Merkle ツリーの概念を理解することが重要です。マークル ツリーは一般的なアキュムレータであり、次の図に示すように、アキュムレータに 1 つの要素が存在することを証明するために使用できます。   (キー: 値) = (06: 32) がツリー (緑色のマーク) に存在することを証明するには、図の赤色のノードをすべて Proof に含める必要があります。 検証者は、図 1 に示す方法に従ってルートを計算し、予想されるルート (灰色のマーク) と比較できます。 ツリーの深さと幅が大きくなると、プルーフのサイズも大きくなることが予想されます (branched-2 の場合、複雑さは であり、branched-k の場合は  . log_2(n) (k−1)log_k です)。 (n) また、検証者は、基本レベルから上位レベルまで、多数のハッシュ計算を実行する必要があります。したがって、ツリーの深さと幅の増加は、検証者の作業負荷の増加につながりますが、これは容認できません。   Verkle Tree - コンセプト Tree の幅を単純に増やすと深さを減らすことができますが、プルーフ サイズが元の から に変わるため、プルーフ サイズは減少しません。 log_2(n) (k−1)log_k(n) すなわち、各層について、証明者は 追加のノード情報を提供する必要がある。論文 Verkle Tree で、John Kuszmaul は、証明の複雑さを に減らすスキームについて言及しました。 （ｋ－１）個の logk(n)   と設定すると、証明は 減少します。 k=1024 log_2(k) = 10 倍  Verkle ツリーの設計は次のように示されます。  各ノードには、次の 2 つの情報があります。(1) 値。 (2) 存在証明  .たとえば、緑色でマークされた は、  がコミットメント に存在し、  がこの引数の証明であることを示しています。 π (H(k,v),π_03) H(k,v) C_0 π_03 同様に、  は がコミットメント に存在し、  がこの引数の証明であることを意味します。 (C_0,π_0) C_0 C_Root π_0 論文 Verkle Tree では、このような存在コミットメントの方法を と呼んでいます。ベクトルコミットメントスキームを使用して元のデータの存在コミットメントを実行すると、Construct Proof の複雑さと更新 Proof の複雑さが あるのに対し、   ) の複雑さを持つ Proof が得られます。それぞれ。 ベクトルコミットメント O(n^2),O(n) で O(1 したがって、バランスを取るために、K-ary Verkle Tree スキームが紙の Verkle Tree で使用され (図 2 を参照)、構成証明、更新証明、および証明の複雑さを です。 O(kn),O(klogk n )、O(logk n) 具体的な性能比較を表 1 に示します。 この記事では、John Kuszmaul が彼の論文でよく説明している特定のベクトル コミットメント スキームの詳細な紹介を提供することを意図していません。 幸いなことに、ベクトル コミットメントと比較して、多項式コミットメントと呼ばれるより効率的なツールがあります。 座標セット と値セット のグループを指定すると、  を満たす多項式 ( ) を構築できます。  であり、この多項式へのコミットを行います。 (c_0,c_1,....,c_n) (y_1,y_2,....,y_n) P(c_i ラグランジュ補間 )=y_i   と は一般的な多項式コミットメント スキームです (この時点で、コミットメントは楕円曲線上のポイントであり、通常は 32 ～ 48 バイトのサイズです)。 KZG10 IPA 基本 シングルポイント用KZG  KZG10を例にとります。多項式 の場合、  を使用して多項式のコミットメントを表します。 P(x) [P(s)]_1 ご存知のように、  について、  の場合、  です。つまり、  と設定すると、  の場合、  は多項式です。 P(x) P(z)=y (x−z)|(P(x)−y) Q(x)=(P (x)−y)/(x−z) Q(x) ここで、P(x)P(x) が P(z)=yP(z)=y を満たす証明を生成します。つまり、[Q(s)]1[Q(s)]1 を計算し、それを検証する必要がある検証者に送信します。  s は有限領域 F 内のランダムに選択された点であるため、証明者の悪の行動が成功する確率は次数 (Q)/P (   ) です。 Schwartz–Zippel lemma 複数点の KZG ここで、  上の多項式 の値がそれぞれ であることを証明したいと思います。したがって、2 つの多項式を定義する必要があります。 (z0,z1,....,zk−1) P(x) (y1,y2,....,yk−1) 上記の説明によれば、  を満たす必要があります。つまり、以下を満たす多項式 が存在します。 V(x)|(P(x)−I(x)) Q(x) したがって、証明者は、  および のコミットメント を提供し、そのコミットメントを検証者に送信する必要があります。 P(x) Q(x) [P(s)]_1、[Q(s)]_1  Verifier は をローカルで計算し、式を検証します。 [I(s)]_1,[V(s)]_2  Point の数に関係なく、プルーフ サイズが一定であることは明らかです。 BLS12-381 曲線を選択した場合、プルーフ サイズはわずか 48 バイトであり、非常に効率的です。 バークル ツリー - ETH 要素の存在を証明するために証明者が サイズの証明を提供する必要があるマークル ツリーと比較して、Verkle ツリーは証明サイズを大幅に改善しました。 O(log_2n)  Verkle Tree の簡単な例を見てみましょう。  マークル パトリシア ツリー構造と同様に、ノードは、空のノード、内部ノード、葉ノードの 3 つのタイプに分類できることがわかります。 各内部ノード ツリーの幅は 16 (16 進数で 0000 -> 1111) です。リーフ ノードの状態が (0101 0111 1010 1111 -> 1213) であることを証明するには、内部ノード A と内部ノード B に対してコミットを行う必要があります。 内部ノード B のコミットメントの値がインデックス 1010 のハッシュ (0101 0111 1010 1111, 1213) であることを証明します。 内部ノード A のコミットメントの値がインデックス 0111 のハッシュ (cm_B) であることを証明します。 ノード ルートのコミットメントの値がインデックス 0101 のハッシュ (cm_A) であることを証明します。   を使用して上記のコミットメントを表し、それぞれ多項式 に対応させます。 C_0(InnernodeB)、C_1(InnernodeA)、C_2(Root) f_i(x) したがって、証明者は次のことを証明する必要があります。 複数のポリゴンの圧縮 簡単にするために、  を使用してインデックスを表します。 z_i 証明者は、多項式集合 について、点 次の条件を満たすことを証明する必要があります。   、それぞれ: 前の説明 (単一点の KZG) によると、各多項式について、以下を満たす商多項式が存在します。 証明者は、元の多項式と商多項式へのコミットメントを行い、それを検証者に送信する必要があります。 f_0(x),f_1(x),....,f_m−1(x) z_0,z_1,....,z_m− で 1  Verifier は検証を実行します。 検証者にそれほど多くのペアリング操作を実行させたくないことは明らかです (コストがかかります)。したがって、次のように Compress を実行する必要があります。 いくつかの乱数 を生成し、上記の商多項式をまとめます。 各 が多項式である場合にのみ、  が多項式になると仮定します (   ) の間の分数が正確にオフセットされる確率は、乱数のために非常に低くなります)。 r_0,r_1,....,r_m−1 q_i(x) g(x) q_i(x 証明者は多項式 にコミットし、  を検証者に送信します。 g(x) [g(s)]_1 次に、  が多項式 へのコミットメントであると検証者に信じさせます。 [g(s)]_1 g(x) 次のように記述できる多項式 g(x)g(x) の形式を観察します。 値 tt をランダムに選択すると、次のようになります。 多項式を定義します。 そのコミットメントは、次の方法で計算できます。 すると、点 tt における多項式 h(x)−g(x)h(x)−g(x) の値は次のようになります。 商多項式 計算します。 q(x)=(h(x)−g(x)−y)/(x−z) を コミットメント 計算し、検証者に送信します。 π = [q(s)]_1=[(h(s)−g(s)−y)/(s−t)]_1 を 検証者は、次の検証を実行します。 計算する 確認 キー プロパティ 証明サイズを変更せずに、このスキームを使用して任意の数の点を証明できます。 (各コミットメントには、証明 があります。) π   の値は、次のレイヤー値のハッシュであるため、明示的に指定する必要はありません。 y_i   の値は、Key から判断できるため、明示的に指定する必要はありません。 x_i 使用される公開情報には、証明されるキーと値のペアと、基本レベルから上位レベルまでの対応するコミットメントが含まれます。 参考文献 Dankrad Feist、「ランダム評価を使用した PCS マルチプルーフ」、   ://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html、アクセス: 2022-05-10。 https  Vitalik Buterin、「Verkle trees」、   ://vitalik.ca/general/2021/06/18/verkle.html、アクセス: 2022-05-10。 https  John Kuszmaul, “Verkle Trees,”   , アクセス: 2022-05-10. https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf

Ethereum

Twitter

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Architecture

2022 - HackerNoon Contributor of the Year - Blockchain

2022 - HackerNoon Contributor of the Year - Optimization

2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Optimization

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Privacy

Nominated for 2022 - HackerNoon Contributor of the Year - Architecture

Nominated for 2022 - HackerNoon Contributor of the Year - Blockchain

このオーディオは、ストーリーの元の言語で制作されています。

長すぎる; 読むには

Ethereum の Verkle Tree を深く掘り下げる

Ethereum の Verkle Tree を深く掘り下げる

About Author

コメント

ラベル

この記事は

Related Stories

AI/ML データレイクのリファレンスアーキテクチャを構築するためのアーキテクトガイド

HackerNoon Coded: HackerNoonが最も活発に活動している上位10カ国

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

18 種類の開発者ツールで生産性を向上しましょう 🚀🔥

AI/ML データレイクのリファレンスアーキテクチャを構築するためのアーキテクトガイド

HackerNoon Coded: HackerNoonが最も活発に活動している上位10カ国

HackerNoon ライティングコンテストで優勝したいですか? #crypto-api コンテスト優勝者のおすすめはこちら

18 種類の開発者ツールで生産性を向上しましょう 🚀🔥

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps