# Stanford - CS251 Fall 2022

ZKPは初回と13回以降を読むと良い

https://cs251.stanford.edu/lectures/lecture13.pdf

[Introduction to zk-SNARKS | ConsenSys](https://consensys.net/blog/developers/introduction-to-zk-snarks/)

# Lecture1

- **CRF** (Collision Resistant Function)
- SHA256など
- $h = H(m)$ == **binding commitment** for *m*
- **not hiding** (h may leak info about *m*)

# Lecture 13

- Cryptographic commitments
- $commit(msg, r) → com$
- $r$: secret randomness
- $com$: commitment string - opened correctly for anyone to verify
- $verify(msg, com, r) → accept\ or\ reject$
- **binding**
- 2つ以上同じ opening を生成できない
- **hiding**
- com は committed data の情報を漏らさない
- $commit(m, r) → com$ において、$r$ を $R$ の中から uniformly にサンプリングすると、統計的に $com$ は $m$ と独立であると言える

## zk-SNARK

- SNARK
- a **succinct** proof that a certain statement is true.
- I know *m* such that SHA256(m) = 0
- **short** and **fast** to verify
- zk-SNARK
- the proof reveals nothing about *m*

## Arithmetic circuits

- $\textbf{F} = \{0, …, p - 1\}$ for some prime $p > 2$
- $C: \textbf{F}^n → \textbf{F}$
- $n$ 次元の項 ($1, x_1, …, x_n$) を入力とし、1 つの値を出力する算術回路
- 各項をノードとし、演算のDAGを作る

- $|C|$ $=$ $C$ のゲート数

### Example

- ハッシュや署名の算術回路
- ⇒ valid なら 0, invalid なら 0 以外を吐く
- $C_{hash}(h, \textbf{m})$
- outputs $0\ if\ SHA256(m) = h$, $\neq 0\ otherwise$
- $C_{sig}(p_k, m, \sigma)$
- outputs 0 if $\sigma$ is a valid ECDSA signature on $m$ with respect to $p_k$

- $C_{hash}(h, \textbf{m})$ を JS で表現

// public hash x, secret value w
function C(x, w) { return ( sha256(w) == x ); }

## NARK: Non-interactive ARgument of Knowledge

- 公開の算術回路 $C(x, w) → \textbf{F}$
- $x$ は $F^n$ 上の公開の入力値
- $w$ は $F^m$ 上の非公開の入力値 (witness)

- $S, P, V$ と前処理 (セットアップ) について
- $\textbf{S}(C)$ → public parameters $(\textbf{pp}, \textbf{vp})$
- $pp, vp$ を生成するセットアップ
- $P(pp, x, w) → proof\ \pi$
- $pp$ を用いた proof 生成器
- $V(vp, x, \pi) → accept\ or\ reject$
- $vp$ を用いた検証器
- $pp$ は証明者, $vp$ は検証者が持つ

- セットアップの例
- verifier がランダムな秘密の値 $\lambda$ を用いて、$(pp, vp) = G(C, \lambda)$ を計算し $pp$ を prover に渡す

### Complete

- $\forall{x, w}: C(x, w) = 0 ⇒ Pr[ V(vp, x, P(pp, x, w)) = accept ] = 1$
- 全ての $x, w$ に対し $C(x, w) = 0$ なら, prover が $w$ を所持する検証の、結果が正しい確率は $1$ である

### Knowledge sound

- $V$ accepts $⇒$ P “knows” $w$ s.t. $C(x, w) = 0$

### Zero knowledge

- $(C, pp, vp, x, \pi)$ “reveal nothing” about $w$

### [補足] Consensysによる説明

- セットアップ
- Alice と Bob で鍵生成をする
- $\lambda$: Bob がランダムに選んだ秘密の値
- $(p_k, v_k) = G(C, \lambda)$
- Bob が Alice に $p_k$ を渡す
- Alice が proof 作成
- $prf = P(p_k, H, s)$
- 秘密の値 $s$ と公開の値 $H$ を引数に、$p_k$ を用いた証明のアルゴリズム $P$ で $prf$ を作成
- Bob が proof を検証
- Alice が $s$ を知っていた場合 $V(v_k, H, prf) = true$ となる。

## SNARK: a Succinct ARgument of Knowledge

ゲート数を $log$ に落とした計算量になる。

- $S(C) → (pp, vp)$
- $P(pp, x, w)$ → **short** proof $\pi$
- $|\pi| = O_\lambda(log(|C|))$
- $V(vp, x, \pi)$ **fast to verify**
- 回路の “要約” というイメージ
- $time(V) = O_\lambda(|x|, log(|C|))$
- (↑この表記が理解できない。$|x|$ または $log(|C|)$ に依存するオーダーという意味？)

- **SNARK:** (S, P, V) は **complete**, **knowledge sound,** **succinct**
- **zk-SNARK**: SNARK + **zero knowledge**

# Lecture14

## セットアップの種類

- セットアップとは
- $\textbf{S}(C; r) →$ public parameters $(pp, vp)$
- 秘密の値 $r$

### trusted setup per circuit

- $\textbf{S}(C; r)$ において $r$ を prover から隠す必要がある
- prover が知ると不正な proof $\pi$ を生成できる

### trusted but universal (updatable) setup

- $r$ が $C$ と独立になる

- $\textbf{S} = (S_{init}, S_{index})$
- $S_{init}(\lambda; r) → gp$
- 初回のみ実行
- $S_{index}(gp, C) → (pp, vp)$
- prover から隠すべき値がない

### transparent setup

- $\textbf{S}(C)$ に秘密の値が不要
- = Trusted setup が不要

## Significant progress in recent years


- いずれも Prover time が線形 $|C|$
- ゲート数が $2^{20}$ とかでしんどい

## knowledge sound とは

- if V accepts then P “knows” $w$ s.t. $C(x, w) = 0$

**P “knows” $w$ とは？**

### (informal def)

- $P$ から $w$ を Extract できること

### (formal def)

- (↓よく分からなかった)

- ※ 論証が健全である (sound) とは (wikipedia)
- => 「論証が妥当である かつ 前提の全てが 真である」
- 全ての人間は死ぬ。ソクラテスは人間なので死ぬ (論証は健全)
- 全ての動物は飛べる。豚は動物なので飛べる (論証が妥当だが健全ではない)

## Zero knowledge

- 下記を満たすとき, $(S, P, V)$ は $\forall{x} \in \textbf{F}^n$ に関して **zero knowledge**
- proof $\pi$ は $w$ に関する情報を, その値が存在すること以外は “何も明かさない”

**“何も明かさない” とは？**

### (informal def)

- verifier が自分で適当な proof $\pi$ を作ることができる
- シミュレータ $Sim$ を用いて, それっぽい $pp, vp, \pi$ が作れる
- $(pp, vp, \pi) ← Sim(C, x)$
- $Sim(C, x)$ は $w$ なしで $\pi$ の算出をシミュレート

### (formal def)

- $(S, P, V)$ は $C$ において **zero knowledge とは**
- 下記を満たす効率的なシミュレータ $Sim$ が存在
- $\forall{x} \in \textbf{F}^n$ s.t. $\exists{w}: C(x, w) = 0$
- $(C, pp, vp, x, \pi)$ の分布において, 本物と $Sim$ とで区別がつかない

# Lecture 15

## PCP-based SNARK

- PCP = Probabilistically Checkable Proofs
- The PCP theorem
- Prover: proof $\pi$ を作成
- Verifier: $\pi$ 中の $O(\lambda)$ bits を読んで accept or reject
- ⇒ $V$ は常に valid な proof を accept する
$w$ が存在しない場合, $V$ は高確率で reject する
- size of proof $\pi$ = $poly(|C|)$
- not succinct
- $poly(n)$: some polynomial in $n$

## Converting a PCP proof to a SNARK

### Interactive な方法

- proof $\pi$ の merkle tree を作る
- prover は merkle root $h$ を verifier に送る (1 hash)
- verifier は $\pi$ 上の $k$ ($k = O(\lambda)$) 個の leaf を指定する
- prover は各の merkle proof を提出する ($O(k\ log|C|)$ hash)
- verifier が accept or reject を判定する

verifier が $O(\lambda log|C|)$ の merkle proof についてのみ検証すれば良いので succinct

- (コメント)
- 具体的な 回路 $C(x, w)$ → $\pi$ → merkle root の変換過程や $P, V$ の内容を見ないとイメージが湧きづらい。

## Making the proof non-interactive

### Fiat-Shamir transform

- Fiat-Shamir: セキュアな interactive protocol を non-interactive にする

- $H: M → R$ 暗号学的ハッシュ関数
- prover がランダムな値を自ら生成する (!)
- Random Oracleを定義
- 入力に対して一意な完全ランダムな値を返すもの
- c.f. 8.8 Fiat-Shamir Paradigm

https://courses.grainger.illinois.edu/cs598dk/fa2019/Files/lecture08.pdf

- Random Oracle は $H$ で代用できる。この時 verifier による入力 $x$ を原像に使用する。
- （$msg1$ を使う理由と $msg2$ が何かよくわからない）

## MEMO

### Interactive Oracle Proof

https://eprint.iacr.org/2016/116.pdf

- Eli Ben-Sasson等の論文