# ゼロ知識証明を学ぶ

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

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

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

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

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

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

## 2-3) ゼロ知識証明の特性

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

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

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

## 2-4) 例題、洞窟の問題
ゼロ知識証明を調べようとすると出てくるやつ。
ここからどうやって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は鍵を持っていると納得しているので
ゼロ知識証明である事がわかる。

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

# 技術的な話
## 3) 離散対数問題（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$)を求めるのは難しい、という事。

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

## 4) 離散対数問題に登場する要素
### 4-1) 剰余演算(モジュラー計算)
$a\ mod\ b = c$
整数$a$を$b$で割った値が$c$であるという事。

$mod\ p$というのは、「素数 **p**で割った余りだけを考える」と言う事、つまり $0$ ~ $p-1$ の数字だけ登場する。
例えば、「mod 7」の場合。0, 1, 2, 3, 4, 5, 6 の 7 つの数が存在する。
$7\ mod\ 3 = 1$ ($7 = 3*2 + 1$)
$17\ mod\ 7 = 3$ ($17 = 7*2 + 3$)
(時計は$mod\ 12$)

### 4-2) 剰余演算と冪乗
べき乗を$mod\ p$で行う。

【2 の場合 (mod 7)】
$$
\begin{eqnarray}
2\equiv1\ ≡ 2 (mod 7) \\
2^2 = 2 × 2 = 4 ≡ 4 (mod 7) \\
2^3 = 4 × 2 = 8 ≡ 1 (mod 7) \\
2^4 = 1 × 2 = 2 ≡ 2 (mod 7) \\
2^5 = 2 × 2 = 4 ≡ 4 (mod 7) \\
\end{eqnarray}
$$
$2, 4, 1$ の数字がループしている。

【3 の場合 (mod 7)】
$$
\begin{eqnarray}
3 ≡ 3 (mod 7) \\
3^2 = 3 × 3 = 9 ≡ 2 (mod 7) \\
3^3 = 2 × 3 = 6 ≡ 6 (mod 7) \\
3^4 = 6 × 3 = 18 ≡ 4 (mod 7) \\
3^5 = 4 × 3 = 12 ≡ 5 (mod 7) \\
3^6 = 5 × 3 = 15 ≡ 1 (mod 7) \\
3^7 = 1 × 3 = 3 ≡ 3 (mod 7) \\
\end{eqnarray}
$$

全ての数字が登場して、初めて「1」に戻るまで 6 回 ($p-1$回)登場する。
つまり、冪乗した場合二つのパターンが存在している。

### 4-3) 原始根

素数$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) \\
2^{12}\equiv1\ (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$ (p: prime number)において、原始根は必ず存在する)

原始根は、$mod p$の世界の数 (0 を除く) を **全部作り出せる生成機(generator)** のようなものなのでそう呼ばれる。

### 4-4) 位数（周期）
$p$で割ったあまりが１になる時の指数のこと。
上でいうと$2(mod 7)$ の場合$3$、$2(mod 13)$の場合$12$。
$2^{3}\equiv1\ (mod\ 7)$
$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}$ の時あまりが１となる。
なお、その後は同じ値が繰り返し出てくる。

### 4-5) 巡回群
群$G$有限個の元$a_1,a_2,...,a_m$で生成(構成)されるとき、$G$を $\langle a_1,a_2,...,a_m\rangle$と書く。
なお、単一の元で生成される時
$G = \langle a \rangle = \{a^i|i∈Z\}$
と書く。
例えば $G = \langle 2 \rangle = \{2,4,8...\}$

### 4-6) 生成
群$G$がその部分集合$S$で生成されるとき、$S$を$G$の生成系とよぶ．この
とき$S$は$G$を生成するともいう。
つまり、群$G=\{1,2,...,12\}$の時、「$２$ をかける＆modをとる」のみを使って$2^1\ mod\ 13,2^2\ mod\ 13,...,2^{12}\ mod\ 13$ 表す事ができるので$S=\langle 2 \rangle$を$G$の生成元と呼ぶ。
なお、一つの要素だけで群$G$の全ての要素を生成できる場合、その特別な元のことを「生成元」と呼ぶ。

**生成系**：あるグループ数から$G$の要素全てを生成できる
**生成元**：ある数から$G$の要素全てを生成できる
「2 は 群 G (mod 13 の乗法群) の生成元である」

