zk-SNARKs をたずねて三千里第 2 回

はじめに

ご無沙汰しています。ようやく一番古いタイプの zk-SNARK を実装することが出来たので、ブログ第 2 弾という形で、その過程と詳細を書いていこうと思います。

注意

動くものは出来ましたが、そこに至るまでの考えかたについては、間違いがいろいろと含まれている可能性があります。記事の内容をあまり信用しないようにしてください。Please don't trust. Verify.

その後

前回のブログを書いた後、QAPの先の部分の理解に必要そうな数学をある程度理解しようと、こんな順番で本を読んだり、動画を見たりしていました。

1. Pairings for Beginners

次はペアリングかなと思ったので、読んでみたんですが、全く理解できませんでしたw

2. A Book of Abstract Algebra / Charles C. Pinter

基本が欠けているんだなと思い、Abstract Algabra の本を読んで見たんですが、具体的なイメージが湧かず、あまり理解した気になれませんでした。

3. Ring Theory / Elliot Nicolson

動画の方がイメージが湧いていいのかなと思い、Youtube で検索していたら、この動画シリーズを見つけました。ChatGPT 4 に相談しながら全て視聴したところ、Abstract Algebra の基本的な部分は、なんとか理解することが出来ました。

4. Pairing for Beginners (再挑戦)

今度はいけるかなともう一度読んでみたのですが、やはり分からず、よく調べてみたところ、Algebraic Algebra に加えて Algebraic Geometry という分野の数学の理解が必要だということがわかりました。

5. Algebraic Curves / William Fulton

というわけで、Algebraic Geometry の一番簡単だと言われている本を読んでみました。しかし、中々先に進まず、早い段階でギブアップしました。

方針転換

数学的なバックグラウンドを理解した上で実装するのは無理筋だと分かったので、わからない部分はブラックボックスとして考えて実装をすることにしました。

実装開始

どの zk-SNARK をどう実装しようか考えたのですが、

橢円曲線は、情報が豊富な BLS12-381
プロトコルは、一番古くてシンプルな Pinocchio

が現実的だと思ったので、この形で進めることにしました。

BLS12-381

まず、プロトコルの土台となる BLS12-381 です。

BLS12-381 には $\mathbb{F}_{q}$, $\mathbb{F}_{q^2}$, $\mathbb{F}_{q^{12}}$ という 3 つのフィールドが使われています。

$q$ は0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab という 381 ビットの素数です。

3 つのフィールドのうち、$\mathbb{F}_{q}$ は素数のフィールドで、$\mathbb{F}_{q^2}$ と $\mathbb{F}_{q^{12}}$ は、$\mathbb{F}_q$ を拡張した extension field ということでした。

Extension field

Extension field は、ベースとなるフィールドに元を追加して拡張したものです。$n$ 次の extension field は、以下のように作ります。

まず、係数がベースフィールドの元で、次数が $n$ の generator 多項式を用意します。この多項式は $n$ 次未満の項の積で表せないようなものである必要があります。

Generator 多項式のルートの中には、0 を除いた extension field の元を全てを $\alpha^k$ $k=0..n$ の形で表わせるような元 $\alpha$ が存在していて、これを primitive 元と呼びます。

$n$ 次の generator 多項式を $g(x)$ とすると、$g(x)$ の primitive 元 $\alpha$ は、$g(x)$ のルートなので、$g(\alpha) = 0$ になります。

そこで、$g(\alpha) = 0$ の $n$ 次の元を左辺に残して、$n$ 次未満の項を全て右辺に移項すると、還元式 $\alpha^n = \cdots$ になります。

例えば、ベースフィールドが $\mathbb{F}_{5}$ で、$x^2 + 1$ が $\mathbb{F}_{5^2}$ の generator 多項式なら、$\alpha^2 + 1 = 0$ で、$\alpha^2 = -1 = 4$ が還元式というような感じです。

Primitive 元と還元式を使うと、extension field の元を全て定義できます。

例として、$\mathbb{F}_{5^2}$ の元を還元式 $\alpha^2 = 4$ を使って作ってみます。

$\alpha^0 = 1$
$\alpha^1$

$\alpha^2$ で、元の次数 $2$ が、extension field の次数 $2$ に到達するので、還元式 $\alpha^2 = 4$ を使って次数を下げます。

$\alpha^2 = 4$
$\alpha^3 = \alpha^2 \cdot \alpha = 4 \alpha$
$\alpha^4 = \alpha^2 \cdot \alpha^2 = 4 \cdot 4 = 16$

このように続けていくと、$\alpha^{24} = 1$ になって $\alpha^0$ に戻ります。

$\alpha^0$ から $\alpha^{23}$ までの元に、加法単位元 $0$ を足したものが、$\mathbb{F}_{5^2}$ の全ての元になります。

BLS12-381 の extension field

BLS12-381 の extension field は、ベースフィールド $\mathbb{F}_q$ を徐々に拡張して作ります。

まず、$\mathbb{F}_{q}$ から $\mathbb{F}_{q^{2}}$
次に、$\mathbb{F}_{q^{2}}$ から $\mathbb{F}_{{(q^{2})}^{3}}=\mathbb{F}_{q^{6}}$
最後に、$\mathbb{F}_{q^{6}}$ から $\mathbb{F}_{{(q^{6})}^{2}}$ $=\mathbb{F}_{q^{12}}$

といった感じです。

それぞれのフィールドの構造は以下の様になっています。

$\mathbb{F}_{q^{2}}$

generator 多項式は $ax^2 + bx + c$ の形式で、$a,b,c \in \mathbb{F}_{q}$
$\mathbb{F}_{q^2}$ の元は $ax + b$ の形式で、$a,b \in \mathbb{F}_{q}$

$\mathbb{F}_{(q^{2})^{3}}=\mathbb{F}_{q^{6}}$

generator 多項式は $ax^3 + bx^2 + cx + d$ の形式で、$a,b,c, d \in \mathbb{F}_{q^2}$
$\mathbb{F}_{q^6}$ の元は $ax^2 + bx + c$ の形式で、$a,b,c \in \mathbb{F}_{q^2}$

$\mathbb{F}_{(q^{6})^{2}}=\mathbb{F}_{q^{12}}$

