Verkle木：多項式コミットメント（第2回/全2回）

Verkle木：多くのリーフノードから1つの輝くコミットメント点へ収束する滑らかな多項式曲線

第1回はある問題を残して終わった。EthereumのステートトライにおけるMerkle証明はステートレスバリデーションには大きすぎる。ブロックあたり数MBの帯域幅コストでは、証明を含めると個人バリデータはデータセンターに追いやられてしまう。

解決策は、ハッシュベースのコミットメントを多項式コミットメントに置き換えることだ。各ノードがハッシュの代わりに曲線上の点を格納し、子の数も16から256に広がる。ルートまでのパス上ですべての兄弟ハッシュ（約3 KB）を提供してリーフを証明する代わりに、証明者は各レベルで小さな証明（約150バイト）を送る。およそ20倍の縮小だ。この記事を読み終えれば、その仕組みがわかるだろう。

値から多項式へ

中心となる考え方はベクトルコミットメントを構築することだ。多数の値にコミットし、他を明かさずにどれか1つを証明できる方式だ。これがVerkleの「V」の由来だ（Vector commitment + Merkle）。1 木の構造は同じで、各ノードのコミットメント方式が異なる。

多項式を使ってこれを実現する。ノードの256個の子すべてを1つの多項式の評価値として表現する。

