Develop with pleasure!

福岡でCloudとかBlockchainとか。

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)}が存在し、この特性を証明するためのもの。

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

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

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

今回のケースだと

 {\displaystyle \pi = -27(2^{0}G) - 10(2^{1}G) + 0(2^{2}G) - 72(2^{3}G)}

これは、 {\pi = (-27(2^{0}) - 10(2^{1}) + 0(2^{2}) - 72(2^{3}))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はセットアップパラメータの1つで定数、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}(3つめのコミット値は81)であることが検証されたことになる。

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

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