「mod p の原始根」＝「mod p の乗法群における生成元」となる。

## 5) 群・環・体
そもそも上で出てきた「群」とは何かについて触れる
### 5-1) 群
- 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を満たす時、**アーベル群**と呼ぶ。

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

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

### 5-3) 群、環の比較
- 群の一般的な定義：ある集合とその上で定義された**一つ**の二項演算について定義している（その演算が加法、乗法などになる）
- 群の一般的な定義：**二つ**の演算（加法と乗法）とその関係性を定義している（加法についてアーベル群、乗法について半群、分配法則が成り立つ）

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

言い換えると
- 足し算・引き算ができる(群)
- 掛け算ができる(群)
- 割り算ができる（0を除く) (new)
- 交換法則,結合法則,分配法則 (環)

を満たす。

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

### 5-5) 有限体(ガロア体)
位数の数が有限の体
演算終わったあと位数で割ったあまりが元となる。
$c=a⋅b\ mod\ p$
要素（数）の個数が有限個なのに、四則演算が矛盾なくできる体（体の定義を満たす）

例として、素数$p$を使った$mod\ p$の世界 ${0, 1, ..., p-1}$は、四則演算が定義できるので「体」になる。加えて要素数が$p$個で有限なので、「有限体」となる。この場合 $GF(p)$ とも書く。

## 6) 楕円曲線

$y^2 = x^3 +ax+b$ で表され点の集まり。

### 6-1) 楕円曲線 （$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$
この式で表される曲線の事。

### 6-2) 有限体$F_p$上の楕円曲線
$y^2=x^3+ax+b$ を満たす$(x,y) x, y ∈ F_p$全体の集合。
ポイントは
- 方程式の文字は$F_p$の数: $x,y,a,b$ はすべて、$\{0, 1, ..., p-1\}$ のどれかとなる。
- 計算は全て$mod\ p$の中でおこなう。

$y^2=x^3+ax+b\ (mod\ 5)$を考える
$$
\begin{align}
&x=0: y^2 ≡ 0^3 +0+1=1(mod5). y^2 =1 となるのは y=1,4 よって点(0, 1), (0, 4) \\
&x=1: y^2 ≡ 1^3 +1+1=3(mod5). y^2 =3 となるのは無いため解なし \\
&x=2: y^2 ≡ 2^3 +2+1=11≡1(mod5). y^2 =1 となるのは y=1,4 よって点(2, 1), (2, 4) \\
&x=3: y^2 ≡ 3^3 +3+1=31≡1(mod5). y^2 =1 となるのは y=1,4 よって点(3, 1), (3, 4) \\
&x=4: y^2 ≡ 4^3 +4+1=69≡4(mod5). y^2 =4 となるのは y=2,3 よって点(4, 2), (4, 3) \\
\end{align}
$$
これに無限遠点$O$ を加えたものが $F_p(5)$ 構成する全ての点である。
なお、この楕円曲線においても足し算は定義されており、点$P$と点$Q$(どちらも$F_p$上の楕円曲線上の点) を足すと、必ず結果も同じ$F_p$上の楕円曲線上の点$R$になる。

### 6-3) 無限遠点
アーベル群の単位元$O$の事

### 6-4) アフィン変換
幾何学における基本的な変換の一つ。
ベクトル空間における線形変換（回転、拡大縮小、せん断など、原点を動かさない変換）に平行移動を加えたもの。
数式では $f(x)=Ax+b$ と表される（x,b はベクトル、 A は行列）。
特徴として、直線を直線に移し、平行な線を平行な線に移す。（点の間の比率も保たれる）。
楕円曲線の文脈では、主に同型写像 (isomorphism) を定義する際に使われる。例えば、体$K$上の二つの楕円曲線$E_1$,$E_2$が同型であるとは、特定の形式のアフィン変換によって互いに移り合う関係にあると言う事。

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

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

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

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

安全性と効率性: ECDLP は、有限体$F_p$上の通常の離散対数問題 (DLP) よりも、同じくらいの安全性を達成するためにより短い鍵長で済むとされている。つまり、より効率的で安全な暗号システム（鍵共有、署名、暗号化など）を構築が可能。これが、ビットコインをはじめとする多くの現代暗号で楕円曲線が使われている理由らしい。

