初代zcashで使われたzkSNARKsで登場する二次スパンプログラム(QSP)とは？

Table of Contents

はじめに

この記事では初代zcashのzkSNARKsであるPinocchio/Groth16プロトコル[6]の基礎になっている二次スパンプログラム(Quadratic Span Program; QSP)について定義を確認し、QSPからzkSNARKsをどのように構成するかを解説します。
zkSNARKSでは任意のステートメントの真偽を検証者による簡潔な計算により判定できる必要があります。その構成ブロックであるQSPが実際にはどのようなものなのかを説明します。

なお実際に回路化されたステートメントを使う際に使用されることが多いQAP(Quadratic Arithmetic Program)も同論文で解説されていますが、QAPは加算と乗算の組み合わせで表現できる回路化されたステートメントをQSPと同じように書き下したものと言えます。回路化されたステートメントを多項式や制約という条件に書き下す必要があると聞いたことがあるかもしれませんが（いわゆるR1CSとか呼ばれているものです）、こちらはQAPのことを指しています。
実際のユースケースではブール関数を証明したいことよりも算術回路を証明したいことの方が多いため、QAPを使うことが多いです。
QSPとQAPの違いについては[4]のコメントも参照してください。

用語

スパンプログラム( Span Programs; SP)

バイナリ関数 $F: \{0,1\}^n \rightarrow \{0,1\}$ を表現する手法。
[2] に定義と例が載っている。

文字列 $w \in \{0,1\}^N$ を入力とするスパンプログラムPは以下をパラメータとして持つ。

任意の数の実数値の基底ベクトル( $\in R^d$ )がパラメータとして存在する。
それらの基底ベクトルは以下の2N個のグループに分割されている。
- グループ「 $w_1 = 0$ 」
- グループ「 $w_1 = 1$ 」
- グループ「 $w_2 = 0$ 」
- グループ「 $w_2 = 1$ 」
  ︙
- グループ「 $w_N = 0$ 」
- グループ「 $w_N = 1$ 」
また目的ベクトル $\tau \in R^d$ がパラメータとして存在する。

Pは以下のように計算を行う。
まず、入力 $w$ に基づいてパラメータのグループを $\text{Avail}$ グループと $\text{Unavail}$ グループに分割する。
$i=1...N$ に対して:
もしも $w_i = 0$ ならば、グループ「 $w_i = 0$ 」と名付けられたものを $\text{Avail}$ グループに移動し、グループ「 $w_i = 1$ 」と名付けられたものを $\text{Unavail}$ グループに移動する。
逆にもしも $w_i = 1$ ならば、グループ「 $w_i = 0$ 」と名付けられたものを $\text{Unavail}$ グループに移動し、グループ「 $w_i = 1$ 」と名付けられたものを $\text{Avail}$ グループに移動する。

その後、目的ベクトル $\tau$ が $\text{Avail}$ グループの中にある基底ベクトルの線型結合で表現されるかどうかを調べ、表現される場合には $P(w) = 1$ をPの計算結果とする。表現されない場合は $P(w) = 0$ を計算結果とする。

すべてのバイナリ入力 $w$ に対して $F(w) = P(w)$ であるとき「PはFを計算する」という。

2次スパンプログラム (Quadratic Span Programs ; QSP)

SPでターゲットベクトルtは数値ベクトルtだったが、これを多項式t(x)に変えたもの。SPではtを張る特定の基底ベクトルが存在するかどうかによって $F$ の出力が変わったが、QSPではターゲットベクトルt(x)によって割り切れる多項式を線型結合（同士の積）で作れるかどうかによって $F$ の出力が変わる。

定義

体 $F$ 上の2次スパンプログラム $Q$ は $V = \{v_k(x): k \in \{0,...,m\}\}, W = \{w_k(x): k \in \{0,...,m\}\}$ という二つの多項式の集合と目的多項式(target polynomial) $t(x)$ を持つ。多項式は全て $F[x]$ に属する。 $Q$ はまた添字 $I = \{1,...,m\}$ の分割として $I = I_{\text{labeled}} \bigcup I_{\text{free}}$ を定義の中に持っており、さらに $I_{\text{labeled}} = \bigcup_{i\in [n], j\in \{0,1\}} I_{i,j}$ のように分割できるものとする。
関数 $f: \{0,1\}^n \rightarrow \{0,1\}$ とその入力 $u \in \{0,1\}^n$ に対して、 $I_u = I_{\text{free}} \bigcup_i I_{i, u_i}$ を「uに属する」添字の集合とする。 $Q$ は入力uを以下の条件の時、かつその時のみに限り受理する。

$k \notin I_u$ に対して $a_k = b_k = 0$ を満たす $(a_1, ..., a_m), (b_1, ..., b_m) \in F^m$ が存在し、 $t(x)$ が $(v_0(x) + \sum_{k=1}^{m} a_k \cdot v_k(x)) \cdot (w_0(x) + \sum_{k=1}^{m} b_k \cdot w_k(x))$ を割り切る。

f(u)=1を満たすようなuのみを受理するとき $Q$ はブール関数fを「計算する」と定義する。

例

