Halo 2の中で使われている多項式コミットメントスキーム

Table of Contents

はじめに

この記事では、zk-SNARKのライブラリであるhalo2で使用される多項式コミットメントスキーム（Polynomial Commitment Scheme; PCS）について解説します([1]のAppendix 2)。
PCSは、名前の通り、多項式のコミットメント(特定の性質を持つ多項式を知っていたことを後で証明できるもの)を伝えるプロトコルです。
halo2の実際の実装と論文の相違点はドキュメント[3]に説明があります。

halo2のPCSとアキュムレーションスキーム

halo2のPCSは入力長の対数に比例するラウンド数でメッセージのやりとりを抑えるように構成されています。このプロトコルは、特殊な形式の内積アーギュメントを利用することで、「アキュムレータ $acc_i$ 」を用いる、Accumulation schemes[1]を実現しています。そして、halo2ではこのAccumulation schemesを利用することでSNARKが構成されています。

アキュムレータは、証明の対象の列 $q_1, q_2\cdots$ において、 $i$ までの対象が正しかったことを示すことができ、(i)その検証時間が通常の $q_i$ の検証よりも短い、(ii)証明のサイズが増加しない、という二つの性質を持っています。

アキュムレーションスキームは、以下の３つのアルゴリズムによって構成されています。

証明者:新しいインスタンスとそれまでのアキュムレータから、新しいアキュムレータを作成
検証者：新しいインスタンスとそれまでのアキュムレータ、証明者によって作成されたアキュムレータの整合性を検証
決定者：証明の最後でアキュムレータに蓄積された証明が正しいかどうかを判断

つまり、アキュムレータは「証明を次々と蓄積していき、それまでの証明が正しいことと、新しい証明が正しいことを一回の計算で検証できるような証明」と言えます。内積アーギュメントを利用したアキュムレーションスキームでは多項式コミットメントを作成します。アキュムレーションスキームのアルゴリズムはそれぞれ以下の様に動作します。

証明者：ランダムオラクルを用いて得たチャレンジを利用して、新しいインスタンスとそれまでのアキュムレータから新しい多項式コミットメントを作成することで新しいアキュムレータを作成
検証者：(i)内積アーギュメントの検証、(ii)ランダムオラクルを用いて生成されたチャレンジを利用した多項式コミットメントの整合性の検証、によって新しいインスタンスとそれまでのアキュムレータの整合性を検証
決定者：証明の最後で、アキュムレータのコミットメント内の多項式を評価点での値を調べることでアキュムレータに蓄積された証明が正しいかどうかを判断

内積アーギュメントを用いたアキュムレーションスキームは、コミットメント $C$ 、このコミットメント内の多項式 $p$ 、評価点 $z$ 、評価値 $v$ 、 $p(z) = v$ である事を示す証明 $\pi$ からなる証明対象のインスタンスと同じフォーマット $(C, z, v, \pi)$ を持ちます。このアキュムレーションスキームでは、離散対数問題に基づくPCSである、 $\text{PC}_{DL}$ を用いており、 $\text{PC}_{DL}$ を用いて多項式コミットメント $C$ が作成されます。

過去のアキュムレータと新たなインスタンスを $(C_1, z_1, v_1, \pi_1),(C_2, z_2, v_2, \pi_2)$ 、この証明 $\pi _1, \pi _2$ から復元された多項式を $h_1(X), h_2(X)$ ランダムオラクルを用いて作成されたチャレンジを $\alpha$ とします。すると、アキュムレーションスキームで作成される新たなアキュムレータでは、 $\pi _1, \pi _2$ から復元したコミットメントを $U_1, U_2$ とすると新たなコミットメントが $U_1+\alpha U_2$ 、対応する多項式が $h_1(X)+\alpha h_2(X)$ となり、ランダムオラクルから得た評価点 $z$ での値は $v = h_1(z)+\alpha h_2(z)$ となります。そして証明 $\pi$ は $p(z) = v$ を示す $\text{PC}_{DL}$ の $Open$ の操作の結果となり、これらを合わせた $(C, z, v, \pi)$ が新たなアキュムレータとなります。

