Develop with pleasure!

福岡でCloudとかBlockchainとか。

IPAを利用した多項式コミットメントスキーム

Cryptography

Inner Product Argument（IPA）は、内積の関係を証明するプリミティブで、いくつかの証明システムに組み込まれて使用されている。IPAの解説については、GBEC動画 or 過去記事参照↓

goblockchain.network

techmedia-think.hatenablog.com

IPAは、多項式コミットメントスキームとしても機能するため、今回はそのプロトコルについて見ていく↓

blog.lambdaclass.com

IPAベースの多項式コミットメント

ここでは、n次の任意の多項式 {p(x) = a_0 + a_1x + a_2x^{2} + ... + a_{n}x^{n}}を想定する。

この多項式をx = zで評価した場合、つまりp(z)は、 {A = (a_0, ..., a_{n})}と {B = (1, z, z^{2}, ..., z^{n})}の内積値p(z) = <A, B>となる。

コミットメント方式のセットアップフェーズとして、可換群 {\mathbb G}が与えられ、以下を決める。

  • n個のベースポイント {G_0, G_1, ..., G_{n} \in \mathbb G}
  • ブラインドファクター用のベースポイント {H \in \mathbb H}

コミット

多項式のコミットメントは、ランダムな値r（ブラインドファクター）を選択し、以下を計算することで得られる。

{C = a_0G_0 + ... + a_{n}G_{n} + rH}

これは楕円曲線上の点で、証明者はこれを多項式p(x)のコミットメントとして検証者に送信する。

オープン

検証者がx = zの場合の評価値p(z)を知りたいのに対して、証明者はy = p(z)がその値であることを検証者に納得させる。yは2つのベクトル {A = (a_0, ..., a_{n})}と {B = (1, z, z^{2}, ..., z^{n})}の内積であるため、Inner Product Argumentを利用してこれを証明する。

証明者、 {A = (a_0, ..., a_{n})}と {B = (1, z, z^{2}, ..., z^{n})}および {G_0, G_1, ..., G_{n} \in \mathbb G}について、それぞれ前半部と後半部に分割し、それを {A_{lo}, A_{hi}, B_{lo}, B_{hi}, G_{lo}, G_{hi}}とする。

検証者は、ランダムな要素 {U \in \mathbb G}を選択し、証明者に送信。

証明者は、ランダムな要素s, s'を選択し、以下のベクトルを計算し、検証者に送信。

  • {L = \langle A_{lo}, G_{hi} \rangle + sH + \langle A_{lo}, B_{hi} \rangle U}
  • {R = \langle A_{hi},G_{lo} \rangle + s'H + \langle A_{hi}, B_{lo} \rangle U}

検証者はランダムな数値xを選択し、証明者に送信。

証明者は、

  • {A' = xA_{lo} + x^{-1}A_{hi}}
  • {B' = x^{-1}B_{lo} + xB_{hi}}
  • {G' = x^{-1}G_{lo} + xG_{hi}}

を計算し、これらを新しいAおよびB、Gとして各ベクトルの長さが2になるまで繰り返す。

証明者は、最終的に得られたA'、B'と、ブラインドファクターについて {r' = sx^{2} + r + s'x^{-2}}を計算し、検証者に送信する。

検証者は、

{x^{2}L + C + x^{-2}R + yU = x^{-1}A'G_0 + xA'G_1 + r'H + A'B'U}

が成立するか検証する。

元のコミットメント {C = a_0G_0 + ... + a_{n}G_{n} + rH}の各係数部分、つまり {A = (a_0, ..., a_{n})}と {G_0, G_1, ..., G_{n} \in \mathbb G}の内積は、IPAの折りたたみプロセスにより、検証式の {x^{-1}A'G_0 + xA'G_1}に含まれる。

実際に利用する際は、証明者と検証者間の対話はFiat-Shamir変換により非対話型で構成される。

というのが、IPAを多項式コミットメントとして使用する方法。冒頭の解説動画/記事の内容との違いは、多項式コミットメントの場合、コミットするのは多項式の各係数とブラインドファクターのみなので、Hのベースポイントはベクトルではなく1つだけ。多項式を評価する値zは、後で検証者から証明者に送られるため、検証者はBのベクトルについては既知になる。