generator 多項式は $ax^2 + bx + c$ の形式で、$a,b,c \in \mathbb{F}_{q^6}$
$\mathbb{F}_{q^{12}}$ の元は $ax + b$ の形式で、$a,b \in \mathbb{F}_{q^6}$

$\mathbb{F}_{q^6}$ について

今回参考にした Haskell 実装では $\mathbb{F}_{q^6}$ が使われていて、自分の実装でも $\mathbb{F}_{q^6}$ を使って extension field を構築したので、$\mathbb{F}_{q^6}$ をここに含めました。

$\mathbb{F}_{q^6}$ 上で計算をすることはなく、$\mathbb{F}_{q^6}$ は、$\mathbb{F}_{q^{12}}$ への橋渡しとして存在しています。

BLS12-381 for the rest of us には $\mathbb{F}_{q^6}$ は出てきません。

Embedding degree

$\mathbb{F}_{q}$ 上で定義した BLS12-381 の橢円曲線の embedding degree は 12 です。

Cryptographic Pairings の 4ページに、embedding degree についての詳しい説明があります。

Let $r$ be a prime with $r | n$, and let $k$ be the embedding degree of $E$ with respect to $r$, i.e. $k$ is the smallest positive integer with $r | q^{k} - 1$. This means that the multiplicative group $\mathbb{F}^{*}_{q^{k}}$ contains as a subgroup the group $\mu_r$ of $r$-th roots of unity. The embedding degree $k$ is an important parameter, since it determines the field extensions over which the groups that are involved in pairing computation are defined.

$\mathbb{F}_q$ を $\mathbb{F}_{q^{k}}$ まで拡張すると、拡張したフィールドを multiplicative group $\mathbb{F}_{q^{k}}^{*}$ として見た場合に、その group の中に r-th root of unity で構成された group $\mu_{r}$ が含まれるということです。また、他の部分で、

$\mu_{r}$ は、位数 $r$ の multiplicative group
$q$ は素数
$E$ は $y^2 = x^3 + ax + b$ の式で、$\mathbb{F}_{q}$ が係数になる形で定義される楕円曲線
$n$ は、$\mathbb{F}_{q}$ の algebraic closure 上で定義した $E$ の式が成り立つ $x, y$ の組み合わせの数に、1つの無限遠点を足した数
$\mathbb{F}_{q}$ の algebraic closure とは、$\mathbb{F}_{q}$ を含んだ、$\mathbb{F}_{q}$ を係数に使って定義できる式の解になる元を全て含んだもの

と説明されています。

BLS12-381 では、位数 $r$ の乗法グループを含むフィールド作るために、$\mathbb{F}_q$ を $\mathbb{F}_{q^{12}}$ まで拡張しています。

$\mathbb{F}_{q^{k}}$ に group $\mu_{r}$ が含まれる理由

$\mathbb{F}_{q^{k}}$ に group $\mu_{r}$ が含まれる理由について調べて見たところ、以下の事がわかりました。

$\mathbb{F}_{q^{k}}$ は、逆元のない加法単位元を省くと multiplicative group $\mathbb{F}^{*}_{q^{k}}$ として見ることが出来る。位数は $q^{k}-1$
ラグランジュの定理の系によれば、$r$ が $q^{k} - 1$ を割り切るなら、$\mathbb{F}^*_{q^{k}}$ には位数が $r$ の元が含まれる
位数 $r$ の元は、$r$ 乗すると乗法単位元 $1$ になる元なので r-th root of unity で、$x^r=1$ が成り立つ $x$
$x^r = 1$ を $x^r - 1 = 0$ と変形してみると、この式の解は Fundamental theorem of algebra によると、重複を含めて $r$ 個存在する。
Finite field で考えた場合には、重複は存在せず、distinct な解が $r$ 存在する

3 つの橢円曲線上のグループ

$\mathbb{F}_{q}$ と $\mathbb{F}_{q^{2}}$ 上の位数 $r$ の加法グループ $G_1, G_2$ と、$\mathbb{F}_{q^{12}}$ の上の位数 $r$ の乗法グループ $G_T$ を以下の様に定義します。

$G_{1}$

橢円曲線の式 $y^2 = x^3 + 4$ が成り立つ $\mathbb{F}_{q}$ の元 $x,y$ の組み合わせで構成される加法グループを $G_1$ とします。

ジェネレーターについては実装を参照してください。

$G_{2}$

BLS12-381 for the rest of us で、こう説明されているように

if we keep extending the field over which $E$ is defined, it can be proved that we eventually find a curve that has more than one subgroup of order $r$ (in fact, $r+1$ of them). That is, for some $k$, $E(F_{q^{k}})$ contains other subgroups of order $r$ that we can use.

$\mathbb{F}_{q^{12}}$ には、位数 $r$ の加法グループが含まれているので、このグループを $G_2$ として使うことも出来るのですが、このグループは楕円曲線の式の係数が 11 次までの多項式になるため、演算に時間がかかるという問題があります。

そこで、sextic twist を使い、$\mathbb{F}_{q^{12}}$ 上の加法グループを、$\mathbb{F}_{q^{2}}$ 上にマップします。

こうすると、楕円曲線の式の係数が 1 次までの多項式となり、計算の複雑度が大きく下がります。
この $\mathbb{F}_{q^{2}}$ 上の加法グループを $G_2$ とします。

具体的には、$G_2$ は橢円曲線の式 $y^2 = x^3 + 4(u + 1)$ が成り立つ、$\mathbb{F}_{q^{2}}$ の元 $x,y$ の組み合わせで構成される加法グループです。$u$ は $u^2 + 1 = 0$ となるような $u$ になります。

ジェネレーターについては実装を参照してください。

$G_{T}$

$\mathbb{F}_{q^{12}}$ 上の乗法グループを $G_T$ とします。

ペアリング

次に $G_1, G_2, G_T$ を使ってペアリングを実装します。

ペアリングを使うと、$G_1$ 上の元と $G_2$ 上の元を掛け合わせた結果を、 $G_T$ に出力することが出来ます。

ペアリングは、Miller's algorithm を使って構築します。

Miller's algorithm

Miller's algorithm については、Ben Lynn のページに、以下の解説があります。

Consider $E[l]$, the $l$-torsion points of an elliptic curve $E$. Write $f_P$ for the rational function with divisor $l(P)-l(O)$.