さらにhalo2では、評価点での値が0になるような、ランダムに選択した多項式を用いることで（Openの2の操作）、 $\text{PC}_{DL}$ にhidingと呼ばれる性質を持たせ、SNARKのゼロ知識性を実現しています。

本稿ではこの $\text{PC}_{DL}$ の解説を試みます。

内積アーギュメント

以降、 $\mathbb{G}$ を位数 $p$ の巡回群（例えば有限体上の楕円曲線の有理点のなす群）とします。
本稿で解説するPCSで用いられる内積アーギュメントは、証明者と検証者が生成元のベクトル $G,H\in \mathbb{G}^n$ と生成元 $U\in \mathbb{G}$ を共有し証明者が予めコミットメントとして
$P = \Sigma _{i=0}^{n}a_i\cdot G_i +\Sigma _{i=0}^{n}b_i\cdot H_i + \braket{\vec{a},\vec{b}} \cdot U \;\;\;(1)$
を伝えておき、後でこれらの内積の値を証明者が検証者に $c = \braket{\vec{a},\vec{b}}$ として送ると、検証者が、「証明者が、コミットメントを作成した時点で、内積の値が $c$ となるベクトル $\vec{a},\vec{b}$ を知っていたこと」を検証できるような、対話型のプロトコルです。

メッセージのやりとりのラウンド数が入力長の対数で抑えられるようなこのような内積アーギュメントの例として、Bulletproofs[2]があります。
詳しくは[4]の解説を参照してください。

PCSの解説

$\text{PC}_{DL}$ の目標は以下を実現することです。

証明者が多項式 $p$ に対するコミットメント $C$ を検証者に伝えておく。
後で検証者が選択した評価点 $z$ に対して証明者が $v=p(z)$ を検証者に送り返すと、検証者がコミットメント $C$ を利用することで証明者が $C$ を作成した時点で多項式 $p$ を知っていたことが分かるが、多項式 $p$ 自体は知ることができない。

$\text{PC}_{DL}$ は

Setup（証明のフォーマットから、コミットメントの公開パラメータを作成）
Trim（コミットメントの公開パラメータの中から、コミットメントの作成に用いる鍵を選択）
Commit（多項式から、その多項式のコミットメントを作成）
Open（多項式に評価点を代入し、開示を行う）
Check（Openで得られた開示とCommitで得られたコミットメントを用いて、証明者が特定の多項式を知っていたことを検証）

の5つの手順から成ります。

Setup

証明者と検証者が共同で行う操作です。
群を選択する際に用いられるセキュリティーパラメータ $\lambda$ と多項式の最大の次数 $D$ を受け取って、公開パラメータとして

群 $\mathbb{G}$ 、その次数 $q$ 、その群を代表する生成元 $G$
多項式の係数と結合される生成元 $G_0,\cdots ,G_{D}$
多項式の係数を秘密にするための生成元 $S$
評価値と結合される生成元 $H$

を返します。

Trim

証明者と検証者が共同で行う操作です。
多項式の次数を表す $D$ 以下の値 $d$ を受け取り、Setupの結果の、多項式と結合される生成元 $G_0,\cdots G_{D}$ の中から $d+1$ 個を選び、改めて $G_0,\cdots G_{d}$ 。と置きます。

以降SetupとTrimの操作で得られた $(\mathbb{G}, q, G, (G_0,\cdots G_{d}), S, H)$ をコミットメントキーとします。

Commit

