Develop with pleasure!

福岡でCloudとかBlockchainとか。

KZGコミットメントを計算して理解する

Cryptography kzg

以前ペアリングが可能な楕円曲線を利用するコミットメントスキームであるKZGコミットメントについて書いた↓

techmedia-think.hatenablog.com

楕円曲線を利用したコミットメントスキームとしては、Pedersenコミットメントが有名だが、Pedersenコミットメントではコミットした値を開示する際、すべてのコミット値を開示する必要がある。それに対し、KZGコミットメントでは、コミットした値を部分的に開示することができる。↑の記事では簡単にしか書いてなかったので、今回はこの仕組みを実際に計算しながら理解していこう。

今回は4つの値をベクトルX = (135, 91, 81, 9)にコミットするケースを考える。

Trusted Setup

KZGコミットメントでは、Trusted Setupにより秘密の値（シークレットパラメーター）sを生成し、そこから {s^{i}G}および {s^{i}H}を計算し、これらの値を共有する。そしてsを廃棄する。sは誰にも知られていてはならない。※G、Hなどの記述は↑の前回の記事内容を使用。

とりあえず、説明を簡単にするためs = 2で進める。※ ほんとはもっと巨大な数値。

今回4つの値にコミットするので、 {G, 2G, 4G, 8G}、 {H, 2H, 4H, 8H}がセットアップパラメータとなる。

※ KZGコミットメントではこのTrusted Setupが発生する。このためかEthereumのVerkle Treeの実装では結局Pedersenコミットメントを採用するみたい。

コミットメントの作成

セットアップパラメータが決まったら、値をコミットする。KZGコミットメントでは、コミットするベクトル値から多項式p(x)を作る。この多項式は、ベクトルに含まれるすべての値 {x_i}に対して、 {p(i) = x_i}となるような多項式。

4つの値にコミットするので、今回は3次の多項式 {p(x) = p_0 + p_1 x + p_2 x^{2} + p_3 x^{3}}を作ることになる。そして、ベクトルの値から、p(0) = 135, p(1) = 91, p(2) = 81, p(3) = 9を満たす多項式になる。こういった多項式はラグランジュ補完を使って求めることができる。今回のケースだと、多項式は↓

{p(x) = 135 - 45x - 7x^{2} + 8x^{3}}

となる。この多項式の各項の係数を {p_i}とすると、多項式は以下のように表現できる。

{\displaystyle p(x) = \sum_{i=0}^{n-1} p_i x^{i}}

そして、この係数と↑のセットアップパラメータ {G, 2G, 4G, 8G}を使ってコミットメントを計算する↓

{\displaystyle C = \sum_{i=0}^{n-1}p_i s^{i}G}

↑の例で展開すると、

{C = 135G - 45(2G) - 7(4G) + 8(8G)}

これはセットアップパラメータ {G, 2G, 4G, 8G}と多項式の係数 {p_i}の内積であることが分かる。つまり、コミットメントCは {p(s)\cdot G}と等しい。

コミットメントの作成フェーズでは、コミットするベクトルを多項式に変換し、その多項式をセットアップパラメータを使って楕円曲線上の点にエンコードしている。なので、コミットする値が増えても、コミットメントのサイズは一定のまま。

プルーフの作成

↑でベクトルX = (135, 91, 81, 9)についてのコミットメントCを作ったので、続いて、コミットした値を開示しよう。KZGコミットメントの場合、ベクトルXのすべての要素を開示する必要はなく、部分的に開示ができる。つまりX内の任意の {x_i}について開示が可能。

Xの内、 {y = x_i}を開示する。ここでは、 {y = x_2 = 81}とする。ベクトルはコミットメントにより多項式に変換されているので、3番目のコミット値が81であることは、 {p(2) = 81}（つまり、 {p(2) - 81 = 0}）であることを証明すればいい。

ここで、新たに多項式q(x)を次のように定義する。

{\displaystyle q(x) = \frac{p(x) - y}{x - i}}

これは以下の多項式の性質を利用したもの：

  • 多項式の剰余の定理：多項式 {p(x)}を二項一次多項式 {(x - i)}で割った場合、余りが {p(i)}となるという定理。
  • 多項式 {a(x)}を多項式 {b(x)}で除算した場合の商を {q(x)}、余りを {r(x)}とした場合、 {a(x) = q(x)b(x) + r(x)}と定義できる。

↑により {y = p(x_i)}について、 {p(x) = q(x)(x - i) + y}が成立し、これを変形したものが↑

今回のケースだと、 {y = x_2 = 81}なので、 {q(x) = \frac{p(x) - 81}{x - 2}}。

これらから、上記のような {q(x)}が存在する場合、 {p(x) - y}は {x - i}で割り切れる。ということは、因数定理（多項式 {p(x)}が {(x - i)}で割り切れる場合、 {p(i) = 0}が成立する）から、 {p(i) - y = 0}、つまり {p(2) - 81 = 0}となる。

KZGプルーフは、このような {q(x)}が存在し、この特性を証明するためのもの。

2022.06.30：q(x)の係数の誤りを指摘して頂いたので以下のq(x)の係数および次数を修正しました。

証明者は、多項式q(x)の各係数 {q_i}を計算する。この場合、q(x)の各係数は、 {(q_0 = -27, q_1 = 9, q_2 = 8)}。

そして、この係数とセットアップパラメーターを使って以下のKZGプルーフを計算する。

{\displaystyle \pi = \sum_{i=0}^{n-1}q_is^{i}G}

今回のケースだと

{\displaystyle \pi = -27(2^{0}G) + 9(2^{1}G) + 8(2^{2}G) }

これは、 {\pi = (-27(2^{0}) + 9 (2^{1}) + 8(2^{2}))G}であることから、

{\pi = q(s)\cdot G}であることが分かる。

コミットメントCが {p(s)\cdot G}、プルーフ {\pi}が {q(s)\cdot G}という構成になっていることが分かる。2つとも未知のシークレットパラメータで評価された、異なる多項式。

検証

証明者は、y = p(2) = 81と上記のプルーフを一緒に検証者に渡す。検証者は、以下のペアリングの等価性について検証する。

{e(\pi, sH - iH) = e(C - yG, H)}

つまり、

{e(\pi, sH - 2H) = e(C - 81G, H)}

ここで、sHはセットアップパラメータの１つで定数、iHはHとiから計算できる。

↑の式は、 {\pi = q(s)G, C = p(s)G}であることから、以下のように変形できる。

{e(q(s)G, (s - i)H) = e((p(s) - y)G, H)}

{e(G, H)^{q(s)\cdot (s - i)} = e(G, H)^{p(s) - y}}

{q(s)\cdot (s - i) = p(s) - y}

の検証になる、つまり、ここで検証しているのは↑で説明したq(x)の存在とそれが満たす特性。

検証者は両多項式の各係数 {p_i, q_i}について知らなくても、この特性を確認することができる。この特性が確認できたということは、 {p(i) = y}つまり、 {p(2) = 81}（３つめのコミット値は81）であることが検証されたことになる。

というのがKZGコミットメントで計算している内容。

ペアリング使うのは最後の検証部分のみ。最初ぱっと見た時は、Trusted Setupで生成するパラメータは、NUMSポイントとかを決定論的に生成して代替できないのか？とか思ったけど、↑のような多項式の性質使う上では {s^{i}}で構成されないと無理 よね。