Develop with pleasure!

福岡でCloudとかBlockchainとか。

KZGコミットメントのマルチプルーフ

Cryptography kzg

多項式コミットメントスキームの１つであるKZGコミットメントの仕組みについて調べた↓

techmedia-think.hatenablog.com

↑では、ベクトルを多項式 {p(x)}に変換することでベクトルにコミットし、その多項式での評価値と単一の楕円曲線のグループ要素をプルーフとして提供することで、コミットしたベクトルの一部をデコミットしていた。

マルチプルーフ

今回は、マルチプルーフと呼ばれる複数の値をデコミットする際のプルーフの作成、検証の仕組みについて見ていこう。KZGコミットメントの場合、多項式補間を使ってマルチプルーフを構成する。

k個の評価値のリストを {(x_0, y_0), (x_1, y_1), ..., (x_{k-1}, y_{k-1})}とすると、これらの値を使って、ラグランジュ補間によりk-1次の補間多項式を算出することができる。

{i(x) = a_0 + a_1x + a_2x^{2} + ... + a_{k-1}x^{k-1}}

元々のコミットされた多項式 {p(x)}も、当然これらすべての点（ {(x_i, y_i)}）を通り、 {p(x) - i(x)}は各 {x_0, x_1, ..., x_{k-1}}においてゼロになる。これは、 {(x - x_0), (x - x_1), ..., (x - x_{k-1})}で割り切れることを意味する。

これらの関係から、単一のプルーフを作成する際に用いた

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

は、マルチプルーフにおいては、 {z(x) = (x - x_0) \cdot (x - x_1)\cdot \cdot \cdot (x - x_{k-1}) = \Pi_{i=0}^{k-1}(x - x_i)}とした場合、以下のように定義できると。

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

そして、マルチプルーフは、この {q(x)}に対して、単一のプルーフと同様に

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

を計算して算出する。つまり、マルチプルーフは単一のプルーフと同様、楕円曲線の単一のグループ要素になる。

検証

マルチプルーフ {\pi}と評価値のリスト {(x_0, y_0), (x_1, y_1), ..., (x_{k-1}, y_{k-1})}が与えられた検証者は、まず評価値のリストを使って補間多項式 {i(x)}と、 {z(x)}を計算する。

単一のプルーフにおいては、以下のペアリングの等価性を検証していたが、

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

マルチプルーフでは、以下のペアリングの等価性を検証するようになる。

{e(\pi, z(s)H) = e(C - i(s)G, H)}

この結果、マルチプルーフの場合、プルーフのサイズは単一のプルーフと変わらずO(1)で、検証コストは評価値のリスト分O(k)に増える。

参考