# ゼロ知識証明を学ぶ

無限(有限)に難しいものが登場してくるので一つ一つ学んできた。
それの経路のメモ。難しい。

## 1) まず「証明」とは
ある命題が正しいことを主張するための一連の演繹のこと。
つまり 「$P$ は　$True/False$である」 という命題が正しいか確かめること。よくある話としては
「私はこの金庫の暗証番号を知っています。暗証番号はXXXXです」のように開示することで証明するとかある。

## 2) 「ゼロ知識証明」とは
証明者が検証者に対して、ある命題が正しい事を、それが正しい事以外の情報を明らかにせずに証明できる手法である。
上の例で言うと
「私はこの金庫の暗証番号を知っています。暗証番号はいえません」
これが許される（この情報で正しいことを確かめる事ができる）

### 3) 「証明者」とは
Prover、命題を主張する人。
命題の根拠となる情報を持っているが、検証者には教えたくない。
最初、なぜProverという単語なのかわからなかったが、
Verifierから受け取った質問(命題)を **証明する** 人と考えたら理解できた。

https://natalie.mu/music/pp/milet05/page/2
いい曲だった。

### 4) 「検証者」とは
Verifier、命題が正しいか検証する人。

## *5) 特性

- 完全性 (Completeness)
証明者が命題の根拠となる情報を持っている、高確率で検証者は
証明者が正しいことを言っている事がわかる。

- 健全性 (Soundness)
証明者が命題の根拠となる情報を持っていないとき、高確率で検証者は
証明者が嘘をついている（命題の根拠となる情報がないので、命題が正しくない）事がわかる。

- ゼロ知識性(Zero Knowledge)
証明者から命題の根拠となる情報を受け取らなくても検証者は証明できる。

## 6) 洞窟の問題
ゼロ知識証明を調べようとすると出てくるやつ。
ここからどうやってzkRollupまで辿り着くのか……。先が長すぎる。
https://pages.cs.wisc.edu/~mkowalcz/628.pdf

最初Peggy($P$)が洞窟に入り、別れ道の部分にいる。
Victor($V$)は洞窟の入り口でまつ。

ここで、以下の手順を繰り返す。
- Peggyは道A,Bどちらかを選択して進む。（このときVictorにはPeggyがどちらに進んだか見えない、かつ先に選んでもらう）
- Victorは「Aから戻ってきて」または「Bから戻ってきて」とPeggyに伝える。
- Peggyは、Peggyは、Victorに言われた道`A/B` から分かれ道に戻る。Victorはそれを見る。
- Peggyは、Victorの指示通りの道`A/B` から分かれ道に戻る。
- Peggyは、自身が選んだ道と、Victorの要求した道が同じであれば、来た道を戻ることで満たせる。
- Peggyは、自身が選んだ道と、Victorの要求した道が異なる場合、Magic Doorの鍵を使い要求した道から戻る。
- Victorは分かれ道に進み、Peggyが要求した道から戻ってくるか確認する。
- 要求通りであれば検証OK、Peggyは鍵を持っている
- 要求通りでなければ検証NG、Peggyは鍵を持っていないで終わり

これを繰り返すことにより、$n$回目まで正しくあり続ける確率は $\frac{1}{2}^n$なので、nが大きければPeggyはMagic Doorの鍵を持っている確率が高い。
確かに、Peggyは鍵を見せることなく鍵を持っていることを証明しているし、
Victorも鍵を見ることなく、Peggyは鍵を持っていると納得しているので
ゼロ知識証明である事がわかる。

## 7) 対話型 / 非対話型
このような形で証明者(Prover)と検証者(Verifier)がやりとりをする形式を「対話型ゼロ知識証明」と呼ぶ。
ただ、この方式だと時間がかかる（試行を何度もしないといけない）ので対話のない形式「非対話型ゼロ知識証明」の方が便利。
Non-interactive Zero-Knowledge Proof　**NIZKP** とも呼ばれている（自分はあまり聞いたことない……）

## 8) 離散対数問題（Discrete Logarithm Problem)

有限体 $F_p$ について、素数 $p$ と生成元$g,y∈{1,2,...,p-1}$
$y=g^x$ を満たすxを探すことはとても難しい。
これは例えば有限体$F_5$に含まれる要素$２$を$6$乗した値($64$)を$5$で割った値にする(あまり$=4$)。この`根,割る数,あまり` ($\{2,5,4\}$)から何回掛けたか(ここでいう$6$)を求めるのは難しい、という事。

## DH(Diffie-Hellman)問題
$g^a$,$g^b$から$g^{ab}$を求める問題、DLPぐらい難しい。
なお、$g^a$,$g^b$から$g^{a+b}$を求めるのは簡単。

### *7) 剰余演算(モジュラー計算)
$a\ mod\ b = c$
整数$a$を$b$で割った値が$c$であるという事。
例えば
$7\ mod\ 3 = 1$ ($7 = 3*2 + 1$)
$17\ mod\ 7 = 3$ ($17 = 7*2 + 3$)

