KZGコミットメント

イーサリアムがProof of Stakeに移行した今日、次の課題はスケーリングとなりました。

10x・100xスケールを実現するために、高度な数学を用いた様々な技術の導入が検討されています。イーサリアムは皆がトランザクションを実行しProof of Stakeでステートに合意する比較的単純なシステムから、zkSNARKsやDASを始めとした先駆的な数学により成り立つ”Moon math”ベースのチェーンになると考えられます。

PoS activated! credit: @EthereumOnARM

この記事で解説するKZGコミットメント（略：KZG）は、スケーラビリティを達成するために必要なプリミティブの一つです。KZGは、Kate-Zaverucha-Goldbergの頭文語で、Kateは"kah-tay"と発音します。 KZGは「多項式コミットメント」の1種であり、KZG以外にもIPA、FRIなどの多項式コミットメントスキームが存在します。多項式コミットメントは、多項式（e.g. $3x^2 + 2x + 7 = 0$）について簡潔な証明を作成するためのプリミティブです。また、この世界の情報は、全て”多項式”で表すことができるため。（イーサリアムのステートでも、人間でも、多項式で表すことができます。）、多項式コミットメントは単一の問題解決のためだけでなく、様々な場面で応用することができます。

今後のイーサリアム自体の進化、またイーサリアムに付随する様々なシステムの発展に、KZGやそれに類似したプリミティブが登場する場面が増えると考えられます。KZGについて知ることで、今後のイーサリアムエコシステムの繁栄について、一段階深い洞察ができるようになる思います。また、非常にオープンな形で行われているイーサリアムリサーチに少しでも多くの人が貢献することに、このような解説資料が役に立つと幸いです。

知識要件

この記事は楕円曲線についての知識を前提としています。

楕円曲線の入門には、以下の記事をおすすめします！

• 英語: Elliptic Curve Cryptography: a gentle introduction
• 日本語: 楕円曲線と楕円曲線暗号
  

KZGでできること

Verkle Tree

• Verkle Treeは、値がデータの中に存在することを簡潔に証明するためのプリミティブです。Verkle Treeはマークル木と同じ問題を解決しますが、マークル木は各々の深さの隣接ノードを証明に含める必要があるのに対し、Verkle Treeは一つ（$O(1)$）の証明で全てのノードの親子関係を示すことができます！イーサリアムのステートはMerkle Patricia Treeで管理されていますが、これをVerkle Treeに置き換えることが検討されています。(The Verge)

zkSNARKs

• zkSANRKを使用すると、計算が正しく行われたことを、その計算に用いられたインプットを晒さずに、簡潔に証明することができます。証明される処理の計算量によらず、検証は常に$O(1)$（zkSNARKの種類により異なることはあります）であるため、ブロックチェーンなど多量な計算を苦手とするシステムから計算を"オフロード"することに役立ちます。また、匿名送金や、匿名帰属証明など、様々な新生的なプライバシーアプリケーションを可能にする技術でもあります。

Overview

KZG Commitmentは多項式コミットメントの1種です。

多項式コミットメントとは、
多項式がある値で評価されたとき、結果が主張された値であることを簡潔に証明できるプリミティブです。言い換えると、 $P(a) = b$であることを、$P(a)$を再実行することなく、検証可能にする方法です。

高次元（$2^{28}$次元など）多項式の場合は実行に時間がかかるため、評価のみを簡単に確認にできることが非常に有り難くなります。

言語としての多項式

KZGのメカニズムについて記述する前に、KZGに限らず、zkSNARK,
zkSTARKなどの「言語」ともいえる「多項式」について深堀ります。

まず、例を挙げると、$3x^2 + 2x + 7 = 0$ は多項式です。

全ての多項式は、

$$\sum_{i=0}^n{a_ix^i}$$

• ($n$: 多項式の次元数)

という形で表現できます。（この形式で表現できないものは多項式でないです。）

では、なぜ多項式が様々なプリミティブの言語となるのでしょうか？
簡単に言うと、

• 如何なる情報も、$a_0 + a_1 * x^1 + a_2 * x^2 ... a_{n} * x^{n}= 0$ の形にエンコードできるため
• 多項式で表現すると様々な操作ができ、便利であるため（例：KZG）

です。

$[2, 4, 6]$というベクトルを多項式にエンコードしたいとしましょう。
ベクトルを多項式で表現するためには、ベクトルの全ての値を通る多項式を作成します。これは、多項式補間と言われる方法です。

この記事では、多項式補間の一つである、ラグランジュ補完を紹介します。

$[2, 4, 6]$というベクトルの場合、

