# 零知識證明（Zero-Knowledge Proof, ZKP）
零知識證明是一種密碼學協議，允許證明者（Prover, $P$）向驗證者（Verifier, $V$）證明某個陳述（Statement）為真，除了「該陳述為真」這個事實之外，不洩露任何關於該陳述的額外資訊（如證明所需的秘密證據 Witness）。

ZKP想解決的問題：如何在不信任的環境下建立信任，既是在不告訴對方對應資訊的前提下，表達我知道該資訊

## ZKP的核心模型
ZKP的場景通常定義在一個關係 $R$ 上：
* 公開輸入（Public Input, $x$）：雙方都知道的資訊（如公鑰、問題描述）
* 私有證據（Private Witness, $w$）：只有 $P$ 知道的秘密（如私鑰、密碼）
* 目標：$P$ 向 $V$ 證明他擁有 $w$，使得 $(x, w) \in R$ 成立

標準的 ZKP 系統通常由以下算法組成（以非互動式 NIZK 為例）
1. 設置 $Setup(1^\lambda) \to (pp, vp)$：生成公共參數 $pp$ 和驗證參數 $vp$（有時包含 Trusted Setup）
3. 證明 $Prove(pp, x, w) \to \pi$：輸入參數、公開輸入和秘密證據，輸出證明 $\pi$
4. 驗證 $Verify(vp, x, \pi) \to \{0, 1\}$：驗證者輸入參數、公開輸入和證明，輸出接受或拒絕

## ZKP的運作機制：Sigma 協議 ($\Sigma$-Protocol)
大多數 ZKP 的基礎是互動式的提交-挑戰-回應三步機制（以 Schnorr 協議證明知道離散對數 $y = g^x$ 為例）：
**承諾（Commitment）**：
證明者 $P$ 選擇一個隨機數 $k$，計算承諾 $t = g^k$，發送 $t$ 給 $V$。目的是鎖定隨機性，防止 $P$ 事後作弊

**挑戰（Challenge）**：
驗證者 $V$ 隨機選擇一個挑戰數 $c$，發送 $c$ 給 $P$。目的是引入不可預測性，讓 $P$ 無法提前偽造

**回應（Response）**：
證明者 $P$ 計算 $z = k + c \cdot x$，發送 $z$ 給 $V$。驗證者 $V$ 檢查等式 $g^z \stackrel{?}{=} t \cdot y^c$ 是否成立

**從互動到非互動（Fiat-Shamir Heuristic）**：
為了實用性，通常使用 Fiat-Shamir 變換將上述交互過程轉為非交互式（Non-Interactive ZKP, eg. NIZK）
* 方法：用一個加密雜湊函數 $H$ 代替驗證者 $V$
* 挑戰 $c$ 不再由 $V$ 給出，而是計算 $c \leftarrow H(x, t)$

## ZKP的性質
**完備性（Completeness）**
如果陳述為真，且證明者 $P$ 和驗證者 $V$ 誠實執行協議，則 $V$ 必定會接受證明。即 $Verify(Prove(x, w)) = 1$ 恆成立

**可靠性（Soundness）**
如果陳述為假（即 $P$ 不知道 $w$），則惡意證明者 $P^*$ 無法欺騙誠實的 $V$（除極小機率外）。即 $Prob(Verify(FakeProof) = 1) \approx 0$

**零知識性（Zero-Knowledge）**
如果陳述為真，驗證者 $V$ 在交互過程中除了「陳述為真」之外，無法獲得關於 $w$ 的任何資訊

定義方式：存在一個模擬器（Simulator），僅需輸入 $x$（不需要 $w$）就能生成一個與真實證明 $\pi$ 在分佈上不可區分的模擬證明

## ZKP在MPC與FHE中的角色
ZKP 是構建高階安全協議的關鍵模塊，用於强制參與者的誠實：
**在 MPC 中：從半誠實到惡意（Semi-Honest to Malicious）**
* MPC 協議（如 GMW）通常會預設為 Semi-Honest
* 為了達到惡意模型安全，要求每個參與者對其發出的每一條消息附加一個 ZK 證明
* 證明內容：「我剛剛發送的訊息是嚴格按照協議執行的，且我的輸入符合一致性」，強制惡意攻擊者必須像半誠實者一樣行為。

在 Verifiable FHE 中伺服器雖然看不到數據，但可能執行錯誤的計算。因此伺服器可以生成一個 ZK 證明，證明「輸出的密文 $c_{out}$ 確實是由輸入密文 $c_{in}$ 經過函數 $f$ 正確運算得來的」，防止伺服器欺詐。

## ZKP的限制
ZKP 雖然能實現隱私保護，計算資源的消耗與系統設置的複雜性上存在不少限制：
**計算不對稱性（Computational Asymmetry）**
ZKP 存在極大的證明開銷（Prover Overhead）。證明者生成證明所需的時間通常遠大於直接執行原始計算的時間。因此若是要應用在高頻或低延遲的實時計算場景（如實時遊戲渲染）下頗有難度。

**可信設置風險（Trusted Setup / Toxic Waste）**
許多高效的 ZKP 方案（如 Groth16）依賴於一個初始的生成階段來產生公共參考串（CRS）。
風險：這個過程會產生中間秘密或被稱為「有毒廢料」。如果這些秘密被洩露或未銷毀，攻擊者就可以偽造假證明，破壞系統的可靠性（Soundness）。
解決：雖然 STARKs 或 Bulletproofs 不需要此設置（Transparent），但通常會犧牲證明大小或驗證速度。

**內存消耗（Memory Consumption）**
生成證明通常涉及大規模的快速傅立葉變換（FFT）和多標量乘法（MSM）。這些運算需要將龐大的電路結構載入記憶體，導致證明者需要較多的 RAM 才可以正確執行，限制了在移動設備或 IoT 設備上生成證明的可行性。

**電路表達的侷限（Circuit Complexity）**
ZKP 要求將所有計算邏輯轉換為特定的算術電路（如 R1CS 或 QAP）。
困難點：傳統程式中的條件跳轉（If-Else）、不定長循環（Dynamic Loops）很難直接轉換為電路，所以現有的code轉到 ZKP 環境的開發成本較高，且電路規模往往會因為展開循環而變得龐大。

## 主流ZKP實現方案分類
| 方案類型 | 代表算法 | 可信設置 | 證明大小 | 特點 | 適用場景 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| zk-SNARKs | Groth16 | 需要 | 小 (~200 Bytes) | 驗證快 (ms級)，但需要針對特定電路 Trusted Setup | Zcash, 隱私支付 |
| Universal SNARKs | Plonk | 需要 (通用) | 小 (~400 Bytes) | 只需一次 Setup 即可支援所有電路，目前業界標準 | zk-Rollups (zkSync, Scroll) |
| zk-STARKs | Fri-based | 不需要 | 大 (數十 KB) | 抗量子攻擊，證明生成速度快，但證明體積大導致 Gas Fee 高 | 高吞吐量計算, dYdX, StarkNet |
| Bulletproofs | Bulletproofs | 不需要 | 中等 (log N) | 無需 Setup，驗證較慢，適合範圍證明 | Monero (Range Proof) |

## 參考資料
1. [The knowledge complexity of interactive proof systems](https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf)
2. [On the size of pairing-based non-interactive arguments](https://eprint.iacr.org/2016/260.pdf)
3. [零知識證明原理？特性與類型介紹/常見應用/儲備證明查詢範例](https://rich01.com/zero-knowledge-proof-zkp/)

> 隨手筆記，有錯誤或需要補充的部分歡迎討論，~~還請鞭小力一點~~