### *8) 原始根

素数$p\ (p\ge3)$と整数$r\ (p-1\ge r \ge 1)$が
「$r,r^2,...,r^{p−2}$のそれぞれを$p$で割った時あまりが$1$にならない」時の $r$ を**mod pの原始根**と呼ぶ。
例えば$r=2,p=13$を例にとると、$2^{11}$まで計算しそれを13で割った余を出す。
$$
\begin{eqnarray}
2\equiv2\ (mod\ 13) \\
2^2\equiv4\ (mod\ 13) \\
2^3\equiv8\ (mod\ 13) \\
2^4\equiv3\ (mod\ 13) \\
2^5\equiv6\ (mod\ 13) \\
2^6\equiv12\ (mod\ 13) \\
2^7\equiv11\ (mod\ 13) \\
2^8\equiv9\ (mod\ 13) \\
2^9\equiv5\ (mod\ 13) \\
2^{10}\equiv10\ (mod\ 13) \\
2^{11}\equiv7\ (mod\ 13) \\
\end{eqnarray}
$$
この時、１があまりに出ないことに加え、重複していない。
つまり、原子根$r^n$の値とあまりの値が１対１に対応している。

**この時、あまりの値($A$)から$r$を何乗したかを求める良い方法が見つかっていない。**
結局全ての累乗の値を1から計算して合致するまで回さないといけない。
（$r^n\equiv A\ (mod\ p),\ (p-2\ge n \ge 1)$において、$n$のことを底$r$についてのAの離散対数と呼ぶ）

(なお、$mod\ p$ において、原始根は必ず存在する)

### *9) 位数（周期）
$p$で割ったあまりが１になる時の指数のこと。
上でいうと$12$。
$2^{12}\equiv1\ (mod\ 13)$
位数を使うと、原子根は
原始根は「位数が$p−1$であるもの」と言い換えられる。
「$r,r^2,...,r^{p−2}$のそれぞれを$p$で割った時あまりが$1$にならない = $r,r^2,...,r^{p−1}$と計算していき、それぞれを$p$でわる、すると $r^{p−1}$ の時あまりが１となる。
なお、その後は同じ値が繰り返し出てくる。

### *10) 巡回群
群$G$有限個の元$a_1,a_2,...,a_m$で生成されるとき、$G$を $\langle a_1,a_2,...,a_m\rangle$と書く。
なお、単一の元で生成される時
$G = \langle a \rangle = \{a^i|i∈Z\}$
と書く。

### *10) 生成
群$G$がその部分集合$S$で生成されるとき、$S$を$G$の生成系とよぶ．この
とき$S$は$G$を生成するともいう。
つまり、群$G=\{1,2,...,12\}$の時、$２$ のみを使って$2^1\ mod\ 13,2^2\ mod\ 13,...,2^{12}\ mod\ 13$ 表す事ができるので$S=\langle 2 \rangle$を$G$の生成元と呼ぶ。

### *11) 群・環・体

#### 群)
- 1) 閉じている $a・b \in G, a,b\in G$
- 2) 結合法則が成り立つ $a+(b+c)=(a+b)+c$
- 3) 単位元がある $a+e=e+a=a$となる要素$e$がある
- 4) 逆元がある $a+(-a)=(-a)+a=e$となる要素$-a$がある
- 5) 可換である $a+b=b+c$

定義として
- 1,2を満たす時、**半群**と呼ぶ。
- 1,2,3を満たす時、**モノイド**と呼ぶ。
- 1,2,3,4を満たす時、**群**と呼ぶ。
- 1,2,3,4を満たす時、**アーベル群**と呼ぶ。

Memo:二項演算子Xが上の定義を満たしているなら群だと思ったが、環の勉強始めたら加法$+$について上の性質を満たすものを群と言っているのでよくわからない。

#### 環)
- 1) 加法についてアーベル群である
- 2) 乗法について以下を満たす(つまり、乗法について半群)
- 結合法則が成り立つ
- 3) 分配法則が加法、乗法で成り立つ
- 4) 乗法について可換である $ab=ba
- 5) 乗法について単位元がある $a1=1a=a$ (つまり、乗法についてモノイド?)

定義として
- 1,2,3を満たす時、**環**と呼ぶ。
- 1,2,3,4を満たす時、**可換環**と呼ぶ。
- 1,2,3,4を満たす時、**単位的**と呼ぶ。

#### 体)
- 単位元を持つ可換環である
- 乗法について逆元を持つ $aa^{-1}=e$

有理数，実数，複素数はいずれも体

## 12) 有限体(ガロア体)
位数の数が有限の体
演算終わったあと位数で割ったあまりが元となる。
$c=a⋅b\ mod\ p$