証明者が行う操作です。
コミットメントの対象となる多項式 $p$ 、乱数 $\omega$ を受け取り、 $p$ の係数を $\vec{c} = (c_0, \cdots c_d)$ としたとき（つまり $p(X) = \Sigma _{i=0}^{d}c_i X^i$ ）、内積アーギュメントのコミットメント(1)のうち、 $\Sigma _{i=0}^{n}a_i\cdot G_i$ の項で $a_i = c_i, G_i = G_i(i = 0, \cdots d)$ とおき、多項式の係数を秘密にするために乱数 $\omega$ と生成元 $S$ の積を加えた $C := \Sigma _{i=0}^{d}c_i\cdot G_i + \omega \cdot S$ をコミットメントとします。

Open

証明者が行う操作です。
多項式自体は秘密に保ったまま、検証者が選んだ評価点で多項式を評価したときの評価値を伝えることで、コミットメント作成時に、多項式を知っていたことを伝えます。

検証者が選んだ評価点 $z$ とCommitの結果、コミットを行ったときに用いた乱数 $\omega$ を用いて、以下の操作を行います。

多項式 $p$ に $z$ を代入した $v = p(z)$ を計算する。
多項式 $\overline{p}(z)=0$ を満たす多項式 $\overline{p}$ と、そのコミットメントに用いる乱数 $\overline{\omega}$ をランダムに選ぶ(多項式の係数を秘密にするための操作)
2.で選んだ $\overline{p}, \overline{\omega}$ にCommitを行い、その結果を $\overline{C}$ とする。
ランダムオラクル $\rho$ を用いてチャレンジ $\alpha = \rho _0 (\overline{C}, z, v, C)$ を作成
開示する多項式 $p':=p + \alpha \overline{p}$ を計算し、係数を $\Sigma _{i=0}^{d}c_i X^i$ とする(開示する多項式から元の多項式が分からない様にしている).
開示する多項式に対応するように乱数も計算し $\omega ':=\omega + \alpha \overline{\omega}$ とする。
証明者の不正(＊)を防ぐために、評価値と結合される生成元 $H$ を変更する。Checkのときとその値を一致させるため、 $p'$ のコミットメントから乱数に影響される項を取り除いた $C ':=C + \alpha \overline{C} - \omega ' S$ をランダムオラクルの入力に与えて得た0番目のチャレンジ $\xi _0 := \rho (C', z, v)$ を用いて $H'=\xi _0 H$ と変更する。
内積アーギュメントをFiat-Shamir変換によって対話型から非対話型に変換したプロトコルによって、 $\vec{L}, \vec{R}, U, c$ を作成する。
最終的な出力として手順9の結果に $\overline{C}, \omega '$ を加えた $(\vec{L}, \vec{R}, U, c,\overline{C}, \omega ' )$ を出力する。

この出力を用いて検証者は
$C + v\cdot H'= \Sigma _{i=0}^{d}c_i\cdot G_i + \omega \cdot S + p(z)\cdot H'\;\;\;(2)$
の検証によって、証明者がコミットメントの $C$ の作成時に $p(z) = v$ を満たすような多項式 $p$ を知っていたことを検証できます。

手順8の、内積アーギュメントをFiat-Shamir変換によって対話型から非対話型に変換したプロトコルによるコミットメントの作成は以下の手順で行われます。以下、ベクトル $\vec{a} = (a_1,\cdots a_n)$ の左半分を $l(\vec{a}) =(a_1,\cdots a_{n/2})$ 、右半分を $r(\vec{a})=(a_{n/2 + 1},\cdots a_{n})$ と表します。
まず $\vec{c}_0 := (c_0, \cdots, c_d), \vec{z}_0 := (1, z\cdots, z^d), \vec{G}_0 := (G_0, \cdots, G_d)$ と初期化したあと、 $i=1,\cdots \log (d+1)$ の順に以下の手順を繰り返します。

