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

マークル ツリーと比較して、バークル ツリーは、ETH2.0 アップグレードの重要な部分としてプルーフ サイズが大幅に改善されました。サイズが 10 億のデータになると、マークル ツリー証明は 1kB かかりますが、バークル ツリー証明は 150 バイト以下しか必要としません。

Verkle Tree の概念は 2018 年に提案されました (詳細については、こちらを参照してください)。 Sin7Y による第 23 回テクニカル レビューでは、Verkle Tree の原理を説明します。

マークルの木

Verkle ツリーを掘り下げる前に、Merkle ツリーの概念を理解することが重要です。マークル ツリーは一般的なアキュムレータであり、次の図に示すように、アキュムレータに 1 つの要素が存在することを証明するために使用できます。

(キー: 値) = (06: 32) がツリー (緑色のマーク) に存在することを証明するには、図の赤色のノードをすべて Proof に含める必要があります。

検証者は、図 1 に示す方法に従ってルートを計算し、予想されるルート (灰色のマーク) と比較できます。

ツリーの深さと幅が大きくなると、プルーフのサイズも大きくなることが予想されます (branched-2 の場合、複雑さはlog_2(n)であり、branched-k の場合は(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 の複雑さがO(n^2),O(n) であるのに対し、 O(1 ) の複雑さを持つ Proof が得られます。それぞれ。

したがって、バランスを取るために、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であり、この多項式へのコミットを行います。

KZG10とIPAは一般的な多項式コミットメント スキームです (この時点で、コミットメントは楕円曲線上のポイントであり、通常は 32 ～ 48 バイトのサイズです)。

基本

シングルポイント用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

ここで、 (z0,z1,....,zk−1)上の多項式P(x)の値がそれぞれ(y1,y2,....,yk−1)であることを証明したいと思います。したがって、2 つの多項式を定義する必要があります。

上記の説明によれば、 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

要素の存在を証明するために証明者がO(log_2n)サイズの証明を提供する必要があるマークル ツリーと比較して、Verkle ツリーは証明サイズを大幅に改善しました。

Verkle Tree の簡単な例を見てみましょう。

マークル パトリシア ツリー構造と同様に、ノードは、空のノード、内部ノード、葉ノードの 3 つのタイプに分類できることがわかります。

各内部ノード ツリーの幅は 16 (16 進数で 0000 -> 1111) です。リーフ ノードの状態が (0101 0111 1010 1111 -> 1213) であることを証明するには、内部ノード A と内部ノード B に対してコミットを行う必要があります。

1. 内部ノード B のコミットメントの値がインデックス 1010 のハッシュ (0101 0111 1010 1111, 1213) であることを証明します。

   
   

2. 内部ノード A のコミットメントの値がインデックス 0111 のハッシュ (cm_B) であることを証明します。

   
   

3. ノード ルートのコミットメントの値がインデックス 0101 のハッシュ (cm_A) であることを証明します。

C_0(InnernodeB)、C_1(InnernodeA)、C_2(Root)を使用して上記のコミットメントを表し、それぞれ多項式f_i(x)に対応させます。

したがって、証明者は次のことを証明する必要があります。

複数のポリゴンの圧縮

簡単にするために、 z_iを使用してインデックスを表します。

証明者は、多項式集合f_0(x),f_1(x),....,f_m−1(x)について、点z_0,z_1,....,z_m− で次の条件を満たすことを証明する必要があります。 1 、それぞれ:
前の説明 (単一点の KZG) によると、各多項式について、以下を満たす商多項式が存在します。
証明者は、元の多項式と商多項式へのコミットメントを行い、それを検証者に送信する必要があります。

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 を計算し、検証者に送信します。

検証者は、次の検証を実行します。

1. 計算する

   

2. 確認

   

キー プロパティ

1. 証明サイズを変更せずに、このスキームを使用して任意の数の点を証明できます。 (各コミットメントには、証明πがあります。)

   
   

2. y_iの値は、次のレイヤー値のハッシュであるため、明示的に指定する必要はありません。

   
   

3. x_iの値は、Key から判断できるため、明示的に指定する必要はありません。

   
   

4. 使用される公開情報には、証明されるキーと値のペアと、基本レベルから上位レベルまでの対応するコミットメントが含まれます。

参考文献

1. Dankrad Feist、「ランダム評価を使用した PCS マルチプルーフ」、 https ://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html、アクセス: 2022-05-10。

   
   

2. Vitalik Buterin、「Verkle trees」、 https ://vitalik.ca/general/2021/06/18/verkle.html、アクセス: 2022-05-10。

   
   

3. John Kuszmaul, “Verkle Trees,” https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf , アクセス: 2022-05-10.