## 13) 楕円曲線 （$Q$上）
$a1, a2, a3, a4, a6 ∈ Q$とする. このとき等式$E$を以下のように定義する
$E : f(x, y) := y^2 + a_1xy + a_3y − (x^3 + a_2x^2 + a_4x + a_6) = 0$
この式で表される曲線の事。

## 14) 有限体$F_p$上の楕円曲線
$y^2=x^3+ax+b$ を満たす$(x,y) x, y ∈ F_p$全体の集合

### *15) 無限遠点
アーベル群の単位元$O$の事

### *16) アフィン変換
調べる

## 17) 楕円曲線上の離散対数問題（Elliptic Curve Discrete Logarithm Problem)
楕円曲線上のある点$P$、$Q$において、$P+Q$が定義可能である。
なんなら加法に関してアーベル群である。

n回足す => n倍と表せるが
$P+P+P+...+P=nP$

$Q=nP$ のQ,Pからnを求めるのは、上の「あまりの値($A$)から$r$を何乗したかを求める」のと同じぐらい難しい。
逆に$n,P$から$Q$を求めるのはとても簡単。

離散対数問題と同じで$P,2P,3P,4P$の値を位数まで計算し続け、
なにが合致するか確かめないといけない。
位数がめちゃくちゃにでかいとしんどい。

### 18) 楕円曲線　Diffie-Hellman鍵共有
調べる

### 19) 楕円曲線　ElGamal 暗号
調べる

### 20) 楕円曲線　DSA
調べる

## 21) ペアリング
楕円曲線上の２点から有限体$F_p$への写像。
$e:E×E\rightarrow F_q$

位数が全て素数$p$である３つの群を考える。
$G_1,G_2$を加法群,$G_e$を乗法群とする。
$P \in G_1$ と $Q \in G_2$をそれぞれ$G_1$,$G_2$の生成元とする。（つまり、$P$によって、$G_1$が,$Q$によって$G_2$が生成される）
ペアリング演算は以下の特性をもつ写像である。$e:G_1×G_2\rightarrow G_e$
- 双線形性： 全ての$a,b \in Z$に対して、$e(aP,bQ)=e(P,Q)^{ab}$
- 非退化： $e(P,Q) \neq 1$

$e(g^a,g^b) = e(g,g)^{ab}$
$e(HH(ax),HH(y)) = e(g^{ax},g^y) = e(g,g)^{axy} = e(g^x,g^{ay}) =e(HH(x),HH(ay))$

### Schwartz–Zippelの補題

$p(x_1,...,x_n) != 0, p \in F_p$を変数非ゼロ多項式とする。
$S$は$F_p$の有限部分集合。
$r_1,...r_n$を$S$から独立にランダムに選ぶ。すると
$Pr(p(r_1,...,r_n) = 0)\leq deg(p)/|S|$
となる。
これは多項式pの次元$deg(p)$をとり得る元の数$F_P$で割ったものである。
（つまり有限でない有理数で雑に$r$を$x+1$などで選んだ時、ほぼ０ということ）

これを応用すると、
n次多項式、$f(x),g(x) \in F_p$が同じか違うか判定できる。
多項式$f(s)$,$g(s)$に対してランダムにsを選び
$f(s)-g(s)=0$ かどうかで判定する。
ここでSchwartz–Zippelの補題を使うことで多項式 $p(s)=f(s)-g(s)$　が$f(s)\neq g(s)$の時０になってしまう確率=>　$p（x）=0$　(pの根になってしまう確率)は$deg(p)/|F_p|$となることがわかる。ここで次数より素数$p$がとても大きければ、ほぼ無視して良いことになる。

### 22) 線型写像
任意のベクトル$X,Y$とスカラー$c$について
$f(X+Y) = f(X) + f(Y), f(cX) = cf(X)$
を満たす写像$f$の事。
線形代数Iでやった。

### 23) 双線形写像
任意のベクトル$(x_1,x_2),(y_1,y_2)$とスカラー$c$について
$f(x_1+x_2,y_1) = f(x_1,y_1) + f(x_2,y_1), f(cx_1,y_1) = cf(x_1,y1)$
$f(x_1,y_1+y_2) = f(x_1,y_1) + f(x_1,y_2), f(x1,cy1) = cf(x_1,y_1)$
を満たす写像$f$の事。
$f(x_1+x_2,y_1+y_2) = f(x_1+x_2,y_1) + f(x_1+x_2,y_2)
= f(x_1,y_1) + f(x_2,y_1) +f(x_1,y_2) +f(x_2,y_2)$

## 24) Homomorphic Hiding(準同型ハイディング)
- $y=HH(x)$という関数において、$y$の値から$x$の値を推測する事ができない。一方向性
- 違う$x$を入れたら必ず違う$y$が出てくる $E(x)\neq E(y)(if\ x\neq y)$。単射性
- もし $E(x),E(y)$を知っているならば、それを用いた演算の答えを知る事ができる。$E(x+y)$の値は$E(x),E(y)$から計算可能

ゼロ知識証明ではこの性質が使える