Let $g_{P,Q}$ be the line between the points $P$ and $Q$, and let $f_c$ be the function with divisor $(f_c) = c(P) - (cP) - (c-1)(O)$. Then for all $a,b \in \mathbb{Z}$, we have $ f_{a+b}(Q) = f_a (Q) f_b (Q) g_{aP,bP} (Q) g_{(a+b)P, -(a+b)P} (Q)$. Let the binary representation of $l$ be $l_t,\cdots,l_0$. Then Miller's algorithm computes $f_P(Q)$ as follows.

set $f \leftarrow 1$ and $V \leftarrow P$
for $i \leftarrow t-1$ to $0$ do
1. set $f \leftarrow f^2_{g_{V,V}}(Q) / g_{2V,-2V}(Q)$ anf $V \leftarrow 2V$
2. if $l_i = 1$ then
  1. set $f \leftarrow f_{g_{V,P}}(Q) / g_{V+P,-(V+P)}(Q)$ and $V \leftarrow V + P$

読み解くと、

$E[l]$: 位数が $l$ の、橢円曲線 $E$ 上の点の集合
Function: R の要素の比 (rational function)。点を入力に取って、比の式の $x,y$ を点の $x,y$ で置き変えることで評価できる。評価結果は、橢円曲線が定義されているフィールド $\mathbb{F}$ の要素。
Divisor: function のふるまいを表すもの。プラスの項はゼロになる点、マイナスの項は評価不能になる点 (pole) を表す。係数はそれぞれ項の multiplicity。より具体的には、$g(x,y)$ が、点 $P$ でゼロや評価不能にならない関数で、$xP$ が $P$ の $x$ 座標だとして、$f_P$ の divisor が $l(P)$ を含んでいる場合は、$f_P(x,y)=(x - xP)^l g(x,y)$ のように、$xP$ が関数のルートになる項が $l$ 個含まれている。
$g_{P,Q}$: 点 $P,Q$ を通る直線の式 $y = mx + b$ の右辺の項を左辺に移項した $y - mx - b = 0$ の左辺が分子で、分母が $1$ の rational function。$m$ は直線の傾きで、$b$ は $y$ 切片。通常の関数と同じように、点を入力として、 $\mathbb{F}$ の要素に評価できる。
$f_c$: $c(P) - (cP) - (c-1)(O)$ という divisor を持つ rational function。 $c$ は $\mathbb{F}$ の要素。divisor の定義内の $c$ が、$f_c$ の $c$ で置き変わる。
$f_c(Q)$: $f_c$ を、点 $Q$ で評価する。評価結果は、$\mathbb{F}$ の要素。
$g_{A,B}(Q)$: $g_{A,B}$ を、点 $Q$ で評価する。評価結果は、$\mathbb{F}$ の要素。
$l_t,\cdots,l_0$: $l$ を binary で表したビットベクター。例えば、[1,0,0,...,1] 。

Miller's algorithm を、$G_1,G_2$ 上の点 $P,Q$ を入力として実行すると、$G_T$ の元が 1 つ返ってきます。

数学的な仕組みは理解できませんでしたが、解説にある疑似コードを実装したところ期待通りに動作しました。

実装はここにあります。

Weil pairing

$P,Q$ を入れ換えて 2 度 Miller's algorithm を実行して、その比を取ったものが、Weil pairing です。

$$
e(P,Q) = \frac{f_P(A_Q)}{f_Q(A_P)}
$$

Tate pairing

Weil pairing の分子部分の Miller's algorithm のみを実行すると Tate pairing になります。

$$
e(P,Q) = f_P(A_Q)
$$

Miller's algorithm を一度しか実行しないので、その分 Weil pairing よりも早いのですが、Tate pairing の結果は、$\mathbb{F}^{*}_{q^{k}} / (\mathbb{F}^{*}_{q^{k}})^{r}$ の equivalence class に含まれている元で、$G_T$ の元とは限りません。そこで final exponentiation を使って、結果の元を $G_T$ の元に移します。

Final exponentiation

Tate pairing の結果を $(q^k-1)/r$ 乗するのが final exponentiation です。こうすることで、結果を $G_T$ の元に移すことが出来ます。

Final exponentiation の仕組み

$\mathbb{F}^{*}_{q^{12}}$ の位数は ${q}^{12}-1$ で、$G_T$ は、位数 $r$ の $\mathbb{F}^{*}_{q^{12}}$ のサブグループなので、ラグランジュの定理から ${q}^{12}-1$ は $r$ で割り切れて、$({q}^{12}-1)/r$ という $\mathbb{F}^{*}_{q^{12}}$ 上の元が存在します。

ここで $g$ を $\mathbb{F}^{*}_{q^{12}}$ のジェネレーターだとすると、${q}^{12}-1$ は $g$ の位数なので、${g}^{{q}^{12}-1} = 1$ です。

$g^{q^{12}-1} = 1$ から $(g^{(q^{12}-1)/r})^r = 1$ なので、$r$ は $g^{(q^k-1)/r}$ の位数です。

なので $g^{(q^k-1)/r}$ をジェネレーターとしてグループを作ると、そのグループの元の位数は全て $r$ になります。

位数 $r$ の元 $x$ は、$x^r = 1$ になるような元なので、$r$ 乗根で $G_T$ の元ということになります。

Pinocchio (プロトコル 2) の実装

ここまでで Pinocchio の実装に必要な部品は全て揃いました。

前回のブログで作った QAP までのコードを拡張して、Pinocchio の論文の 5 ページで説明されているプロトコル 2 を実装します。

以下は、前回のブログで行なった計算の要約です。

Prover が witness を知っていることを証明したい式

$(x \cdot x \cdot x) + x + 5 = 35$

Circuit

                      Out
                       |
                      (*)
                     /   \
                   t4     1
                   |
                 _(*)_
                /     \
           ___(+)___   1
          /         \
        t2          t3
        |           |
       (*)         (*)
      /   \       /   \
     t1    x    (+)    1
     |         /   \
    (*)       x     5
   /   \
  x     x

Constraints

$t1 = x \cdot x$
$t2 = x \cdot t1$
$t3 = (x + 5) * 1$
$t4 = (t2 + t3) * 1$
$out = t4 \cdot 1$

Statement / Witness