• $P(1)= 2$
• $P(2) = 4$
• $P(3)= 6$
  となるような多項式$P(X)$を作成します。

まずは、$P(1) = 2$を満たすことだけに集中します。

• $P(1) = 2$
• $P(2) = 0$
• $P(3) = 0$

上記3つの等式を満たす多項式$P_1(x)$を構築します。

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

という分数で表してみましょう。

• $x$が$2, 3$の時、分子が0になるため、$P_1(x) = 0$
• $x$が$1$の時は分子と分母が同一となるため、$P_1(x) = 1$

従って、

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

となります。

$P(2) = 4$, $P(3) = 6$にも、同等の$P_2, P_3$を作成し、$P_1, P_2, P_3$を加算すると、$P(x)$が完成します！

まとめると、

• $P(x) = \frac{2(x - 2)(x - 3)}{(1 - 2)(1 - 3)} + \frac{4(x - 1)(x - 3)}{(2 - 1)(2 - 3)} + \frac{6(x - 1)(x - 2)}{(3 - 1)(3 - 2)}$

が、ベクトル$[2, 4, 6]$を表す多項式となります！

ペアリング

KZGを構築するコンポーネントの一つであるペアリングは、BLS署名やzkSNARKの構築材料ともなっています。
ペアリングには、2つの異なる楕円曲線が用いられます。その楕円曲線を$E_1$, $E_2$とします。また、ペアリングに用いる$E_1$, $E_2$上の巡回群をそれぞれ$G_1$,$G_2$と定義します。

ペアリングは、$G_1$,$G_2$それぞれの点$P_{[1]}$, $P_{[2]}$から、別の群の値$P_t$を出力する関数です。$e$をペアリング関数とした時、

• $e(P_{[1]}, P_{[2]}) = P_{t}$

と表現されます。

また、$G_1$の生成元を$G$、そして$G_2$の生成元を$H$としたとき

• $[x]_1 = xG$
• $[x]_2 = xH$

となります。

また、ペアリングには双線型写像(bilinear map)、というプロパティが存在します。

KZGというコンテキストでは、以下の双線型写像により成り立つ等式が重要となります。

• $e([a]_1, [b]_2) = e(G, H)^{ab}$

ペアリングの内部メカニズムは非常に複雑で、自分自身も辛うじて理解しているとしか言えません。
KZGなどのプリミティブを学ぶ際に、ペアリングはブラックボックスとして考えて問題ないと思います。

多項式評価の証明

ここから、KZGのメカニズムについて記述します！

KZGを用いて$P(a) = b$であることを証明することを目標にしましょう。
大まかには以下の2ステップを実行します。

$P(a) = b$を示すために、$P(a) - b = 0$であると証明すれば良いと言えます。
$P(a) - b = 0$を証明するために、$(x - a)$が$P(x) - b$の因数であることを示します。これは、$P(x) - b$に$(x - a)$が因子として存在すれば、$P(x) - b$を$a$で評価した時に$(a - a) = 0$が因子となるためです。つまり、$P(x) - b$を$x - a$で割り切ることができる、言い換えると

• ${P(x) - b} = Q(x)(x - a)$
  • $Q(x)$: 除算の商

という等式が成り立つことを証明すれば良いのです！

次に、Kate commitmentを使って、この等式が成り立つことを証明します。

Kate commitment

コミットメント
多項式やデータについて陳述する際に、その多項式・データにコミットする必要があります。（Merkle Treeの場合、Merkle Rootがコミットメントに当たります。）コミットメントには、バインディングというプロパティが存在します。バインディングとは、元のデータが変化することによりコミットメントも変化する、という性質です。また、コミットメント関数は一方向であるため、任意のコミットメントになるような元データを作成することはできません。

実際にコミットメントとして用いられる値は、ブロックチェーンのブロックヘッダー等、皆が予め合意するものである場合が多いです。ブロックのMerkle Rootが計算されるのも、そのMerkel Rootをコミットメントとして用いて、ブロックについて簡潔な証明（Merkle Proof）を作成するためです。

Kate commitment
Kate commitmentは、

• $[f(s)]_1$

と定義されます。$[ ]_1$は、ペアリング関数の一つ目の群$G_1$に存在する値であることを示します（$[f(s)]_1 = f(s) * G_1$となります）。

また、ここで使用される $s$ は、誰も知らない値である必要があります。（$s$が知られていると、偽の証明を作成することができてしまいます。）$s$が秘密の値であるとき、どのように$ [f(s)]_1$を計算すれば良いのでしょうか？

$[f(s)]_1$は、$f(x)$が多項式であるため、多項式の一般的な形（詳細は上記）を用いて

$$G_1 * \sum_{i=0}^n{f_is^i}$$