$HH(x):=g^x$ はこの性質を持つ。以下は$HH(x):=g^x$とする
ここで$HH(1)$,$HH(s^1)$,$HH(s^n)$が与えられたとする。
当然、$s,...,s^n$ の値は一方向性から求められない。
しかし、$HH$に多項式　$P(x)=\sum_i c_i x^i$を入れた$HH(P(s))$ を入れた場合
$HH(P(s))=g^{\sum_i c_i s^i} = g^{c_1 s^1 + c_2 s^2 + ... + c_n s^n} = {g^{s^1}}^{c_1}{g^{s^2}}^{c_2}...{g^{s^n}}^{c_n} = \prod_i (g^{s^i})^{c_i} = \prod_i HH(s^i)^{c_i}$
つまり、$HH(P(s))= \prod_i HH(s^i)^{c_i}$　と変換すれば
$HH(1)$,$HH(s^1)$,$HH(s^n)$の値は知っているので、$s$の値がわからなくても$HH(P(s))$の値を出すことができる。

### 25) アリスとボブの例
まとめる

### 26) 原始根/モジュラー計算

$E(x)$の要素が$\{0,1,...,p-2\}$であり,$x \in Z_p^*$の時は

$E(x)=g^x$

は**Homomorphic Hiding**な関数となる。

- $y=E(x)=g^x$という関数において、$y$の値から$x$の値を推測する事ができない。
離散対数問題を解くのはむずかしいので成り立つ
- 違う$x$を入れたら必ず違う$y$が出てくる $E(x)\neq E(y)(if\ x\neq y)$
位数（$p-1$)のひとつ前なので全ての値は出るが、必ず違う値になる。
- もし $E(x),E(y)$を知っているならば、それを用いた演算の答えを知る事ができる。$E(x+y)$の値は$E(x),E(y)$から計算可能
$E(x+y)=g^{x+y\ mod\ p−1}=g^x\cdot g^y=E(x)\cdot E(y)$ で導出可能

## 27) Blind Evaluation of Polynomials(多項式のブラインド評価)

多項式の中身を伝える事なく、中身を知っていることを証明する事ができるしくみ。

Alice が次数$d$の多項式$P$を持ち、Bobが無作為に選んだ点$s \in F_p$を持っていると仮定する。
この時、Bobは$P$の内容を知る事なく$E(P(s))$を知る事ができる。

以下の特徴を持つ。
- **Blindness**:
AliceはBobから受け取った情報から入力$s$について知ることができない
BobはAliceから受け取った情報から$P$について知ることができない
- **Verifiability**:
Aliceが偽の$E(P(s))$を伝えた場合、BobはAliceの証明を受け入れない

これにより多項式をゼロ知識で伝達する事ができる。

## 28) Knowledge of Coefficient Test

Aliceが正しい$E(P(s))$を渡すことを強制したい。
$\alpha \in F_p^*$のとき、$a,b \neq 0$と $b = \alpha \cdot a$を満たすような$G$の元のペア$(a, b)$を$\alpha -pair$と呼ぶことにすると、KC Test は以下のように行われる（これは$b$の$\alpha$倍が$a$となるペア)

1. Bobはランダムな$\alpha \in F_p^*$と$a \in G$を選び、$b = \alpha \cdot a$を計算する
2. BobはAlice に$\alpha-pair(a, b)$を伝える
3. Aliceは異なる$a' \in G$を選び$\alpha-pair(a', b')$をBobに伝える
4. Bobは受け取った$(a', b')$が$\alpha-pair$かどうか検証する
Bob は$\alpha$ を知っているので、$b'=\alpha \cdot a'$を計算すれば良い

これを繰り返す。

## 29) Knowledge of Coefficient Assumption

Aliceは$\alpha$を知っているならばBobが受け入れ可能な$(a',b')$を簡単に作る事ができるが、$\alpha \cdot a$の値と$G$しか知らないため離散対数問題の難しさにより、$\alpha$を求めるのは大変。
どうする？

$\gamma \in F_p^*$ を用いて $(a', b')=(\gamma \cdot a, \gamma \cdot b)$を計算すればよい。このとき、
$b' = \gamma \cdot b = \gamma\alpha \cdot a = \alpha(\gamma \cdot a) = \alpha \cdot a'$
であり、$b' = \alpha \cdot a'$になっている

つまり、上の指向を繰り返す上で、Aliceが多くの場合において正しい$(a',b')$を返すならばAliceは$a' = \gamma \cdot a$となるような $\gamma$を知っているという事。

## 29) Extend Knowledge of Coefficient Assumption, Extend KCA
KCAを拡張する。

1. BobはAlice に*複数の*$\alpha-pair(a, b)$を伝える
3. Aliceは*複数の*$\alpha-pair(a, b)$を元に一つの$\alpha-pair(a', b')$をBobに伝える
4. Bobは受け取った$(a', b')$が$\alpha-pair$かどうか検証する

