ステートレスクライアントのためのVerkle Trie

Ethereumのスケーラビリティを考えた際にネックになるのが巨大なステートストレージ。利用者は１回だけ手数料を積んだトランザクションを発行するだけだけど、ネットワークに参加するフルノードは以降ずっとそのデータを維持しなければならず、ステートの成長とともに維持コストも膨れ上がりネックになる。

この問題へのアプローチの１つとして、ステートレスクライアントというアイディアがある。全ステートに対する暗号学的なコミットメントが、Ethereumのブロックヘッダーにステートルートという形で記録されている。ブロックの提供者に各トランザクションがアクセスするステート自体とそれが有効なステートであることの証明をセットで提供してもらうことで、ノードがそのストレージにステートを保持しなくて済むようにしようというもの。

Merkle Patricia Trieの包含証明

あるステートが有効かどうかはMerkle Patricia Trieのアイテムの包含証明を提供することで検証可能だ。web3-ethでもこのプルーフを取得するための関数getProofが提供されている。

Bitcoinのような二分木であれば、各ノードは2つの子ノードしか持たないため、ルートから対象のリーフノードまでのパス上にある兄弟ノードの数分の各ノードのハッシュ値がプルーフになる（ ${\log_2 n}$ ）。

一方、Merkle Patricia Trieのような16-ary(hex-ary)ツリーは、16個の子ノードを持つ。つまり各ノードが最大16個の子ノードのハッシュ値を持っている。そのため、単一のアイテムの包含証明には、ツリーのルートからそのアイテムがあるリーフノードまでのツリーの経路上のノードデータがプルーフとして必要になる。厳密にいうと、ルートノードは既知であるから必要なく、それ以外の経路上のノードデータの内、関係する子ノード以外の兄弟ノードのハッシュ値になるので15個のハッシュ。これらがあれば、リーフノードのデータから各ノードのハッシュを計算し、上位ノードの兄弟ノードのハッシュ値（プルーフ）を計算しながらツリーをたどり、ルートノードの子ノードのハッシュ値と合致すれば、アイテムがツリーに包含されていることを検証できる。ちなみに↑のgetproof関数は、兄弟分とかは関係なく経路上のノードの全データを返してるっぽい。

ステートレスクライアントのようなアプローチをする場合、現状のMerkle Patricia Trieだと上記のように１つのプルーフあたり ${15 \log_{16} n}$ のデータが必要になり、これがネックになる。

Verkle Trie

↑の課題を解消するために提案されているのがVerkle Trieという木構造とKZGコミットメントのアキュムレーター構造を組み合わせたもの↓

https://notes.ethereum.org/_N1mutVERDKtqGIEYc-Flw

Verkleという名前はVectorとMerkleから取った模様。Verkle Trieでは、プルーフの生成に多項式コミットメントスキームの一種であるKZGコミットメントを使用している↓

techmedia-think.hatenablog.com

一般的に、マークルツリーはn個の要素に対するベクトルコミットメントとして機能するが、多項式コミットメントも、n次の多項式にコミットするように構成すれば、n個の要素に対するベクトルコミットメントとして機能する。

そしてこの多項式コミットメントスキームの利点は、ベクトル内のアイテムの包含証明が、アイテムの数に依存せず、一定サイズになるという点（アキュムレーターのように機能する）。これによりステートレスクライアント導入にあたって、ステートの存在証明のサイズを小さな一定サイズにすることができる。

Verkle Trieのアイディアは、16個の子ノードを保持するMerkle Patricia Trieの内部ノードをKZGコミットメントに置き換えたKZGコミットメントのツリーを構成しようというもの。

中間ノードのKZGコミットメント

システムパラメータとして16個の ${s_0G, s_iG, ..., s_{15}G}$ 楕円曲線上の点が与えられるので（Gはそのベースポイント）、それと16個の子ノードの各データ（おそらくハッシュ値）を ${p_0, p_1, ..., p_{15}}$ を使って、

$commitment = \sum_i^{15}p_i s_iG$

を計算すれば、これがその中間ノードのKZGコミットメントになる。

見ての通り、このコミットメントは楕円曲線の1要素なので、サイズは使用する楕円曲線に依存するがBLS12-381とかだと48バイトくらいのはずで（KZGコミットメントにはペアリングが可能な曲線が必要）、既存の32バイトのハッシュ値×16個よりもとても小さくなる。

また、KZGコミットメントへの置き換えにより、包含証明に必要なプルーフのデータが ${15 \log_{16} n}$ から ${\log_{16} n}$ まで削減できる。

Verkle Trieの包含証明

Vercle Trie内にアイテムが存在するかは、以下のデータを使って検証される。

実際のリーフノードのデータ
データが保持されているノードまでのすべての中間ノードのKZGコミットメント
単一のプルーフ（KZGコミットメントに対してプルーフをどう検証するかは前回のブログ記事参照↑）

これらのデータを使って

リーフノードのデータが、親ノードのKZGコミットメントに含まれているか。
1の親ノードのデータがさらにその親のKZGコミットメントに含まれているか。
これをルートまで繰り返す。

ここまでだと、中間ノードの数分のコミットメントとプルーフが必要に思えるが、Multi-proofsという仕組みを利用すると小さな単一のプルーフ（200バイト以下）でこれらの証明が可能になるみたい↓

https://notes.ethereum.org/nrQqhVpQRi6acQckwm1Ryg

この辺り、また詳しく追っていきたい。

Trusted Setup

ただ、KZGコミットメントは、↑のブログ記事に書いたようにTrusted Setupを必要とする。↑のような16-aryツリーを構成する場合は、16個のシークレットパラメータ（ ${s_0, s_i, ..., s_{15}}$ ）を予め、誰もその値を知りえないようMPCなどで計算する必要がある。

Merkle Patricia Trieの課題から二分木に移行しようという議論もあったけど、Verkle Trieは、16-aryツリーのままアイテムの包含証明のサイズを削減できる新しいアプローチになる。

Develop with pleasure!

福岡でCloudとかBlockchainとか。