公開されている、カテゴリー io の部分が statement で、Prover のみが知っている、非公開でカテゴリー mid の部分が witness です。

変数	値	インデックス	カテゴリー
1	1	0	io
x	3	1	io
out	35	2	io
t1	9	3	mid
t2	27	4	mid
t3	8	5	mid
t4	35	6	mid

Constraints の変数を statement / witness で置き換えると

$9 = 3 \cdot 3$
$27 = 3 \cdot 9$
$8 = (3 + 5) * 1$
$35 = (27 + 8) * 1$
$35 = 35 \cdot 1$

となります。

R1CS

$c = (1,x,out,t1,t2,t3,t4) = (1,3,35,9,27,8,35)$

$v$

     1 2 3 4 5
1   [0,0,5,0,0]
x   [1,1,1,0,0]
out [0,0,0,0,0]
t1  [0,0,0,0,0]
t2  [0,0,0,1,0]
t3  [0,0,0,1,0]
t4  [0,0,0,0,1]

$w$

     1 2 3 4 5
1   [0,0,1,1,1]
x   [1,0,0,0,0]
out [0,0,0,0,0]
t1  [0,1,0,0,0]
t2  [0,0,0,0,0]
t3  [0,0,0,0,0]
t4  [0,0,0,0,0]

$y$

     1 2 3 4 5
1   [0,0,0,0,0]
x   [0,0,0,0,0]
out [0,0,0,0,1]
t1  [1,0,0,0,0]
t2  [0,1,0,0,0]
t3  [0,0,1,0,0]
t4  [0,0,0,1,0]

$c \circ v * c \circ w - c \circ y = 0$

QAP

$v_k$ は、$x$ 番目の constraint の、$k$ 番目の witness の値を返す多項式です。例えば、今回の例では $v_1(3) = 5$ になります。

v
      /------- k --------\
      1  x out t1 t2 t3 t4
    +---------------------
/ 1 | 0  1  0  0  0  0  0
| 2 | 0  1  0  0  0  0  0
x 3 | 5  1  0  0  0  0  0
| 4 | 0  0  0  0  1  1  0
\ 5 | 0  0  0  0  0  0  1

QAP の結果として、全ての statement / witness 変数について、$v_k(x), w_k(x), y_k(x)$ の多項式が出力されています。

QAP に続く部分の実装

記事の説明と実装との違い

Pinocchio の論文では、ペアリングは入力の 2 つのグループが同じ $\mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$ という前提になっています。

この記事でも、同じ前提で説明を進めていきますが、実装では BLS12-381 を使っているため、ペアリングが $\mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ となり、元が入力のどちら側で使われるのかによって、元が属するグループを変える必要があります。その結果、関連する部分については、実装と記事での説明とが異なっています。

定数

名前	値	意味
$N$	3	入出力（カテゴリー $io$）の変数の数
m	4	全変数の合計数

評価・検証キーの生成

Trusted setup と呼ばれている、論文で $(EK_F, VK_F) \leftarrow KeyGen(F, 1^{\lambda})$ と書かれているステップです。

QAP の結果から、評価・検証キーを作ります。サーキットが変わると、このステップはやり直しが必要になります。

Toxic waste の生成

まず、以下の入力グループの元をランダムに生成します。

$r_v, r_w, s, \alpha_v, \alpha_w, \alpha_y, \beta, \gamma$

次に、生成した $r_v, r_w$ から、$r_y$ を作ります。

$r_y = r_v \cdot r_w$

これらの元は、知っていると証明の偽造が出来てしまうので、toxic waste と呼ばれています。

Toxic waste は trusted setup の過程で外部に漏れないように慎重に扱い、trusted setup が終った段階で破棄します。

この trusted setup が実際に行なわれた様子を Zcash の Trusted setup についての動画で見ることが出来ます。

Hiding

キーに直接 toxic waste を使うことは出来ないので、離散対数問題を解くことの難しさを利用して、toxic waste を隠します。

具体的には、$g$ をジェネレーター、隠したい toxic waste を $x$ とすると、$g^x$ の様にします。この様に隠すと、隠した元同士を足し合わせることもできます。

$E(x) = g^x$ として、

$E(x + y) = g^{x + y} = g^x + g^y = E(x) + E(y)$

というような感じです。

$E(x)$ は hiding と呼ばれています。

$g_v,\ g_w,\ g_y$ の生成

まず、キー生成の下準備として、hiding と $r_v, r_w, r_y$ を使って、$v,w,y$ 用のジェネレーター $g_v,\ g_w,\ g_y$ を作ります。

$g_v = g^{r_v}$

$g_w = g^{r_w}$

$g_y = g^{r_y}$

評価キーの生成

次に、witness に対応する QAP の結果の多項式 $v_k, w_k, y_k$ を $s$ で評価した結果の元を、$g_v,\ g_x,\ g_y$ に掛け合わせたものを作ります。今回の例では、witness は $t1, t2, t3, t4$ です。

${ g_v^{v_k(s)} }\ k \in I_{mid}$

${ g_w^{w_k(s)} }\ k \in I_{mid}$

${ g_y^{y_k(s)} }\ k \in I_{mid}$

$I_{mid}$ は、カテゴリーが mid の変数に対応するインデックスの集合なので、witness 変数のインデックスの集合になります。今回の例では $I_{mid} = { 3,4,5,6 }$ です。

その $I_{mid}$ では、

${ g_v^{v_k(s)} }\ k \in I_{mid} = {g_v^{v_3(s)}, g_v^{v_4(s)}, g_v^{v_5(s)}, g_v^{v_6(s)} }$

となります。

$g_v^{v_k(s)}$ は、多項式 $v_k$ を $s$ で評価した結果分だけ、ジェネレーター $g_v$ を足していくという意味になります。例えば、$v_k(s) = 100$ なら $g_v$ を 100 回足します。

他にも、ジェネレーターに多項式を $s$ で評価した結果で掛けて、さらに対応する $\alpha_*$ を掛けた

${ \alpha_v g_v^{v_k(s)} }\ k \in I_{mid}$

${ \alpha_w g_w^{w_k(s)} }\ k \in I_{mid}$

${ \alpha_y g_y^{y_k(s)} }\ k \in I_{mid}$

や、多項式 $v_k,w_k,y_k$ をそれぞれ $s$ で評価して $\beta$ を掛けたものを、ジェネレーターに掛けて全て足し合わせた