と表すことができます。（$f_i$が$f(x)$の係数です）。

$s$自体は秘密の値ですが、$s$を多項式で評価する際に必要な「中間の値」 $[s^i]_1$は公開されています。これらの値はTrusted setupにより生成されます。Trusted setupについて詳細を知りたい方には、こちらの記事がおすすめです！

そして、

$$G_1 * \sum_{i=0}^n{f_is^i}$$

$$=\sum_{i=0}^n{f_is^i*G}$$

$$=\sum_{i=0}^n{f_i[s^i]_1}$$

であるため、$s$を知らずとも、Trusted setupにより生成された$({[s^0]_1, [s^1]_1..[s^n]_1)}$を用いて、$[f(s)]_1$を構築することができます！

証明

Kate commitmentの定義と計算方法がわかったので、

$$P(x) - b = Q(x)(x - a)$$

を証明することに戻りましょう。

まず、$P(x)$のKate commitmentを作成します。

$$C = [P(s)]_1$$

次に、$Q(x)$のKate commitmentを作成します。KZGでは、これが証明($\pi$)となります。

$$\pi = [Q(s)]_1$$

検証

証明者から渡される値は以下の3つです。コミットメント$C$に該当する多項式を$a$で評価したとき、結果は$b$となる、という証明者の主張を検証します。

$$\pi, b, a, C$$

以下のペアリング等式が成り立つことを検証します。

$$e(\pi, [s - a]_2) = e(C - [b]_1, H)$$

（$H$は、巡回群$G_2$の生成元で、$G_2$の中で1に相当します。）

では、なぜ上記が成り立つと$P(a) = b$であると確証できるのでしょうか？

両辺を展開して見ます。

左辺

$$e(Q(s) * G, (s - a) * H)$$

$$= e((\frac{P(s) - b}{s - a}) * G, (s - a) * H)$$

$$= e(G, H)^{\frac{P(s) - b}{s - a}(s - a)}$$

$$= e(G, H)^{P(s) - b)}$$

右辺

$$e(C - [b]_1, H)$$

$$=e((P(s) - b) * G, H)$$

$$e(G, H)^{P(s) - b}$$

このように、両辺同値であることがわかります。

健全性

ここで、偽の証明の作成を試みましょう。

$P(a)$が、$b$ではなく、$b'$と評価されるという偽の証明を作成したい場合、$P(a) - b' \neq 0$なので、$\frac{P(x) - b'}{x - a}$に余りが出てしまいます。（言い換えると、$（x - a）$が $P(x) - b$ の因子であるという命題が偽となってしまいます。）
$P(a) = b'$を示すための、商$Q(x)$は作成できないことがわかりました。

では、$\pi$を操作するとどうでしょうか？

$$\pi = (C - [b]_1)^{\frac{1}{s - a}}$$

という$\pi$、を作成すれば、

$$e((C - [b]_1)^{\frac{1}{s - a}}, [s - a]_2)$$

$$= \frac{1}{s - a} * {s - a} * e((C - [b]_1), H)$$

$$= e((C - [b]_1), H)$$

となり、ペアリング等式を満たすことできます。

しかし、$s$は誰も知らない値なので、そのような$\pi$を作成することはできません。$s$が誰も知らない値である必要があるのはこのためです。$s$が知られていると、偽の証明が作成されてしまいます。

振り返り

最後に、上記で行ったことを振り返りましょう。
KZGを用いて、$P(a) = b$を証明します。

証明者

1. $P(x)$のKate commitmentを計算します。

   • $C = [P(s)]_1$
   • この時、Trusted setupで生成された[$s^{0}G, s^{1}G, s^{2}G...s^{n}G$]を用いて$[P(s)]_1$を計算します。

2. $\frac{P(x) - b}{x - a} = Q(x)$を求めます。

3. $Q(x)$のKate commitmentを計算することで、証明$\pi$を取得します。

   • $\pi = [Q(s)]_1$

検証者

• $P(a) - b = Q(x)(x - a)$であるかどうかを、ペアリングで検証します。
  • $e(\pi, [s - a]_2) = e(C - [b]_1, H)$

これが、KZGを用いて多項式の評価を証明する流れの全てとなります。

EIP-4844のTrusted setupセレモニー

EIP-4844で用いるための、KZGのTrusted setupが行われています。（2022年11月）参加者がそれぞれの秘密の値を蓄積させ、誰も知らない$s$を基にした、$[s^{0}G, s^{1}G, s^{2}G...s^{n}G]$を生成するセレモニーです。今回のセレモニーで生成された値は、EIP-4844だけでなく、どのKZG使用場面でも用いることができます。