前の手順で作られたベクトルの半分 $l(\vec{G}_{i-1}), r(\vec{c}_{i-1}), l(\vec{z}_{i-1})$ を用いたコミットメントとして
$L_i := commit_{l(\vec{G}_{i-1})||H'}(r(\vec{c}_{i-1})||\braket{r(\vec{c}_{i-1}),l(\vec{z}_{i-1}))}) = \braket{l(\vec{G}_{i-1}), r(\vec{c}_{i-1})} + \braket{r(\vec{c}_{i-1}),l(\vec{z}_{i-1}))} H'$
を計算する。
1と同様に $r(\vec{G}_{i-1}), l(\vec{c}_{i-1}), r(\vec{z}_{i-1})$ を用いたコミットメントとして
$R_i := commit_{r(\vec{G}_{i-1})||H'}(l(\vec{c}_{i-1})||\braket{l(\vec{c}_{i-1}),r(\vec{z}_{i-1}))}) = \braket{r(\vec{G}_{i-1}), l(\vec{c}_{i-1})} + \braket{l(\vec{c}_{i-1}),r(\vec{z}_{i-1}))} H'$
を計算する。
ランダムオラクル $\rho_0$ を用いてチャレンジ $\xi _i := \rho _0 (\xi _{i-1}, L_{i}, R_{i})$ を作成
次のラウンドで用いるためのベクトル $\vec{G}_i := l(\vec{G}_{i-1}) + \xi _i\cdot r(\vec{G}_{i-1}), \vec{c}_i := l(\vec{c}_{i-1}) + \xi _i^{-1}\cdot r(\vec{c}_{i-1}), \vec{z}_i := l(\vec{z}_{i-1}) + \xi _i\cdot r(\vec{z}_{i-1})$ を作成

以上の手順によって、最終的に $U:=G_{\log (d+1)}, c:=c_{\log (d+1)}$ として $\vec{L}_{\log (d+1)}, \vec{R}_{\log (d+1)}, U, c$ を出力します。

ここで防いでいる証明者の不正

ここで、Openの7の操作(＊)で防いでいる、証明者の不正の例を挙げます。

悪意のある証明者が知っている多項式 $p(X) = \Sigma _{i=0}^{d}c_i X^i$ に対する本来のコミットメント $C = \Sigma _{i=0}^{d}c_i\cdot G_i + \omega \cdot S$ の代わりに公開されている生成元 $H$ と適当な値 $t$ を使った偽のコミットメント $\tilde{C} := \Sigma _{i=0}^{d}c_i\cdot G_i + t\cdot H + \omega \cdot S$ をコミットしたとします。7の操作を行なわず、生成元 $H$ を変更しなかった場合には、Openの操作で証明者が本来の値 $v = p(z)$ の代わりに $\tilde{v} = p(z)-t$ を送ることで
$\tilde{C} + \tilde{v}\cdot H = \Sigma _{i=0}^{d}c_i\cdot G_i + t\cdot H + \omega \cdot S + (p(z)-t)\cdot H=C+v\cdot H$ より、(2)が成り立つので、検証者が偽の証明を受理してしまいます。したがって悪意のある証明者の「 $v$ を代入すると値が $p(z)-t$ となるような多項式を知っていた」という偽の証明が成功します。

Check

検証者が行う操作です。
多項式の次数 $d$ 、証明者のコミットメント $C$ 、検証者が送った評価点 $z$ で証明者が多項式の評価を行なった値 $v$ 、Openの操作で作成したその証明 $(\vec{L}, \vec{R}, U, c,\overline{C}, \omega ' )$ を受け取り、以下のように非対話型の内積アーギュメントの検証を行います。
ここで、SetupとTrimの操作で得られたコミットメントキーは $(\mathbb{G}, q, G, (G_0,\cdots G_{d}), S, H)$ です。

多項式の次数 $d$ とコミットメントキーのベクトル $(G_0,\cdots G_{d})$ の長さが対応していること( $d = |(G_0,\cdots G_{d})| - 1$ であること)を確認する。
ランダムオラクル $\rho _0$ を用いてチャレンジ $\alpha = \rho _0 (\overline{C}, z, v, C)$ を復元する。(Openの手順4に対応)
同様に、 $p'$ のコミットメントから乱数に影響される項を取り除いた $C ':=C + \alpha \overline{C} - \omega ' S$ 、0番目のチャレンジ $\xi _0 := \rho (C', z, v)$ 、生成元 $H'=\xi _0 H$ を復元する。（Openの手順8に対応）
内積アーギュメントの検証を行う。C_0 := C + v\cdot H'と置き、i = 1, \cdots \log (d+1)に対して以下の操作を繰り返す。(Openの手順9に対応)
- チャレンジ $\xi _i := \rho _0 (\xi _{i-1}, L_{i}, R_{i})$ を作成する。
- コミットメント $C_i := \xi ^{-1}L_i + C_{i-1}+ \xi _i R_i$ を復元する。
多項式 $h(X) := \prod _{i=0} ^{\log (d+1) -1} (1+ \xi _{\log (d+1)-i} X^{2^i})$ を定義する。
評価点として $v' := c\cdot h(z)$ を計算し、5で得られた最後のコミットメント $C_{\log (d+1)}$ について、 $C_{\log (d+1)}=c\cdot U + v'\cdot H'$ が成り立つことを検証する。
多項式 $h(X)$ の $i$ 次の係数を $h_i$ とおくとき $U = \Sigma _{i=0}^d h_i\cdot G_i$ が成り立つことを検証する。

Checkの簡単な解説

Checkの手順5で定義した多項式 $h(X) := \prod _{i=0} ^{\log (d+1) -1} (1+ \xi _{\log (d+1)-i} X^{2^i})$ には「その係数ベクトルと $\vec{G}_0$ の内積が、 $\vec{G}_{\log (d+1)}$ と一致する」という性質を持ちます。

例えば、多項式 $p$ が3次式、 $d = 3, \log (d+1) =2$ の場合には、
$\vec{G}_0 = (G_1, G_2, G_3, G_4)$
とすると、
$\vec{G}_1 = (G_1, G_2)+\xi_1(G_3, G_4) = (G_1+\xi_1 G_3, G_2+\xi_1 G_4)$
$\vec{G}_2 = l(\vec{G}_1)+\xi_2r(\vec{G}_1) = G_1 + \xi_2G_2 + \xi_1G_3 + \xi_1\xi_2G_4$
となります。一方、このとき
$h(X) := \prod _{i=0} ^{1} (1+ \xi _{2-i} X^{2^i})$
$\;\;\;\;\;\;=(1+ \xi _{2} X)(1+ \xi _{1} X^{2})$
$\;\;\;\;\;\;=1+ \xi _{2} X+ \xi _{1} X^{2} + \xi _{1}\xi _{2} X^3$
となるので、係数ベクトルを
$\vec{h}=(1,\xi _{2},\xi _{1},\xi _{1}\xi _{2})$ とおくと $\vec{G}_2=\braket{\vec{h}, \vec{G}_0}$ が成り立ちます。

Checkの手順7ではこれを利用して、 $U = G_{\log (d+1)}$ が $\braket{\vec{h}, \vec{G}_0}=\Sigma _{i=0}^d h_i\cdot G_i$ と一致することを検証しています。

疑問点

halo2のPCSで使われている内積アーギュメントはBulletproofsとよく似た形ではありますが、厳密には異なっています。この形の内積アーギュメントがアーギュメントとして成立しているのかどうかまでは確認できていません。
対話型のプロトコルである、内積アーギュメントを非対話型に変換する際に、ランダムオラクルを用いたFlat-Shamir変換を行なっているようですが、この変換の正当性、安全性について理解していません。Flozen Heartと呼ばれる脆弱性とも関連しているようです。
このPCSは[5]で与えられている、PCSの特殊な場合となっているようです。[5]ではIPAを一般化した、Generalized Inner Product Argument (GIPA)を提唱し、GIPAをPCSへの応用しています。しかし、詳細は理解しきれていません。