たとえば、２つの$\alpha-pair$、$(a_1,b_1),(a_2,b_2)$から作る場合、定数$c_1,c_2 \in F_p$をランダムに選んで、$(a′,b′)=(c_1\cdot a_1+c_2\cdot a_2,c_1\cdot b_1+c_2\cdot b_2)$のようにする。
この時$b′=c_1\cdot b_1+c_2\cdot b_2=c_1\cdot α\cdot a_1+c_2\cdot α\cdot a_2=α(c_1\cdot a_1+c_2\cdot a_2)=α\cdot a′$
なので、$(a', b')$は$\alpha-pair$となる。
これはつまりAliceは
$a′=c_1\cdot a_1+...+c_n\cdot a_n$となる$c_1,...,c_n \in F_p$の値を知っている = $a_1,a_2,...,a_n$ と $a'$ の線形関係を知っている
つまり多項式という形式にすれば**Aliceは知っている内容を開示せずにBobにその事実を証明することができる**

## 29) SAT 充足可能性問題
**充足可能性問題** とは
整数$n \geq 1$論理関数 $f: \{0, 1\}^n \to {0, 1}$ という関数 $f$ が充足可能関数か否かという問題。
$(x_1 \lor x_2 ) \land (x_1 \land \lnot x_2 ) \to 1$ になる$x_1,x_2$の値があるか。

### 論理関数
$f: \{false, true\}^n \to \{false, true\}$ への関数のこと
複数のBool値の積、和を取ったりして一つの結果にする。

その上で充足可能関数とは$f (a) = true$となるような$a$がある$f$。
ないものは充足不可能関数と呼ぶ。

**充足可能性問題** とは
整数$n \geq 1$論理関数 $f: \{0, 1\}^n \to {0, 1}$ という関数 $f$ が充足可能関数か否かという問題。

### 連言標準形(conjunctive normal form, CNF)/選言標準形(disjunctive normal form, DNF)

- 原子式：単一の命題変数・命題定数からなる論理式
- リテラル：原子式または原子式の否定
- 節： 有限個のリテラル$L_1,...,L_n$を$\lor$で結んだ形の論理式$L_1\lor...\lor L_n$
- 連言標準形: 有限個の節$C_1,...,C_n$を$\land$で結んだ形$C_1\land ...\land C_n$
- 選言標準形: 有限個の節$C_1,...,C_n$を$\lor$で結んだ形$C_1\lor ...\lor C_n$

それぞれの論理式について充足可能性問題を考える時 `CNF充足可能性問題 (CNF-SAT)` / `DNF充足可能性問題 (DNF-SAT)` と呼ぶ。
ここで `CNF充足可能性問題 (CNF-SAT)` は **NP完全である** 。
(`DNF 充足可能性問題` は多項式時間で解ける)

## 30) クラスP
「多項式時間アルゴリズムで解ける判定問題」全体の集合
指数時間ではない

#### 多項式時間アルゴリズム
計算時間が入力のサイズの多項式で抑えられるアルゴリズム

- 判定問題
yes か no かを答える問題, P は `true/false` か
てきなやつ。
- 最適化問題
最も「良い」値を求める問題
$f(x) = x^2 − 3x + 2$ が最小となる$x$を求めよ。
てきなやつ。
- 組合せ最適化問題
Group A, B からそれぞれn,m個選んだとき、価値が最大となる組み合わせを求めよ。
てきなやつ。

## 30) クラスNP
非決定性チューリングマシンによって多項式時間で解くことができる問題
効率的に解くアルゴリズムが見つかっていない判定問題の集合かつ、
その判定問題のYesとなる解が与えられたとき、それが本当に正しいのかを診断するのは多項式時間で済むような判定問題の集合
$P \subseteq NP$
ハミルトン閉路問題とかがこれにあたる。

#### 決定性/非決定性チューリングマシン(TM/NTM)
言語$L$を入力した時、出力される結果が一意に決まるなら決定。そうでないなら非決定。

#### 非決定性アルゴリズム
アルゴリズム中に「２択」を含む解法．２択は，可能な限り最終
的に “yes” が出るように選ばれる

#### 多項式時間変換
ある問題の入力から別の問題の入力を作る手順
• yes–no の値が変わらないようにする
• 変換を行う時間は入力の多項式で抑えられる

#### NP困難問題
NP に属する任意の問題がこの問題に多項式時間で変換できる（帰着できる）

#### NP完全問題
NP に属するNP困難問題

## 30) Quadratic Arithmetic Program(QAT)
算術回路をエンコードした多項式
$y = (x_1 + x_2) * x_3 + x_4$
を算術回路で表してみる。
これってただの逆ポーランド記法にして二分木にしただけでは？
$y = x_1\ x_2 +\ x_3\ *\ x_4\ +$

    y
    |
    + 
 |     |
x4     *
    |     |
    +    x3
  |   |
 x1  x2