${ g_v^{\beta_v v_k(s)}\ g_w^{\beta_w w_k(s)}\ g_y^{\beta_y y_k(s)} }\ k \in I_{mid}$

また、多項式 $v_k, w_k, y_k, p, t$ ($p, t$ については後述) の中での最大の次数 $d$ を使った

${ g^{s^{k}} }\ k \in [d]$

を計算します。$[d]$ は、${0, 1, \cdots, d }$ の集合という意味です。

以上を集めたものが評価キーになります。

実装はここにあります。

$p(x)$

$d$ の決定に使った $p$ は、QAP の結果 $v_k, w_k, y_k$ に、対応する statement / witness を掛けて、それぞれを足し上げて $v, w, y$ を作り、$v * w - y$ を計算することで作られる多項式です。

今回の例では、statement / witness を $c_1,\ c_2, \cdots, c_7$ だとすると、こんな感じで作ります。

$v(x) = c_1 \cdot v_1(x) + c_2 \cdot v_2(x) + \cdots + c_7 \cdot v_7(x)$

$w(x) = c_1 \cdot w_1(x) + c_2 \cdot w_2(x) + \cdots + c_7 \cdot w_7(x)$

$y(x) = c_1 \cdot y_1(x) + c_2 \cdot y_2(x) + \cdots + c_7 \cdot y_7(x)$

$p(x) = v(x) \cdot w(x) - y(x)$

$p(x)$ は、$1$ から $m$ の間のどの数で評価しても $0$ になる多項式です。

$t(x)$

同じく $d$ の決定に使った $t$ は、$(x-n)$ の項を $n=1 \cdots m$ での元で作り、全てを掛け合わせて出来る、以下のような多項式です。

$t(x) = (x-1)(x-2) \cdots (x-m)$

$t(x)$ は $p(x)$ を割り切る

$p(x)$ は、$1$ から $m$ 間の数で $0$ に評価されるので、$(x-1), (x-2), \cdots, (x-m)$ をルートに持っていることになります。

言い換えると、ある多項式 $h(x)$ が存在して、$p(x) = (x-1)(x-2) \cdots (x-n) \cdot h(x) = t(x) \cdot h(x)$ なので、$p(x)$ は $t(x)$ で割り切れます。

検証キーの計算

以下を集めたものが検証キーになります。

ジェネレーターをそれぞれ $1, \alpha_v, \alpha_w, \alpha_y, \gamma, \beta \gamma$ で掛けたもの
$t$ を $s$ で評価して、$g_y$ に掛けたもの
Statement に対応する QAP の結果の多項式 $v_k, w_k, y_k$ を $s$ で評価した結果の元を、ジェネレーターに掛けたもの

検証キー 3 の生成に使われるインデックス

検証キー 3 は論文では、
${ g_v^{v_k(s)}, g_w^{w_k(s)}, g_y^{y_k(s)} }\ \in { 0 } \cup [N]$ と表わされています。

論文 3 ページの QAP の説明に

A QAP $Q$ over field $\mathbb{F}$ contains three sets of $m+1$ polynomials $V = { v_k(x) },\ W = { w_k(x) },\ Y = { y_k(x) }$, for $k \in {0 \cdots m}$

We associate an index $k \in [m] = {1 \cdots m}$ to each input of the circuit and to each output from a multiplication gate

とあり、statement に対応するインデックスは $1, 2$ となります。$m+1$ の $+1$ の部分は、恐らく statement / witness の変数リストの先頭に付け加えられる $1$ で、これをインデックス $0$ に置いているのだと思います。

この $1$ が変数に組み込まれていると、$t3 = (x + 5) * 1$ ような、定数の加算 ($+ 5$ にあたる部分) に対応することが出来ます。

他にも、同じく 3 ページに、

The actual construction [30] is a bit more complex, as it handles addition and multiplication by constants

という記述があります。

$[d] = {0,1,\cdots,d}$ だったので、${0}$ は $[N]$ に含まれていると思うのですが、$0$ を強調するために、${ 0 } \cup [N]$ と書いているのかもしれません。

CRS

評価キーと検証キーをあわせたものは、CRS (Common Reference String) とも呼ばれます。

Knowledge of Coefficients (KC)

多項式を評価すると結果は 1 つのグループの元になります。なので、あたかも実際に評価したように装い、検証式が成り立つような元をうまく準備すると、証明を偽造することが出来てしまいます。

これを防ぐために、多項式の係数を実際に知っていること (Knowledge of Coefficients) の確認を、検証式に含めます。

$\alpha$-ペア

$a,b$ をグループの元、$\alpha$ をグループが定義されているフィールドの元だとして、
$b = \alpha \cdot a$ のような関係を持つ $a, b$ の組みを $\alpha$-ペアと呼びます。

$a,b$ を渡されたとしても、離散対数問題を解くことが難しいため、$\alpha$ は分かりません。

Knowledge of Coefficient Assumption (KCA)

ひろしが $\alpha$-ペア $a,b$ をよしえに渡して、よしえに別の $\alpha$-ペアを返すように求めたとします。
$b$ から $\alpha$ を求めることは出来ないので、別の $\alpha$-ペアを返す唯一の方法は、
$a, b$ の両方に $\gamma$ を掛け合わせた $a' = \gamma \cdot a, b' = \gamma \cdot b$ を計算して $a', b'$ を返すことになります。

$b' = \gamma \cdot b = \gamma \cdot \alpha \cdot a = \alpha \cdot \gamma \cdot a = \alpha \cdot a'$

で $a', b'$ は $\alpha$-ペアです。

ひろしは $a'$ に $\alpha$ を掛けたものが、$b'$ になることを確認することで、よしえが $\alpha$-ペアを返して来たかを確認することが出来ます。

仮に よしえが別の $\alpha$-ペアを返して来た場合には、よしえは $a' = \gamma \cdot a$ であるような $\gamma$ を知っています。

これを Knowledge of Coefficient Assumption と呼びます。

d-power Knowledge of Coefficient Assumption (d-KCA)

今度は、ひろしが $d$ 個の $\alpha$ ペア

$(a_1, b_1), \cdots, (a_d, b_d)$

をよしえに送ります。

そして、よしえは、フィールドの元 $c_1, \cdots c_d$ を用意して、