$n = 2, t(x) = x(x^2+ 1)$ とする。集合 $\mathcal{V} = \{v_0(x) = 1, v_1(x) = x, v_2(x) = x^2\}, \mathcal{W} = \{w_0(x) = x+1, w_1(x) = x+2, w_1(x) =x+3 \}$ を定める。以下の表に従って、入力 $u$ の各ビットが使用できる要素のタプルを決める。

$u_1 = 0: (\phi, \{x+2, x+3\}) \subseteq (\mathcal{V}, \mathcal{W} )$
$u_1 = 1: (\{x\}, \phi) \subseteq (\mathcal{V}, \mathcal{W} )$
$u_2 = 0: (\{x^2\}, \phi) \subseteq (\mathcal{V}, \mathcal{W} )$
$u_2 = 1: (\phi, \{x+3\}) \subseteq (\mathcal{V}, \mathcal{W} )$

従って $F(0,0)$ では適当な $(a,b,c)$ に対して $(1 + ax^2)((x+1)+b(x+2)+c(x+3))$ を $t(x) = x(x^2+ 1)$ が割り切れるかどうかを調べると、割り切ることができるので $F(0,0) = 1$ となる。
同様に $F(1,1)$ では適当な $(a,b)$ に対して $(1 + ax)((x+1)+b(x+3))$ を $t(x) = x(x^2+ 1)$ が割り切れるかどうかを調べると、割り切ることができないので $F(1,1) = 0$ となる。

カノニカルQSP

[1]の論文の2章では任意の回路をQSPに変換する方法が説明されている。
また、QSPそのままだと証明者によって不正ができる可能性があるので、カノニカルQSPというその穴を潰した手法についても書かれている。

QSPからSNARKを実現する方法

QSPがある関数fを計算可能な時、fの出力が1になる時、かつその時のみに限り必ず $(a_1, ..., a_m), (b_1, ..., b_m)$ が存在して、それらから構成される多項式v(x), w(x), h(x)と所与のt(x)に対して $v(x)\cdot w(x) = h(x)\cdot t(x)$ が成立するようにできる。
これはすなわち、ある計算結果が正しいことを証明したい関数をfとおき、その関数の出力が1になる入力を知っていることを示したい時には、 $v(x)\cdot w(x) = h(x)\cdot t(x)$ を満たす $(a_1, ..., a_m), (b_1, ..., b_m)$ を知っていることを、 $(a_1, ..., a_m), (b_1, ..., b_m)$ の値を隠したまま証明できればよいということになる。

以下その方法を大まかに説明する。

まず、証明者は位数の十分大きな有限巡回群の生成元 $g$ を用いて、 $g^{v(x)}, g^{w(x)}, g^{h(x)}, g^{t(x)}$ を証明として検証者に渡す。これを受け取った検証者から見て証明の長さは定数であり、 $v(x), w(x), h(x), t(x)$ の値は隠されていることになる。

ここで検証者はt(x) を共有していることに注意。また、検証者は v(x), w(x) の値は知らないが、v(x), w(x)があらかじめ決められたV, Wの多項式の線型結合で表現できることを（他の乱数を使った何らかの方法で）確認できなければならない。

検証者は $v(x)\cdot w(x) = h(x)\cdot t(x)$ が成立することを検証できれば良い。
通常の群を使った計算だけではこの証明は難しいが、ツールとして双線型写像を使うことで上の式が成立することを確かめることができる。

[5]の定義の双線型写像 $e(\cdot, \cdot)$ を考える。

双線形写像では $e({P_1}^n,Q_1) = e(P_1,Q_1)^n, e(P_1,{Q_1}^n) = e(P_1,Q_1)^n$ の性質が成り立つ。
したがって $e(g^{v(x)}, g^{w(x)}) = e(g,g)^{v(x)w(x)}$ かつ $e( g^{h(x)}, g^{t(x)}) = e(g,g)^{h(x)t(x)}$ である。
よって、 $e(g^{v(x)}, g^{w(x)}) =e( g^{h(x)}, g^{t(x)})$ が成り立つならば $v(x)\cdot w(x) = h(x)\cdot t(x)$ も成り立つことがわかり、結果として入力 $g^{v(x)}, g^{w(x)}, g^{h(x)}, g^{t(x)}$ のみを使い両辺が一致することを確認できる。
なお、このとき実際に多項式を評価するためにxに代入する値sがzcashなどで用いられるトラステッドセットアップの秘密パラメータとなり、 $g^s, g^{s^2}, ...$ などが公開パラメータとなる。実際の $g^{v(s)}$ などは公開パラメータの線型結合で表現される。

考察

zcashで使われているPinocchioベースのzkSNARKsは既知のツールとして利用されていることが多いですが、実際に任意の計算回路と楕円曲線を効率的に結びつける具体的な構成法が何なのかというのは意外と知られていないように思います。
実際にQSPを使う場合双線形写像が必要であり、[3]に書いてある通り標準的な暗号学の仮定とは異なる仮定も必要になることがわかります。
ツールの名前を読んだだけだと暗号学的仮定を詳細に知ることができないため、勉強になってよかったです。