## 7) 「楕円曲線上の離散対数問題 (ECDLP)」を使った暗号。

共通の準備
これらの方式を使う前に、アリスとボブ（そして関係者全員）は、使用する「楕円曲線のパラメータ」を共有しておく必要がある。
- 楕円曲線: $E: y^2 =x^3 +ax+b$ の係数 $a, b$
- 有限体 $Fp$: どの$mod\ p$で計算するかを決める素数$p$
- ベースポイント $G$: 曲線上の点のひとつで、全ての計算の基準となる点
- 位数 $n$: $G$をn回足すと初めて無限遠点$O$に戻るような整数$n$($G$によって生成される部分群の位数）

これらは公開情報である。

### 7-1) 楕円曲線　Diffie-Hellman鍵共有 (ECDH)
**目的**: 安全でない通信路（インターネットなど）を使って、アリスとボブが二人だけの共通の秘密の鍵を作り出すこと。盗聴されても大丈夫なものとする。
仕組み:
- 秘密の選択:
アリスは秘密の整数 $d_A$ をランダムに選ぶ。
ボブは秘密の整数 $d_B$ をランダムに選ぶ。
公開鍵の計算と交換:
- 1) アリスは自分の公開鍵 $P_A = d_A G$ (G を $d_A$ 回足す) を計算し、ボブに送る。
- 2) ボブは自分の公開鍵 $P_B = d_B G$ (G を $d_B$ 回足す) を計算し、アリスに送る。
- 3) 共通鍵の計算:
アリスは、ボブの公開鍵 $P_B$ と自分の秘密鍵 $d_A$ を使って、$K=d_A P_B = d_A ( d_B G) = (d_A d_B ) G$ を計算する。
ボブは、アリスの公開鍵 $P_A$ と自分の秘密鍵 $d_B$ を使って、$K=d_B P_A = d_B ( d_A G) = (d_B d_A ) G$ を計算する。
- 4) 結果: アリスとボブは、お互いの秘密鍵 ($d_A,d_B$)を相手に知らせることなく、同じ点 $K$ (共通の秘密鍵として利用できる) を計算できた。

**安全性**: 盗聴者が公開鍵 $P_A (=d_A G),P_B (=d_B G)$ を傍受しても、ECDLP が困難なため、秘密鍵 $d_A,d_B$ を計算できない。したがって、共通鍵 $K=(d_A d_B) G$ も計算できない。
**例え** : アリスとボブがそれぞれ秘密の色（秘密鍵）を選び、みんなが知っている共通のベースの色（G）と混ぜて公開色（公開鍵）を作って交換する。受け取った相手の公開色と自分の秘密の色を混ぜると、不思議と同じ「秘密の最終色」（共通鍵）が出来上がるイメージ。盗聴者は途中の公開色を見ても最終的な色は作れない。

### 7-2) 楕円曲線　ElGamal 暗号 (EC-ElGamal)
**目的**: アリスがボブに秘密のメッセージを送りたい場合に使う公開鍵暗号方式。ボブの公開鍵で暗号化し、ボブだけが自分の秘密鍵で復号できるようにする。
仕組み:
- 鍵生成 (受信者ボブ):ボブは秘密鍵となる整数 $d_B$ をランダムに選ぶ。
- ボブは公開鍵 $P_B = d_B G$ を計算し、公開する。
- 暗号化 (送信者アリス): アリスは送りたいメッセージ $M$を楕円曲線上の点 $P_M$ に変換する (※)。
- アリスは一時的な乱数 k を選ぶ。アリスは暗号文として、2つの点のペア $(C_1,C_2)$ を計算する。
$C_1 =kG$
$C_2 =P_M + kP_B$ (メッセージ点に、乱数 k とボブの公開鍵を掛けた点を足す)
- アリスは $(C_1,C_2)$ をボブに送る。
- 復号 (受信者ボブ): ボブは受け取った暗号文 $(C_1,C_2)$ と、自分の秘密鍵 $d_B$ を使う。
- $C_2$ から $d_B C_1$ を引き算する
$C_2 - d_B C_1 = (P_M + kP_B ) - d_B(kG)$
$= P_M + k (d_B G) - d_B k G$
$= P_M + k P_B - k P_B = P_M$