それぞれのNodeからの出力に変数を当てる.
出力Edge

    y
    |c
    + 
 |     |b
x4     *
    |a    |
    +    x3
  |   |
 x1  x2

するとそれぞれは以下の等式がなりたつ =(制約がある？)

$x_1 + x_2 = a$
$a * x_3 = b$
$x_4 + b = c$

積は代入して式の数を減らす（式の数が多いと次元が増えるので良くない）

$(x_1 + x_2) * x_3 = b$
$x_4 + b = c$

$x_1,x_2,...x_n$ を $c_i$ に置き換える。

    y
    |c6
    + 
 |     |c5
c4     *
    |     |
    +    c3
  |   |
 c1  c2

$(c_1 + c_2) * c_3 = c_5$
$c_4 + c_5 = c_6$

$c_5$をゲート5
$c_6$をゲート6
と呼ぶ。この上でこの式を多項式で表す。

ここである多項式 $D(z), P(z), H(z)$ を考える。
この多項式は以下の制約を持つ
- $D(z)|P(z)$ 割り切れる。
- $\exists H(z)\cdot D(z)=P(z)$ ある適切な多項式$H$によって$P$となる。
- $\forall r_i D(r_i) = 0\Rightarrow P(r_i) = 0$

この制約を満たす時、
$\{c_1,c_2,...,c_n\}$ は良い状態(valid)

- $\forall c_n:\ c_n =c'_n1 \cdot c'_n2$ 積の評価値となる $c_n$ を取り出す。（上でいうと $c_5$ )
- 取り出した$c_n$ を元に、$D(z)$ を定義する。ここでは$D(z) = (z-c_5)$、ただ一般的には$D(z) = (z-c_5)(z-c_6)(z-c_7)...$ など積の評価値の数だけ増える。
- $P(z)$ を定義する。 ここでポイントは３つの多項式の組である。
$\{v_1(z),...v_m(z)\}$,$\{w_1(z),...w_m(z)\}$ ,$\{y_1(z),...y_m(z)\}$
それぞれは以下のルールで以下の値となる。

#### V(left inputs)
ここで $c_5$ が
$(c_1 + c_2) * c_3 = c_5$
のとき、左項は$(c_1 + c_2)$なので、$1$,$2$の項目　$v_1(z)$, $v_2(z)$が1になる。

||$Z=c_5$|
|:--|:--:|
|$v_1(z)$|1|
|$v_2(z)$|1|
|$v_3(z)$|0|
|$v_4(z)$|0|
|$v_5(z)$|0|
|$v_6(z)$|0|

#### W(rights inputs)
ここで $c_5$ が
$(c_1 + c_2) * c_3 = c_5$
のとき、右項は$c_3$なので、$3$の項目　$w_3(z)$が1になる。

||$Z=c_5$|
|:--|:--:|
|$w_1(z)$|0|
|$w_2(z)$|0|
|$w_3(z)$|1|
|$w_4(z)$|0|
|$w_5(z)$|0|
|$w_6(z)$|0|

#### Y(outputs)
ここで $c_5$ なので、$5$の項目　$y_5(z)$が1になる。

||$Z=c_5$|
|:--|:--:|
|$w_1(z)$|0|
|$w_2(z)$|0|
|$w_3(z)$|0|
|$w_4(z)$|0|
|$w_5(z)$|1|
|$w_6(z)$|0|

まとめると、 $c_5$は積の形なので、
$(\sum_i^m c_i v_i(z))(\sum_i^m c_i w_i(z))=(\sum_i^m c_i y_i(z))$ mはゲート数。
と表すことができ、移行すると
$P(z) = (\sum_i^m c_i v_i(z))(\sum_i^m c_i w_i(z)) - (\sum_i^m c_i y_i(z))$
となる。

ここでさっきの定義を当てはめると、
$D(c_5) = 0; P(c_5) = (c_1*c_2)(c_3)-c_5 = 0$
となる。
なお、ここで$P(z)$は$c_5$の時０になるので、$(z-c_5)$で割れる。
逆に$\prod_n (z-c_n)$ で $P(z)$ が割り切れるならば　$c_n$ は正しく回路内に位置している。

$\prod_n (z-c_n)$ で $P(z)$ が割り切れる。
=> $c_n$ は正しく回路内に位置している。
=> 元の多項式　$y = (x_1 + x_2) * x_3 + x_4$　を知っている。

## まとめ
ある多項式 $F$, 積の評価値の集合 $M$, それに対応する
$\{v_1(z),...v_m(z)\}$,$\{w_1(z),...w_m(z)\}$ ,$\{y_1(z),...y_m(z)\}$
があることを考える。
この時、それぞれの $c_1,c_2,...,c_m \in F_p$ が多項式 $F$ の正しい位置に存在しているとは
$t(z) = \prod_{n\in M} (z-c_n)$ で
$P(z) = (\sum_i^m c_i v_i(z))(\sum_i^m c_i w_i(z)) - (\sum_i^m c_i y_i(z))$
を割り切れる事と必要十分条件である。

