Verkleツリーは、Merkleツリーと同様に機能するコミットメントスキームですが、目撃者ははるかに少なくなります。これは、マークルツリーのハッシュをベクトルコミットメントに置き換えることで機能します。これにより、より広い分岐係数がより効率的になります。
投稿に関するフィードバックを寄せてくれたKevaundrayWedderburnに感謝します。
バークルツリーの仕組みの詳細については、以下を参照してください：
この投稿の目的は、ドラフトバークルツリーEIPの具体的なレイアウトを説明することです。これは、バークルツリーを実装したいと考えており、EIPを深く掘り下げる前に紹介を探しているクライアント開発者を対象としています。
バークルツリーは、ツリー構造に多くの変更をもたらします。最も重要な変更は次のとおりです。
バークルツリーのベクトルコミットメントスキームとして、 Pedersenコミットメントを使用します。 。 Pedersenのコミットメントは、楕円曲線に基づいています。 Pedersenコミットメントの概要と、内積引数を使用してそれらを多項式またはベクトルコミットメントとして使用する方法については、こちらを参照してください。
使用している曲線はバンダースナッチです。この曲線が選択されたのは、パフォーマンスが高く、BLS12_381の効率的なSNARKが将来的にバークルツリーについて推論できるようになるためです。これは、ロールアップに役立つだけでなく、すべての目撃者を1つのSNARKに圧縮できるようになると、それ以上のコミットメントの更新を必要とせずに、実用的になるようにアップグレードできます。
バンダースナッチの曲線次数/スカラー場のサイズは p =13108968793781547619861935127046491459309155893440570251786403306729687672801 、これは253ビットの素数です。この結果、最大252ビットのビット文字列にのみ安全にコミットできます。そうしないと、フィールドがオーバーフローします。バークルツリーには256の分岐係数（幅）を選択しました。これは、各コミットメントがそれぞれ252ビットの最大256の値（正確には、最大 p-1 の整数）にコミットできることを意味します。 ）。これを Commit（v₀、v₁、…、v₂₅₅）と記述します。 リストにコミットする v 長さ256。
バークルツリーEIPの設計目標の1つは、隣接する位置（たとえば、ほぼ同じアドレスまたは隣接するコードチャンクを持つストレージ）へのアクセスを安価にすることです。これを行うために、キーはステムで構成されます 31バイトとサフィックス 合計32バイトの1バイトの。キースキームは、「近い」ストレージロケーションが同じステムと異なるサフィックスにマップされるように設計されています。詳細については、EIPドラフトをご覧ください。
バークルツリー自体は、次の2種類のノードで構成されます。
拡張ノードへのコミットメントは、4要素ベクトルへのコミットメントです。残りの位置は0になります。それは：
C₁とC₂は、ステムが stem に等しいすべての値にコミットする2つの追加のコミットメントです。 。コミットメントが必要な理由は、値が32バイトであるため、フィールド要素ごとに252ビットしか格納できないためです。したがって、単一のコミットメントでは256個の値を格納するのに十分ではありません。したがって、代わりに、C₁はサフィックス0〜127の値を格納し、C₂は128〜255を格納します。ここで、値はフィールドサイズに収まるように2つに分割されます（後で説明します）。
拡張とコミットメントC1およびC2は、「拡張と接尾辞木」（略してEaS）と呼ばれます。
図1 キー abcd..ff を表します。 04 の値を含む2つのサフィックスツリーコミットメント 、v₄。
各拡張子および接尾辞ツリーノードには、256個の値が含まれています。値は256ビット幅であり、1つのフィールド要素に安全に格納できるのは252ビットのみであるため、単純に1つのフィールド要素に1つの値を格納しようとすると、4ビットが失われます。
この問題を回避するために、256個の値のグループをそれぞれ128個の値の2つのグループに分割することを選択しました。グループ内の各32バイト値は、2つの16バイト値に分割されます。したがって、V + + v ==V T +
になるように、値V T≒∞とv≒∞に変わる。「リーフマーカー」がv⁽ˡᵒʷᵉʳ⁾ᵢに追加され、アクセスされたことのないリーフと0で上書きされたリーフを区別します。 バークルツリーから値が削除されることはありません 。これは、今後の州の有効期限スキームに必要です。そのマーカーは129ビット、すなわちv⁽ˡᵒʷᵉʳᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ=v⁽ˡᵒʷᵉʳ⁾ᵢ+2¹²⁸vᵢが以前にアクセスされた場合、およびv⁽ˡᵒʷᵉʳᵐᵒᵈⁱᶠⁱᵉᵈ⁾ᵢ=0vᵢがアクセスされていない場合。>
次に、2つのコミットメントC1とC2は次のように定義されます
拡張ノードへのコミットメントは、「拡張マーカー」で構成されます。これは、番号1、2つのサブツリーコミットメントC1とC2、およびステムです。 この拡張ノードにつながるキーの一覧。
親内部ノードを子内部ノードにブリッジするキーのセクションのみを含むMerkle-Patriciaツリーの拡張ノードとは異なり、ステムはその時点までのキー全体をカバーします。これは、バークルツリーがステートレスプルーフを念頭に置いて設計されているためです。拡張機能を2つに「分割」する新しいキーが挿入された場合、古い兄弟を更新する必要がないため、プルーフを小さくすることができます。
内部ノードには、コミットメントのより簡単な計算方法があります。ノードは、256個のサブツリーのそれぞれのルートコミットメント（のフィールド表現）である256個の値のベクトルとして表示されます。空のサブツリーのコミットメントは0です。サブツリーが空でない場合、内部ノードのコミットメントは
です。
ここで、Cᵢは内部ノードの子であり、子が空の場合は0です。
図2は、ツリーに新しい値を挿入するプロセスを示しています。これは、ステムがいくつかの初期バイトに衝突すると興味深いものになります。
図2 値v₁₉₂は場所 0000000000 ... 0000 の場所に値v₁₂₇のみを含むバークルツリー内 。ステムは3番目のバイトで異なるため、異なるバイトまで2つの内部ノードが追加されます。次に、完全な31バイトの語幹を持つ別の「拡張と接尾辞」ツリーが挿入されます。最初のノードは変更されておらず、C²₀は挿入前のC⁰₀と同じ値です。
バークルツリー構造により、ツリーが浅くなり、保存されるデータの量が減ります。しかし、その真の力は、より小さな証拠、つまり証人を作成する能力から来ています。これについては次の記事で説明します。