元のメッセージ点 $P_M$ が復元できるので、そこからメッセージ M を取り出す (※)。
安全性: 盗聴者がボブの公開鍵 $P_B,(C_1,C_2)$ を傍受しても、ボブの秘密鍵 $d_B$ やアリスが使った乱数 $k$ を知ることは困難 (ECDLP) なため、元のメッセージ$P_M$を復元できない。
例え: ボブだけが開けられる特別な南京錠（公開鍵 $P_B$）がついた箱がありある。アリスはメッセージ（$P_M$)を箱に入れ、一時的な合鍵（$k$）を使って作った別の情報（$C_1=kG$）と一緒に送る。ボブは自分の秘密の鍵（$d_B$）で箱（$C_2$)を開け、一緒に送られてきた情報（$C_1$）を使うことで、メッセージを取り出すことができる。

(※) メッセージ M を点 P_M にしたり、点 P_M から M に戻したりする具体的な方法は少し複雑だが、標準的な方法が存在する。

### 7-3) 楕円曲線　DSA (ECDSA)
**目的**: アリスが送ったメッセージが、確かにアリス本人によって作成され、途中で改ざんされていないことをボブが確認できるようにするためのデジタル署名方式。
仕組み:
- 鍵生成 (署名者アリス): アリスは秘密鍵となる整数 $d_A$ をランダムに選ぶ。アリスは公開鍵 $P_A = d_A G$ を計算し、公開する。（検証者はこれを使う）
- 署名生成 (アリス):アリスは送りたいメッセージ $m$ のハッシュ値 $e=H(m)$ を計算する ($H$ は $SHA-256$ などのハッシュ関数)。
アリスは一時的な乱数 k を選ぶ。
$kG=(x_1,y_1)$ を計算し、$r=x_1 (mod\ n)$ とする。($n$は$G$の位数)
$s=k^{−1}(e+rd_A)\ (mod\ n)$ を計算する ($k^{-1}$)は$k$の$mod\ n$での逆元)。
署名はペア$(r,s)$。アリスはメッセージ$m$と署名$(r,s)$をボブに送る。
- 署名検証 (ボブ): ボブは受け取ったメッセージ $m'$ と署名 $(r′,s′)$ を使う。
メッセージ $m'$のハッシュ値 $e′=H(m′)$ を計算する。
$w=(s′)^{−1}\ (mod\ n)$を計算する。
$u_1=e′ w\ (mod\ n)$と
$u_2=r′ w\ (mod\ n)$ を計算する。
点 $X=u_1 G+u_2 P_A$ を計算する ($P_A$ はアリスの公開鍵)。
$X=(x_1',y_1') $とし、$v=x_1'\ (mod\ n) $を計算する。
もし $v=r′$ であれば、署名は有効と判断する。そうでなければ無効。

安全性:アリスの秘密鍵 $d_A$ を知らない第三者が、有効な署名$(r,s)$を偽造することは非常に困難。
有効な署名$(r,s)$とメッセージ$m$から、アリスの秘密鍵 $d_A$ を計算することも困難でもある (ECDLP)。

### 7-4) まとめ
- **ECDH**: 安全な鍵共有。
- **EC-ElGamal**: 安全なメッセージの暗号化・復号（公開鍵暗号）。
- **ECDSA**: メッセージの認証（本人が作った）と完全性（改ざんされていない）の保証（デジタル署名）。

## 8) 準同型ハイディング (Homomorphic Hiding, HH)
準同型ハイディング、数字を「隠す」（秘匿する）ための関数である。ただ隠すだけでなく、隠された状態のままでも、元の数字に対する計算（例えば足し算）ができるという、非常に便利な性質を持つ。

HHが持つべき性質
- 一方向性 (Hiding): 関数 $y = HH(x)$ から、元の値 $x$ を推測することは非常に困難であること。
- (加法) 準同型性 (Homomorphism): $HH(x)$ と $HH(y)$ があれば、それらを使って $x$ と $y$ の和 $x+y$ に対応する隠された値 $HH(x+y)$ を計算できること。
- 単射性: 異なる $x$ は異なる $HH(x)$ に対応すること ($x \neq y \implies HH(x) \neq HH(y)$)。
具体例: $HH(x) = g^x$
有限体 $\mathbb{F}_p$ 上の原始根（または群の生成元） $g$ を使うと、$HH(x) = g^x \pmod p$ は準同型ハイディングのいい一例となる。
- 一方向性: $y = g^x \pmod p$ から $x$ を求めるのは離散対数問題 (DLP) であり、困難。
- 準同型性: $HH(x+y) = g^{x+y} = g^x \cdot g^y = HH(x) \cdot HH(y)$。つまり、元の数の「足し算」が、HH後の「掛け算」に対応する