$(a',b') = (c_1 \cdot a_1 + \cdots + c_d \cdot a_d, c_1 \cdot b_1 + \cdots + c_d \cdot b_d)$

を返します。この $a', b'$ も

$b' = c_1 \cdot b_1 + \cdots + c_d \cdot b_d = c_1 \cdot \alpha \cdot a_1 + \cdots + c_d \cdot \alpha \cdot a_d = \alpha \cdot (c_1 \cdot a_1 + \cdots + c_d \cdot a_d) = \alpha \cdot a'$

なので $\alpha$-ペアです。

そして、$a' \cdot \alpha$ が $b'$ になるかを、ひろしが確認出来た場合には、よしえは、$a_1, \cdots, a_d$ の線形結合 $c_1 \cdot a_1 + \cdots + c_d \cdot a_d$ が $a'$ になるような $c_1, \cdots, c_d$ を知っていることになります。

d-KCA は、$a_{1}, \cdots, a_{d}$ を $g^{s^{0}}, g^{s^{1}}, \cdots, g^{s^{d}}$で置き換えて $c_1 \cdot g^{s^{0}} + \cdots + c_d \cdot g^{s^{d}}$ という形にして、よしえが多項式の項の係数を知っていることを知っていることを示します。

具体的には、ひろしが
$(g^{s^{0}}, \alpha \cdot g^{s^{0}}), (g^{s^{1}}, \alpha \cdot g^{s^{1}}), \cdots, (g^{s^{d}}, \alpha \cdot g^{s^{d}})$ $\alpha$ ペアをよしえに渡して、よしえが $c_{0}, \cdots c_{n}$ を用意して、上記の方法で、$a', b'$ を作って、ひろしに渡します。

もし、ひろしが、$b' = \alpha \cdot a'$ であることを確認できた場合は、よしえは $c_1 \cdot s^{0} \cdot g + \cdots + c_{d} \cdot s^{d} \cdot g$ が $a'$ になるような $c_{1}, \cdots, c_{d}$ を知っていることになります。

これが d-KCA です。

証明の作成

論文では $(y, \pi_y) \leftarrow \text{Compute}(EK_F, u)$ で説明されている部分です。

Prover は statement $u$ を入力として、サーキットを評価して、QAP を実行します。

そして、

QAP の実行結果である $v_k, w_k, y_k$
Statement / witness から作る $p(x)$
全ての多項式中での最大の次数 $d$ から作る $t(x)$
評価キー

を使って、以下を計算し、計算結果を証明とします。

$g^{h(x)}$

$t(x)$ は $p(x)$ を割り切る多項式なので、$p(x) = h(x) \cdot t(x)$ のような $h(x) = \frac{p(x)}{t(x)}$ が存在します。その $h(x)$ を、ジェネレーターに掛け合わせたものを計算します。

$g_v^{v_{mid}(s)}, g_w^{w_{mid}(s)}, g_y^{y_{mid}(s)}$ (3 つの元)

$v_{mid}(x) = \sum_{k \in I_{mid}} c_k \cdot v_k$ で、評価キーが $g_v^{v_k}$ を含んでいるので、$g_v^{v_k}$ に、対応する $c_n$ を掛けながら足し上げて、$g_v^{v_{mid}(s)}$ を計算します。$ g_w^{w_{mid}(s)}, g_y^{y_{mid}(s)}$ についても、同じ要領で計算します。

$g_v^{\alpha_v v_{mid}(s)}, g_w^{\alpha_w w_{mid}(s)}, g_y^{\alpha_y y_{mid}(s)}$ (3 つの元)

評価キーが $g_v^{\alpha_v v_k}$ を含んでいるので、$g_v^{\alpha_v v_k}$ に、対応する $c_n$ を掛けながら足し上げて、$g_v^{\alpha_v v_{mid}(s)}$ を計算します。$ g_w^{\alpha_w w_{mid}(s)}, g_y^{\alpha_y y_{mid}(s)}$ についても、同じ要領で計算します。

$g_v^{\beta v_{mid}(s)} g_w^{\beta w_{mid}(s)} g_y^{\beta_y y_{mid}(s)}$ (1 つの元)

評価キーが $g_v^{\beta v_k(s)} g_w^{\beta w_k(s)} g_y^{\beta_y y_k(s)}$ $g_v^{\alpha_v v_k}$ を含んでいるので、$g_v^{\beta v_k(s)} g_w^{\beta w_k(s)} g_y^{\beta_y y_k(s)}$ $g_v^{\alpha_v v_k}$ に、対応する $c_n$ を掛けながら足し上げて、$g_v^{\beta v_{mid}(s)} g_w^{\beta w_{mid}(s)} g_y^{\beta_y y_{mid}(s)}$ を計算します。

証明の検証

論文では ${0, 1} \leftarrow \text{Verify}(VK_F, u, y, \pi_y)$ で説明されている部分です。

証明と検証で、元の呼び方が変わるので注意してください。以下はその対応です。

証明	検証
$g^{h(x)}$	$g^H$
$g_v^{v_{mid}(s)}, g_w^{w_{mid}(s)}, g_y^{y_{mid}(s)}$	$g^{V_{mid}}, g^{W_{mid}}, g^{Y_{mid}}$
$g_v^{\alpha_v v_{mid}(s)}, g_w^{\alpha_w w_{mid}(s)}, g_y^{\alpha_y y_{mid}(s)}$	$g^{V'_{mid}}, g^{W'_{mid}}, g^{Y'_{mid}}$
$g_v^{\beta v_{mid}(s)} g_w^{\beta w_{mid}(s)} g_y^{\beta_y y_{mid}(s)}$	$g^Z$

検証では、まず $p(x) = h(x) \cdot t(x)$ が成り立つかを確認します。

$p(x) = v(x) \cdot w(x) - y(x)$ なので、$p(x)$ を、この右辺で置き換えて、$v(x) \cdot w(x) - y(x) = h(x) \cdot t(x)$ として、掛け算部分にペアリングを使って確認します。

論文では、検証式は

$e(g_v^{v_0(s)} g_v^{v_{io}(s)} g_v^{v_{mid}(s)}, g_w^{w_0(s)} g_w^{w_{io}(s)} g_w^{w_{mid}(s)}) $

$= e(g_y^{t(s)}, g^H)\ e(g_y^{y_0(s)} g_y^{y_{io}(s)} g_y^{y_{mid}(s)}, g)$

と書かれていますが、分かりにくいので、乗算ベースから加算ベースに書き直します。

$e(v_0(s)\ g_v + v_{io}(s)\ g_v + v_{mid}(s)\ g_v, w_0(s)\ g_w + w_{io}(s)\ g_w + w_{mid}(s)\ g_w)$

$= e(t(s)\ g_y, H g)\ + e(y_0(s)\ g_y + y_{io}(s)\ g_y + y_{mid}(s)\ g_y, g)$

$e(a, b)$ はペアリングです。

細かく見ると、

$v_0(s)\ g_v + v_{io}(s)\ g_v + v_{mid}(s)\ g_v$ は $y(s)$
$w_0(s)\ g_w + w_{io}(s)\ g_w + w_{mid}(s)\ g_w)$ は $w(s)$
$e(t(s)\ g_y, H g)$ は $h(s) \cdot t(s)$
$e(y_0(s)\ g_y + y_{io}(s)\ g_y + y_{mid}(s)\ g_y, g)$ は $y(s)$