ここで $c$ を２種類に分割する
- $c_1,c_2,...,c_n$: $F$ の入出力に対応する。例えば $F=(x_1+x_2)*x_3+x_4*x_5$ でいう $x_1,x_2,x_3,x_4,x_5$
- $c_{n+1},c_{n+2},...,c_m$: $F$ の中間値に対応する。例えば $F=(x_1+x_2)*x_3+x_4*x_5$ でいう $(x_1+x_2)*x_3,x_4*x_5$

そして$v$,$w$,$y$ も
$v_{io}(z) = \sum_i^n c_i v_i(z)$
$v_{mid}(z) = \sum_i^m c_i v_i(z)$,

$w_{io}(z) = \sum_i^n c_i w_i(z)$
$w_{mid}(z) = \sum_i^m c_i w_i(z)$,

$y_{io}(z) = \sum_i^n c_i y_i(z)$
$y_{mid}(z) = \sum_i^m c_i y_i(z)$,
に分ける。(`io` は入力値、 `mid` は中間地の$c$を使う)

### Setup
Prover,Verifierは
$\{v_1(z),...v_m(z)\}$,$\{w_1(z),...w_m(z)\}$ ,$\{y_1(z),...y_m(z)\}$
を共有しておく。
ここでポイントは、この$v$,$w$,$y$ は入力値 $z$, 出力値$y$ の値と関係ない。
なぜならそれぞれは二項演算子の左右の値、答えの値はどの $c$ かという情報しか持っていない。

### 証明の作成
ここで、Proverは$y=F(u)$となる$(y,u)$を知っているものとする。
- $h(x):=P(x)/t(x)$ (右項*左項 - 結果)/(x - 積の評価値)
- $v_{mid}(z) = \sum_i^m c_i v_i(z)$ 右項になる中間値
- $w_{mid}(z) = \sum_i^m c_i w_i(z)$ 左項になる中間値
- $y_{mid}(z) = \sum_i^m c_i y_i(z)$ 結果になる中間値
と、**$(u,y)$をVerifierに送る。**