応用：多項式の値を隠したまま計算する
次数 $d$ の多項式 $P(x) = c_0 + c_1 x + c_2 x^2 + ... + c_d x^d$ を考える。
ある秘密の値 $s$ があり、この $s$ を相手に知られずに、$P(s)$ の値を計算して、それを隠した値 $HH(P(s))$ を得たいとする。
もし、$HH(1), HH(s), HH(s^2), ..., HH(s^d)$ の値（これらは $g^1, g^s, g^{s^2}, ..., g^{s^d}$）が事前に分かっている（または計算できる）なら、次のように $HH(P(s))$ を計算が可能。
$P(s) = \sum_{i=0}^d c_i s^i$ なので、
$HH(P(s)) = HH(\sum_{i=0}^d c_i s^i)$
ここで $HH(x)=g^x$ を使うと、
$$
g^{P(s)} = g^{\sum_{i=0}^d c_i s^i} = g^{c_0 s^0 + c_1 s^1 + ... + c_d s^d}
$$
指数法則(指数間の足し算は積に分解可能) により、
$$= (g^{s^0})^{c_0} \cdot (g^{s^1})^{c_1} \cdot ... \cdot (g^{s^d})^{c_d}$$
$$= HH(s^0)^{c_0} \cdot HH(s^1)^{c_1} \cdot ... \cdot HH(s^d)^{c_d}$$
$$= \prod_{i=0}^d HH(s^i)^{c_i}$$
$$HH(P(s))= \prod_i HH(s^i)^{c_i}$$　

つまり、$HH(1), HH(s), ..., HH(s^d)$ の値を知っていれば、秘密の $s$ を知らなくても、$P(s)$ を隠した値 $HH(P(s))$ を計算ができる。

なお、$HH(x)=g^x$ のような準同型ハイディングは、元の数の「足し算」をHH後の「掛け算」に対応させることができるが、元の数の「掛け算」の結果（例えば $HH(x \cdot y)$）を $HH(x)$ と $HH(y)$ から直接計算するのは一般的に困難。

## 9) ペアリング

ペアリングの役割:
準同型ハイディングだけでは扱いにくかった、HH後数同士の「掛け算」に関する関係を扱えるようにするのがペアリングである。
楕円曲線上の２点から有限体$F_p$への写像へ変換する。
$e:E×E\rightarrow F_q$
ペアリング関数$e$は$E_1$から点$P$を,$E_2$から点$Q$を取ってきてペアにし、$G_T$の要素$e(P,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}$
- 非退化性 (Non-degeneracy)： $e(P,Q) \neq 1$

$e(g^a,g^b) = e(g,g)^{ab}$
入力側の「足し算のスカラー倍」が、出力側の「掛け算のべき乗」となる。

### 9-1) 準同型ハイディングの場合。
準同型ハイディング $HH(x)=g^x$ とした場合のペアリングを考える。$g$は$G_1,G_2$ の生成元
$e(HH(ax),HH(y)) = e(g^{ax},g^y) = e(g,g)^{axy} = e(g^x,g^{ay}) =e(HH(x),HH(ay))$
これは
$P = HH(x) = g^x$, $Q = HH(y) = g^y$
のケースである。
$e(HH(ax), HH(y))$ : ペアリングの入力として、指数が$ax$と$y$であるような $G_1,G_2$の元を考える。
$e(g^{ax},g^y) = e(g,g)^{axy}$ 双線形によりこのように変換できる。
$e(g^x,g^{ay})=e(g,g)^{x(ay)}=e(g,g)^{axy}= e(g^x,g^{ay})=e(HH(x), HH(ay))$