の hiding になっています。

以下、注意点です。

$v_0(s)$ は $1$、$v_{io}(s)$ は、サーキットの入力の全てと出力、$v_{mid}(s)$ は中間の値に対応する witness に対応しているので、その全てを足し合わせることで $v(s)$ になります。$w, y$ についても同じです。
$g$ は単位元で、掛けても結果は変わりません。なので、$e(y_0(s)\ g_y + y_{io}(s)\ g_y + y_{mid}(s)\ g_y, g)$ は、$y_0(s)\ g_y + y_{io}(s)\ g_y + y_{mid}(s)\ g_y$ に対応する $G_T$ の元になります。

次に、KC の確認を行います。

論文では、

$e(g_v^{V'_{mid}}, g) = e(g_v^{V_{mid}}, g^{\alpha_v})$

$e(g_w^{W'_{mid}}, g) = e(g_w^{W_{mid}}, g^{\alpha_w})$

$e(g_y^{Y'_{mid}}, g) = e(g_y^{Y_{mid}}, g^{\alpha_y})$

と、

$e(g^Z, g^{\gamma}) = e(g_v^{V_{mid}} g_w^{W_{mid}} g_y^{Y_{mid}}, g^{\beta \gamma})$

の 4 つの、KCの確認を行っています。

ゼロ知識化

攻撃者が constraint が全て成立する witness を見つけた場合に、その witness を使って証明を作り、実際の証明と比較をすると、その witness が証明に使われた witness とは異なることが、攻撃者に分かってしまいます。

これを防ぐために、$v_{mid}(s), w_{mid}(s), y_{mid}(s)$ のそれぞれに、ランダムな元 $\delta_v, \delta_w, \delta_y$ を $t(s)$ に掛けたものを足し、$v_{mid}(s), w_{mid}(s), y_{mid}(s)$ を隠します。具体的には、以下の様な感じです。

$v(s) * w(s) - y(s)$ に、

$\delta_v t(s), \delta_w (s), \delta_y (s)$ を足して、

$(v(s) + d_v t(s)) \cdot w(s) - (y(s) + d_y t(s) + d_y t(s))$

とします。これを展開していくと、

$= v(s) \cdot w(s) + d_v t(s) \cdot w(s) - y(s) - d_y t(s) - d_y t(s)$

$= v(s) \cdot w(s) - y(s) + d_v t(s) \cdot w(s) - d_y t(s) - d_y t(s)$

$v(s) \cdot w(s) - y(s) = t(s) \cdot h(s)$ なので、

$= t(s) \cdot h(s) + d_v t(s) \cdot w(s) - d_y t(s) - d_y t(s)$

$t(s)$ をくくり出すと

$= t(s) \cdot (h(s) + d_v \cdot w(s) - d_y t - d_y)$

となります。

この式から分かるように、ゼロ知識化をすると $h(x)$ 部分にその影響が出るので、
$h(x)$ は $h(s) + d_v \cdot w(s) - d_y t - d_y$ と置き換えて検証を行なう必要があります。

Groth16

Groth16 は、Pinocchio よりも後に出た zk-SNARK で、CRS や証明のサイズが小さくなっています。

Pinocchio では、Knowledge of Coefficient の確認が、検証式の大きな割り合いを占めていましたが、Groth16 ではそれが無くなっています。

KC を使わないでも大丈夫な理由

Groth16 の論文の 5 ページに、

A second source of efficiency gain compared to previous work is a more aggressive compilation of the LIP. Bitansky et al. [BCI+13] propose a transformation in the symmetric bilinear group setting, where each field element gets compiled into two group elements. They then use a knowledge of exponent assumption to argue that the prover knows the relevant field elements. A less conservative choice would be to compile each field element into a single group element. Compiling with a single group element per field element improves efficiency but we only prove security generic group model [Sho97,BBG05] since we can no longer use the knowledge of exponent assumption. It is also possible to make a choice between these two extremes, Parno et al. [PHGR13] for instance have a LIP with 4 field elements, which gets compiled into 7 group elements. To summarize, in this paper we have opted for maximal efficiency and compile each field element in the LIP into a single group element and argue security in the generic group model.

とあって、これが KC を使わないでも大丈夫な理由の説明のように見えますが、どうなんでしょうか。良くわかりません。ちなみに、[PHGR13] は、Pinocchio の論文です。

プロトコルの詳細

Groth16の論文の 17 ページにある、3.2 NIZK arguments for quadratic arithmetic programs で、プロトコルが説明されています。

QAPまでは Pinocchio と同じで、trusted setup 以降が以下のように変わっています。

前提

$g$ は、$\mathbb{G}_1$ のジェネレーター
$h$ は、$\mathbb{G}_2$ のジェネレーター
$e(g,h)$ は、$\mathbb{G}_T$ のジェネレーター
$n$ は degree。$h(x)$ の degree は $n-2$
$m$ は、サーキットの全ワイヤー数
$l$ は、サーキットの公開ワイヤー数
Statements は、$(a_1, \cdots, a_l) \in \mathbb{F}_q^l$
Witness は、$(a_{l+1}, \cdots, a_m) \in \mathbb{F}_q^{m-l}$

Trusted setup

$(\sigma, \tau) \leftarrow \text{Setup}(R)$ で説明されている部分です。

Pinocchio と同じく Trusted setup を行います。非ゼロのランダムなベースフィールドの元 $\alpha, \beta, \gamma, \delta, x$ を準備して、以下の $\sigma$ を計算します。

$\sigma = (\alpha, \beta, \delta, {x^i}_{i=0}^{n-1}, {\frac{\beta u_i(x) + \alpha v_i(x) + \gamma w_i(x)}{\gamma}}_{i=0}^{l}, {\frac{\beta u_i(x) + \alpha v_i(x) + \gamma w_i(x)}{\delta}}_{i=l+1}^{m}, {\frac{x^i t(x)}{\delta}}_{i=0}^{n-2})$

自分の実装

証明の作成

$\pi \leftarrow \text{Prove}(R, \sigma, a_{1}, \cdots, a_{m})$ で説明されている部分です。

非ゼロの元 $r,s$ をベースフィールドからランダムに選んで以下の形で証明を計算します。$A, B, C$ の 3 つの元が証明になります。

$A = \alpha + \sum_{i=0}^{m} a_i u_i(x) + r \delta$

$B = \beta + \sum_{i=0}^{m} a_i v_i(x) + s \delta$

$C = \frac{\sum_{i=l+1}^m a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x)) + h(x)t(x)}{\delta} + As + rB - rs \delta$

自分の実装

証明の検証

$\text{0/1} \leftarrow \text{Vfy}(R, \sigma, a_{1}, \cdots, a_{l}, \pi)$ で説明されている部分です。

以下の $LHS, RHS$ を計算して、一致するかを調べます。

$LHS = A \cdot B$

$RHS = \alpha \cdot \beta + \frac{\sum_{i=0}^l a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x))}{\gamma} \cdot \gamma + C \cdot \delta $

自分の実装

検証式ついて深掘り

どうしてこれで検証できるのか、直感的には理解しにくいので、$LHS, RHS$ を展開・変形して、同じ形になるのかを確認します。

$LHS$

$= A \cdot B$

$= (\alpha + \sum_{i=0}^{m} a_i u_i(x) + r \delta) \cdot (\beta + \sum_{i=0}^{m} a_i v_i(x) + s \delta)$

$= \alpha \cdot \beta + \alpha \sum_{i=0}^{m} a_i v_i(x) + \alpha s \delta + \beta \sum_{i=0}^{m} a_i u_i(x) + \sum_{i=0}^{m} a_i u_i(x) \cdot \sum_{i=0}^m a_i v_i(x)$

$+ s \delta \sum_{i=0}^{m} a_i u_i(x) + r \delta \beta + r \delta \sum_{i=0}^{m} a_i v_i(x) + rs \delta^2$

$= \alpha \cdot \beta + \sum_{i=0}^{m} \alpha a_i v_i(x) + \alpha s \delta + \sum_{i=0}^{m} \beta a_i u_i(x) + \sum_{i=0}^{m} a_i u_i(x) \cdot \sum_{i=0}^m a_i v_i(x)$

$+ \sum_{i=0}^{m} s \delta a_i u_i(x) + r \delta \beta + \sum_{i=0}^{m} r \delta a_i v_i(x) + rs \delta^2$

$= \alpha \cdot \beta + \sum_{i=0}^{m} (\beta a_i u_i(x) + \alpha a_i v_i(x)) + \sum_{i=0}^{m} a_i u_i(x) \cdot \sum_{i=0}^m a_i v_i(x) + \sum_{i=0}^{m} s \delta a_i u_i(x)$

$+ \sum_{i=0}^{m} r \delta a_i v_i(x) + \alpha s \delta + \beta r \delta + rs \delta^2$

$RHS$

$= \alpha \cdot \beta + \frac{\sum_{i=0}^l a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x))}{\gamma} \cdot \gamma + C \cdot \delta $

