多項式コミットメントスキーム Kate(KZG) commitment

コミットメントスキーム自体は、いろんなスキームがあり、さまざまなところで使われている（Confidential Transactionなどで登場するPedersen Commitmentや、ゼロ知識で範囲証明を提供するBulletproofsなど）。身近なところだと、ブロックチェーンでよく使用されるデータ構造の一種であるマークルツリーを使ったコミットメントなんかも。

例えば高さ４のマークルツリーには2⁴個の要素を持つが、これは各要素のリストをベクトルとし、マークルルートをそのベクトルとベクトルコミットメントとして扱うことができる。このコミットメントにある要素が含まれているかどうかは、4個のハッシュ（マークルプルーフ）を使って証明することができる。

Kate(KZG) commitmentは、KateおよびZaverucha、Goldbergによって発表された多項式コミットメントスキームで（↑のマークルツリーを使ったコミットメントはベクトルコミットメント）、最近、Ethereumで現状のマークルツリーベースのステートプルーフを、よりコンパクトにするために多項式コミットメントの導入が検討されてることもあって注目されてる。今回はこのKate commitmentの仕組みについて見ていく。

多項式の性質

次数nの多項式は、 ${p(x) = \sum_{i=0}^{n} p_{i} x^{i}}$ と表現できる。この多項式にコミットするのが多項式コミットメント。多項式コミットメントの説明に入る前に、多項式の性質について。

多項式p(x)において、p(z) = 0になるようなzを多項式の根と呼ぶ。
そして、p(x)を因数分解してp(x) = q(x)(x - z)となるようなq(x)が成立すると仮定し、そのq(x)の根が同じzである場合、zはp(x) = q'(x)(x - z)^kとなる重複度kを持つ。
多項式p(x)を二項一次多項式(x - z)で割った余りはp(z)となるという多項式の剰余の定理から、p(a) = yとなる場合、p(x) = q(x)(x - a) + p(a)が成立する。
多項式a(x)を多項式b(x)で除算すると、商q(x)と剰余r(x)は、a(x) = q(x)b(x) + r(x)と定義することができる。
n次の多項式は、多項式の代入値と結果のペア（x, y）がn + 1個あれば、ラグランジュ補完公式を使って多項式を復元することができる（シャミアの秘密分散などで使われてる）。

マークルツリーを使った多項式コミットメント

ちなみに、マークルツリーを使って多項式コミットメントを作るとどうなるか？ベクトルコミットメントの場合は、ベクトルの要素をリーフノードとして配置してマークルツリーを構成したけど、多項式コミットメントの場合は、n次の多項式であればリーフノードにn + 1個の各係数を配置すれば多項式にコミットしたことになる。

ただ、問題として証明者が多項式p(x)にコミットしていることを証明するためには、検証者に全ての係数を公開する必要がある。コミットメントのサイズ自体はマークルルートなので一定サイズだが、それを証明するプルーフのサイズは多項式の次数に比例する。

Kate commitment

Kate commitmentは、ペアリングが可能な楕円曲線を利用するコミットメントスキームで、多項式p(x)にコミットし、y = p(a)となるyとそれがコミットとした多項式にaを代入して得られた値であることを証明するプルーフを用いて多項式をデコミットする。特徴としては、コミットメントは１つの楕円曲線グループの要素で、プルーフも多項式の次数に関係なく１つの楕円曲線グループの要素となり、プルーフが一定サイズになる。

ペアリングが可能な楕円曲線

Kate commitmentは、ペアリングが可能な楕円曲線を必要とする。位数pの２つの楕円曲線を ${\mathbb G_1, \mathbb G_2}$ とし、 ${e: \mathbb G_1 ✕ \mathbb G_2 → \mathbb G_t}$ とする。そして、GとHをそれぞれ ${\mathbb G_1, \mathbb G_2}$ のジェネレーターとする。

ペアリングが可能ため、任意の ${P \in \mathbb G_1, Q \in \mathbb G_2}$ について、 $e(aP, bQ) = e(P, Q)^{ab}$ となる双線形性を持つ。

Trusted Setup

n次の多項式をコミットする場合、n + 1個*1のランダムシークレット（sとする）が必要になる。このランダムシークレットの値は誰にも知られない必要があるため、通常このTrusted SetupはMPCなどを用いて実行する必要がある。

ランダムシークレットsを使って、n + 1個の ${(s^{i}G, s^{i}H) (i = 0, ..., n)}$ を計算する。

コミットメントの作成

n次の多項式 ${p(x) = \sum_{i=0}^{n} p_{i} x^{i}}$ のコミットメントはTrusted Setupで生成した各要素を使って、

$C = \sum_{i=0}^{n} p_i s^{i}G$

を計算することで得られる。これは、Trusted Setupで生成した楕円曲線上の点を各次数にマッピングし、各次数の点に多項式の係数（ ${p_i}$ ）を乗算（つまり楕円曲線のスカラー倍算）し、それらを合算（楕円曲線の点と点の加算）したものである。つまりコミットメントCも楕円曲線上の点で、サイズは固定だ。