$$P(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_{255} x^{255}$$

位置 $0, 1, \ldots, 255$ を選び、係数 $a_0, \ldots, a_{255}$ を次のように決める。

$$P(i) = v_i \quad (i = 0, 1, \ldots, 255)$$

これで、すべての子の値を通る次数255の多項式が得られる。このような多項式は常に存在し、一意だ。$n$個の位置と値のペアが与えられれば、次数 $n - 1$ の多項式がちょうど1つ決まる。2 この多項式を見つけるアルゴリズムがラグランジュ補間だ。

ラグランジュ補間の仕組み

1つの点で1、他のすべての点で0になる基底多項式を構築し、それらの重み付き和をとる。$n$個の点に対して、位置 $j$ のラグランジュ基底多項式は次の通りだ。

$$L_j(x) = \prod_{\substack{m=0 \\ m \neq j}}^{n-1} \frac{x - m}{j - m}$$

$L_j(j) = 1$ で、$m \neq j$ のすべての $m$ に対して $L_j(m) = 0$ だ。完全な多項式はそれらの重み付き和になる。

$$P(x) = \sum_{i=0}^{n-1} v_i L_i(x)$$

たとえば4つの点の場合、位置0の基底多項式は次のようになる。

$$L_0(x) = \frac{(x-1)(x-2)(x-3)}{(0-1)(0-2)(0-3)}$$

$x = 0$ で1、$x = 1, 2, 3$ で0になる。完全な多項式 $P(x) = v_0 L_0(x) + v_1 L_1(x) + v_2 L_2(x) + v_3 L_3(x)$ は4つすべての値を通る。

ここまではただの代数だ。子をエンコードする多項式が手に入った。しかし $P$ を直接共有すれば256個の係数すべてを送ることになり、子そのものを送るのと変わらない。$P$ を短いコミットメントに圧縮する方法が必要だ。ここで楕円曲線の出番だ。

多項式1つに対して曲線上の点1つ

注意点を一つ。ここから先のすべての算術（多項式の係数、その評価値、楕円曲線のスカラー）は、同じ有限体 $\mathbb{F}_p$ 上で行われる。

誰も知らない秘密のスカラー $s$ が存在し、以下の公開パラメータにみんながアクセスできるとしよう。

$$G, \ sG, \ s^2G, \ \ldots, \ s^dG$$

$s$ の生成と破棄については付録で扱う。ここではこれらの点を所与とする。$P(x)$ にコミットするために、証明者は次を計算する。

$$\begin{aligned} C &= a_0 \cdot G + a_1 \cdot sG + \cdots + a_d \cdot s^dG \\ &= P(s) \cdot G \end{aligned}$$

証明者は $C$ を計算するのに $s$ を知る必要がない。自分の多項式の係数と公開パラメータを組み合わせるだけだ。3

結果は1つの曲線上の点（圧縮48バイト）で、多項式全体にコミットする。衝突耐性のあるハッシュが2つの異なる入力に対して同じ出力を返さないのと同様に、このコミットメントは束縛性を持つ。2つの異なる多項式 $P \neq Q$ に対して $P(s) \neq Q(s)$ が圧倒的な確率で成り立ち、したがってコミットメント $C = P(s) \cdot G$ も異なる。4

各Verkleノードはハッシュの代わりにこの $C$ を格納する。コミットメントは手に入った。次はその中身を証明する方法が必要だ。

開示証明：1つの値を証明する

Aliceはコミットメント $C$ を位置 $z$ でオープンし、値 $y$ が含まれていることを確認したい。証明者は $P$ も他の子も明かさずに $P(z) = y$ であることを納得させなければならない。どうやって？

ここがポイントで、多項式の代数から来ている。$P(z) = y$ ならば $P(x) - y$ は $x = z$ に根を持ち、$(x - z)$ で割り切れる。商多項式を定義する。

$$Q(x) = \frac{P(x) - y}{x - z}$$

この除算が割り切れるのは $P(z) = y$ のときに限る。偽の主張では余りが残り、証明者は有効な $Q$ を生成できない。

開示証明 $\pi$ は単に $Q$ へのコミットメントだ。

$$\pi = Q(s) \cdot G$$

曲線上の点1つ。兄弟は不要。

次に検証者は $Q$ が正当かどうかを確認する。除算が割り切れたなら、逆に掛け戻すと多項式の恒等式が得られ、$x = s$ を含むすべての点で成り立つ。

$$P(s) - y = Q(s) \cdot (s - z) \tag{1}$$

検証者はこの等式を直接検証できない。$C = P(s) \cdot G$ と $\pi = Q(s) \cdot G$ を持っているが、曲線上の点はそのスカラーを隠している。そこから $P(s)$ や $Q(s)$ を取り出すのは離散対数問題だ。そして $(s - z)$ には $s$ の知識が必要だが、誰もそれを持っていない。

ペアリングによる証明の検証

ペアリング $e$ とは、一方の曲線群（$\mathbb{G}_1$）の点ともう一方（$\mathbb{G}_2$）の点を受け取り、ターゲット群の元を出力する関数で、双線形性という性質を持つ。

$$e(aG_1, bG_2) = e(G_1, G_2)^{ab}$$

あるスカラー $a$ を隠す点と $b$ を隠す別の点を入力すると、出力がそれらの積を捉える。$a$ や $b$ を取り出すことはできないが、2つの積が等しいかどうかをペアリングの出力を比較して確認できる。5 ペアリングには2つの異なる曲線群が必要だ。これまで使ってきた $G$ は $\mathbb{G}_1$ に属し（$G_1$ となる）、$G_2$ は $\mathbb{G}_2$ の生成元だ。公開パラメータには $sG_2$ も含まれる。

戦略はこうだ。等式 $(1)$ の各辺を2つのスカラーの積として表し、一方の因子を $\mathbb{G}_1$ に、他方を $\mathbb{G}_2$ に入れる。右辺は自然に $Q(s) \cdot (s - z)$ と因数分解される。左辺は $(P(s) - y) \cdot 1$ にすぎないので、生成元 $G_2$ とペアリングする。

左辺：$(P(s) - y)G_1 = C - yG_1$ なので

$$e(C - yG_1, G_2) = e(G_1, G_2)^{P(s) - y}$$

右辺：$Q(s) \cdot G_1 = \pi$ で $(s - z)G_2 = sG_2 - zG_2$ なので

$$e(\pi, sG_2 - zG_2) = e(G_1, G_2)^{Q(s)(s-z)} $$

これらが等しくなるのは等式 $(1)$ が成り立つときに限る。検証は1つのチェックに帰着する。

$$e(C - yG_1, G_2) = e(\pi, sG_2 - zG_2) \tag{2}$$

検証者はこの等式のすべての変数を知っている。$C$ と $\pi$ は証明者から受け取り、$y$ と $z$ は主張された値と位置、$G_1$、$G_2$、$sG_2$ は公開パラメータだ。ペアリングチェック1回、兄弟なし。

全体像

ここで一歩引いて、構築したものを振り返ろう。256個の子を持つノードが多項式にエンコードされ、1つの曲線上の点に変換される。1つの子を開示するために、証明者は対応する根で割って商多項式を求め、それを2つ目の曲線上の点に変換する。ペアリング関数が2つの曲線群をつないで、双線形性で、曲線上の点だけから割り算の正確さを検証する。点2つ、チェック1回。これで終わりだ。こんなものが成り立つのは、宇宙の綻びを覗き込んでいるようだ。

このコミット・オープン・検証方式はKZG（Kate-Zaverucha-Goldberg）と呼ばれる。ノードごとに1つのコミットメント、レベルごとに1つの開示証明。幅16のMerkle木は約8〜10レベル必要で、各レベルで15個の兄弟ハッシュ（480バイト）がかかる。幅256のVerkle木は同じ状態をわずか約3レベルでカバーし、6 各レベルで約48バイトの証明1つだけだ。

MerkleとVerkleの証明構造の比較：Merkleは各レベルで15個の兄弟ハッシュが必要だが、Verkleは各レベルで1つの証明だけで済み、証明サイズが約20分の1になる
具体的な流れ

AliceはETH残高を検証したい。Aliceのハッシュされたアドレスから位置 $k_0, k_1, k_2$ が得られ、ルート $\to$ $C_1$ $\to$ $C_2$ $\to$ リーフ $v$ というパスをたどる。証明者はAliceにリーフの値 $v$、中間コミットメント $C_1$ と $C_2$、各レベルの開示証明 $\pi_i$ を送る。Aliceはボトムアップで検証する。

  1. $C_2$ は位置 $k_2$ で $v$ にオープンするか？ $\pi_2$ を検証。
  2. $C_1$ は位置 $k_1$ で $C_2$ にオープンするか？7 $\pi_1$ を検証。
  3. $C_0$ は位置 $k_0$ で $C_1$ にオープンするか？ $\pi_0$ を検証。
  4. $C_0$ はブロックヘッダのステートルートと一致するか？ 完了。

開示証明3つ（各約48バイト）、合計約150バイトだ。

多項式コミットメントはハッシュベースのMerkle証明が抱えるトレードオフも解消する。 Merkle木では幅を狭くすると証明は小さくなる（各レベルの兄弟が減る）が、深い木はルックアップあたりのディスクリードが増える（第1回の付録のボトルネック）。ステートレスバリデーションは深さの問題を緩和するが、証明サイズは依然として幅とともに増大する。多項式コミットメントではそうならない。ノードを広く、木を浅くできる。

EthereumのVerkle提案：IPA

上の数値はKZGの証明サイズを反映している。Ethereumの実際のVerkle木提案は異なる構成要素を入れ替えている。コミットメントの種類（Pedersen）、証明手法（IPA）、曲線（Bandersnatch）のそれぞれが異なる。アーキテクチャは同じだが、個々の証明はより大きく（約544バイト）、検証はより遅い。しかしそのトレードオフには価値がある。トラステッドセットアップが不要になるのだ。KZGセレモニーの秘密 $s$ が復元されてしまえば、方式全体が崩壊する。Ethereumのすべての価値を保全するステートツリーに対して、コミュニティはそのリスクを完全になくす道を選んだ。

ブロックレベルでは、Dankrad Feistのマルチプルーフ方式がブロック内のすべての開示証明を、状態アクセスの数によらず1つの定数サイズの証明（約200バイト）にまとめる。

今後の展望

Verkle木がEthereumに採用される見込みは現在薄い。楕円曲線暗号への依存が耐量子性を欠くためで、コミュニティはハッシュベースのバイナリステートツリーへと舵を切りつつある。しかし、ここで築いた考え方（多項式でデータにコミットし、すべてを明かさずに性質を証明する）は、もっと大きなものの基盤になる。ゼロ知識証明だ。状態アクセスだけでなく、ブロック全体の実行が正しいことを1つのコンパクトな証明で示せるようになる。証明が小さくなればすべてが解決するわけではない（たとえば、増え続ける状態を保存してブロックを構築する人は依然として必要だ）が、ますます目指されるのは、証明を増やし、保存を減らすことだ。

ゼロ知識証明の背後にある暗号技術（算術回路から証明システムの違いまで）は、近いうちにこのブログで探っていくつもりだ。楽しみにしていてほしい。

付録

トラステッドセットアップ・セレモニー

KZGコミットメントには公開パラメータ（曲線上の点 $G, sG, s^2G, \ldots, s^dG$）が必要だ。秘密 $s$ は生成後に破棄しなければならない。誰も知るべきでない数をどうやって破棄するのか。

このセレモニーではマルチパーティ計算を使う。参加者が順番にランダム性を提供する。

  1. 参加者1がランダムな $s_1$ を選び、各べき乗 $i$ について $s_1^i G$ を計算し、結果を公開して $s_1$ を破棄する。
  2. 参加者2が $s_2$ を選び、前の出力を「再ランダム化」して $(s_1 s_2)^i G$ を生成し、$s_2$ を破棄する。
  3. これをすべての参加者について繰り返す。

最終出力は $(s_1 s_2 \cdots s_n)^i G$ だ。結合された秘密 $s = s_1 s_2 \cdots s_n$ は、少なくとも1人の参加者が自分の寄与を正直に破棄していれば安全だ。他のすべての参加者が悪意を持っていても、正直な1人がいれば十分だ。

Ethereumは2023年初頭にEIP-4844（proto-danksharding）のためにまさにこのタイプのセレモニーを実施した。14万人以上が参加し、史上最大のトラステッドセットアップ・セレモニーとなった。得られたパラメータは現在、Ethereum上のblobコミットメントに使われている。

  1. この名前と構成はJohn KuszmaulがVerkle Trees（2018）で導入した。 ↩

  2. 存在：ラグランジュ補間が $P$ を直接構成する。一意性：$P$ と $Q$ が同じ $n$ 点を通ると仮定する。$D = P - Q$ は $n$ 点すべてでゼロだが、$D$ の次数は高々 $n-1$ なので根は高々 $n-1$ 個。$D = 0$（つまり $P = Q$）でない限り矛盾する。多項式補間（一意可解性定理）を参照。 ↩

  3. スカラー倍が点の加法に分配するためこれが成り立つ。$a_0 \cdot G + a_1 \cdot sG = (a_0 + a_1 s)G$。写像 $f(a) = aG$ はスカラーから曲線上の点への群準同型だ。 ↩

  4. $P \neq Q$ ならば $D = P - Q$ は次数高々 $d$ の非ゼロ多項式で、$\mathbb{F}_p$ 内に高々 $d$ 個の根を持つ。コミットメントが一致するには、$s$ が $p$ 個のうちの $\leq d$ 個の値のどれかでなければならない。その確率は高々 $d/p$ で、$p \sim 2^{255}$ かつ $d = 255$ なので無視できるほど小さい。 ↩

  5. ペアリング対応曲線にはこれを可能にする特殊な構造がある。すべての楕円曲線がペアリングをサポートするわけではない。今日Ethereumで使われているBLS12-381は、効率的なペアリングのために特別に設計された。 ↩

  6. ノードあたり256個の子で、$256^3 \approx 1670$ 万、$256^4 \approx 43$ 億。Ethereumには約2億5000万のアカウントとコントラクトストレージスロットがあるため、深さ3〜4で現在の状態をカバーできる。 ↩

  7. 多項式の評価値はスカラーでなければならないが、$C_2$ と $C_1$ は曲線上の点だ。ブランチノードは各子コミットメントを体の元（たとえばシリアライズされたx座標）に変換してから多項式を補間することで対処する。ステップ3も同様だ。 ↩

この記事はClaudeと協力して執筆しました。