利点：もし誰かが$HH(x),HH(y),HH(ax),HH(ay)$という4つの値（これらは$g^x,g^y,g^{ax},g^{ay}$）を提示してきたら、ペアリング$e$を使って両辺を計算し、それらが等しいかどうかを検証することができる。
重要なのは、この検証には元の秘密の値$a,x,y$や生成元$g$を知る必要がなく、$HH(X)$の値だけあれば十分。
**これは、「ある値$A(=HH(ax))$と$B(=HH(y))$のペア」と「別の値$C(=HH(x))$と$D(=HH(ay))$のペア」の間に、ペアリングを通じて特定の数学的関係 $axy$(全ての数の積) が成り立っていることを、秘密の情報$(a,x,y)$を明かすことなく検証できることを意味する。**

例：ある人が $a,x,y$ を知っているが、その中身は秘密である。
本当に $axy$ と言う関係性を持つ、$a,x,y$ を知っているのか、正しい手順で$A,B、C、D$を生成したのかを確かめたい。

証明者が正直に、元となる秘密の数字 a,x,y を使って、
定められた手順通りに（A=HH(ax),B=HH(y),C=HH(x),D=HH(ay) という風に）、
一貫性を持って 4 つの数を作ったかが判断できる。

Memo:
- HHの特性, $HH(x), HH(y)$があれば,$x,y$を知らなくても$HH(x+y)$が計算で求められる。
- ペアリングの特性, $(HH(x), HH(ay))$ と $(HH(x), HH(ay))$ を同じものと扱えるため
比較することで、x,a,y の値がわからない状態で結果の正しさが検証できる。

### 9-2 appendeix) 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$がとても大きければ、ほぼ無視して良いことになる。

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

### 9-4 appendeix) 双線形写像
任意のベクトル$(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)$

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

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

$E(x)=g^x$

は**Homomorphic Hiding** (HH) な関数となる。

- $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(多項式のブラインド評価)
HH、ペアリング、SZ補題などで隠された値同時の和・積が正しい事が証明できた。
多項式の中身を伝える事なく、中身を知っていることを証明する事ができるしくみ。

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の証明を受け入れない

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

### 10-1) Knowledge of Coefficient Test

Aliceが正しい$E(P(s))$を渡すことを強制したい。
$\alpha \in F_p^*$のとき、$a,b \neq 0$と $b = \alpha \cdot a$を満たすような$G$の元のペア$(a, b)$ 例えば $(g^x,g^{\alpha x})$。を$\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'$を計算すれば良い

これを繰り返す。

### 10-2) 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$を知っているという事。
Alice がαを知らずにテストをクリアする方法は、本質的にこのγを使う方法しかないだろう、という考え方。
つまり、与えた数を正しい比率で計算して返却できる = 係数を知っている。

## 10-3) Extend Knowledge of Coefficient Assumption, Extend KCA
KCAを拡張する。複数のペア$(a_1,b_1)...(a_n,a_b)$を Alice に送り、それらの「線形結合」で作られた新しい α-pair $(a',b')$を返すように要求する。

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′$
$b' = \Sigma c_i b_i = \Sigma c_i (\alpha b_i) = \alpha (\Sigma c_i b_i) = \alpha 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にその事実を証明することができる**

## 11) P
問題(Problem)とは，次を定めることで記述される
- 入力 ：アルゴリズムが何を受け取るのか
- 出力 ：アルゴリズムが何をもたらすのか
- 条件 ：出力が満たすべき性質は何なのか
- 評価：出力の良さをどのように測るのか

その上で、問題$P$を解くアルゴリズム$A$があるとして、その複雑性によってクラスが変わってくる。複雑性とは $A$の実行にかかる計算資源=「実行時間」の量のこと。「Pの複雑性」＝問題を解く最適なアルゴリズムの複雑性。

計算量理論におけるPとは、多項式時間(Polynomial time)で解ける判定問題の集合の事。

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

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

- 判定問題
yes か no かを答える問題, P は `true/false` か。てきなやつ。

### 11-2) クラスNP(Non-deterministic Polynomial)
効率的に解くアルゴリズムが見つかっていない判定問題の集合かつ、
その判定問題のYesとなる解が与えられたとき、それが本当に正しいのかを診断するのは多項式時間で済むような判定問題の集合
$P \subseteq NP$
P = NP か？は未解決。

非決定性チューリングマシンによって多項式時間で解くことができる問題。
ハミルトン閉路問題とかがこれにあたる。

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

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

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