### 検証
Verifierは次の検証をする
- $h(x)$が多項式であること($P(x)$は$t(x)$で割り切れる）
- $v_{mid}(z)$が$v_i(z)$の線型結合であること($\sum_i^m c_i v_i(z)$の形式)
- $w_{mid}(z)$が$w_i(z)$の線型結合であること
- $y_{mid}(z)$が$y_i(z)$の線型結合であること
次に $(y,u)$　を元に $v_{io}$,$w_{io}$,$y_{io}$を計算し,
$P(z) = (v_{io}(z) + v_{mid}(z))(w_{io}(z) + w_{mid}(z)) - (y_{io}(z) + y_{mid}(z))$
を算出。最後に
$P(z)=h(x)/t(x)$
を確認する。
これは単純にProverからの情報を受け取り、Verifierが算術回路を再構築して
正しいか確認する手順でしかない。

これをゼロ知識化していく。

### Bool to Arithmetic

$A, B, C \in {0,1}, f: (A,B) \to C$

|Bool|Arithmetic|
|:--|:--:|
|And|A*B|
|Or |(A+B)-A*B|
|NOT|1-A|
|XOR|(A+B)-2A*B|

信頼できる第三者が秘密の$s$をランダムに選び$HH(s^0),HH(s^1),...HH(s^n)$ を
提供する場合、Schwartz–Zippelの補題により、多項式$P(x)$,$Q(x)$が同じことを証明できる。

- Proverは $HH(P(s))$, $HH(Q(s))$を計算しVerifierに送る
- Verifierは受け取った$HH(P(s))$, $HH(Q(s))$、$HH(s^0),HH(s^1),...HH(s^n)$を元に、$HH(P(s))=HH(Q(s))$を検証する。

ここでProverが正しい$HH(P(s))$を渡すことを強制したい。
`Knowledge of Coefficient Test` が使える。

## 確率的検証可能証明 (Probabilistically Checkable Proofs,PCP)
まとめる

# SNARK コード

# Token、演算子, 数字, 変数がある
# ['234', '+', 'x', '=']
class Token:
  num = None
  ope = None
  var = None

  def __init__(self, n, s):
    self.num = n
    if s in opes:
      self.ope = s
    else:
      self.var = s
    
  def is_number(self):
    return self.num != None

  def  __str__(self):
    if self.num:
      return "{}".format(self.num)
    elif self.var: 
      return "{}".format(self.var)
    else: 
      return self.ope

# Nodeともいう
class Gate:
  left = None
  right = None  
  operand = None
  out = None
  def __init__(self, left: str, right: str, operand: str, out: str):
    self.left = left
    self.right = right
    self.operand = operand
    self.out = out 
    
  def __str__(self):
    return "{} {} {} = {}".format(
      self.left,
      self.operand,
      self.right,
      self.out
    )

## 1 数式をTokenize

# 簡単なやつ。
# f('x ^ 3 + x + 5 = 35') = ['x','^','3','+',...]
def tokenize(expr: str) -> List[Token]:
  ret = []
  
  n = ""
  expr += "."
  for i in expr:
    if i == " ":
      pass

    if i.isdigit():
      n += i

    if len(n) != 0:
      if not i.isdigit():
        ret.append(Token(int(n),None))
        ret.append(Token(None,i))
        n = ""
    else:
      ret.append(Token(None,i))

  ret.pop()
  return ret

## 2 Parse、算術回路化（ただの二分木）

# 本当はもっといい方法があるが、とりあえず "x*x*x"などのケース対応よう
def parse_pow(tokens: List[Token]):
  if len(tokens) == 1:
    return Node.make_leaf(tokens[0])
  for i in range(len(tokens)):
    if tokens[i].ope == "*":
      left = parse(tokens[0:i])
      right = parse(tokens[i+1:])
      return Node.make_node(tokens[i], left, right)

def parse(tokens: List[Token]):
  if len(tokens) == 1:
    return Node.make_leaf(tokens[0])
  elif len(tokens) == 3:
    l = Node.make_leaf(tokens[0])
    r = Node.make_leaf(tokens[2])
    return Node.make_node(tokens[1], l, r)
  else:
    for i in range(len(tokens)):
      if tokens[i].ope == "+":
        left = parse(tokens[0:i])
        right = parse(tokens[i+1:])
        return Node.make_node(tokens[i], left, right)

    # case like x*x*x
    return parse_pow(tokens)

     x
       *-c2
x
  *-c1
x
            +-c4
     x
       +-c3
     5

https://github.com/MizukiSonoko/study-zk

## 参考
https://e-words.jp/w/%E9%9B%A2%E6%95%A3%E5%AF%BE%E6%95%B0%E5%95%8F%E9%A1%8C.html
https://www.alchemy.com/overviews/snarks-vs-starks
https://cs251.stanford.edu/lectures/lecture13.pdf
https://zenn.dev/senk/articles/c12206d0709fcbd41e39
https://medium.com/acompany/%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF%E3%83%81%E3%82%A7%E3%83%BC%E3%83%B3%E3%81%A7%E4%BD%BF%E3%82%8F%E3%82%8C%E3%81%A6%E3%81%84%E3%82%8B%E6%9A%97%E5%8F%B7%E3%81%AE%E8%A7%A3%E8%AA%AD%E5%9B%B0%E9%9B%A3%E6%80%A7%E3%81%AE%E6%A0%B9%E6%8B%A0%E3%81%A8%E3%81%AA%E3%82%8B%E9%9B%A2%E6%95%A3%E5%AF%BE%E6%95%B0%E5%95%8F%E9%A1%8C%E3%82%92%E3%81%96%E3%81%A3%E3%81%8F%E3%82%8A%E7%90%86%E8%A7%A3%E3%81%99%E3%82%8B-b0612b6d256c
https://hazm.at/mox/security/public-key/discrete-logarithm-problem/index.html
https://pebble8888.hatenablog.com/entry/2017/06/10/231249
https://www.cryptrec.go.jp/exreport/cryptrec-ex-2602-2016.pdf
http://lupus.is.kochi-u.ac.jp/shiota/misc/InfinityPoint/InfinityPoint.html

もっと読む
https://tex2e.github.io/blog/crypto/point-of-elliptic-curve-over-GF

https://www.tj.chiba-u.jp/~wkishi/bilinear1.html
https://hazm.at/mox/security/public-key/pairing/index.html
https://www.zeroknowledgeblog.com/index.php/the-pinocchio-protocol/homomorphic-hiding
https://qiita.com/nrnrk/items/693e0444f528ef6aa6b3
https://electriccoin.co/blog/snark-explain2/
https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-2-blind-evaluation-of-polynomials-ed9e3cd11bc1
https://medium.com/returnvalues/zk-snarks-%EA%B8%B0%EC%B4%88-4-how-to-make-blind-evaluation-of-polynomials-verifiable-e914e4e55be5
https://www.zeroknowledgeblog.com/index.php/the-pinocchio-protocol/knowledge-of-coefficient

https://kyopro.hateblo.jp/entry/2019/01/08/091302
http://www2.kobe-u.ac.jp/~ky/complexity/chap1.pdf
https://daigakudenki.com/np-hard/
https://zenn.dev/airev/articles/airev-quantum-03
http://www2.yukawa.kyoto-u.ac.jp/~kanehisa.takasaki/edu/logic/logic4.html
https://coders-errand.com/constraint-systems-for-zk-snarks/
https://www.di.ens.fr/~nitulesc/files/slides/QAP.pdf
https://tasusu.hatenablog.com/entry/2014/10/30/210828
https://hooktail.sub.jp/algebra/Homomorphic/