$= \alpha \cdot \beta + \frac{\sum_{i=0}^l a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x))}{\gamma} \cdot \gamma + (\frac{\sum_{i=l+1}^m a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x)) + h(x)t(x)}{\delta} + As + rB - rs \delta) \cdot \delta $

$= \alpha \cdot \beta + \sum_{i=0}^l a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x)) + \sum_{i=l+1}^m a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x))$

$+ h(x)t(x) + As \delta + rB \delta - rs \delta^2$

$= \alpha \cdot \beta + \sum_{i=0}^m a_i(\beta u_i(x) + \alpha v_i(x) + \omega_i(x)) + h(x)t(x) + As \delta + rB \delta - rs \delta^2$

$= \alpha \cdot \beta + \sum_{i=0}^m (\beta a_i u_i(x) + \alpha a_i v_i(x) + a_i \omega_i(x)) + h(x)t(x) + A s \delta + B r \delta - rs \delta^2$

$h(x)t(x)$ は、$u_i \cdot v_i - w_i$ に witness $a_i$ を掛けたものと等しいので、こう書けます。

$\sum_{i=0}^m a_i u_i(X) \cdot \sum_{i=0}^m a_i v_i(X) = \sum_{i=0}^m a_i \omega_i(X) + h(X)t(X)$

注：$f(X)$ は多項式が評価されていない状態で、$f(x)$ は $x$ で評価した状態です。

ここから、

$\sum_{i=0}^m a_i u_i(X) \cdot \sum_{i=0}^m a_i v_i(X) - \sum_{i=0}^m a_i \omega_i(X) = h(X)t(X)$

なので、$h(x)t(x)$ を左辺で置き換えて、

$= \alpha \cdot \beta + \sum_{i=0}^m (\beta a_i u_i(x) + \alpha a_i v_i(x) + a_i \omega_i(x)) + \sum_{i=0}^m a_i u_i(x) \cdot \sum_{i=0}^m a_i v_i(x)$

$- \sum_{i=0}^m a_i \omega_i(x) + A s \delta + B r \delta - rs \delta^2$

$= \alpha \cdot \beta + \sum_{i=0}^m (\beta a_i u_i(x) + \alpha a_i v_i(x)) + \sum_{i=0}^m a_i u_i(x) \cdot \sum_{i=0}^m a_i v_i(x) + A s \delta + B r \delta - rs \delta^2$