## 12) 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$の値が最低一つでもあるか。

### 12-1) 論理関数
$f: \{false, true\}^n \to \{false, true\}$ への関数のこと
複数のBool値の積、和を取ったりして一つの結果にする。
=> いくつかの$True / False$ の問題の答えの組み合わせによって、最終的に一つの$True / False$の結論に帰着するもの。

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

**充足可能性問題** とは
整数$n \geq 1$論理関数 $f: \{0, 1\}^n \to {0, 1}$ という関数 $f$ が充足可能関数か否かという問題。
例えとして
$f(x_1, x_2) = x_1 \land x_2$は充足可能。
$f(x_1) = x_1 \land (\lnot x_1)$は充足不可能。

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

- 基本部品 ($x_1$) や、その否定 ($\lnot x_1$)
- 原子式：単一の命題変数・命題定数からなる論理式
- リテラル：原子式または原子式の否定
- 節： 有限個のリテラル$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 充足可能性問題` は多項式時間で解ける)

## 13) Quadratic Arithmetic Program(QAT)

コンピュータが行う任意の計算が「正しく」実行されたことを証明するために、
その計算の正しさを「ある多項式 P(z) が 別の多項式 t(z) で割り切れるか？」という、多項式の問題に変換するための仕組み。
コンピュータの計算は、たとえ複雑に見えても、内容は単純な足し算や掛け算のステップ（ゲート）の組み合わせである。
計算全体が正しいことを証明するには、本来、これら一つ一つのステップがすべて正しく行われたかを確認する必要があるが、コストが大きすぎるQAPを使うと多項式の割り算で検証できるのでとても有益。

手順
### 13-1) 計算を回路に変換
TLAのように実行するコードを算術回路に変換する。
算術回路を多項式にする。
$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になる。
積の左側の部分に 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になる。
積の右側の部分に 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になる。
積の結果に 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$　を知っている。
つまり式を一つの木として見た時、それぞれの計算はどの位置にあるかを割り算で確認でき、
全てで正しく割り切れる＝正しい。と判断できる。

### 13-2) まとめて考える
ある多項式 $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$を使う)

#### 13-3) 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$ かという情報しか持っていない。

#### 13-4) 証明の作成
ここで、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に送る。**

#### 13-5) 検証
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が算術回路を再構築して
正しいか確認する手順でしかない。

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

## 14) QAP 検証をゼロ知識化する手順

13の検証手順では、Prover が計算の内部情報（$h(z)$や中間値多項式$u_{mid},y_{mid}$をVerifier に送る必要があり、ゼロ知識ではなかった。ここからは、これをゼロ知識化していく。
これには、これまで学んだ暗号学的なツールを組み合わせていく必要がある

- 準同型ハイディング (HH): 値を隠した状態で演算(足し算）できる関数 $HH(x)$。
- ペアリング: 隠された値の間の「掛け算の関係」をチェックできる算 $E(P,Q)$。
- KCA (係数の知識の仮定): 多項式において、正しい係数を使ったことをチェックできる
- SZ補題: 多項式の等式チェックを一点での評価に置き換える。

### 14-0) 信頼された設定 (Trusted Setup)
- 秘密の選択: 信頼できる誰か（または複数人による分散計算）が、誰も知らない秘密のランダムな値$s$や$α$などを選ぶ。
- CRS の生成: これらの秘密の値を使って、たくさんの「暗号化された値」を計算する。この値は準同型ハイディング$E$を使って隠されている。（d は多項式の最大次数）。
${E(s^0),E(s^1),E(s^2),...,E(s^d)}$ （計算時に使う単位的なもの）
${E(αs^0),E(αs^1),E(αs^2),...,E(αs^d)}$　（チェック時につかう）
- 秘密の破棄: CRS を生成したら、元の秘密$s$や$α$は完全に破棄され、誰も知ることができなくない状態にする
- CRS の公開: 生成された CRS は公開され、Prover と Verifier の両方が利用できるようにする。
- なお $(計算の入力u,出力y)$ は公開されている

### 14-1) 証明の作成 (Prover の作業)
Prover は計算$y=F(u)$を行い、その計算途中の正しさゼロ知識で証明するために以下を行う。
- 通常計算: まず、以前と同様に式を分解し、全ての値の割り当て$c_i$ (公開$c_{i,o}=(u,y)$と秘密$c_{mid}$) を取得する。
- 多項式計算: $L(z),R(z),O(z),P(z),H(z)=P(z)/t(z)$を計算する。
- 情報を隠して評価: $H(z)$や$L_{mid},(z)$などを直接送る代わりに、CRSを使ってこれらの多項式を秘密の点$s$で評価し、その結果を準同型ハイディング$E$で隠す。
Prover は$CRS$の$E(s_i)$と$H(z)$の係数を使って、$E(H(s))$を計算する。（HH の準同型性を利用）
同様に、CRS の$E(s_i)$と$L_{mid}(z),R_{mid}(z),O_{mid}(z)$の係数を使って、$E(L_{mid}(s)),E(R_{mid}(s)),E(O_{mid}(s))$ を計算する。 さらに、KCAに基づくチェックに必要な、$α$を含む隠された値（例: $E(αL
_{mid}(s)$) など）も計算しておく。
- 証明 (Proof) の作成: これらの計算結果（$E(H(s)$)や$E(L_{mid}(s)$) など、暗号化された評価値のセット）をまとめて「証明 (Proof)」として Verifier に送る。

### 14-2) 検証 (Verifier の作業)
Verifier は Prover から証明（隠された評価値のセット）を受け取り、CRS と公開情報$(u,y)$を使って、以下のチェックをする。この時、Verifier は秘密の$s$や$c_{mid}, H(s)$などは知らない。
- QAP方程式の検証: 目標: $P(s)=H(s)t(s)$、つまり $L(s)R(s)−O(s)=H(s)t(s)$が成り立っているかを、隠された値を使って検証する。
方法: Verifierは、Prover から受け取った証明$(E(H(s)), E(L_{mid}(s))$など) と、自分で計算できる公開情報部分($E(L_{io}(s)$) など、CRSと u,y から計算)、そして CRS に含まれる値 (例: $E(t(s)$) やペアリング計算用の特定の値) を使って、特定のペアリング等式が成り立つかをチェックする。
例えば,
$$e(E(L_{io}(s)) + E(L_{mid}(s)),\ E(R_{io}(s)) + E(R_{mid}(s))) \stackrel{?}{=} e(E(O_{io}(s)) + E(O_{mid}(s)),\ E(1)) \cdot e(E(H(s)),\ E(t(s)))$$
この等式が成り立てば、ペアリングの双線形性により、隠されたレベルで $L(s)R(s)=O(s)+H(s)t(s)$ が成り立っていることが保証される。
- 中間値多項式の形式検証:
目標: Prover が送ってきた $E(L_{mid}(s)$) などが、本当に正しい形式（$c_mid$と補助多項式の線形結合）で作られているかを検証する。
方法: CRS に含まれる$α$付きの値（例: $E(α)$）とペアリングを使う。Prover は証明の中に $E(L_{mid}(s)$) に加えて、$E(αL_{mid}(s)$) のような値も含めて送る。Verifier は、次のようなペアリング等式を検証する。
$$e(E(L_{mid}(s)), E(\alpha)) \stackrel{?}{=} e(E(\alpha L_{mid}(s)), E(1))$$
これが成り立てば、KCA の仮定に基づき、$E(L_{mid}(s)$) は正しい「係数」（元の $c_{mid}$）を使って作られたものだと確信できる。
$E(R_{mid}(s)),E(O_{mid}(s))$ についても同様のチェックをする。
結論：ゼロ知識証明の達成 上記の検証ステップ 1 と 2 が両方とも成功すれば、Verifier は以下のことを確信できる。
Prover は、QAP方程式$P(z)=H(z)t(z)$を満たすような商$H(z)$と値の割り当て係数$c_i$を知っている
Prover は、その証明を生成するために正しい手順を踏んだ。

ポイントとしてVerifier はこれらの検証を、Prover から送られてきた暗号化された値（証明）と公開されている CRS、入力u、出力yだけを使って行っており、秘密の$s$,$c_{mid}, H(s)$ などは知らぬ間に証明できている。zk-SNARKs では、さらにこの証明を非常に短く（Succinct）し、Prover と Verifier の間のやり取りを不要（Non-interactive）にするための工夫が加えられている。

# 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/